基于距离函数的改进kmeans算法

　　摘要：聚类算法在自然科学和和社会科学中都有很普遍的应用，而K-means算法是聚类算法中经典的划分方法之一。但如果数据集内相邻的簇之间离散度相差较大，或者是属性分布区间相差较大，则算法的聚类效果十分有限。本文基于离散度的思想，采用新的加权距离函数代替了传统算法的欧氏距离，在一定程度上优化了k-means算法的聚类结果。
　　关键词：聚类；k-means算法；离散度
　　1 概述
　　在当今时代，数据可以说是最宝贵的财富，数据挖掘算法成了发掘数据财富的最有效手段，而聚类分析可以算是数据挖掘算法的重要组成部分。聚类分析是指根据物理或者抽象对象的集合相似度来分组的分析过程，目标是尽量将类似的对象归为一类。聚类源于各种领域，包括计算机科学，数学，统计学，经济学和生物学等。用于衡量不同数据元素之间的相似性，并根据相似性将数据元素归类到不同的簇中。而根据对象间相似性度量和聚类评价准则的不同，聚类方法可以分成五类：层次方法，划分方法，基于密度的方法，基于网格的方法和基于模型的方法[1]。
　　K-means算法是很典型的基于距离的聚类算法，同是也是一种基于划分的算法，采用距离作为相似性的评价指标。该算法简单且易于使用，运行速度快，与其他聚类算法相比应用更加广泛[2]。但同时k-means的缺陷也十分明显。首先，算法只能求得局部最优解，无法得到全局最优；其次，算法是硬聚类，初始中心点的选择对最终结果的影响相当大；再次，对于异常点非常敏感；最后，对于簇间离散度相差较大的数据集的边界点分类效果不好。
　　针对k-means的缺陷，出现了许许多多不同的改进，主要针对类别个数K的选择，初始中心点，异常点剔除，相似性度量和聚类评价准则这四个方面。对于最佳聚类数的确定，国外学者Hamerly等提出了对于簇数量的估算方法[3]，可以根据簇的分布估算出K的大小，国内学者周世兵[4]等从样本几何结构的角度设计了一种新的聚类有效性指标，并在此基础上提出了一种新的确定最佳聚类数的方法；关于初始中心点的选择，朱颢东[5]等提出的使用改进的模拟退火算法来优化初始中心点，将退火算法和k-means结合在一起，较好的改进了算法对初始中心点敏感这一缺点；对于样本异常点对于分类的影响，张玉芳[6]等提出了基于取样的划分思想，直接在样本层面排除了一部分的异常点，张琳[7]等采用密度的思想，通过设定EPS领域以及EPS领域内至少包含的对象数minpts来排除孤立点，并将不重复的核心点作为初始聚类中心；最后关于k-means相似性度量和聚类评价准则，这一直是改进的主要方向，特别是对于原算法使用的欧氏距离，Mao & Jain[8]提出了Mahalanobis距离来代替，但是本身缺点也很明显。后来，先后出现了Itakura-Saito，Bregman等距离，相对于欧式距离有许多突出优点，如克服局部最优，线性时间复杂度等[9]。
　　2 K-means算法的基本思想和过程
　　2.1 K-means基本思想
　　k-means算法是硬聚类算法，它将数据元素到中心点的某种距离作为聚类规则并迭代求极小值，是基于原型的目标函数聚类方法的代表。最原始的k-means算法用元素点到中心点的欧式距离作为相似度测度，本质是一种贪心的思想，只选择当前所能看到的最优解，所以只能得到局部最优解。算法以K为簇的数量，一旦确定在算法执行过程中就不会改变，把n个对象分为K簇，k-means的核心思想就是先从n个待聚类对象中选出K个点作为第一次聚类的初始中心点，而剩余的对象则根据相似度测度即到中心点的欧式距离分配到离得最近的簇，分配结束后计算新形成的簇的中心点。这是个迭代的过程直到中心点不再有较大的变化，达到聚类的效果。显然，k-means的几个主要的缺点，初始K值难以确定、初始中心点选择影响较大也是因此而来。
　　2.2 K-means算法的基本过程
　　第一步：在X中任意选择k个对象作为初始的簇中心；
　　第二步：REPEAT；
　　第三步：计算每个对象到每个簇中心点的距离，将每个对象分配给离得最近的簇（即最相似的簇）；
　　第四步：根据新的聚类计算每个簇新的中心点；
　　第五步：直到每个簇的中心不再变化，或者变化小于某个阈值。
　　3 改进的K-means算法
　　3.1 改进的出发点
　　对于数据集来说如何才算是好的划分，除了要使同一簇中的对象相似，不同簇之间的对象不相似外，还应该看聚类结果是否能揭示数据的内在联系，得到合理的可解释的数据分类[10]。但是一个数据集内的簇不可能都是分布均匀的，他们之间的离散度可能相差很大。这种情况下，传统k-means算法很难有很高的聚类正确率，特别是对于离散度比较大的簇，由于其准则函数是将各个簇的误差平方值直接相加而得到的，很容易将大离散度的簇的元素点，特别是两个簇的边界点，分配给离散度小的元素集中的簇，从而影响了聚类的质量。所以改进的出发点就在聚类评价准则。我们都知道，标准差可以用来描述组内个体间的离散程度，假设有一组数值则其标准差公式为：
　　3.2 对象分配以及算法的改进
　　改进后的距离公式如下所示：
　　输入：含有N个对象的数据集以及簇的个数k；
　　输出：在k个中心点稳定之后的k个簇；
　　第一步：在数据集中随机选取k个对象作为初始的簇中心；
　　第二步：REPEAT；
　　第三步：使用改进之后的距离函数计算每个对象到每个簇中心点的距离，使dist（）最小，将每个对象分配给离得最近的簇（即最相似的簇）；
　　第四步：根据新的聚类计算每个簇新的中心点并计算此簇的标准差；
　　第五步：直到元素点的类别不在变化。
　　从上面的算法步骤可以看出，改进后的算法和传统k-means步骤上没有什么区别，只有dist函数不一样。自然，改进后的算法时间复杂度比之传统k-means算法要高一些。
　　4 试验和结果分析
　　模拟试验使用的数据由MATLAB生成，包含一个数据集，数据集如图1所示：
　　数据集包含两个相邻的圆形簇。所有的数据点都是用的MATLAB随机方法生成，具体的数据见表1。
　　两个数据集的特点都是相邻的簇的离散度相差比较大，其中一个簇的数据元素的属性分布比较广，而且簇之间的距离比较近。分别对两个数据集上运行传统的k-means算法和改进的k-means算法。数据集二的试验结果如下所示，图3是传统k-means算法的聚类结果，图4是改进算法的聚类结果。
　　对比可以看出，在模拟数据集下改进后的算法的正确率相对于传统k-means有一定的提高。
　　5 结论
　　参考文献：
　　[3] Hand D J， Mannila H， Smyth P.Principles of data mining. MIT press，2001.
　　[4] Jain A K， Mao J， Mohiuddin K. Artificial neural networks： A tutorial. Computer，1996（3）：31-44.
　　[5] Soman K， Diwakar S， Ajay V. Data Mining： Theory and Practice [WITH CD]. 2006： PHI Learning Pvt. Ltd.
　　[8] 张玉芳，毛嘉莉， 熊忠阳. 一种改进的 K―means算法[J]. 计算机应用， 2003，23（8）：31-33.
　　[9] 周世兵，徐振源， 唐旭清. K-means 算法最佳聚类数确定方法[J].计算机应用，2010，30（8）：1995-1998.