基于密度的最佳聚类数确定方法

1、基于密度的最佳聚类数确定方法    关键字聚类评估，聚类数，聚类有效性指标 0 引言 聚类是数据挖掘研究中重要的分析手段，其目的是将数据集中对象聚集成类，使得同一类中的对象是相似的，而不同类中的对象是不同的。迄今研究者已经提出了为数众多的聚类算法，并已经在商务智能、图形分析、生物信息等领域得到了广泛应用。作为一种非监督学习的方法，对学习得到的聚类结果进行评估是非常有必要的。因为许多聚类算法需要用户给定数据集的聚类数量，而在实际应用中这通常是事先不知道的。确定数据集的聚类数问题目前仍是聚类分析研究中的基础性难题之一 12。 聚类评估用于评价聚类结果的质量，

2、这被认为是影响聚类分析成功与否的重要因素之一3。它在聚类分析过程中的位置如图1所示。聚类评估的一些重要问题包括确定数据集的聚类趋势、确定正确的类个数、将聚类分析结果与已知的客观结果比较等，本文主要研究其中的最佳聚类数的确定。 通常最佳聚类数的确定是通过以下计算过程来确定的。在给定的数据集上，通过使用不同的输入参数（如聚类数 ）运行特定的聚类算法，对数据集进行不同的划分，计算每种划分的聚类有效性指标，最后比较各个指标值的大小或变化情况，符合预定条件的指标值所对应的算法参数 被认为是最佳的聚类数 4。 迄今为止，已有各种类型的度量指标从不同角度来评估数据集划分的有效性，这些指标称为聚类有效性指标（

3、Clustering Validation Indices）。一般地，用于评估聚类的各方面的评估度量指标可分成以下两类5。 1）外部指标（External index）：指聚类分析的评价函数是针对基准问题的，其簇的个数及每个数据对象的正确分类均为已知。代表性外部指标有熵、纯度、F-measure等。 2）内部指标（Internal index）：指数据集结构未知的情况下，聚类结果的评价只依靠数据集自身的特征和量值。在这种情况下，聚类分析的度量追求两个目标：类内紧密度和类间分离度。这也是本文的主要研究领域，代表性内部指标有DB，CH，XB，SD等。 从其他不同角度，聚类有效性指标又可分为分割指标

4、与层次指标，模糊指标与非模糊指标，统计指标与几何指标。 用内部指标来评估聚类有效性，获取数据集最佳划分或最佳聚类数的过程一般分为以下4步6： 第一步：给出一系列用来对数据集进行聚类的聚类算法； 第二步：对于每一种聚类算法，分别使用不同的输入参数以获得不同的聚类结果； 第三步：对于第二步中得到的不同聚类结果，计算其内部指标并得到相应的取值； 第四步：根据内部指标所要求的规则选择最佳分割或最佳聚类数。 1 常用聚类有效性指标 1.1 Davies-Bouldin 指标（DB）7 DB指标首先计算每个类中各点与类中心的平均距离，然后以此计算每个类与其他各类的相似度，并取最大值作为该类的相似度，最后，

5、DB指标由所有类的相似度平均得到。容易得出，DB越小表示类与类之间的相似度越低，从而对应越佳的聚类结果。 1.2 Calinski-Harabasz指标（CH）8 CH指标通过计算类中各点与类中心的距离平方和来度量类内的紧密度，通过计算各类中心点与数据集中心点距离平方和来度量数据集的分离度，CH指标由分离度与紧密度的比值得到。从而，CH越大代表着类自身越紧密，类与类之间越分散，即更优的聚类结果。 1.3 Xie-Beni指标（XB）9 XB指标使用最小的类与类中心距离平方来衡量类间分离度，使用类中各点与类中心的距离平方和来衡量类内紧密度。XB指标也是类内紧密度与类间分离度的比值。和CH指标一样

6、，XB就是在类内紧密度与类间分离度之间寻找一个平衡点，使其达到最小，从而得到最优的聚类结果。 1.4 SD指标10 SD有效性指标定义为 SD指标通过计算类中对象的标准差来衡量类内紧密度，通过计算类与类之间的距离来衡量类间分离度。其中 是加权项，可以平衡类内紧密度和类间分离度之间的相对重要性，在本文中， 取值为 。 、 分别是类 与数据集的标准偏差。 2 基于密度的聚类有效性指标（Density Based Index） 由于对于一个特定的聚类算法，不同的输入参数会导致不同的聚类划分。而对某一个特定的数据集而言，只有一个划分结果是最优的。此处的最优划分是指，相比其他划分，它和数据集原本的真实划

7、分是最接近的。 因此，本课题研究的目标是定义一个新的聚类有效性指标，用来评估不同聚类划分的质量。这个聚类有效性指标可以从数据集使用某一聚类算法得到的划分结果中，找出最符合真实情况的那一个划分，从而得到这一划分所需的输入参数，如聚类个数。        现有的聚类有效性指标大都是基于对象与中心之间的距离度量，使得其不能很好地捕捉类内部的对象分布情况，同时也忽略了类间的对象分布紧密程度。 由于聚类分析的目的是将数据集中对象聚集成类，使得同一类中的对象是相似的，而不同类中的对象是不同的。从数据几何分布的角度来看，聚类将使

