最小方差优化初始聚类中心的K-means 算法

谢娟英，王艳娥

(陕西师范大学计算机科学学院，西安 710062)

1 概述

聚类分析是数据挖掘研究的一项重要技术［1］，属于无监督机器学习方法，它基于物以类聚原理，分析和探索事物的内在联系和本质。在聚类分析过程中，以相似度为基础，使得同一类簇中的模式具有较高的相似度，而不同类簇的模式具有很低的相似度。聚类分析广泛应用于模式识别、数据分析、图像处理等领域［2］。常用的聚类分析方法包括基于划分的方法、基于层次的方法、基于密度的方法、基于网格的方法、基于模型的方法和基于变换的聚类算法［1-2］。

K-means 算法是一种典型的基于划分的聚类算法，该算法将一个含有n 个样本的集合划分为K 个子集合，其中每个子集合代表一个类簇，同一类簇中的样本具有高度的相似性，不同类簇中的样本相似度较低。K-means 算法以其思路简洁、收敛速度快成为应用最广泛的聚类算法。但传统K-means 算法需要预先提供确定的类簇数K，在K 值给定的前提下，随机产生初始聚类中心进行聚类，聚类结果的随机性很大，严重依赖于初始聚类中心，经常收敛于局部最优解。关于K-means 算法的研究形成2 个分支，一是如何确定好的初始聚类中心;二是如何确定合适的K 值。

本文在分析关于K-means 优化初始聚类中心研究的基础上，提出一种基于样本空间分布的最小方差优化K-means 初始聚类中心的聚类算法，以克服现有优化K-means 初始聚类中心的算法需要人为选择一定参数，聚类结果严重依赖于参数选择的缺点。根据样本的分布特征，计算样本的相似度、平均距离及方差;选择方差最小，且相距较远(不小于样本间平均距离)的K 个样本作为K-means 算法的初始聚类中心，避免传统K-means 算法随机选取初始聚类中心所导致的聚类结果不稳定和不可靠现象，以及现有优化初始聚类中心的K-means 算法过多依赖于参数选择的问题。

2 K-means 算法介绍及研究现状

K-means 算法以类簇数K 为参数，将n 个样本划分为互不相交的K 个类簇，同一类簇中的样本相似度较高，而不同类簇的样本相似度较低。常用的相似度判断是计算样本间的欧氏距离。K-means算法的基本思想是:首先从n 个样本集中随机选择K 个样本作为初始聚类中心，根据每个样本与各个聚类中心的相似度，将其分配给最相似的聚类中心，得到K 个互不相交的类簇集合;然后重新计算每个类簇的新中心，再将每个样本根据相似性原理分配给最近的簇中心重新计算每个类簇的新中心，分配每个样本到距离最近的类簇。这个过程不断重复，直到各个类簇的中心不再变化，得到原始样本集合的K 个互不相交的稳定的类簇。

然而，K-means 算法是一个局部搜索过程，其聚类结果依赖于初始聚类中心以及初始划分［3］，并且K-means 算法的最终结果只是相对于初始划分更好，未必是全局最优的划分［4］。但是，如果初始聚类中心选择得好，初始划分按照Forgy 方法产生，即按照最近邻方法将样本分配到各个初始聚类中心产生初始聚类，聚类结果将会达到全局最优［5］。为此，诸多学者致力于K-means 算法的最佳初始聚类中心选择研究。文献［6］提出确定性的初始聚类中心选择方法，根据样本的局部密度选择Kmeans 算法的K 个初始聚类中心;为提高聚类性能，文献［7］在K-means 算法的迭代过程中对每个类簇的新中心重新进行计算;文献［8-9］研究了Kmeans 算法的初始化问题;文献［10］等利用谱方法估计特征中心得到K-means 算法的初始聚类中心;文献［11-14］分别采用不同的样本密度计算方法估计样本点的密度，选择相互距离最远的K 个处于高密度区域的样本作为K-means 算法的初始聚类中心;文献［15］采用密度敏感度量样本的相似性，计算样本密度，启发式地生成K-means 算法的初始聚类中心;文献［16-17］根据样本的空间分布信息以及密度RPCL 算法确定K-means 的初始聚类中心;文献［18］利用密度网格优化K-means 聚类。以上这些优化K-mean 算法一定程度上改善了K-mean的聚类性能，但因需要主观选择一些参数，在一定程度上缺少了客观性。因此，本文基于每个类簇中心的样本方差最小原理，提出基于样本分布紧密度的最小方差优化初始聚类中心的K-means 聚类算法。

