K-menas聚类算法C++实现

野性酷女 2022-05-11 09:18 124阅读 0赞

基本介绍： k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 工作过程： 　　k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 （1） 从 n个数据对象任意选择 k 个对象作为初始聚类中心； 　　（2） 循环（3）到（4）直到每个聚类不再发生变化为止 　　（3） 根据每个聚类对象的均值（中心对象），计算每个对象与这些中心对象的距离；并根据最小距离重新对相应对象进行划分； 　　（4） 重新计算每个（有变化）聚类的均值（中心对象） 　　k-means 算法接受输入量 k ；然后将n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。 　　k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 　　计算复杂度： 　　O(nkt), 其中t是迭代次数。 　　k-means算法是一种基于样本间相似性度量的间接聚类方法，属于非监督学习方法。此算法以k为参数，把n 个对象分为k个簇，以使簇内具有较高的相似度，而且簇间的相似度较低。相似度的计算根据一个簇中对象的平均值（被看作簇的重心）来进行。此算法首先随机选择k个对象，每个对象代表一个聚类的质心。对于其余的每一个对象，根据该对象与各聚类质心之间的距离，把它分配到与之最相似的聚类中。然后，计算每个聚类的新质心。重复上述过程，直到准则函数会聚。k-means算法是一种较典型的逐点修改迭代的动态聚类算法，其要点是以误差平方和为准则函数。逐点修改类中心：一个象元样本按某一原则，归属于某一组类后，就要重新计算这个组类的均值，并且以新的均值作为凝聚中心点进行下一次象元素聚类；逐批修改类中心：在全部象元样本按某一组的类中心分类之后，再计算修改各类的均值，作为下一次分类的凝聚中心点。

/*kmeans算法实现（此处只考虑元组只有两个属性的情况）
    *@File:k_means.cpp
    *@Author:Cai0538
    *@Create:2011-12-10
    *@Last Modified:2011-12-10
    */
    #include <iostream>
    #include <fstream>
    #include <vector>
    #include <math.h>
    #define k 3
    using namespace std;
    //存放元组的属性信息
    struct Tuple{
    	float attr1;
    	float attr2;
    };
    //计算两个元组间的欧几里距离
    float getDistXY(Tuple t1, Tuple t2) 
    {
    	return sqrt((t1.attr1 - t2.attr1) * (t1.attr1 - t2.attr1) + (t1.attr2 - t2.attr2) * (t1.attr2 - t2.attr2));
    }
     
    //根据质心，决定当前元组属于哪个簇
    int clusterOfTuple(Tuple means[],Tuple tuple){
    	float dist=getDistXY(means[0],tuple);
    	float tmp;
    	int label=0;//标示属于哪一个簇
    	for(int i=1;i<k;i++){
    		tmp=getDistXY(means[i],tuple);
    		if(tmp<dist) {dist=tmp;label=i;}
    	}
    	return label;	
    }
    //获得给定簇集的平方误差
    float getVar(vector<Tuple> clusters[],Tuple means[]){
    	float var = 0;
    	for (int i = 0; i < k; i++)
    	{
    		vector<Tuple> t = clusters[i];
    		for (int j = 0; j< t.size(); j++)
    		{
    			var += getDistXY(t[j],means[i]);
    		}
    	}
    	//cout<<"sum:"<<sum<<endl;
    	return var;
     
    }
    //获得当前簇的均值（质心）
    Tuple getMeans(vector<Tuple> cluster){
    	
    	int num = cluster.size();
    	double meansX = 0, meansY = 0;
    	Tuple t;
    	for (int i = 0; i < num; i++)
    	{
    		meansX += cluster[i].attr1;
    		meansY += cluster[i].attr2;
    	}
    	t.attr1 = meansX / num;
    	t.attr2 = meansY / num;
    	return t;
    	//cout<<"sum:"<<sum<<endl;
    	
     
    }
    void KMeans(vector<Tuple> tuples){
    	vector<Tuple> clusters[k];
    	Tuple means[k];
    	int i=0;
    	//默认一开始将前K个元组的值作为k个簇的质心（均值）
    	for(i=0;i<k;i++){
    		means[i].attr1=tuples[i].attr1;
    		means[i].attr2=tuples[i].attr2;
    	}
    	int lable=0;
    	//根据默认的质心给簇赋值
    	for(i=0;i!=tuples.size();++i){
    		lable=clusterOfTuple(means,tuples[i]);
    		clusters[lable].push_back(tuples[i]);
    	}
    	//输出刚开始的簇
    	for(lable=0;lable<3;lable++){
    		cout<<"第"<<lable+1<<"个簇："<<endl;
    		vector<Tuple> t = clusters[lable];
    		for (i = 0; i< t.size(); i++)
    		{
    			cout<<"("<<t[i].attr1<<","<<t[i].attr2<<")"<<"   ";
    		}	
    		cout<<endl;
    	}
    	float oldVar=-1;
    	float newVar=getVar(clusters,means);
    	while(abs(newVar - oldVar) >= 1) //当新旧函数值相差不到1即准则函数值不发生明显变化时，算法终止
    	{
    		
    		for (i = 0; i < k; i++) //更新每个簇的中心点
    		{
    			means[i] = getMeans(clusters[i]);
    			//cout<<"means["<<i<<"]:"<<means[i].attr1<<"  "<<means[i].attr2<<endl;
    		}
    		oldVar = newVar;
    		newVar = getVar(clusters,means); //计算新的准则函数值
    		for (i = 0; i < k; i++) //清空每个簇
    		{
    			clusters[i].clear();
    		}
    		//根据新的质心获得新的簇
    		for(i=0;i!=tuples.size();++i){
    			lable=clusterOfTuple(means,tuples[i]);
    			clusters[lable].push_back(tuples[i]);
    		}
    		//输出当前的簇
    		for(lable=0;lable<3;lable++){
    			cout<<"第"<<lable+1<<"个簇："<<endl;
    			vector<Tuple> t = clusters[lable];
    			for (i = 0; i< t.size(); i++)
    			{
    				cout<<"("<<t[i].attr1<<","<<t[i].attr2<<")"<<"   ";
    			}	
    			cout<<endl;
    		}
    	}
    	
    }
    int main(){
     
    	char fname[256];
    	cout<<"请输入存放数据的文件名： ";
    	cin>>fname;
    	cout<<endl;
    	ifstream infile;
    	infile.open(fname,ios::in);
    	if(!infile){
    		cout<<"不能打开输入的文件"<<fname<<endl;
    		return 0;
    	}
    	int count=0;
    	vector<Tuple> tuples;
    	Tuple tuple;
    	//从文件流中读入数据
    	while(!infile.eof()){
    		count++;
    		if(count%2==1) infile>>tuple.attr1;
    		else {
    			infile>>tuple.attr2;
    			tuples.push_back(tuple);
    		}
    	}
    	//int k;
    	//cout<<"请输入期望的簇的个数："
    	//cin>>k;
    	//cout<<endl;
     
    	//输出文件中的元组信息
    	for(vector<Tuple>::size_type ix=0;ix!=tuples.size();++ix)
    		cout<<"("<<tuples[ix].attr1<<","<<tuples[ix].attr2<<")"<<"    ";
        cout<<endl;
    	KMeans(tuples);
    	return 0;
    }

原文转自：[https://blog.csdn.net/cai0538/article/details/7061922][https_blog.csdn.net_cai0538_article_details_7061922]

[https_blog.csdn.net_cai0538_article_details_7061922]: https://blog.csdn.net/cai0538/article/details/7061922