K-Means聚类算法及实现代码.doc

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) 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) 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+) 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; /保存所有输入的特征对象 whil