基于K—means的最佳聚类数确定方法研究

李红岩　胡林林　王江波　周红芳

摘要：确定数据集的最佳聚类数是聚类研究中的一个重要难题。为了更有效地确定数据集的最佳聚类数，该文提出了通过改进K-means算法并结合一个不依赖于具体算法的有效性指标[Q（c）]对数据集的最佳聚类数进行确定的方法。理论分析和实验结果证明了该方法具有良好的性能和有效性。

关键词：K-means；最佳聚类数；聚类有效性指标；聚类

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2014）01-0110-05

传统的获取最佳聚类数的算法一般是采用的是基于一种迭代的trial-and-error过程[1]，来获取数据集的最佳聚类数目。由于k-means算法适用于大型数据集的处理，且其效率比较高，特别是当数据集中的数据对象分布呈现类内团聚状时，所得到的聚类结果往往是比较好的。在实际中，由于用户缺乏丰富聚类分析的经验，所以能够准确地确定数据集的聚类数k的值是一个非常困难的问题[2]，这样就大大限制的该算法应用，而且确定的k值也往往不能保证是合适的，就需要结合一些有效性指标来确定其最佳聚类数，目前已经提出了一些检验聚类有效性的指标，主要代表有[Vxie]指标[3]、[Vwsj]指标[1]等。由于这些指标都是基于其他算法提出的，在k-means算法运用往往得不到比较理想的结果。鉴于此种情况，该文在传统的k-means算法基础上，给定一个聚类数目k的范围，然后再引入一个不依赖于具体算法的有效性指标，把两者结合在一起来进行最佳聚类数的判定。实验结果和理论分析都表明，该文提出的算法具有良好的性能与可行性。

1 K-means算法

1.1 K-means算法介绍

传统的K-means算法需要用户必须事先给定聚类个数k，并且它能自动地选取k个初始聚类中心，并按最小距离原则将数据对象指派到离其最近的类，然后不停地获取新的聚类质心并不断调整各个数据对象所属的类别，最终达到的结果是各个数据对象到其所属聚类中心的距离平方之和是最小的。K-means算法主要步骤[4]如下：

输入：数据集和该数据集的聚类个数k；

输出：使得某个准则函数最小时的k个类情况。

1）选择k个数据对象作为初始质心；

2）Repeat

3）计算数据对象与各个类的质心的距离，将对象划分到距离其最近的类，形成k个类；

4）重新计算每个类的质心点；

5）until 质心点不再发生变化。

1.2 K-means算法优缺点

K-means算法对大型数据集的处理是具有较高的效率[5]和伸缩性，该算法的时间复杂度为[O（nkt）]，其中n为数据集数据成员的个数，k是聚类个数，t是迭代次数。算法主要缺点是必须要求先给定数据集的聚类个数k，不准确的k就会导致聚类的效果[5]。而且对于结构比较复杂的数据集，聚类结果容易受到聚类质心的影响，最終导致聚类效果不理想。

2 聚类有效性指标

为了能够更好的反映聚类效果，一般是采用类内紧凑度和类间分离度进行衡量，该文在此引用一个不依赖于某些具体算法的有效性指标[Q（C）]来评估聚类的效果。该有效性指标主要是通过衡量数据集中的类内数据对象紧凑度和类间分离度 [6]。下面就大概介绍一下所采用的有效性指标。

2.1 聚类有效性指标

假设给定数据集DB，其中的一个聚类划分为[Ck={C1，C2，...，Ck}]，在该指标中用[Scat（Ck）]衡量[Ck]的类内紧凑度，[Sep（Ck）]衡量对应[Ck]的类间分离度。[Scat（Ck）]的原理是一个类中的任意两个数据对象之间的距离的平方和，其具体定义如下：

[Scat（Ck）=i=1kX，Y∈CiX-Y2] （1）

其中，X，Y是类[Ci]中的任意两个数据对象，k是此时数据集DB被划分的聚类个数。而[Sep（Ck）]则是将数据类看作是一个比较大的“数据对象”， “数据对象”之间的“距离”是通过类与类之间的点对的平均距离来获取。这样，它们在度量上就保持了一致性[6]。

[Sep（Ck）=i=1kj=1，j≠ik1Ci.CjX∈Ci，Y∈CjX-Y2] （2）

其中，X，Y分别属于类[Ci]，[Cj]中的数据对象，k为此时数据集DB被划分的聚类个数。代入欧式距离公式再做简单的变换，[Sep（Ck）]和[Scat（Ck）]可分别表示为：

