摘 要 聚类分析是数据挖掘中的一个重要研究领域。K-means 算法对随机选取K个初始点作为初始值是很敏感的，聚类的质量依赖于初始值。在分析聚类结果对初值依赖性的基础上，对初值选取方法进行了分析和研究，并提出了一种有效的改进方法，通过试验证明了改进算法的有效性。

关键词 数据挖掘；聚类；K-means；初值

1 引言

数据挖掘(Data Mining)，又称为数据库中的知识发现(简称 KDD)，是从大量数据中提取可信的、新颖的、有效的并能被人们理解的模式的处理过程。它是一门新兴的交叉学科，汇集了来自机器学习、模式识别、数据库、统计学、人工智能等各领域的研究成果。聚类是数据挖掘中的一种主要技术，是把一组个体按照相似性归成若干类别即“物以类聚”。它的目的是使得属于同一类别的个体之间的距离尽可能的小而不同类别上的个体间的距离尽可能大。

2 聚类K-means算法简介

K-means 算法属于数据挖掘聚类分析方法中一种基本的且应用最广泛的划分算法，它是一种已知聚类类别数的聚类算法。指定类别数为K，对样本集合进行聚类，聚类的结果由K 个聚类中心来表达，基于给定的聚类目标函数(或者说是聚类效果判别准则)，算法采用迭代更新的方法，每一次迭代过程都是向目标函数值减小的方向进行，最终的聚类结果使目标函数值取得极小值，达到较优的聚类效果。根据聚类结果的表达方式又可以分为硬 K-means(HCM)算法、模糊 K-means 算法(FCM)和概率 K-means 算法(PCM)。

该算法的基本框架如下：

