kmeans.cpp

用MFC开发的简单的k-means实现代码

//************************************************************************
//在命令行cmd输入程序名之后指定数据文件路径。
//如：kmeans D:\dataset.txt
//**************************************************************************
#include<iostream>
#include<vector>
#include<cmath>
#include<fstream>
using namespace std;
float distance(vector<float> &point,vector<float> &kp)       //计算两个点之间距离
{
  float difference;
  float tempsum=0;
  int n=kp.size();
  for(int i=0;i<n;i++){
     difference=point[i]-kp[i];   
     difference*=difference;
     tempsum+=difference;
  }
  return sqrt(tempsum);
}
void average(vector< vector<float> > &points,vector< vector<float> > &kps) //计算某一类点的平均值,重新确定指定点
{		
       int n=kps[0].size(); 
	   int k=kps.size();
	   vector< vector<float> > sum(k);        
	   for(int i=0;i<k;i++)
	   { sum[i].resize(n);
	   }
	   vector<int> number(k);                //属于第K类的点有多少个
	 
	   for(i=0;i<points.size();i++){            
		for(int j=0;j<n;j++)
			sum[points[i][n]][j]+=points[i][j];
	number[points[i][n]]++;
	}
	for(i=0;i<k;i++)                          //重置指定的点
		for(int j=0;j<n;j++){
			if(number[i]!=0)
		    kps[i][j]=(float)sum[i][j]/number[i];
		}
}
void sortpoint(vector< vector<float> > &points,vector< vector<float> > &kps){
	int n=kps[0].size();
	int k=kps.size();
    vector< vector<float> > temp(k);         //指定的点与重置点相比较,看指定点是否改变
	for(int i=0;i<k;i++){
	    temp[i].resize(n);	
	}

    vector<float> distances(k);                 //存某点与K个指定点的距离
	 int count=0;                                 
	do{                                  
       for(int i=0;i<points.size();i++){		 
		   for(int j=0;j<k;j++){             //计算每一类点与每一个指定点的距离,并存入distances中
			  distances[j]=distance(points[i],kps[j]);	 
		  }
          float minjuli=distances[0];
		  int minflag=0;                     //记录最短距离的点的下标
          for(j=1;j<k;j++){
			  if(minjuli>distances[j]) {
				 minjuli=distances[j];
			     minflag=j;
			  }
		  }
		  points[i][n]=minflag;               //为该点归类
	   }
	   
	   cout<<"第"<<++count<<"次分类指定的K个点变为:"<<endl;
    	for(i=0;i<k;i++){
		   for(int j=0;j<n;j++)
	           cout<<"  "<<kps[i][j];
	           cout<<endl;
		}	
		cout<<endl;
	  temp=kps;	   
      average(points,kps);
   }while(temp!=kps);
}

void main(int argc,char *argv[]){
	vector< vector<float> > points;               //存数据点
	vector< vector<float> > kps;                  //存K个点
    int k;                                        //点数
	int n;                                        //维数
	int i,j;
	cout<<"输入维数(N):"<<endl;
    cin>>n;
	cout<<"输入点数(K)："<<endl;
	cin>>k;
	cout<<"输入K个点的坐标(输入完每个点之后按回车)："<<endl;
	vector<float> kp;
	kp.resize(n);
    for(i=0;i<k;i++){
		cout<<"第"<<i<<"类点:"<<endl;
		for(j=0;j<n;j++){
		    cin>>kp[j];		
		}
		kps.push_back(kp);
	}
	cout<<"指定的K个点的坐标为:"<<endl;
    for(i=0;i<k;i++){
		for(j=0;j<n;j++)
	    cout<<"  "<<kps[i][j];
	    cout<<endl;
	}	
    ifstream in(argv[1]);                    //运用命令提示符方式打开文件
	vector<float> point;
	point.resize(n+1);
	while( !in.eof()){
        for(j=0;j<n;j++)
		in>>point[j];
		points.push_back(point);	
	}
	points.pop_back();
	cout<<endl;
	cout<<"该K个点的变化情况为:"<<endl;
	sortpoint(points,kps);
	cout<<"这些点的分类情况为:"<<endl;
	for(i=0;i<points.size();i++){
		for(j=0;j<n;j++){
		cout<<"   "<<points[i][j];
		}		
	cout<<"   第"<<points[i][n]<<"类点"<<endl;
	}
	cout<<"数据总数:"<<points.size()<<endl;

	
}