Kmeans聚类算法以和实现

K means聚类算法以及实现

一、Kmeans算法

k-means 算法接受参数 k ；然后将事先输入的n个数据对象划分为 k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高；而不同聚类中的对象相似度较小。聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”（引力中心）来进行计算的。

K-means算法是最为经典的基于划分的聚类方法，是十大经典数据挖掘算法之一。K-means算法的基本思想是：以空间中k个点为中心进行聚类，对最靠近他们的对象归类。通过迭代的方法，逐次更新各聚类中心的值，直至得到最好的聚类结果。

假设要把样本集分为c个类别，算法描述如下： （1）适当选择c个类的初始中心；

（2）在第k次迭代中，对任意一个样本，求其到c个中心的距离，将该样本归到距离最短的中心所在的类； （3）利用均值等方法更新该类的中心值；

（4）对于所有的c个聚类中心，如果利用（2）（3）的迭代法更新后，值保持不变，则迭代结束，否则继续迭代。

该算法的最大优势在于简洁和快速。算法的关键在于初始中心的选择和距离公式

二、算法流程

首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数. k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。 Kmeans算法实现的步骤具体描述为：

完美整理

Word格式

(1)从疗个数据对象中任意选取k个对象作为初始的聚类中心。

(2)分别计算每个对象到各个聚类中心的距离，把对象分配到距离最近的聚类中。 (3)所有对象分配完成后，重新计算k个聚类的中心。

(4)与前一次计算得到的k个聚类中心比较，如果聚类中心发生变化，转(2)，否则转(5)。

(5)输出聚类结果。 实现的流程框图为

开始绘制原始数据图输入聚类个数K和迭代次数执行初始化K个聚类中心分配各个数据对象到距离最近的类中否重新计算各个聚类的中心E是否收敛是输出聚类结果接受并可视化显示结束

首先从n个数据对象中任意选择k个对象作为初始聚类中心；而对于所剩下的其它对象，则根据他们与这些聚类中心的相似度(距离)，分别将他们分配给与其最相似的(聚类中心所代表的)聚类。

然后再计算每个所新聚类的聚类中心(该聚类中所有对象的均值)。不断重复这一 过程直到标准测度函数开始收敛为止。一般都采用均方差作为标准测度函数，具

完美整理

Word格式

体定义如下：

其中E为数据库中所有对象的均方差之和；p为代表对象的空间中的一个点； m，为聚类G的均值(p和m，均是的)．上述公式所示聚类标准旨在使所获得的k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类间尽可能的分开。

三、设计实现

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

本程序使用C++实现算法本身，然后用C#调用C++函数完成了数据的传送和

接收算法的输出并可视化结果。并且数据是保存在Access数据库中的一个sample表格中然后通过字符串连接数据库读入数据

也可以使用其他数据库，例如sqlserver，修改相应的字符串连接语句即可。 下面主要介绍一个导出的函数DataMining_KMeans，这个函数要接收C#传过来的原始数据、K值及其它参数，同时还要将处理的结果赋值给引用参数以便在C#中可以接收到处理结果。DataMining_KMeans函数的原型如下：

/*

* @Author:YinPSoft * @param: * raw: 原始数据 完美整理

Word格式

* count: 数据点个数 * K: 聚类中心个数 * means: 初始聚类中心

* minOffset: 聚类中心的最小偏移量，用于控制聚类处理的精度。 * times: 最大迭代次数 * c:每个聚类的数据点索引值 * sizes:每个聚类的容量

* finalMeans:最终的聚类中心位置 */

void DataMining_KMeans(double* data, int count, int K, int* means, double minOffset, int times, int* c, int* sizes, double* finalMeans);

在这个原型声明中可以看到初始聚类中心点要从外部输入，从外部输入这种方式有更大的灵活性，当有特定的初始聚类中心生成策略的时候可能通过这个策略来生成中心点，而没有策略的时候也可以通过随机来生成。初始聚类中心的值可以很大程度地影响到整个算法的效率，适当的选择聚类中心点可以减少算法的迭代次数。 接着是初始化：

