cmeans.cpp

K-means一个用C++实现的聚类算法

    /*****************************************************************
      这个程序是实现了一个聚类CMI算法，对给定一个数据集，按要求将其划分为
	  三个类，并计算其分类的效率，并给出一定的结果比较及输出！！
********************************************************************/
#include<fstream.h>
#include<iostream.h>
#include<iomanip.h>
#include<string.h>
#include<math.h>
#include <stdio.h>
#include <set>
const int c=3;
const int dim=5;//数据的维数
const int size=150;//表明数据集的大小；
class cluster;
//////定义一个数据单元的类
class metadata{
	public:
	int tag;//定义数据数元的标记，如属于某一类；
	double value[dim];//定义数据单元的值；
//	friend class data;
	friend class cluster;
	 metadata(){}
	 metadata(double tvalue[]){
		for(int j=0;j<dim;j++){
			value[j]=tvalue[j];}
         tag=int(value[4]);
         }
};

///////////定义一个cluster集，并进行分类
class cluster{
public:
	int clustersize[3];//表示类的大小
	metadata clustersample[size];//表示每类中的样本集
	metadata clustercenter[c];//每类样本的中心
	cluster(metadata initdata[]){
		for(int j=0;j<size;j++){
			//clustersample[j](initdata[j]);
			for(int i=0;i<dim;i++){
			clustersample[j].value[i]=initdata[j].value[i];}
		clustersample[j].tag=int(initdata[j].value[4]);
		}
				
			
			
			//clustercenter=
		initcenter(clustersample);
		///////测试//////////////////
		cout<<"the initial cluster center is:"<<endl;
		for(int m=0;m<c;m++){
			for(int n=0;n<dim;n++){
		cout<<setw(4)<<clustercenter[m].value[n]<<' ';
			}
			cout<<endl;
		}
		///////////////////////
			for(int k=0;k<c;k++)
 				clustersize[k]=0;
	}
/*	///////重载=号运算符
	metadata operator =(metadata sample){
		metadata temp;
		for(int i=0;i<=dim;i++){
			temp.value[i]=sample.value[i];}
		temp.tag=sample.tag;
		return temp;
	}*/
/*	metadata operator =(metadata sample[]){
		metadata temp[3];
		for(int i=0;i<3;i++){
			temp[i]=sample[i];
		}
	}*/


/////////取得初始的类中心
void  initcenter(metadata clustersample[]){
//        float t=0.7;
         double temp=0;
         double maxdistance=0;
         double mindistance=0;
        // metadata clustercenter[c];
         clustercenter[0]=clustersample[0];
         for(int i=0;i<=size-1;i++){
                 temp=distance(clustercenter[0],clustersample[i]);
                 if(maxdistance<=temp){
                                        maxdistance=temp;
                                        clustercenter[1]=clustersample[i];
                                        }
                 }
		  temp=0;
         for(int k=0;k<=size-1;k++){
                 double a=distance(clustercenter[0],clustersample[k]);
                 double b=distance(clustercenter[1],clustersample[k]);
                 if(a<=b)
                         {mindistance=a;
                         if(mindistance>=temp){
                                       temp=mindistance;
                                       clustercenter[2]=clustersample[k];
                                       }
				 }
                 else 
                      {mindistance=b;
                      if(mindistance>=temp){
                                       temp=mindistance;
                                       clustercenter[2]=clustersample[k];
                                       }
                      }
		 }
         //return clustercenter;
}
////////距离函数
static   double distance(metadata x,metadata y){
           //metadata x=x;
           //metadata y=y;
           double distance;
           double temp=0;
           double dis=0;
           for(int i=0;i<=dim-1;i++){
                   temp=x.value[i]-y.value[i];
                   temp=temp*temp;
                   dis=dis+temp;
                   }
           distance=dis;
           return distance;        
          
}
	/////求新的类中心的函数
/*  static	metadata newcenter(metadata tempcluster[],int j)
	{
		//metadata tempcluster=tempcluster;
		metadata tempcenter;
		//int j=j;
		int n=0;
		for(int i=0;i<4;i++)tempcenter.value[i]=0;
		tempcenter.value[4]=j;
		for(int k=0;k<size;k++){
			if(tempcluster[k].value[4]==j)
			{for(int l=0;l<4;l++){
				tempcenter.value[l]=tempcenter.value[l];
			}
			n++;
			}
		}
			for(int h=0;h<3;h++){
				tempcenter.value[h]=tempcenter.value[h]/n;
			}
	
			return tempcenter;
			
} */
	
	
/*//////进行打印并对所得数据和原始数据进行比较 
    void clusterprint(int it){
		 //int it=it;
		 cout<<"the number of the iterance to abtain the cluster is:"<<it<<endl;
		 cout<<"the final cluster center is:"<<endl;
		 for(int j=0;j<c;j++){
			 for(int i=0;i<dim;i++){
				 cout<<setw(4)<<clustercenter[j].value[i]<<' ';
			 }
		 cout<<endl;
		}
	 }
///////////////////////////////////////////////////////////*/
		 void cmp(metadata initcluster[]){
			 int wrong=0;
			 //metadata initcluster[size]=initcluster;
			 cout<<"the first column is the cluster in fact;"<<endl;
			 cout<<"the second column is expected cluster the data belong to;"<<endl;
			 for(int i=0;i<size;i++)
			 {
				 int t=int(clustersample[i].value[4]);
				 if(t==1)t=2;
				 else if(t==2)t=1;
				 cout<<setw(4)<<t<<setw(4)<<initcluster[i].value[4]<<endl;
				 switch(t){
				 case 0: clustersize[0]++;break;
				 case 1: clustersize[1]++;break;
				 case 2: clustersize[2]++;break;
				 default:break;}
					 if(t!=initcluster[i].value[4])wrong++;
			 }
			 cout<<"the number of cluster that is wrongly classified is:"<<wrong<<endl;


		 }
///////进行分类
  double cmeans(){
		int it=1;
		double a,b,d;
		double th=0.001;
		metadata tempcenter[3];
		int lable=0;
		//clustercenter=initcenter(clustersample);
		//cout<<"begin"<<endl;
		//////进行初步的分类
		/*	///////测试//////////////////
		cout<<"the initial cluster center is:"<<endl;
		for(int m=0;m<c;m++){
			
			for(int n=0;n<dim;n++){
		cout<<setw(4)<<clustercenter[m].value[n]<<' ';
			}
			cout<<endl;
		}
		/////////////////////// */
		do{
		for(int i=0;i<150;i++){
			a=distance(clustercenter[0],clustersample[i]);
			b=distance(clustercenter[1],clustersample[i]);
			d=distance(clustercenter[2],clustersample[i]);
			if(a<=b&&a<=d)clustersample[i].value[4]=0;
			if(b<=a&&b<=d)clustersample[i].value[4]=1;
			if(d<=a&&d<=b)clustersample[i].value[4]=2;
					
		}
/*		 //////////测试数据/////////////////////////
	 for(int k=0;k<size;k++){
		 for(int l=0;l<dim;l++){
			 cout<<setw(4)<<clustersample[k].value[l]<<' ';
					  
		 }
		 cout<<endl;
	 }
	 ////////////////////////////////  */
		cout<<"continue"<<endl; 
		//////得到新类后求新类的中心
		for(int j=0;j<c;j++)//tempcenter[j]=newcenter(clustersample,j);
		{
			int n=0;
		for(int i=0;i<4;i++)tempcenter[j].value[i]=0;
		tempcenter[j].value[4]=j;
		for(int k=0;k<size;k++){
			if(clustersample[k].value[4]==j)
			{for(int l=0;l<4;l++){
				tempcenter[j].value[l]=tempcenter[j].value[l]+clustersample[k].value[l];
			}
			n++;
			}
		}
	//	cout<<"fsfsdafasf"<<n<<endl;
			for(int h=0;h<4  ;h++){
				tempcenter[j].value[h]=tempcenter[j].value[h]/n;
			}
		}
		///////
			 for(int y=0;y<c;y++){
			 for(int i=0;i<dim;i++){
				 cout<<setw(4)<<tempcenter[y].value[i]<<' ';
			 }
		 cout<<endl;
		}
		////////
		it++;
		a=distance(clustercenter[0],tempcenter[0]);
		b=distance(clustercenter[1],tempcenter[1]);
		d=distance(clustercenter[2],tempcenter[2]);
		if(a<=th&&b<=th&&d<=th)lable=0;
		else lable=1;
		/*if(it>100){
			lable=0;
			cout<<"numbers of iteration exceeded;"<<endl;
			return 0;
		}*/
		for(int w=0;w<dim;w++){
			clustercenter[0].value[w]=tempcenter[0].value[w];
		clustercenter[1].value[w]=tempcenter[1].value[w];
		clustercenter[2].value[w]=tempcenter[2].value[w];
        }
		}while(lable);


	cout<<"the number of the iterance to abtain the cluster is:"<<it<<endl;
		 cout<<"the final cluster center is:"<<endl;
		 for(int j=0;j<c;j++){
			 for(int i=0;i<dim;i++){
				 cout<<setw(4)<<clustercenter[j].value[i]<<' ';
			 }
		 cout<<endl;
		}
	cout<<"done!"<<endl;
   return 0;

	}

};

///////////主函数
void main()
{
     double temp[dim];
     metadata initdata[size];
    // cluster initcluster;
     //cluster finalcluster;
	 ifstream file1("E:\\test\\iris.dat");
	 int j=0;
	 while(!file1.eof()){
		 file1>>temp[0]>>temp[1]>>temp[2]>>temp[3]>>temp[4];
						  
						  for(int k=0;k<dim;k++){
			initdata[j].value[k]=temp[k];}
         initdata[j].tag=int(temp[4]); 
                          //initdata[j](temp);
                          j++;
                          }
/*	 //////////测试数据/////////////////////////
	 for(int k=0;k<size;k++){
		 for(int l=0;l<dim;l++){
			 cout<<setw(4)<<initdata[k].value[l]<<' ';
					  
		 }
		 cout<<endl;
	 }
	 ////////////////////////////////   */
	   //file1.close();
	   cluster finalcluster(initdata);
	   //cout<<"all over"<<endl;
       finalcluster.cmeans();
	   finalcluster.cmp(initdata);
	  
	   system("pause");
	 


}