Kmeans聚类算法以及实现

1、K means 聚类算法以及实现一、 Kmeans算法k-means 算法接受参数 k；然后将事先输入的n 个数据对象划分为k 个聚类以便使得所获得的聚类满足： 同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。K-means 算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。 K-means 算法的基本思想是：以空间中k 个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。假设要把样本集分为c 个类别，算法描述如下：（ 1）适当选择c

2、 个类的初始中心；（ 2）在第k 次迭代中，对任意一个样本，求其到c 个中心的距离，将该样本归到距离最短的中心所在的类；（ 3）利用均值等方法更新该类的中心值；（ 4）对于所有的 c 个聚类中心，如果利用（ 2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式二、算法流程首先从 n 个数据对象任意选择k个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的） 聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值） ；不断重

3、复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k 个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。Kmeans算法实现的步骤具体描述为：(1) 从疗个数据对象中任意选取 k个对象作为初始的聚类中心。(2) 分别计算每个对象到各个聚类中心的距离， 把对象分配到距离最近的聚类中。(3) 所有对象分配完成后，重新计算 k个聚类的中心。(4) 与前一次计算得到的 k个聚类中心比较，如果聚类中心发生变化，转 (2) ，否则转 (5) 。(5) 输出聚类结果。实现的流程框图为首先从 n 个数据对象中任意选择 k 个对象作为初始聚类中心； 而对于所剩下的其

4、它对象，则根据他们与这些聚类中心的相似度 ( 距离 ) ，分别将他们分配给与其最相似的 ( 聚类中心所代表的 ) 聚类。然后再计算每个所新聚类的聚类中心 ( 该聚类中所有对象的均值 ) 。不断重复这一过程直到标准测度函数开始收敛为止。 一般都采用均方差作为标准测度函数， 具体定义如下：其中 E 为数据库中所有对象的均方差之和； p 为代表对象的空间中的一个点；m，为聚类 G的均值 (p 和 m，均是多维的 ) 上述公式所示聚类标准旨在使所获得的 k 个聚类具有以下特点：各聚类本身尽可能的紧凑， 而各聚类间尽可能的分开。三、设计实现K-Means算法是聚类算法的一种， 它通过计算样本数据点之间的

5、逻辑距离来判断某个样本数据点属于哪一个簇， 算法最终的目的是要把用于算法的样本数据点分配到 K 个簇中，使簇内的点有较大的相似度，而簇间的点有较小的相似度。K-Means中的 K 表示聚类中心的个数，在算法运行过程中，要反复扫描所有样本数据点，要计算每个非中心数据点与某个聚类中心点的距离， 并将这个数据点归为与其距离最小的那个聚类中心对应的簇之中。 每扫描一次就要重新计算每个聚类中心点的位置。当聚类中心点的位置变化在一定的阈值之内的时候停止处理，最后就可以得到K 个簇，并且簇中每个样本数据点到本簇的中心的距离都小于到其它簇中心的距离 。本程序使用 C+实现算法本身，然后用C#调用 C+函数完成

6、了数据的传送和接收算法的输出并可视化结果。并且数据是保存在Access 数据库中的一个sample 表格中然后通过字符串连接数据库读入数据也可以使用其他数据库，例如sqlserver，修改相应的字符串连接语句即可。下面主要介绍一个导出的函数DataMining_KMeans，这个函数要接收C#传过来的原始数据、 K 值及其它参数，同时还要将处理的结果赋值给引用参数以便在C#中可以接收到处理结果。DataMining_KMeans函数的原型如下：/* Author:YinPSoft* param:* raw:原始数据* count:数据点个数* K: 聚类中心个数* means:初始聚类中心*

7、minOffset:聚类中心的最小偏移量，用于控制聚类处理的精度。* times:最大迭代次数* c: 每个聚类的数据点索引值* sizes:每个聚类的容量* finalMeans:最终的聚类中心位置*/voidDataMining_KMeans(double * data,intcount,intK,int* means,doubleminOffset,inttimes,int* c,int* sizes,double* finalMeans);在这个原型声明中可以看到初始聚类中心点要从外部输入，从外部输入这种方式有更大的灵活性， 当有特定的初始聚类中心生成策略的时候可能通过这个策略来生成中

