基于距离函数的改进k—means 算法

郑帅　赵晓东

摘要：聚类算法在自然科学和和社会科学中都有很普遍的应用，而K-means算法是聚类算法中经典的划分方法之一。但如果数据集内相邻的簇之间离散度相差较大，或者是属性分布区间相差较大，则算法的聚类效果十分有限。本文基于离散度的思想，采用新的加权距离函数代替了传统算法的欧氏距离，在一定程度上优化了k-means算法的聚类结果。

关键词：聚类；k-means算法；离散度

中图分类号：TP18 文献标识码：A 文章编号：1009-3044（2015）34-0167-03

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 对象分配以及算法的改进

改进后的距离公式如下所示：

最近的元素点。该分配函数目的是使得簇的离散度和簇内元素的粘合度也成为影响分类的因素，[1σ2]这个惩罚系数在一定程度上增加了元素点分配给离散度大的簇的概率，当元素点到达两个簇中心的距离相近时更倾向于分配给离散度大的点；相比于传统的k-means距离函数，改进之后的函数加入了待分配点到离其最近的点的距离，使得簇内元素之间的距离和簇之间的距离也成为分类时需要考量的因素。试想离散度比较大的簇，或者说属性分布区间比较大的簇，如果分配函数只计算到中心点的距离，对于这个簇的边界点，误分的概率几乎是百分之百。而且分配错误的结果会引起中心点相应的偏离，造成更大的误差。改进后的k-means算法对于离散度均匀的数据集，聚类效果和传统k-means算法相近；但是对于存在两个距离过近的簇的数据集，改进算法的效果会比传统k-means算法差。

聚类对象分配函数改进之后，元素点不再直接分配到距离最近中心点所在那个簇中，而是综合考虑上述几点因素，根据加权距离来确定最后的归属，而算法的聚类准则函数和重新选取中心点的函数还是和传统k-means算法一样。改进后的k-means算法的具体过程如下：

输入：含有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是改进算法的聚类结果。

从以上结果中可以看出，离散度大的簇的边界点有很大一部分被分配给小而密的簇。簇1中共有23个数据点被误分给了簇2，误分率为11.5%，直接使用欧式距离分类的缺陷非常明显，同一个簇的元素间的联系完全没有被考虑在内。

改进版算法的聚类结果如下图所示，簇1中有7个点被错误的分类，误分率为3.5%，具体对比见表2。

对比可以看出，在模拟数据集下改进后的算法的正确率相对于传统k-means有一定的提高。

5 结论

通过改进迭代过程中的分配函数，将到各个簇中心的欧式距离调整为到簇中心的距离加上到簇内离其最近元素点的距离之和，并将[1σ2]作为惩罚因子。在簇离散度不均匀且相邻簇大小相差较大的数据集上，元素点将更有可能分配给簇内元素属性分布比较广离散度较大的簇，改进后的k-means算法在一定程度上减少了不合理的分类；对于簇离散度和属性分布差不多或者是簇之间距离较大的数据集，改进后的算法聚类效果和传统k-means一样，但是速度慢一些；对于簇之间距离过小的数据集，改进算法比之传统k-means算法略差。

参考文献：

[1] Berkhin P. A survey of clustering data mining techniques， in Grouping multidimensional data，2006：25-71.

[2] Hamerly G， Elkan C， Learning the k in A> means. Advances in neural information processing systems， 2004（16）：281.

[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.

[6] 王千. K-means 聚类算法研究综述[J]. 电子设计工程，2012，20（7）：21-24.

[7] 张琳.一种基于密度的 K-means 算法研究[J].计算机应用研究，2011，28（11）：4071-4073.

[8] 张玉芳，毛嘉莉， 熊忠阳. 一种改进的 K—means算法[J]. 计算机应用， 2003，23（8）：31-33.

[9] 周世兵，徐振源， 唐旭清. K-means 算法最佳聚类数确定方法[J].计算机应用，2010，30（8）：1995-1998.

[10] 朱颢东， 钟勇， 赵向辉. 一种优化初始中心点的K-Means文本聚类算法[J]. 郑州大学学报： 理学版，2009（2）.