isodata.cpp

聚类分析isodata算法的C++实现程序

#include<iostream.h>
#include<fstream.h>
#include<iomanip.h>
#include<math.h>
#include<stdlib.h>
#define InDim 4 
#define SamNum 150

#define MAXDIS 1000.0
/************************************************************************/
/* 结构体定义                                                           */
/************************************************************************/
struct Sample //样品
{
	int SampleIndex;          //样品编号
	int SCategory;       // 样本所属类别
	double SFeature[InDim];  //每个样品有N个特征值

};


struct Center //聚类中心结构
{
	int CenterIndex; //中心编号
	double CFeature[InDim]; //中心特征值
	double StanDeviation[InDim];
	int  MaxStanDevIndex;  
	double MaxStanDev;
	int HasSampleNum;  //包含样品数目
	int HasSample[SamNum];
};

/************************************************************************/
/*  函数声明                                                            */
/************************************************************************/
void SetParameter();
void PutinData();
void CreateRandomCenters();
double GetDistance(double *fea1,double* fea2);
int FindMinPos(double *p,int n);
void InitiateCenters();
void ClassJudge();
void DecreaseCenters();
void UpdateCenter();
void CalCenterDist();
void CalAllAvgDist();
void CalStanDeviation();
void FindMaxStanDeviation();
void Split(int i);
void Cal22CenterDist();
void Taxis();
void Combination();
void ShowResults();
int FindMinPos(double *p,int n);

/************************************************************************/
/*  变量定义                                                            */
/************************************************************************/
 Sample m_sample[SamNum]={0}; //样本,暂定最多有200个
 Center m_center[SamNum]={0};     //聚类中心
 int CenterNum;       //聚类中心数目
 int ExpectCenterNum;
 int MergerTimes=0;
 int MinSampleNum;   //每个聚类域中最少样本数
 double MaxStanDeviation;                //同一聚类域中样本标准差的最大值
 int MaxCombinNum;         //输入一次可以合并的聚类中心的最多对数
 int MaxMergerTimes;			 // 最多迭代次数,由用户决定
 double MinCenterDist;			 //两个类中心最小距离,小于该阈值将合并
 double MinEquation;       //类内方差阈值
 double AvgDistance[SamNum];     //每一类内平均距离
 double AllAvgDist;       //全部样品中心平均距离
 double Source[SamNum*InDim];
 double Distij[SamNum*SamNum];
 int Disti[SamNum];
 int Distj[SamNum];
 int ss;
 int sss;
 ifstream infile;
 ofstream outfile;
 
 bool flag1=false;
 bool flag2=false;
 bool flag3=false;
 /************************************************************************/
/*  设定参数                                                            */
/************************************************************************/
void SetParameter()
{
	cout<<endl<<"输入预期聚类中心数目: ";
	cin>>ExpectCenterNum;
	CenterNum=ExpectCenterNum;
	
	cout<<endl<<"输入每个聚类域中最少的样本数: ";
	cin>>MinSampleNum;

	cout<<endl<<"输入同一聚类域中样本标准差的最大值(推荐值0.5): ";
	cin>>MaxStanDeviation;

	cout<<endl<<"输入不同聚类域距离最小值(<1.79): ";
	cin>>MinCenterDist;

	cout<<endl<<"输入一次可以合并的聚类中心的最多对数: ";
	cin>>MaxCombinNum;

	cout<<endl<<"输入最大迭代次数: ";
	cin>>MaxMergerTimes;
}


/************************************************************************/
/*  读入数据                                                            */
/************************************************************************/
void PutinData()
{
  
	int count = 0;
	float temp=0;
	int i=0,j=0;
	ifstream infile("irisdata.txt");
	if(!infile)
	{
		cout<<"Can't Open the file"<<endl;
		exit(1);
	}
	
	while(infile>>temp)
	{
		Source[count]=temp;
		count++;
	}
	
  for(i=0;i<SamNum;i++)
    {
    	m_sample[i].SCategory=0;
		  for(j=0;j<InDim;j++)
		    {
		  	  m_sample[i].SampleIndex=i*InDim+j;		    
			  m_sample[i].SFeature[j]=Source[i*InDim+j];
			  cout<<setw(5)<<m_sample[i].SFeature[j];			  
		  	}
	  	  cout<<endl;
		}
  for(i=0;i<SamNum;i++)
    {
    	m_center[i].HasSampleNum=0;
    	m_center[i].CenterIndex=i;    	
		  for(j=0;j<InDim;j++)
		    {
		  	  m_sample[i].SampleIndex=i*InDim+j;		    
		      m_center[i].CFeature[j]=0;
		  	}
		  for(j=0;j<SamNum;j++)
		  	m_center[i].HasSample[j]=0;
    	
		 }		
	infile.close(); 
	cout<<m_sample[100].SFeature[3]<<endl; 
    cout<<m_sample[149].SFeature[3]<<endl;  
	cout<<endl<<"读入数据成功!!"<<endl;
};