8、心点， 而没有策略的时候也可以通过随机来生成。初始聚类中心的值可以很大程度地影响到整个算法的效率，适当的选择聚类中心点可以减少算法的迭代次数。接着是初始化：for(i =0 ; i < K; i+)vector<int> cluster;clusters.push_back(cluster);meanIndex.push_back(*(means + i);dots.at(*(means+i).isMean =true;dots.at(*(means+i).isVirtual =false;上面的代码有两个目的：一是初始化vector<int>数组用于存放K 个簇

9、的样本点索引；二是将外部传进来的K 个聚类中心点添加到dots对象之中， dots对象是 vector<Dot2D>类型的。在DataMining_KMeans最开始就要通过PreProcessor函数将外部传进来的数据点封装成vector<Dot2D>的对象，在这里是dots。Dot2D的定义如下， isMean和isVirtual是数据点的两个标志，前者用于标识这个数据点是否是聚类中心，后者用于表示这个点是不是虚拟数据点，虚拟数据点在这里意为这个点的位置是通过计算得到，而不是原始数据中的数据点。实际上， 在这个算法中， 虚拟数据点都是在处理过程中得到的聚类中心点，因

10、为每一轮计算完成后要重新计算聚类中心位置，而这个计算出来的位置很可能不同于原始数据中的任何一个点，所以要把这些点保存下来用于下一轮的计算：typedefstructDotdoublex;doubley;boolisMean;boolisVirtual; Dot2D, *Ptr_Dot2D;接下来就是一个while 循环，反复地扫描样本数据点并将其分配K 个簇中。在这个while循环中包括两大部分，首先就是计算并比较数据点与聚类中心的距离并进行分配；其次就是重新计算聚类中心。代码如下：for(i =0 ; i < count; i+)if(!dots.at(i).isMean &&

11、amp; !dots.at(i).isVirtual)dist = INFINITE_DISTANCE;for(j =0 ; j < K; j+)term = Distance(dotsi, dotsmeanIndexj);if(term < dist)dist = term;/ 存放与聚类中心有最小距离的那个数据点的索引值c = j;/ 将第 i 个数据点放入第 j 个聚类clusters.at(c).push_back(i);对所有数据点的扫描计算的前提是这些数据点不是聚类中心并且也不是虚拟数据点。然后将中间距离变量设置一个初值，接下来的for 循环就要计算当前这个数据点与每个

12、聚类中心的距离，如果当前点到第K 个聚类中心的距离是最小的，那么就把它的索引值存放到clusters的第K 个vector<int>对象中。当所有的样本数据点都被分配到K 个簇中以后就要重新计算中心点的位置，代码如下：for(i =0 ; i < K; i+)maxminvalues = FindMaxMinValues(dots, clusters.at(i);newMean.x = (maxminvalues.at(0) + maxminvalues.at(newMean.y = (maxminvalues.at(1) + maxminvalues.at(newMean.

13、isMean =true;2) /3) /2.0 ;2.0 ;newMean.isVirtual =true;term = Distance(newMean, dotsmeanIndexi);flag = (term > minOffset) ? true dots.at(meanIndex.at(i).isMean =: flag;false;dots.push_back(newMean);*(finalMeans+i) = newMean.x;*(finalMeans+i+K) = newMean.y;meanIndex.at(i) = dots.size() -1;上面的代码用于计

14、算新的聚类中心点的位置，并覆盖之前的聚类中心位置。在这个算法中通过计算簇所占有的矩形区域的中心点来作为新的聚类中心点的位置。在这个 for 循环中还有一件事情就是要计算新的聚类中心点与前一轮的聚类中心点的距离或者称为聚类中心点的位移，在函数原型中我们设置了这个位移的最小值，当K 个位移都小于这个值的时候就要结束算法处理。另外每次进入while循环的时候要清空clusters对象，否则clusters中会有多余的数据，并且会随原始数据量而膨胀。以上就是K-Means算法实现C+ 部分的主要代码，也是这个演示程序的核心部分。除了算法实现部分之外就是算法结果的展示了。另一个项目DMAlgorithm

15、s.Demo用于向算法传送原始数据以及接收算法的输出并可视化结果。在DMAlgorithms.Demo项目中要调用C+函数，方法是通过.NET 的 P/Invoke调用，其代码如下：/ <summary>/ K-Means 聚类分析/ </summary>/<param name="rawdata">KMeans 原始数据 </param>/<param name="rows">数据点个数 </param>/<param name="K">聚类个数 &

16、lt;/param>/<param name="means">初始聚类中心 </param>/<param name="minOffset">聚类中心的最小位移量</param>/<param name="times">最大迭代次数 ,-1 为不控制 </param>/<param name="result">聚类划分结果 </param>>/<param name="finalMeans&q

17、uot;>返回的最终聚类中心 </param>/<param name="size">表示第一个参数的长度 </param>/<param name="finalMeans_size">表示第九个参数的长度</param>DllImport("SimpleKMeans.Core.dll", EntryPoint ="DataMining_KMeans" ,CharSet = CharSet.Auto)publicstaticexternvoid DataMining_KMeans(MarshalAs(UnmanagedType.LPArray, SizeParamIndex =9)double rawdata,introws,intK,MarshalAs(UnmanagedType.LPArray, SizeParamIndex =