[Scat（Ck）=2i=1kCiSSi-LSi] （3）

[Sep（Ck）=2k-1i=1kSSiCi-i=1kLSiCi2+i=1kLSi2Ci2] （4）

其中，[SSi=j=1Cix2j]，[LSi=j=1Cixj]，k表示数据集DB被划分的聚类个数，[xj]表示类[Ci]中的数据对象，[Ci]表示类[Ci]中数据对象的个数。我们可以得到：[Scat（C）]的值越小，说明类内数据对象越紧凑；[Sep（C）]越大，说明类与类间隔越大。一般采用式5来平衡[Sep（C）]和[Scat（C）]之间的差异：

[Q（C）=Scat（C）+β.Sep（C）] （5）

其中，[β]为组合参数，用来平衡[Sep（C）]和[Scat（C）]在取值范围上存在的差异。该文假设把数据集DB的聚类划分个数C看作是一个变量，其聚类变量C的范围为[{C1，C2，....，Cn}]，根据理论分析，我们可以假定[β]为1[7]。

由参考文献[6]可知，在给定的数据集DB中，[Sep（C）]和[Scat（C）]具有相同的值域范围，在初始状态中，即是当其聚类个数为n时，由公式（1）可知，[Scat（Cn）]为0，而此时设：

[Sep（Cn）=2（n.x∈DBx2-（x∈DBx）2）=M] （6）

因为[Scat（C）]是单调递增函数，而[Sep（C）]为单调递减函数[6]。当聚类数k为1时，可以得到[Sep（C1）]=0，而此时[Scat（C1）]=M。所以算法采用的有效性指标函数[Q（C）]可表示为：

[Q（C）=1M（Scat（C）+Sep（C））] （7）

2.2最佳聚类数的确定

有效性指标函数[Q（C）]是反映整个聚类过程中的聚类效果，当类内紧凑度和类间分离度达到一个平衡点时，此时对应的是最佳聚类划分[1]，有效性指标函数[Q（C）]在数值上反应为取得最小值时。由此可得，有效性指标值越小，则数据集的聚类效果就越好，该文认为聚类有效性指标函数[Q（C）]在取得最小值时所对应的聚类划分则是最佳的，论文中利用公式（8）来获得数据集中的最佳的聚類划分。

[C*=argminCk∈{C1，C2，...，Cn}Q（Ck）] （8）

数据集中往往存在噪声点或者孤立点等异常点，由于它们对聚类结果影响，由上述过程所得出的聚类数并不一定是最佳的，所以本文采用一直基于MDL剪枝算法[8]来去除异常点，利用公式（9）获得最佳聚类数。该公式可以被认为是对异常点进行处理的过程。

[kopt=β（C*）] （9）

在以上公式中，[C*]是表示聚类有效性指标函数[Q（C）]的值达到最小时所对应的聚类划分个数，[kopt]表示获得的最佳聚类划分个数。

2.3 异常点的消除过程

由于数据集中往往存在噪声点或孤立点等异常点，由于它们对聚类结果的影响，所以单独利用有效性指标函数获取的聚类个数为最佳聚类数[k*]的结论并不成立。因为异常类也是聚类划分过程的组成部分，但这些类所包含的数据对象往往比较少[8]。根据参考文献[6][7]和[8]可知，MDL算法的基本原理是对所使用的数据进行统一编码，进而选择具有最短编码长度的编码方案。在本文所提出的算法中，所使用的数据是某一时刻聚类划分中的各个类所包含的数据对象的个数。该文采用基于MDL剪枝的算法来对数据集中的异常点进行去除。大概过程如下：

令[C*={C*1，C*2，......C*k}]，其中[C*i]为类[C*i]包含的数据点的个数。首先把[C*i]按从大到小次序进行排序，此时产生新的序列[C1，C2，.....Ck]，然后将这个新序列以 [Cm] （1