/************************************************************************/
/*  随机初始化类中心                                                    */
/************************************************************************/

void CreateRandomCenters()
{
    cout<<endl<<"随机初始化类中心开始!!"<<endl;
    int i=0,j=0;
    int random[CenterNum];    
    srand( (unsigned)time( NULL ) );
    for( i=0;i<CenterNum;++i)
    {
        int a=rand()%SamNum;
        for(j=0;j<i;j++)
        {
            if(random[j]==a)
            {
                break;
            }
        }
        if(j>=i)
        {
            random[i]=a;
        }
        else
        {
            i--;
        }
       cout<<"random["<<i<<"]="<<random[i]<<endl;
    }    
    for(i=0;i<CenterNum;i++)
      {
      	m_center[i].CenterIndex=i;
      	m_sample[random[i]].SCategory=i;
        for(j=0;j<InDim;j++)
		       {
		       	m_center[i].CFeature[j]=m_sample[random[i]].SFeature[j];
		        cout<<setw(10)<<m_center[i].CFeature[j];
		      }
			}  
	  cout<<endl<<"随机初始化类中心结束!!"<<endl;  
};


/************************************************************************/
/*  分类前初始化类中心                                                  */
/************************************************************************/
void InitiateCenters()
{
	int i,j;
	for(i=0;i<CenterNum;i++)
	  {
	  	m_center[i].HasSampleNum=0;
	  	for(j=0;j<SamNum;j++)
	  		m_center[i].HasSample[j]=0;
	  }
};


/************************************************************************/
/*						   求距离                                                 */
/************************************************************************/
double GetDistance(double *fea1,double* fea2)
{//暂用欧氏距离
	double dis=0.0;
	for(int i=0;i<InDim;i++)
	dis+=(fea1[i]-fea2[i])*(fea1[i]-fea2[i]);
	return sqrt(dis);

}



/************************************************************************/
/*  找到与某类中心距离最近的一个                                        */
/************************************************************************/
int FindMinPos(double *p,int n)
{   
	
     double d=p[0];
     int i,Pos=0;
     for(i=0;i<n;i++)
         if(d>p[i])
             {
               d=p[i];
               Pos=i;
             }   
     return Pos;
};


/************************************************************************/
/* 依据距离分类                                                         */
/************************************************************************/
void ClassJudge()
{ 
	 cout<<endl<<"依据距离分类开始!!"<<endl;      
   int i,j,k;
   for(i=0;i<SamNum;i++)
     {
       double *d=new double[CenterNum];//开辟内存用于保存距离       
       for(j=0;j<CenterNum;j++)       
	        d[j]=GetDistance(m_sample[i].SFeature,m_center[j].CFeature);        
       int Pos=FindMinPos(d,CenterNum);         
       m_center[Pos].HasSample[m_center[Pos].HasSampleNum]=i;
       m_center[Pos].HasSampleNum++;       
       delete []d;       
     }  
    MergerTimes++; 
   cout<<endl<<"依据距离分类结束!!"<<endl; 
};    


/************************************************************************/
/* 减少类的数目                                                         */
/************************************************************************/

void DecreaseCenters()
{
	cout<<endl<<"减少类的数目开始!!"<<endl;  
   int i,j,k;
   for(j=0;j<CenterNum;j++)               //是否可以去掉一些数据
	 {
		 if(m_center[j].HasSampleNum<MinSampleNum)
		 {
		  	flag1=true;
		  	CenterNum--;
		 	  for(i=j;i<CenterNum;i++)
		 	    m_center[i]=m_center[i+1];
		}
	}
	cout<<endl<<"减少类的数目结束!!"<<endl;  
} ;
/*
for(i=j;i<CenterNum;i++)
		 	    {
		 		    m_center[i].CenterIndex=m_center[i+1].CenterIndex;
		 		    m_center[i].HasSampleNum=m_center[i+1].HasSampleNum;
		 		    for(k=0;k<InDim;k++)
		 		  	   m_center[i].CFeature[k]=m_center[i+1].CFeature[k];
		 		    for(k=0;k<m_center[i].HasSampleNum;k++)
		 	         m_center[i].HasSample[k]=m_center[i+1].HasSample[k];
		 	    }
*/


/************************************************************************/
/*	更新类中心                                                          */
/************************************************************************/
void UpdateCenter()