3 本文算法

传统K-means 算法随机选取的初始聚类中心有可能是一些孤立点或噪声点，或者不同类簇的初始聚类中心位于同一个类簇，导致聚类结果可能偏离数据集样本的真实分布，得到错误的聚类结果，或者使聚类的收敛速度缓慢甚至很难收敛。选取相互距离较远的样本作为初始聚类中心，可避免初始聚类中心可能位于同一类簇的缺陷，但对噪声点非常敏感，可能导致聚类结果的偏差。文献［6，11-17］分别研究了基于密度优化初始聚类中心的K-means 算法，以解决K-means 算法选择相互距离较远的样本为初始聚类中心时，可能选择到噪音点的问题。然而，尽管这些研究使得这一问题得到一定程度的改善，提高了聚类结果的准确性，但是这些文献中涉及到了密度调节系数或噪声调节系数，聚类结果直接依赖于这些参数的选择，参数选择不好，聚类结果会变得非常差。因此，这些研究带有很大程度上的主观性，需要对原始数据集有一定的先验知识和经验值，且有些算法的执行时间过长，不能处理较大数据集。

本文以样本的方差作为选取K-means 初始聚类中心的启发信息，以样本间的平均距离为半径，选择K 个位于不同区域且在该区域方差最小的样本作为初始聚类中心，不需要其他参数选择，提出基于样本分布紧密度的最小方差优化初始聚类中心的Kmeans 聚类算法。根据方差的定义可知，本文的优化K-means 算法选择的初始聚类中心为紧密度较高，即周围样本分布比较密集的样本，从而保证K-means算法快速地收敛到全局最优解或近似全局最优解，而且初始聚类中心的选择无需人工干预，不需要输入任何参数，保证了K-means 算法聚类结果的客观性和稳定性。

3.1 算法原理

方差是数据集中各数据与其平均数之差的平方和的期望，样本方差的算术平方根为样本标准差［19］。样本方差与样本标准差都是衡量一个样本波动大小的量，样本方差或样本标准差越大，样本数据的波动就越大。在概率论与数理统计中，方差用来度量随机变量与其数学期望(即均值)之间的偏离程度。方差和标准差是测算样本离散趋势最重要和最常用的指标。方差是测算数值型数据离散程度的最重要方法。

K-means 算法的初始聚类中心如果选择到每一个类簇的中心，其方差将最小。基于此原理，本文通过计算数据集所有样本的方差，以及所有样本间的距离均值R，启发式地选择位于样本分布密集区域，且相距较远的样本为K-means 的初始聚类中心。启发式选择过程为:首先选择方差最小的那个样本为第一个类簇的初始中心，以R 为半径做圆;然后，在圆之外的样本中，寻找方差最小的样本作为第二个类簇的初始中心，以R 为半径做圆;重复在剩余样本中选择下一个类簇的初始聚类中心，直到第K 个类簇的初始中心选择到。此时，便得到了K-means 算法的初始聚类中心向量。

3.2 基本概念

假设待聚类的数据集为:

K 个初始聚类中心分别为C1，C2，…，Ck，用W1，W2，…，Wk表示K 个类簇所包含的样本集合，所有样本的集合为W。

定义1 样本xi，xj之间的欧氏距离:

定义2 样本xi到所有样本距离的平均值:

定义3 样本xi的方差:

定义4 数据集样本的平均距离:

定义5 聚类误差平方和:

3.3 算法步骤

算法步骤描述如下:

(1)确定初始聚类中心

1)根据定义1～定义3 计算数据集中每一个样本的方差，在数据集W 中寻找方差最小的样本将其作为第一个类簇的初始聚类中心C1;根据定义4计算数据集样本的平均距离cmean，令:

2)如果c≺K，则令c=c +1，在数据集W 中寻找方差最小的样本将其作为第c 个类簇的初始聚类中心Cc，并令:

否则，找到K 个初始聚类中心C1，C2，…，Ck，转步骤(2)。

3)转步骤2)。

(2)构造初始划分

1)根据定义1 计算数据集中每个样本到各个初始聚类中心的距离，根据相似性原理将样本分配到距离最近，即最相似的类簇中，得到初始划分。

