Kmeans算法最佳聚类数评价指标研究

郭靖+侯苏

摘要：聚类分析广泛应用于商务智能、图像模式识别、Web搜索、生物学等领域，是一种无指导的观察式学习。然而，绝大多数聚类分析算法都面临着一个非常棘手的问题——最佳聚类数的确定。Kmeans是典型的基于划分的聚类方法，它需要用户输入聚类数K，但这通常非常困难。聚类数的确定是决定聚类质量的关键因素。虽然有许多被用来估计最优聚类数的聚类评价指标，但对于不同的聚类算法，不同的评价指标效果差异很大。为确定针对Kmeans聚类算法效果最好的评价指标，采用4种典型的不同聚类结构特征的人工模拟数据以及来自UCI的真实数据集对7种评价指标的性能进行实验比较，结果表明CH指标和I指标在评估Kmeans算法的最佳聚类数时效果较好。

关键词关键词：聚类指标；Kmeans算法；聚类分析；聚类数

DOIDOI：10.11907/rjdk.171885

中图分类号：TP301

文献标识码：A文章编号文章编号：16727800（2017）011000504

0引言

聚类分析（Cluster Analysis）是一种无指导的观察式学习，其基本原理是根据样本自身属性，在没有任何模式可供参考或依循，即没有先验知识的情况下，用数学方法按照某种相似性或差异性指标，计算样本之间的相似度，并按这种相似度对样本进行聚类。近年来，随着聚类分析的逐渐成熟，产生了很多聚类算法。根据基本思想不同，大致可以将聚类算法分为6大类：基于层次的聚类算法（CURE、ROCK、CHAMELEON）、基于划分的聚类算法（Kmeans、Kmedoids、PCM）、基于密度的聚类算法（DBSCAN、OPTICS、FDC）、基于网格的聚类算法（STING、CLIQUE、OPTIGRID）、基于神经网络的聚类算法（自组织神经网络SOM）与基于统计学的聚类算法（COBWeb、CLASSIT、AutoClass）。Kmeans聚類算法是一种简洁、高效的基于划分的聚类算法[1]，它的伪代码如下所示：

2实验与比较分析

本文使用Kmeans算法将实验数据集划分为k个簇，并使用上述7种评价指标估计最优聚类数。实验采用4种典型的不同聚类结构特征的人工模拟数据集以及来自UCI[9]的真实数据集。k的取值范围为[2，kmax]，根据一般经验准则，k≤n，所以kmax=intn，其中，n是数据集的样本总数。并且，为使Kmeans算法拥有稳定的较好聚类结果，选择文献[10]中的方法选取初始聚类中心，具体方法如下：①首先选择距离全部样本中心最近的一个样本对象作为第1个初始聚类中心Z1；②当聚类数为2时，从剩余所有样本中选择距离Z1最远的样本对象作为第2个初始聚类中心Z2；③当聚类数为3时，计算剩余各样本与Z1、Z2之间的距离，并求出它们之中的最小值di，根据Dt=max{di}，选择第t个样本对象作为第3个初始聚类中心；④当聚类数为k并且k≤kmax时，针对已存在的k-1个初始聚类中心，计算剩余各样本到各聚类中心的距离dij，并计算出Dr=max{min{di1，di2，…，di（k-1）}}，选择第r个样本作为第k个初始聚类中心。

2.1人工模拟数据集实验

人工模拟数据集共有4个，包括简单的和复杂的聚类结构特征：相距较远的完全分离的聚类（特征A）、靠近的完全分离的聚类（特征B）、小的聚类靠近大的聚类（特征C），以及轻微重叠的聚类（特征D），详细信息如表1所示。图1给出了人工模拟数据集的二维平面。

表2给出了各种聚类评价指标得出最佳聚类数的结果，可以看出，CH指标最好，I指标次之，而其它几个指标的效果不尽如人意。对于相距较远的完全分离的聚类（特征A），所有指标都可以得到正确的聚类数，但只要有两个聚类靠得比较近时，XieBeni指标、DB指标、Dunn指标、BWP指标和Sil指标就不能得到最佳聚类数。

2.2UCI真实数据集实验

UCI数据集是著名的关于机器学习的真实数据集。此次实验的4组数据集都是来自UCI的常用数据集，分别是iris数据集、QualitativeBankruptcy（简称QB）数据集、seeds数据集和Vertebral Column（简称VC）数据集，详细信息如表3所示。

表4给出了真实数据集的实验结果，从中可以看到

CH指标和I指标效果较好，其它几个指标仅在聚类数为2时得到正确结果。真实数据集比人工模拟数据集的空间结构复杂得多，因此正确估计真实数据集的分类数是非常困难的。

3结语

通过对上述7种聚类质量评价指标的实验比较分析，可以看到XieBeni指标、DB指标、Dunn指标、BWP指标和Sil指标仅在评估相距较远且完全分离的聚类结构特征的最佳聚类数时有着较好效果，而对于其它聚类结构特征效果并不好。由于真实数据集聚类结构特征的复杂性，只有CH指标和I指标效果显著，XieBeni指标、DB指标、BWP指标和Sil指标由于自身的局限性，仅对聚类数为2的数据集效果较好。因此，在评估Kmeans算法的最佳聚类数时，CH指标和I指标是两个不错的选择。

参考文献参考文献：

[1]FAHIM A， SALEM A E， TORKEY F， et al. An efficient KMeans with good initial starting points[J]. Computer Sciences & Telecommunications，2009.

[2]CALINSKI R B， HARABASZ J. A dendrite method for cluster analysis[J].Communications in Statistics，1974，3（1）：127.endprint

[3]MAULIK U， BANDYOPADHYAY S. Performance evaluation of some clustering algorithms and validity indices[J]. Pattern Analysis and Machine Intelligence，2002（12）：16501654.

[4]XIE X L， BENI G. A validity measure for fuzzy clustering[J].Pattern Analysis and Machine Intelligence，1991（13）：841847.

[5]DAVIES D L， BOULDIN D W. A cluster separation measure[J]. Pattern Anal Machine Intell，1979 （4）：224227.

[6]DUNN J C. A fuzzy relative of the ISODATA process and its use in detecing compact wellseparated clusters[J].Journal Cybernetics，1973，3（3）：3257.

[7]ZHOU S B， ZHENYUAN X U. New method for determining optimal number of clusters in Kmeans clustering algorithm[J]. Journal of Computer Applications，2010，30（8）：19951998.

[8]DUDOIT S， FRIDLYAND J.A prediction based resampling method forestimating the number of clusters in a dataset[J].Genome Biology，2002，3（7）：121.

[9]BLAKE C L，MERZ C J.UCI repository of machine learning databases[EB/OL]. http：//archive.ics.uci.edu/ml/.

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

责任编辑（责任编辑：黄健）endprint