for (i = 0; i < K; i++) { vector cluster;

clusters.push_back(cluster);

meanIndex.push_back(*(means + i)); dots.at(*(means+i)).isMean = true;

完美整理

Word格式

dots.at(*(means+i)).isVirtual = false;

上面的代码有两个目的：一是初始化vector数组用于存放K个簇的样本点索引；二是将外部传进来的K个聚类中心点添加到dots对象之中，dots对象是vector类型的。在DataMining_KMeans最开始就要通过PreProcessor函数将外部传进来的数据点封装成vector的对象，在这里是dots。Dot2D的定义如下，isMean和isVirtual是数据点的两个标志，前者用于标识这个数据点是否是聚类中心，后者用于表示这个点是不是虚拟数据点，虚拟数据点在这里意为这个点的位置是通过计算得到，而不是原始数据中的数据点。实际上，在这个算法中，虚拟数据点都是在处理过程中得到的聚类中心点，因为每一轮计算完成后要重新计算聚类中心位置，而这个计算出来的位置很可能不同于原始数据中的任何一个点，所以要把这些点保存下来用于下一轮的计算：

typedef struct Dot {

double x;

double y;

bool isMean; bool isVirtual; } Dot2D, *Ptr_Dot2D;

接下来就是一个while循环，反复地扫描样本数据点并将其分配K个簇中。在这个while循环中包括两大部分，首先就是计算并比较数据点与聚类中心的距离并进行分配；其次就是重新计算聚类中心。代码如下：

for (i = 0; i < count; i++) {

if (!dots.at(i).isMean && !dots.at(i).isVirtual) {

dist = INFINITE_DISTANCE; for (j = 0; j < K; j++) {

term = Distance(dots[i], dots[meanIndex[j]]); if (term < dist) {

dist = term;

//存放与聚类中心有最小距离的那个数据点的索引值 c = j; } 完美整理

Word格式

}

//将第i个数据点放入第j个聚类 clusters.at(c).push_back(i); } }

对所有数据点的扫描计算的前提是这些数据点不是聚类中心并且也不是虚拟数据点。然后将中间距离变量设置一个初值，接下来的for循环就要计算当前这个数据点与每个聚类中心的距离，如果当前点到第K个聚类中心的距离是最小的，那么就把它的索引值存放到clusters的第K个vector对象中。当所有的样本数据点都被分配到K个簇中以后就要重新计算中心点的位置，代码如下：

for (i = 0; i < K; i++) {

maxminvalues = FindMaxMinValues(dots, clusters.at(i));

newMean.x = (maxminvalues.at(0) + maxminvalues.at(2)) / 2.0; newMean.y = (maxminvalues.at(1) + maxminvalues.at(3)) / 2.0; newMean.isMean = true; newMean.isVirtual = true;

term = Distance(newMean, dots[meanIndex[i]]); flag = (term > minOffset) ? true : flag; dots.at(meanIndex.at(i)).isMean = false; dots.push_back(newMean); *(finalMeans+i) = newMean.x;

*(finalMeans+i+K) = newMean.y; meanIndex.at(i) = dots.size() - 1; }

上面的代码用于计算新的聚类中心点的位置，并覆盖之前的聚类中心位置。在这个算法中通过计算簇所占有的矩形区域的中心点来作为新的聚类中心点的位置。在这个for循环中还有一件事情就是要计算新的聚类中心点与前一轮的聚类中心点的距离或者称为聚类中心点的

完美整理

Word格式

位移，在函数原型中我们设置了这个位移的最小值，当K个位移都小于这个值的时候就要结束算法处理。另外每次进入while循环的时候要清空clusters对象，否则clusters中会有多余的数据，并且会随原始数据量而膨胀。

以上就是K-Means算法实现C++部分的主要代码，也是这个演示程序的核心部分。除了算法实现部分之外就是算法结果的展示了。另一个项目DMAlgorithms.Demo用于向算法传送原始数据以及接收算法的输出并可视化结果。在DMAlgorithms.Demo项目中要调用C++函数，方法是通过.NET的P/Invoke调用，其代码如下：

///

/// KMeans原始数据 /// 数据点个数 /// 聚类个数

/// 初始聚类中心

/// 聚类中心的最小位移量 /// 最大迭代次数,-1为不控制 /// 聚类划分结果 > /// 返回的最终聚类中心 /// 表示第一个参数的长度 /// 表示第九个参数的长度

[DllImport(\"SimpleKMeans.Core.dll\", EntryPoint = = CharSet.Auto)]

public static extern void DataMining_KMeans(

[MarshalAs(UnmanagedType.LPArray, SizeParamIndex = 9)] double[] rawdata, int rows, int K,

[MarshalAs(UnmanagedType.LPArray, SizeParamIndex = 2)] int[] means,

double minOffset, int times,

[MarshalAs(UnmanagedType.LPArray, SizeParamIndex = 1)] int[] result,

[MarshalAs(UnmanagedType.LPArray, SizeParamIndex = 2)] int[] sizes,

[MarshalAs(UnmanagedType.LPArray, SizeParamIndex = 10)] double[] finalMeans,

int size, int finalMeans_size );

实验最终效果图如下：K=5

完美整理

,CharSet \"DataMining_KMeans\"Word格式

K=4

完美整理

Word格式

完美整理