2)计算每一个类簇中所有样本的均值，作为该类簇的新中心。

3)根据定义5 计算当前聚类结果的聚类误差平方和E。

(3)重新分配样本并更新聚类中心

1)根据定义1 计算数据集中每个样本到各个类簇中心的距离，根据相似性原理将样本分配到距离最近的类簇中。

2)计算每一个类簇中所有样本的均值，作为该类簇的新中心。

3)根据定义5 计算当前聚类结果的聚类误差平方和E'。

4)如果E' -E≺10-10，即聚类中心不再变化，则算法结束，输出聚类结果;否则，令E=E'，转向步骤3)。

4 仿真实验

为验证本文算法的聚类效果及其稳定性，分别在UCI 数据集和随机生成的人工模拟数据集两大类数据集上进行测试，并与文献［11，13，15，16］以及传统K-means 算法的聚类结果进行比较，其中传统Kmeans 算法的聚类结果是执行100 次的平均值，文献［11，13，15］的实验结果是调整参数所取得的最好结果。各算法聚类结果的评价除采用聚类误差平方和、聚类时间、聚类准确率这些常用评价方法外，还采用了外部评价法的Rand 指数、Jaccard 系数和Adjusted Rand Index 参数。其中外部评价方法是一种基于预先给定的分布结构，即在数据集样本类标已知情况下对待测试的聚类算法的聚类性能进行评价的有效指标［16，20-23］，Adjusted Rand Index 参数是其中最好的聚类有效性评价准则［24］。

4.1 实验数据集

实验使用的UCI 机器学习数据库［25］的10 个测试聚类算法的常用数据集的描述如表1 所示。

表1 实验所用的UCI 数据集描述

测试本文算法聚类效果的人工模拟数据集包含11 组，其中1 组不含噪音，其他10 组分别含有5%，10%，15%，20%，25%，30%，35%，40%，45% 和50%不同比例的噪音。这些人工模拟数据集每组都含有3 类分别符合不同正态分布的600 个样本，每类200 个。第i 类的横坐标x 的均值为纵坐标y的均值为，第i类的标准差为σi。噪音样本分布在第3 类，其标准差为σl。随机生成的人工模拟数据集的生成参数如表2 所示。

表2 随机生成的人工模拟数据集的各项参数

4.2 实验结果与分析

下面分别是本文算法在UCI 数据集和人工模拟数据集上的实验结果与分析。需要说明的是用于实验对比的优化初始聚类中心K-means 算法是在最佳参数设置下的运行结果。对比算法严重依赖于参数调整，本文采用其他算法的最好实验结果与本文算法的实验结果进行对比，以说明本文算法的优越性。

4.2.1 UCI 数据集的聚类结果与分析

表3 为各算法在10 组UCI 数据集上的聚类误差平方和比较;表4 是各算法在这10 组UCI 数据集的聚类时间比较。表3～表4 中加粗的数据表示最佳的聚类结果，下同。

表3 各算法在UCI 数据集的聚类误差平方和比较

表4 各算法在UCI 数据集的聚类时间比较 s

由表3 聚类误差平方和比较可见，传统K-means算法运行100 次的平均聚类误差平方和在Ionosphere 数据集最优，本文算法在不需要任何初始参数调整条件下在该数据集上的聚类误差平方和明显优于文献［16］的结果，且不差于文献［11，13，15］的聚类误差平方和。表3 的实验结果还显示，本文算法在Iris，Haberman，Balance-scale 3 个数据集上的聚类误差平方和略高于在文献［16］的算法，但在其他数据集上都取得了很好的聚类效果，特别是在Soybean-small 和new-thyroid 数据集上，本文算法的聚类误差平方和绝对地优于其他优化初始聚类中心的K-means 算法的最好聚类误差平方和，以及传统K-means 算法的平均实验结果。以上聚类误差平方和的分析可见，本文算法在不需要任何参数调整的条件下，得到了很好的初始聚类中心，是一种不依赖任何参数调整的优化初始聚类中心的K-means 聚类算法。