[CL（m）=log2（μSL（m））+1≤j

其中，[μSL（m）=1≤j

通常认为聚类个数比较少的类为异常数据点所在的类，在本算法中，也即是[SR（m）]中所包含的类，在此认为最佳聚类数[kopt]为m。

3 最佳聚类数确定算法

本文中提出了一个算法COKS，为了在该算法中更有效性地利用k-means算法，特对k-means算法的缺点进行必要的改进，使该算法更能准确地对数据集进行聚类分析。首先要确定聚类数k的搜索范围。

3.1 聚类数K搜索范围的确定

对于k-means算法中的聚类数k的范围的确定，由于本算法所采用的聚类有效性指标需要得到在聚类数为1的情况下的[Sep（C1）]和[Scat（C1）]的值，所以，在本文中，设定其的最小聚类数[kmin]为1。至于最大聚类数[kmax]，根据大多数研究者所得出的经验[9]，最佳聚类数[kopt]应是[kopt≤n]，其中n为数据集中的数据对象的个数。所以在此取最大聚类数[kmax=n]。所以，根据以上分析可以得出本算法中的聚类数k的搜索范围为[[kmin]，[kmax]]。

3.2 最佳聚类数确定算法（COKS）

算法COKS主要原理是利用改进的k-means算法并结合第2节所介绍的不依赖于具体算法的聚类有效性指标，进而提出一种获取最佳聚类划分个数的聚类算法（COKS）。算法主要步骤归纳如下：

输入：数据集和数据集中数据对象的个数n；

输出：有效性指标值及所对应的聚类数和最佳聚类数。

1）选择聚类数的搜索范围[[kmin]，[kmax]]；

2）For k = [kmin] to [kmax]

a）调用K-means算法进行划分；

b）根据式（7）计算此时聚类划分的有效性指标函数[Q（C）]的值；

c）把获取的有效性指标值和所对应的聚类划分个数保存一个数组A中；

3）根据式（8）获取数组A中最小的聚类指标值以及所对应的聚类划分；

4）对所步骤3得到的聚类指标值以及对应的聚类划分，再按式（9）对其中异常点所组成的类进行剔除，最后得到的值则认为是最佳聚类个数[kopt]。

4 实验验证与分析

为了验证COKS算法的有效性以及性能，该文选择4个数据集并分成两组进行实验。在较多的聚类有效性指标中，该文选择了两种比较常用的其具有代表的有效性指标[Vxie][3]和[Vwsj][1]作为对比对象。由于这两种指标是基于FCM聚类算法提出的，所以，该文选择FCM作为聚类对比算法。其中，[Vxie]是第一个提出并运用“紧凑度”和“分离度”的指标，而[Vwsj]则是改进了线性组合，可以更为有效地处理包含有重叠的类和异常类的数据集。

4.1实验中的数据集

1） 人工数据集。在本实验中，采用的两个人工生成的数据集，其代号分别为数据集DB1和DB2。其中数据集DB1是由中心数据点分别为（10，10），（40，40）的二维高斯分布数据对象组成，其中数据集中以（10，10）为类的样本个数有500个，而以（40，40）为类的也有500个数据，该数据集的主要特征为两个聚类的类中心点不同，则两个类之间属性差别比较大。而数据集DB2则是一个二维的有三个类别的人工合成数据集，具有松散的、轻微重叠和带有少量异常点的聚类结构。

2） 标准数据集。本实验还采用了2个UCI的真实标准数据集，其数据集代号分别为DB3和DB4，名称分别是IRIS和Wiconsin breast cancer。所采用的4个数据集的属性以及其参数如表1所示。

表1 测试数据集的属性表

[数据集代号＼&数据集名称＼&数据集大小＼&数据集维数＼&真实聚类数＼&DB1＼&人工合成＼&1000＼&2＼&2＼&DB2＼&人工合成＼&1600＼&2＼&3＼&DB3＼&IRIS＼&150＼&4＼&3＼&DB4＼&Wiconsin breast cancer＼&699＼&9＼&2＼&]

4.2实验结果

实验主要分为两部分，第一部门主要是验证算法COKS的性能。把实验中所采用的4个数据集分别在COKS算法运行，所得到的有效性指标值与聚类划分个数如图1所示。

（a）DB1， [kopt]=2 （b） DB2， [kopt]=3

（c） DB3， [kopt]=3 （d） DB4， [kopt]=2

圖1 数据集聚类结果图

由图1可知。由于数据集中的数据对象的分布以及几何结构各不同，算法COKS对每个数据集的处理效果也有所不同。由于数据集DB1在合成过程中，保持了类与类之间具有较大的差异性，并且数据对象分布比较集中、其几何结构也比较标准，所获取的有效性指标值能够更好地反应出最佳聚类划分情况，由图1（a）所示，在聚类个数为2时所对应的有效性指标值与其他值差别比较明显，而且其有效性指标值最小。数据集DB2，由于其中存在异常点和重叠点，获取的指标值差别不大，当聚类数为15以上时，指标值逐渐趋于平衡，如图1（b）所示。由于数据集DB3中的数据对象个数比较少，而且包含两个重叠的簇[11]，如图1（c）所示，COKS算法能够比较正确且有效地区分重叠的类。图1（d）显示，对于数据集DB4，当聚类个数由3降到2时，其有效性指标值存在很小的差异，但COKS算法也能获取最佳的数据值。总之，算法COKS能够正确处理待测数据集并能获得其数据集的最佳聚类数。

第二部分主要是验证算法COKS的有效性。为了说明该算法在对数据集的最佳聚类数的确定具有更好的有效性，论文采用参考文献[1][3]中所述的基于FCM算法的有效性指标[Vxie]和[Vwsj]与指标[Q（C）]对比，其设置FCM模糊因子m为2。不同算法所获得的最佳聚类数情况如表2所示。

在本次实验中，根据3.1节所述，我们把FCM算法中的聚类个数k的范围设置为[1，12]，这样可以快速提高FCM的效率。为了使实验结果的准确性更高，把4个数据集在各个算法上分别运行多次，将聚类个数出现次数最多的聚类结果作为最终聚类划分数，这样可以减少由于其他因素对聚类结果造成的误差。由表2可知，算法COKS能够正确处理和获得数据集的最佳聚类数，同其它算法相比，其准确率比较高。

在实验中，因为每个数据集要在每个算法运行多次。我们取这些时间的平均值则所用的时间如表3所示。

表3 不同算法运行时间

[数据集＼&运行时间（秒）＼&FCM（[Vxie]）＼&FCM（[Vwsj]）＼&COKS＼&DB1＼&0.9＼&0.8＼&0.9＼&DB2＼&0.5＼&0.6＼&0.4＼&DB3＼&0.6＼&0.5＼&0.6＼&DB4＼&2.1＼&2.4＼&1.2＼&]

由表3可知，数据集结构比较标准、且分布比较集中，三个聚类算法所用时间相当，而当数据集的维度比较高时，可以得出该算法所处理的时间比较少，效率比较高。同其它聚类算法相比，该算法的时间效率较高。总之，算法COKS具有较高的准确率和时间效率。

5 结束语

需要用户根据先验知识提供聚类划分个数K，但在具体应用中，聚类个数k往往是事先无法准确确定，这就限制传统K-means算法的使用。该文采用了基于数据集的几何结构而提出了有效性指标函数，并和K-means算法结合在一起使用，获取数据集的最佳聚类个数。理论研究和实验结果表明本文所提出的COKS算法具有比较好的性能与有效性。

参考文献：

[1] Sun H， Wang S， Jiang Q. FCM-Based model selection algorithms for determining the number of cluster. Pattern Recognition， 2004，37（10）：2027-2037.

[2] 周世兵，徐振源，唐旭清.新的K-均值算法最佳聚类数确定方法[J].计算机工程与应用， 2010， 46（16）：27-31.

[3] Xie X， Beni G. A validity measure for fuzzy clustering. IEEE Trans， on Pattern Analysis and Machine Intelligence， 1991，13（8）：841-847.

[4] 孫吉贵，刘杰，赵连宇.聚类算法研究[J].软件学报，2008，19（1）：48-61.

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

[6] 陈黎飞，姜青山，王声瑞. 基于层次划分的最佳聚类数确定方法[J].软件学报， 2008，19（1）：62-72.

[7] Foss A， Zaiane OR. A parameterless method for efficiently discovering clusters of arbitrary shape in large datasets. In： Kumar V， Tsumoto S， eds. Proc. of the ICDM， Los Alamitos： IEEE Computer Society Press， 2002.179-186.

[8] Agrawal R， Gehrke J， Gunopulos D， Raghavan P. Automate subspace clustering of high dimensional data. Data Mining and Knowledge Discovery， 2005， 11（1）：5-33.

[9] 于剑，程乾生.模糊聚类方法中的最佳聚类数的搜索范围[J]，中国科学（E辑）， 2002，32（2）：274-280.

[10] Hong Z， Jiang Q， Dong H， Wang S. A new cluster validity index for fuzzy clustering. Computer Science， 2004，31（10）：121-125.

[11] Zhang T， Ramakrishnan R， Livny M. BIRCH： An efficient data clustering method for very large database. In： Jagadish HV， Mumick IS， eds. Proc. of the ACM-SIGMOD. New York： ACM Press， 1996.103-114.

[12] Brecheisen S， Kriegel HP， Pfeifle M. Multi-Step density-based clustering. Knowledge and Information Systems， 2006， 9（3）：284-308.

[13] Sudipio Guha， Rajeev Rastogi， Kyuseok Shim. CURE： an efficient clustering algorithm for large database [J]. Information Systems， 2001， 26（1）：35-58.