8、得同一类空间里的对象分布较为密集，而类与类之间的空间对象分布较为稀疏，即可理解为同一类中对象密度比类间对象密度更大。使用基于密度的方法来评估聚类结果的有效性，是和聚类分析的本质相符合的。 给定一个 维数据集 ， 为一个数据对象， 为数据集 中数据对象的个数。一个硬划分聚类算法将 划分为 个子集的集合 ，子集 称为 的类。本文中用 表示数据集 中心点，用 表示类 中心点， 表示 中对象个数， 表示对象间距离。 定义1：类中心密度（cluster center density） 类中心密度是以类 中心点 为中心，给定半径范围 ，此类中所有到类中心点距离小于等于 的对象个数。 。 定义2：类半径（c

9、luster radius） 类半径是类中所有对象到类中心的距离的平均值。 定义3：类间中位点（medium point between clusters） 类间中位点是在以两类中心的连线上的一个点，使得中位点到两类中心的距离的比值等于两类半径的比值。如图2所示，数据集中存在类 、 、 三个类，其中类 的半径是类 、 的一半，则类 与类 的中位点 到类 中心 距离为到类 中心 距离的一半，而类 与类 的中位点 到类 中心 距离与到类 中心 距离相等。 定义4：类边缘密度（cluster boundary density） 类边缘密度是以类 中心点 与数据集中某一类 中心点 的中位点（mediu

10、m point）为中心，给定半径范围 ， 与 中所有到中位点距离小于等于 的对象个数的均值。 在本文中， 取值为 。 定义5：基于密度有效性指标（Density Based Index, DBI） 3 实验结果 为了说明新指标DBI的效果，我们测试了DBI在各种各样的数据下的表现，现仅以较具代表性的5组来做一个说明，其中包括了3组生成数据和2组实际数据。3组生成数据由混合高斯分布生成，而另外2组实际数据来源于UCI数据库。这5组数据的特征如表1所示。 由于数据集Iris和Satimage的维数都大于3维，在文中无法展示其结构。而人工数据集DS1、DS2、DS3的分布如图3所示。从图中可以看出，

11、DS1中存在5个分布较好的类和一些噪音，DS2中3个类之间存在着不均衡的分布，而DS3的5个类中存在着子簇群。 实验中， 使用CLUTO工具对数据集进行聚类，其中数据集DS2使用了Chameleon算法，其余数据集使用了Kmeans算法。因为DS2中存在着不均衡分布，Kmeans算法无法得到合适的聚类结果。实验中设置最小聚类数为2，最大聚类数为9，包括了5个数据集的最佳聚类数。各指标对5个数据集所选择的最佳聚类数如表2所示。 从实验结果可以看出，CH指标对数据集DS2选择了错误的聚类数，DB和SD在数据集DS3下没能选择正确的聚类数。对实际数据Iris，只有新指标DBI选择了正确聚类数3，而对

12、实际数据Satimage，所有的指标都没有选择正确的聚类数。在这组实验中，DBI的正确率最高，为80%，而其他4个指标中，最高为XB正确率60%，其他均只有40%。 4 结论与展望 现有的聚类算法通常都需要用户根据经验知识提供输入参数，如聚类数，但通常情况下这事先无法确定。使得在实际应用中，用户对于聚类分析的结果无法进行正确的选择。本文提出了一种新的确定最佳聚类数的有效性指标，该指标着重于分析簇的几何结构，从数据对象分布密度的角度来度量类内紧密度与类间分离度。该指标对噪声不敏感并且可以识别数据集中的子簇群，在实际数据和合成数据上的实验结果表明,新指标的性能优于广泛使用的其他指标，对于聚类分析的

13、实际应用提供了一定的参考。 参考文献 1 陈黎飞，姜青山，王声瑞，基于层次划分的最佳聚类数确定方法，软件学报，(19):1, 2008, pp.62-72. 2 杨燕，靳蕃，K. Mohamed，聚类有效性评价综述，计算机应用研究，(25):6, 2008, pp.1630-1632. 3A. K. Jain and R. C. Dubes, Algorithms for clustering data. Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 1988. 4 杨善林，李永森，胡笑旋，等，K-means算法中的k值优化问题研究，系统工

14、程理论与实践，2006(2):97-101. 5 P.N. Tan, M. Steinbach, and V. Kumar, Introduction to Data Mining. USA: Addison-Wesley Longman, Inc., 2005. 6 周世兵，徐振源，唐旭清，新的K-均值算法最佳聚类数确定方法，计算机工程与应用，46(16), 2010, pp.27-31. 7 D. Davies and D. Bouldin, “A cluster separation measure,” IEEE PAMI, vol. 1, no. 2, pp. 224227, 1979. 8 T. Calinski and J. Harabasz, “A dendrite method for cluster analysis,” Comm. in Statistics, vol. 3, no. 1, pp. 127, 1974. 9 X. L. Xie and G. Beni, “A validity measure for fuzzy clustering,” IEEE PAMI, vol. 13, no. 8, pp. 841847, 1991.    &