表4 关于各算法聚类时间的比较揭示，传统Kmeans 聚类算法的运行时间最快;本文算法的运行时间优于文献［11，13，15］优化初始聚类中心的Kmeans 算法;与本文在文献［16］的优化初始聚类中心的K-means 聚类算法相比，本文算法只在Pima Indians Diabetes 和Haberman 这2 个数据集上的运行时间较快，但是本文算法不需要选择任何参数。总体时间分析显示，本文算法和文献［16］算法的时间性能差别不大，不如传统K-means 快速，但优于文献［11，13，15］的算法。

图1(a)～图1(d)分别是各算法的聚类准确率、聚类结果的Rand Index 参数、Jaccard 系数以及Adjusted Rand Index 参数的比较。

图1 UCI 数据集的聚类结果

由图1(a)关于聚类准确率的比较可见，本文算法的聚类准确率在各个数据集上都最优，特别是Iris和Soybean-small 2 个数据集上，本文算法的聚类准确率接近90%。图1(b)关于各算法在10 个UCI 机器学习数据库数据集上的Rand 指数可见，本文采用样本空间分布紧密度启发的优初始聚类中心Kmeans 算法在9 个数据上取得了最好的实验结果;在Iris 数据集上，本文算法的性能位居第二，不如文献［16］优化初始聚类中心的K-means 算法的Rand指数，但优于其他优化初始聚类中心K-means 算法。图1(c)关于各算法聚类结果的Jaccard 系数比较可见，本文算法在各个数据集上都最优。图1(d)关于最有效的聚类结果评价指标Adjusted Rand Index 的比较显示，本文算法具有最好的聚类效果。

以上结果表明，相比于其他优化初始聚类中心的K-means 算法的聚类结果严重依赖参数选择的缺陷，本文算法在不依赖于任何参数调整的条件下，可取得较好的聚类效果，并且聚类结果比较稳定。

4.2.2 人工模拟数据集的聚类结果分析

在人工模拟数据集上分别运行传统K-means 算法、文献［11，13，15，16］算法和本文算法，所得聚类误差平方和如表5 所示;各算法的聚类时间如表6所示。表5 的聚类误差平方和比较可见，文献［13］算法的聚类误差平方和最小(优)，本文算法与文献［15，16］的聚类误差平方和相同，优于传统Kmeans 算法的聚类误差平方和，以及文献［11］的聚类误差平方和。表6 各算法聚类时间的比较显示，K-means 算法运行速度最快，文献［15］算法需要的聚类时间最长，本文算法的聚类时间和文献［13，16］的聚类时间基本持平，都优于文献［11］的优化Kmeans 聚类算法。从聚类时间比较可见，本文算法是一种快速的K-means 聚类算法。

表5 人工模拟数据集的聚类误差平方和比较

表6 人工模拟数据集的聚类时间比较 s

图2(a)～图2(d)分别展示了各聚类算法的聚类准确率、聚类结果的Rand Index 参数、Jaccard 系数以及Adjusted Rand Index 参数。

图2(a)关于各算法聚类准确率的比较显示，本文算法和文献［15-16］算法的聚类准确率相同，都高于文献［11，13］的优化K-means 聚类算法，以及传统K-means 算法;另外，图2(a)的实验结果显示Kmeans 算法的聚类准确率最差。图2(b)～图2(d)关于聚类结果的外部评价参数Rand 参数、Jaccard 系数、Adjusted Rand Index 参数的比较显示，本文算法和文献［15-16］达到了同样好的聚类效果，都优于文献［11，13］的算法和传统K-means 算法;另外，图2的结果比较还揭示传统K-means 算法的聚类效果最差。

图2 人工模拟数据集的聚类结果

以上关于人工模拟数据集的实验结果分析表明，本文基于样本分布紧密度的最小方差优化初始聚类中心的K-means 算法在含有不同比例噪声的人工模拟数据集上都取得了很好的聚类效果，聚类准确率高且聚类结果稳定。另外，本文算法的聚类结果不依赖于任何参数调整，而文献［11，13，15］的聚类算法如果参数选择不合适，聚类结果会变得非常差。

5 结束语

针对传统K-means 算法初始聚类中心随机选取带来的聚类结果不稳定，以及现有优化初始聚类中心的K-means 算法的参数选取较多，聚类结果严重依赖于参数选择的问题，本文利用类簇中心的样本方差最小、具有最高紧密度原理，提出了最小方差优化初始聚类中心的K-means 聚类算法。UCI 机器学习数据库数据集以及带有同比例噪音的人工模拟数据集的仿真实验表明，本文算法与传统K-means 算法以及现有优化初始聚类中心的K-means 算法相比，不仅提高了聚类准确率、聚类结果稳定，而且对噪音数据有较好的免疫性，能客观地呈现出原始样本的分布状况。

