K-means聚类算法的实现及应用内容摘要本文在分析和实现经典k-means算法的基础上，针对初始类中心选择问题，结合已有的工作，基于对象距离和密度对算法进行了改进。
在算法实现部分使用vc6.0作为开发环境、sql sever2005作为后台数据库对算法进行了验证，实验表明，改进后的算法可以提高算法稳定性，并减少迭代次数。
关键字 k-means；随机聚类；优化聚类；记录的密度1 引言1.1聚类相关知识介绍聚类分析是直接比较各事物之间性质，将性质相近的归为一类，将性质不同的归为一类，在医学实践中也经常需要做一些分类工作。
如根据病人一系列症状、体征和生化检查的结果，将其划分成某几种方法适合用于甲类病的检查，另几种方法适合用于乙类病的检查，等等。
聚类分析被广泛研究了许多年。
基于聚类分析的工具已经被加入到许多统计分析软件或系统中，入s-plus,spss,以及sas。
大体上，聚类算法可以划分为如下几类：1) 划分方法。
2) 层次方法。
3) 基于密度的算法。
4) 基于网格的方法。
5) 基于模型的方法。
1.2 研究聚类算法的意义在很多情况下，研究的目标之间很难找到直接的联系，很难用理论的途径去解决。
在各目标之间找不到明显的关联，所能得到的只是些模糊的认识，由长期的经验所形成的感知和由测量所积累的数据。
因此，若能用计算机技术对以往的经验、观察、数据进行总结，寻找个目标间的各种联系或目标的优化区域、优化方向，则是对实际问题的解决具有指导意义和应用价值的。
在无监督情况下，我们可以尝试多种方式描述问题，其中之一是将问题陈述为对数分组或聚类的处理。
尽管得到的聚类算法没有明显的理论性，但它确实是模式识别研究中非常有用的一类技术。
聚类是一个将数据集划分为若干聚类的过程，是同一聚类具有较高相似性，不同聚类不具相似性，相似或不相似根据数据的属性值来度量，通常使用基于距离的方法。
通过聚类，可以发现数据密集和稀疏的区域，从而发现数据整体的分布模式，以及数据属性间有意义的关联。
2 k-means算法简介2.1 k-means算法描述k-means 算法接受输入量k，然后将n个数据对象划分为k个聚类以便使得所获得的聚类满足：同一聚类中的对象相似度较高，而不同聚类中的对象相似度较小。
聚类相似度是利用各聚类中对象的均值所获得一个“中心对象”来进行计算的。
k-means 算法的工作过程说明如下：首先从n个数据对象任意选择 k 个对象作为初始聚类中心；而对于所剩下其它对象，则根据它们与这些聚类中心的相似度（距离），分别将它们分配给与其最相似的（聚类中心所代表的）聚类；然后再计算每个所获新聚类的聚类中心（该聚类中所有对象的均值）；不断重复这一过程直到标准测度函数开始收敛为止。
一般都采用均方差作为标准测度函数。
k个聚类具有以下特点：各聚类本身尽可能的紧凑，而各聚类之间尽可能的分开。
2.2 k-means算法实现步骤在原始的k-means算法中，由于数据对象的分类被不断地调整，因此平均误差准则函数在每次迭代过程中的值必定在不断减小。
当没有数据对象被调整时，e（e指每个对象到该类中心的距离平方之和）的值不再变化，说明算法运行结果已经达到最优，同时算法运行结束。
（1）给定大小为 n 的数据集，令 i =1，选取 k 个初始聚类中心 z j(i)，j =1，2，3，...，k ；（2）计算每个数据对象与聚类中心的距离d(xi，zj(i))；其中 i=1，2，3，…，n，j=1，2，3，…，k，如果满足xi 到wk的聚类中心距离最小则xi∈wk；（3）令i=i+1，计算k个新的聚类中心；j=1，2，3，…，k以及平均误差准则函数e的值（4）判断：若 e(i+1)=e(i)则算法结束，否则i=i+1，返回继续执行（2）步。
从上面步骤可以看出，该算法的特点为调整一个数据对象后就修改一次聚类中心和准则函数e的值，当考察完n个数据对象后，一次迭代运算完成，新的聚类中心和e值也计算出来了。
如果在一次迭代前后，e的值没有变化，说明算法已经收敛，即使用准则e作为算法是否结束的依据。
在迭代的过程中，e值逐渐减小，直到它的最小值为止。
在算法的每次迭代过程中，把每一个数据对象分到离它最近的聚类中心所在的簇。
3. k-means算法初始类中心的选择3.1 经典k-means算法初始类中心选择方法先从需要聚类的所有对象中随机选取一个对象作为第一个初始聚类中心，然后从剩下的记录中随机选出下一个初始类中心，如此依次得到所有初始聚类中心，这样避免的类中心的重复。
c++语言实现如下：m_numcluster指要聚类的数目，m_object[]保存记录对象，index_cluster[]保存初始类中心在m_object[]中的下标。
3.2 改进k-means算法类中心选择方法本文列出了2种选择初始类中心的优化方法：远距离优化法和最大密度优化法。
3.2.1初始类中心的选择——远距离改进法在k-means算法中，选择不同的初始聚类中心会产生不同的聚类结果且有不同的准确率．研究的目的就是如何一开始就可以快速，尽可能准确的找到数据在空间分布上的初始聚类中心，从而对数据进行划分．在用欧氏距离作为相似性度量的k-means算法中，相互距离最远的数据对象比随机取的数据对象更具有代表性，它们属于不同聚类的可能性比较大．如果能够寻找到是个相对距离最远的数据对象，它们分别代表了k个不同的数据集合，那么就可以找到与数据在空间分布上相一致的初始聚类中心．为了找到与数据在空间分布上相一致的、相似程度较大的数据集合。
找最远距离的两个对象步骤如下：确定需要划分簇的个数k，计算数据对象两两之间的距离；找出距离最远的两个数据对象，形成两个独立的数据对象a1 和a2；计算数据对象a1 ，a2。
与数据对象集合u中每一个样本的距离，找出在u中与a1 ，a2同时最远的数据对象，将它作为数据对象a3。
重复上面的过程，直到确定了ak个数据对象为止，形成k个初始聚类中心．根据排列组合可知，求距离语句的频度为cn2 =n(n-1)/2，则其时间复杂度为o(n2)；如果对时间效率有要求，显然是不妥的。
我们不用找最远的两个数据对象，我们只要找到最终不聚到一个类中的两个数据对象。
试验中我采用的是找两个相距较远（尽可能使其最终不再一个类中）的数据对象作为前两个初始聚类中心，这是一种更高效的方法：先找出边界上的对象（拿二维数据对象举例来说，即是用一个矩形框刚好将所有数据对象围住，如图1所示，三维数据对象是用矩形体刚好把所有数据对象框住），得到k个点，从k个点中找最远的两个点。
一般情况边界点数目k远远小于n个（n为所有聚类对象数目）,如下图1:图1边界对象展示先遍历一遍所有数据对象找到出现过的最小的和最大的横纵坐标，再遍历一遍所有数据对象保存下边界数据对象，再求边界数据对象的最远距离，若边界数据对象是k个，关键语句执行频度为2n+ck2,则其时间复杂度为o(n)；由此可见，当数据量很大时，第2种初始化类中心方法效率高很多。
在找到两个相距较远的数据对象作为聚类中心后，找接下来的据类中心，我们很容易想到3种方法：（1）找到离已知类中心最近距离最大的数据记录；（2）找到离已知类中心最远距离最小的数据记录；（3）找到离已知类中心最远距离最大的数据记录；但其中只有第一种是合适的，第二种和第三种都是不合理的。
我们找接下来的初始类中心，是希望这个记录与已知的类中心相比具有一定的独立性，最后聚类完成后属于不同的类簇中。
3.2.2初始类中心的选择——密度最大改进法3.2.2.1 邻域和密度的说明我们可以认为每一个聚类对象也就是数据记录都有一个邻域，邻域中的数据记录代表一个对象在所有对象中的位置，它可以体现该对象周围数据记录的密集程度，若一个对象的周围团结的很多其他对象，我们则认为这个对象的密度很大，相反，则认为其密度很小。
3.2.2.2 密度的求法对于数据记录，我们大多时候直接根据距离来归类，所以我们通过统计以该对象为中心，半径为r（r大小可据情况而定）的区域中记录的数目来计算该对象的密度。
当一个聚类对象的密度很大时，其周围的其他对象肯定很密集，其最终成为收敛的聚类中心或就在收敛类中心附近的概率就会很大，这样聚类过程中，把类中心渐渐合理化的迭代过程就会减少。
可以避免最大距离改进法中较远散落点的缺陷。
4.实验及结果分析比较本文选取了两个数据集分别对上述算法进行了测试。
第一个数据集是一些二维点的集合，这些点可以通过我开发的k-means聚类程序手动生成，如5所示；第二个数据集是从数据库中的学生考试成绩的集合，如表2所示。
4.1实验一分析（1）聚类效果图2、图3、图4分别展示了某次随机聚类、远距离优化聚类、最大密度优化聚类的结果（求密度时r=30）。
从中可以看出，在随机的情况比较好的时候，其聚类结果与优化后相似。
但是随机聚类是不稳定的，有些时候，随机聚类会出现效果不稳定的结果，如下图是随机聚类中出现不稳定结果的展示：（2）迭代次数下表是十次试验中各种聚类方法迭代次数比较，我们可以看出对于上图中的数据对象，最大密度优化法效果最优，远距离优化法次之，随机聚类最差。
上表计算结果：随机聚类平均迭代次数为6.5；远距离优化法迭代次数为3；最大距离优化法迭代次数为4。
可知远距离优化法和最大密度优化法都能带来较大的时间效率，随机聚类的时间开销较大。
4.2实验二分析（1）聚类效果下表是本次试验的聚类对象此表表示的意义是：根据english，math，cs这三门成绩聚类，class字段表示随机聚类的结果，class_youhua表示最大密度优化法聚类后的结果，average表示平均成绩。
如表2所示，实验处理的对象是数值型（只对3门成绩处理），次试验中我们选择的邻域半径为10。
按此方法，求得图10中各个记录的密度如下表：由表三可知记录14 的密度最大为5，故将选为第一个初始类中心。
(2) 聚类效果的比较我们先认为将平均成绩分为5类：[85，100]为第一类，[70,85）为第二类，[55,70）为第三类，[40，55）为第四类，[0,40）为第五类。
聚类结果的效果有图10中class和class_youhua两个字段体现，这两个字段中的数字代表某一类，但不是每次0都是代表成绩最好的那一类，4代表最差的那一类，也许是每次代表不同的意义，但我们可以简单地看出其代表的好坏意义。
例如本次实验中，对于随机聚类成绩由好到坏代表的依次是0、4、1、2、3，根据统计的平均成绩，0代表的成绩区间为[93，97.3]，4代表的成绩区间为[76,82]，1代表的成绩区间为[68.6,77.6]，2代表的成绩区间为[49.6,62]，3代表的成绩为44；对于最大密度优化聚类成绩由好到坏代表的已依次是0、4、2、3、1，0代表的成绩区间为[84.6，97.3]，4代表的成绩区间为[76,82]，2代表的成绩区间为[62，72]，3代表的成绩56，1代表的成绩区间为[44，51.6]。