2022年K-Means聚类算法及实现代码 .pdf

K-Means算法k-means 算法接受参数k；然后将事先输入的n 个数据对象划分为k 个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。假设要把样本集分为c 个类别，算法描述如下：（1）适当选择c 个类的初始中心；（2）在第 k 次迭代中，对任意一个样本，求其到c 个中心的距离，将该样本归到距离最短的中心所在的类；（3）利用均值等方法更新该类的中心值；（4）对于所有的c 个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。#include#include#include#define _NUM 3/预定义划分簇的数目using namespace std;/*特征对象，表示一个元组，一个元组有两个数值属性*/struct Tuple int attr1;int attr2;/*获取两个特征对象之间的距离，在此以欧基米德距离作为距离度量标准*/double getDistXY(Tuple t1,Tuple t2)return sqrt(t1.attr1-t2.attr1)*(t1.attr1-t2.attr1)+(t1.attr2-t2.attr2)*(t1.attr2-t2.attr2);/*计算簇的中心点，在此以簇中所有对象的平均距离来计算中心点*/Tuple getMeansC(vector c)名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 4 页 -int num=c.size();double meansX=0,meansY=0;Tuple t;for(int i=0;i num;i+)meansX+=ci.attr1;meansY+=ci.attr2;t.attr1=meansX/num;t.attr2=meansY/num;return t;/*获取算法的准则函数值，当准则函数收敛时算法停止*/double getE(vector classes,Tuple means)double sum=0;for(int i=0;i _NUM;i+)vector v=classesi;for(int j=0;j v.size();j+)sum+=(vj.attr1-meansi.attr1)*(vj.attr1-meansi.attr1)+(vj.attr2-meansi.attr2)*(vj.attr2-meansi.attr2);coutsum:sumendl;return sum;/*对当前的特征对象，查找与其最临近的簇，最临近即到簇中心点的距离最短*/int searchMinC(Tuple t,Tuple means_NUM)int c=0;int d=(t.attr1-means0.attr1)*(t.attr1-means0.attr1)+(t.attr2-means0.attr2)*(t.attr2-means0.attr2);for(int i=1;i _NUM;i+)int temp=(t.attr1-meansi.attr1)*(t.attr1-meansi.attr1)+(t.attr2-meansi.attr2)*(t.attr2-meansi.attr2);if(temp d)名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 4 页 -c=i;d=temp;return c;/*k-Means算法*/void kMeans(vector init)vector classes_NUM;/定义簇数组，共需划分 _NUM 个簇int c;Tuple means_NUM;/定义中心点数组，每个簇对应一个中心点double newE,oldE=-1;/定义准则函数值for(int i=0;i c;classesi.push_back(initc-1);meansi=getMeansC(classesi);/计算当前每个簇的中心点coutmeansi:meansi.attr1 meansi.attr2endl;newE=getE(classes,means);/计算当前准则函数值coutnewE:newE oldE:oldEendl;for(i=0;i=1)/当新旧函数值相差不到1 即准则函数值不发生明显变化时，算法终止 for(int j=0;j init.size();j+)/遍历所有特征对象，将其加入到离它最近的簇 int toC=searchMinC(initj,means);classestoC.push_back(initj);cout-endl;for(i=0;i _NUM;i+)/打印出当前每个簇的特征对象 vector temp=classesi;cout类i+1:endl;for(j=0;j temp.size();j+)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 4 页 -couttempj.attr1 tempj.attr2endl;cout-endl;for(i=0;i _NUM;i+)/更新每个簇的中心点 meansi=getMeansC(classesi);coutmeansi:meansi.attr1 meansi.attr2endl;oldE=newE;newE=getE(classes,means);/计算新的准则函数值for(i=0;i _NUM;i+)/清空每个簇 classesi.clear();/*程序入口*/void main(int args,char*arg)int n1,n2;vector init;/保存所有输入的特征对象while(cin n1 n2)&n1!=-1&n2!=-1)/输入特征对象 Tuple p;p.attr1=n1;p.attr2=n2;init.push_back(p);kMeans(init);/调用 k-Means算法进行聚类分析 名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 4 页 -