［1］Han Jiawei，Kamber M.Data Mining:Concepts and Techniques［M］.2nd ed.Beijing，China:China Machine Press，2011.

［2］孙吉贵，刘 杰，赵连宇.聚类算法研究［J］.软件学报，2008，19(1):48-61.

［3］Pena J M，Lozano J A，Larranaga P.An Empirical Comparison of Four Initialization Methods for the KMeans Algorithm［J］.Pattern Recognition Letters，1999，20(10):1027-1040.

［4］Vance F.Clustering and the Continuous K-Means Algorithm［J］.Los Alamos Science，1994，22:138-134.

［5］Jain A K，Murty M N，Flynn P J.Data Clustering:A Review［J］.ACM Computing Survey，1999，31 (3):264-323.

［6］Kaufman L，Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis［M］.New York，USA:John Wiley ＆ Sons，Inc.，1990.

［7］Dhillon I S，Guan Yuqiang，Kogan J.Refining Clusters in High Dimensional Text Data［C］//Proceedings of the 2nd SIAM Workshop on Clustering High Dimensional Data.Arlington，USA:［s.n.］，2002:59-66.

［8］Khan S S，Ahmad A.Cluster Center Initialization for Kmeans Clustering［J］.Pattern Recognition Letters，2004，25(11):1293-1302.

［9］Deelers S，Auwatanamongkol S.Enhancing K-means Algorithm with Initial Cluster Centers Derived from Data Partitioning Along the Data Axis with the Highest Variance［J］.Proceedings of World Academy of Science，Engineering and Technology，2007，26:323-328.

［10］钱 线，黄萱菁，吴立德.初始化K-means 的谱方法［J］.自动化学报，2007，33(4):342-346.

［11］袁 方，周志勇，宋 鑫.初始聚类中心优化的Kmeans 算法［J］.计算机工程，2007，33(3):65-66.

［12］赖玉霞，刘建平.K-means 算法的初始聚类中心的优化［J］.计算机工程与应用，2008，44(10):147-149.

［13］王塞芳，戴 芳，王万斌，等.基于初始聚类中心优化的K-均值算法［J］.计算机工程与科学，2010，32(10):105-107.

［14］韩凌波，王 强，蒋正峰，等.一种改进的K-means 初始聚类中心选取算法［J］.计算机工程与应用，2010，46(17):150-152.

［15］汪 中，刘贵全，陈恩红.一种优化初始中心点的Kmeans 算法［J］.模式识别与人工智能，2009，22(2):299-304.

［16］谢娟英，郭文娟，谢维信，等.基于样本空间分布密度的初始聚类中心优化K-均值算法［J］.计算机应用研究，2012，29(3):888-892.

［17］谢娟英，郭文娟，谢维信，等.基于密度RPCL 的Kmeans 算法［J］.西北大学学报，2012，32(3):646-650.

［18］米 源，杨 燕，李天瑞.基于密度网格的数据流聚类算法［J］.计算机科学，2011，38(12):178-181.

［19］盛 骤，谢式千，潘承毅，等.概率论与数理统计［M］.2 版.北京:高等教育出版社，1997.

［20］张惟皎，刘春煌，李芳玉.聚类质量的评价方法［J］.计算机工程，2005，31(20):10-12.

［21］于 剑，程乾生.模糊聚类方法中的最佳聚类数的搜索范围［J］.中国科学:E 辑，2002，32(2):274-280.

［22］杨 燕，靳 蕃，Kamel M.聚类有效性评价综述［J］.计算机应用研究，2008，41(6):1631-1632.

［23］Hubert L，Arabie P.Comparing Partitions［J］.Journal of Classification，1985，2:193-218.

［24］Vinh N X，Epps J，Nailey J.Information Theoretic Measures for Clustering Comparison:Is a Correction for Chance Necessary?［C］//Proceedings of the 26th International Conference on Machine Learning.Montreal，Canada:［s.n.］，2009:1073-1080.

［25］Frank A，Asuncion A.UCI Machine Learning Repository［D］.Irvine，USA:School of Information and Computer Science，University of California，2010.