搜索
K-Means算法k-means算法接受参数k；然后将事先输入的n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。假设要把样本集分为c个类别，算法描述如下：（1）适当选择c个类的初始中心；（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类；（3）利用均值等方法更新该类的中心值；（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。#includeiostream#includemath.h#includevector#define_NUM3//预定义划分簇的数目usingnamespacestd;/**特征对象，表示一个元组，一个元组有两个数值属性**/structTuple{intattr1;intattr2;};/**获取两个特征对象之间的距离，在此以欧基米德距离作为距离度量标准**/doublegetDistXY(Tuplet1,Tuplet2){returnsqrt((t1.attr1-t2.attr1)*(t1.attr1-t2.attr1)+(t1.attr2-t2.attr2)*(t1.attr2-t2.attr2));}/**计算簇的中心点，在此以簇中所有对象的平均距离来计算中心点**/TuplegetMeansC(vectorTuplec){intnum=c.size();doublemeansX=0,meansY=0;Tuplet;for(inti=0;inum;i++){meansX+=c[i].attr1;meansY+=c[i].attr2;}t.attr1=meansX/num;t.attr2=meansY/num;returnt;}/**获取算法的准则函数值，当准则函数收敛时算法停止**/doublegetE(vectorTupleclasses[],Tuplemeans[]){doublesum=0;for(inti=0;i_NUM;i++){vectorTuplev=classes[i];for(intj=0;jv.size();j++){sum+=(v[j].attr1-means[i].attr1)*(v[j].attr1-means[i].attr1)+(v[j].attr2-means[i].attr2)*(v[j].attr2-means[i].attr2);}}coutsum:sumendl;returnsum;}/**对当前的特征对象，查找与其最临近的簇，最临近即到簇中心点的距离最短**/intsearchMinC(Tuplet,Tuplemeans[_NUM]){intc=0;intd=(t.attr1-means[0].attr1)*(t.attr1-means[0].attr1)+(t.attr2-means[0].attr2)*(t.attr2-means[0].attr2);for(inti=1;i_NUM;i++){inttemp=(t.attr1-means[i].attr1)*(t.attr1-means[i].attr1)+(t.attr2-means[i].attr2)*(t.attr2-means[i].attr2);if(tempd){c=i;d=temp;}}returnc;}/**k-Means算法**/voidkMeans(vectorTupleinit){vectorTupleclasses[_NUM];//定义簇数组，共需划分_NUM个簇intc;Tuplemeans[_NUM];//定义中心点数组，每个簇对应一个中心点doublenewE,oldE=-1;//定义准则函数值for(inti=0;i_NUM;i++)//对每个簇初始赋予一个特征对象{cinc;classes[i].push_back(init[c-1]);means[i]=getMeansC(classes[i]);//计算当前每个簇的中心点coutmeans[i]:means[i].attr1means[i].attr2endl;}newE=getE(classes,means);//计算当前准则函数值coutnewE:newEoldE:oldEendl;for(i=0;i_NUM;i++)//清空每个簇{classes[i].clear();}while(abs(newE-oldE)=1)//当新旧函数值相差不到1即准则函数值不发生明显变化时，算法终止{for(intj=0;jinit.size();j++)//遍历所有特征对象，将其加入到离它最近的簇{inttoC=searchMinC(init[j],means);classes[toC].push_back(init[j]);}cout--------------------endl;for(i=0;i_NUM;i++)//打印出当前每个簇的特征对象{vectorTupletemp=classes[i];cout类i+1:endl;for(j=0;jtemp.size();j++){couttemp[j].attr1temp[j].attr2endl;}}cout--------------------endl;for(i=0;i_NUM;i++)//更新每个簇的中心点{means[i]=getMeansC(classes[i]);coutmeans[i]:means[i].attr1means[i].attr2endl;}oldE=newE;newE=getE(classes,means);//计算新的准则函数值for(i=0;i_NUM;i++)//清空每个簇{classes[i].clear();}}}/**程序入口**/voidmain(intargs,char*arg[]){intn1,n2;vectorTupleinit;//保存所有输入的特征对象while((cinn1n2)&&n1!=-1&&n2!=-1)//输入特征对象{Tuplep;p.attr1=n1;p.attr2=n2;init.push_back(p);}kMeans(init);//调用k-Means算法进行聚类分析}