(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，如果满足(1)式：

则X_i∈Wk；

(3)计算K个新的聚类中心

(4)判断：若Zj(I+1)≠Zj(I)，j=1，2，3，…，K，则I=I+1，返回(2)，否则该算法结束。

从上面的算法思想和算法框架，我们不难看出，K个初始聚类中心点的选取对聚类结果具有较大的影响，因为在该算法中是随机地选取任意K个点作为初始聚类中心。如果有先验知识，可以选取具有代表性的点作为初始中心点。

3 聚类K-means算法的初值依赖性

3.1 初值依赖性分析

无论是原始K-means算法还是使用了聚类准则函数的K-means算法，都具有一个共同的特点：在算法的初始阶段都要选取K个点作为初始聚类中心，然后在此基础上进行反复迭代。选取的点不同，聚类结果可能就有所不同，所以这个算法的聚类结果对初值的依赖性很强，这样的依赖性导致聚类结果的不稳定。当然也有可能碰到最极端的初值选取情况，这种情况使得算法运行时间加长，聚类准则函数难以收敛，聚类结果更加难以预测。

3.2 实验结论

为了证明初值选取对聚类结果的影响，制作了一个测试模块。运用算法测试模块得到的结果分别如图1和2所示，图中圆圈代表的是初始的聚类中心即初值，zi(i=1，2，3，4，5)表示聚类完成后的聚类中心，wi(i=1，2，3，4，5)表示每个簇。每一个数据对象被分配给离它最近的聚类中心所在的类。我们可以很清楚地看到初始值的选取对聚类结果的影响，反过来也可以说是聚类结果对初始聚类中心的依赖。

显然，图2中由于初始聚类中心点的选择比较好，因此最后的聚类结果较为理想。因此，随机选择初始聚类中心使得聚类很难得到一个稳定的聚类结果。针对聚类初值选择这一问题，有文献考虑了冗余类中心初始化方法，该方法扩大了解空间的搜索范围，减少了某些极值点附近无初值的机会，初始聚类中心在数据空间中分布较广，具有多样性。具体方法为采用适当准则逐步减小类的个数，直到指定达到指定的k 的数目，这样得到的聚类结果受随机选择初始聚类中心的影响较小。初始的聚类中心选的越多，聚类结果受初值的影响就越小。但在这个算法中，需要确定一个合并参数d，即对类间距小于d的类就进行合并。实际上，对这个合并参数d很难确定，而这个参数的选择又直接影响着聚类结果。该改进算法使得在增加聚类中心的同时也增加了算法中的计算量和聚类结果的不确定性。

图1 测试结果1

图2 测试结果2

因此，初始聚类中心的选取方法是很多的，可以随机产生，凭经验知识获取，采用密度方法等等。无论聚类算法采用哪一种选取方法，我们都希望聚类中心越稳定越好，需要先验知识越少越好，需要确定的参数越少越好，而且希望算法能够产生一个较稳定的聚类结果，而不是对初始聚类中心非常敏感，不同的初始聚类中心产生不同的聚类结果。在传统的 K-means 算法中，聚类结果对初始聚类中心有较强的依赖性，即不同的初始聚类中心会产生不同的聚类结果，因此聚类结果的有效性直接依赖于初始聚类中心的选择。

4 有关初值选取的现有方法

目前针对初值选取的问题，主要概括有以下几种方法：

(1)任意选取K个样本数据作为初始聚类中心。

(2)依据经验选取有代表性的点作为初始聚类中心。根据个体性质，观察数据结构，筛选出比较合适的代表点。

(3)把全部混合样本直观地分成k 类，计算各类均值作为初始聚类中心。(4)通过“密度法”选择代表点作为初始聚类中心。所谓密度是指具有统计性质的样本密度。例如，以每个样本为中心，以某个给定正数d1为半径，在特征空间里划出一个球形邻域，计算落入该邻域里的样本数目作为该点的密度。在计算完每个数据对象的密度后，首先选取密度最大的样本作为第一个初始聚类中心，它对应着样本分布密度的最高峰值点；然后，给定一个正数d2，在离开第一个初始聚类中心距离d2 之外选择次大密度点作为第2个代表点，这样可以避免代表点过分集中；依此类推，可以选出k 个初始聚类中心。

(5)由(k-1)类聚类问题解出k类问题的代表点。例如：先把全部样本看成一个类，样本总均值点就是第 1 类的初始聚类中心；然后，由第1类的初始聚类中心和离它最远的一个样本作为两类的初始聚类中心；依此类推，由(k-1)类的代表点和离它们最远的一个数据对象作为k类问题的初始聚类中心。

(6)按最大最小距离聚类法中寻找聚类中心的方法确定初始聚类中心。

(7)进行多次初值选择、聚类，找出一组最优的聚类结果。

(8)采用遗传算法或者免疫规划方法进行混合聚类。

除了以上的选取方法以外，另外还有一种扩展的聚类中心选取方法。这种选取方法与上述方法有一个很大的区别，即由原来的点延伸到一条线段，这种选取方法在类之间有干扰点时效果较好。由图3我们可以发现，如果聚类中心选择如图所示的c1和c2，则w1，w2两个类都可能被拆分，而且p点从理论上讲应该划分到w2类中，因为pc1〉pc2，即p点距离簇2近，但实际上把p点划分到簇w1更合理，因为p到w1的距离较近。所以此时，选用 A1B1，A2B2则更合适，在此方法中p点是w1，w2两个类间的干扰点。

图3 带有干扰点P的聚类

综上所述，初始聚类中心的选取方法很多，无论聚类算法采用哪一种选取方法，都是为算法能够产生一个较稳定的聚类结果，而不依赖于初始聚类中心。

5 改进初值选取的K-means算法

从随机选择的初始聚类中心开始进行聚类是很难得到一个稳定的聚类结果，针对这个问题，对聚类中心的选取进行了改善，改善聚类算法中选择初值时候的依赖性，提高聚类结果的稳定性，并给出实验结果。

5.1 改进过程简要说明

采用K-means算法对原始数据集进行聚类输出K^/个聚类中心，这里K^/〉K，K是最终要确定的簇数目，然后考察各聚类中心之间的距离，合并聚类中心最为靠近的聚类数，直到聚类簇的数量减少到指定的K值为止。具体描述如下：

算法：基于改进选取初始聚类中心的K-means 算法；

输入：n个数据对象集合xi；

输出：k个聚类中心 Zj及k 个聚类数据对象集合 Cj；

Begin

Runmeans(K^/)；// 执行K-means算法，产生K^/个聚类中心；

Repeat

合并聚类中心中距离最近的点；

Until 聚类数减少到K； //合并K^/—K

End；

在该算法中，对于比较小的数据集，搜索初始聚类中心的过程数据量较少，迭代次数也很小，速度很快。对于数据集合非常大的情况，搜索初始聚类中心的过程所耗费的时间在整个算法中可以忽略不计，所需总的时间为O(nk^/d)。

5.2 实验结果

如表1所示为改进前后的簇中心及平均距离。

表1 改进前后参数对比

算法	簇中心坐标(七维)	各簇平均距离
改进前	簇1：(-0.52，-0.45，-0.31，-0.29，-1.23，-1.06，-0.62) 簇2：(0.49，0.41，0.56，0.32，0.73，0.59，0.24) 簇3：(0.09，0.09，0.25，-0.05，-0.14，-0.15，-0.32)	1.103 0.782 0.913
改进后	簇1：(-0.15，-0.20，-0.14，-0.14，-0.65，-0.58，-0.58) 簇2：(0.42，0.40，0.53，0.33，0.73，0.57，0.33) 簇3：(0.25，0.30，0.64，-0.06，0.09，0.08，-0.4)	1.07 0.776 0.690

对比实验主要考察算法改进前后产生聚类结果的准确性。实验中选取的数据集是我校学生的真实成绩。由表1我们可以看到改进后的算法明显优于改进前的，同样这也证明了改进后的算法是有效可用的。

6 结论

在K-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化，这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，所以对该问题的研究成为聚类K-means 算法的重点，初值选取的好坏直接关系到算法运行的结果。

参考文献

[1] 张云涛等.数据挖掘原理与技术.电子工业出版社，2004

[2] [加]Jiawei Han， Micheline Kamber.数据挖掘概念与技术[M]．范明，孟小峰，译.北京：机械工业出版社，2001

[3] 谭勇，荣秋生.一个基于K-Means的聚类算法的实现[J].湖北民族学院学报，2004.22(1)：69-71

[4] 范森淼，程晓青.数量关联规则发现中的聚类方法研究[J].计算机学报，2002.8，Vol.23，No.8：P866-871

[5] 王实．数据挖掘中的聚类算法[J]．计算机科学，2002，27(4)：42-45

[6] 荣秋生．基于DBSCAN聚类算法的研究与实现[J].计算机应用，2004，24(1)：45-47

[7] 孙孝萍.基于聚类分析的数据挖掘算法研究.硕士生论文，2002.4

[8] 数据挖掘讨论组，数据挖掘资料汇编.www.dmgroup.org.cn

[9] 郭军华.数据挖掘中聚类分析的研究.武汉理工大学硕士生论文，2003.12

[10] 郑洪英.数据挖掘聚类算法的分析和应用研究.重庆大学硕士生论文，2002.5

[11] 徐燕.对一个矢量量化聚类算法的改进及应用[J].华北电力大学学报，2001.28(3)：62-65