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

《基于密度的最佳聚类数确定方法l》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、基于密度的最佳聚类数确定方法l基于密度的最佳聚类数确定方法[摘要]确定数据集的正确聚类数目是聚类分析中的一个基础性难题。常用的聚类数确定方法通常依赖特定的聚类算法，且在数据集存在子簇群的情况下效果欠佳。本文提出一种新的最佳聚类数确定的指标，该指标着重于分析簇的几何结构，从数据对象分布密度的角度来度量类内紧密度与类间分离度。该指标对噪声不敏感并且可以识别数据集中的子簇群，在实际数据和合成数据上的实验结果表明,新指标的性能优于广泛使用的其他指标。[关键字]聚类评估，聚类数，聚类有效性指标0引言聚类是数据挖掘研究中重要的分析手段，其目的是将数据集中对象聚集成类，使得同一类中的对象是相似的，而不同类中

2、的对象是不同的。迄今研究者已经提出了为数众多的聚类算法，并已经在商务智能、图形分析、生物信息等领域得到了广泛应用。作为一种非监督学习的方法，对学习得到的聚类结果进行评估是非常有必要的。因为许多聚类算法需要用户给定数据集的聚类数量，而在实际应用中这通常是事先不知道的。确定数据集的聚类数问题目前仍是聚类分析研究中的基础性难题之一[1][2]。聚类评估用于评价聚类结果的质量，这被认为是影响聚类分析成功与否的重要因素之一[3]。它在聚类分析过程中的位置如图1所示。聚类评估的一些重要问题包括确定数据集的聚类趋势、确定正确的类个数、将聚类分析结果与已知的客观结果比较等，本文主要研究其中的最佳聚类数的确定。

3、通常最佳聚类数的确定是通过以下计算过程来确定的。在给定的数据集上，通过使用不同的输入参数（如聚类数）运行特定的聚类算法，对数据集进行不同的划分，计算每种划分的聚类有效性指标，最后比较各个指标值的大小或变化情况，符合预定条件的指标值所对应的算法参数被认为是最佳的聚类数[4]。迄今为止，已有各种类型的度量指标从不同角度来评估数据集划分的有效性，这些指标称为聚类有效性指标（ClusteringValidationIndices）。一般地，用于评估聚类的各方面的评估度量指标可分成以下两类[5]。1）外部指标（Externalindex）：指聚类分析的评价函数是针对基准问题的，其簇的个数及每个数据对象的

4、正确分类均为已知。代表性外部指标有熵、纯度、F-measure等。2）内部指标（Internalindex）：指数据集结构未知的情况下，聚类结果的评价只依靠数据集自身的特征和量值。在这种情况下，聚类分析的度量追求两个目标：类内紧密度和类间分离度。这也是本文的主要研究领域，代表性内部指标有DB，CH，XB，SD等。从其他不同角度，聚类有效性指标又可分为分割指标与层次指标，模糊指标与非模糊指标，统计指标与几何指标。用内部指标来评估聚类有效性，获取数据集最佳划分或最佳聚类数的过程一般分为以下4步[6]：第一步：给出一系列用来对数据集进行聚类的聚类算法；第二步：对于每一种聚类算法，分别使用不同的输入参

5、数以获得不同的聚类结果；第三步：对于第二步中得到的不同聚类结果，计算其内部指标并得到相应的取值；第四步：根据内部指标所要求的规则选择最佳分割或最佳聚类数。1常用聚类有效性指标1.1Davies-Bouldin指标（DB）[7]DB指标首先计算每个类中各点与类中心的平均距离，然后以此计算每个类与其他各类的相似度，并取最大值作为该类的相似度，最后，DB指标由所有类的相似度平均得到。容易得出，DB越小表示类与类之间的相似度越低，从而对应越佳的聚类结果。1.2Calinski-Harabasz指标（CH）[8]CH指标通过计算类中各点与类中心的距离平方和来度量类内的紧密度，通过计算各类中心点与数据集中

6、心点距离平方和来度量数据集的分离度，CH指标由分离度与紧密度的比值得到。从而，CH越大代表着类自身越紧密，类与类之间越分散，即更优的聚类结果。1.3Xie-Beni指标（XB）[9]XB指标使用最小的类与类中心距离平方来衡量类间分离度，使用类中各点与类中心的距离平方和来衡量类内紧密度。XB指标也是类内紧密度与类间分离度的比值。和CH指标一样，XB就是在类内紧密度与类间分离度之间寻找一个平衡点，使其达到最小，从而得到最优的聚类结果。1.4SD指标[10]SD有效性指标定义为SD指标通过计算类中对象的标准差来衡量类内紧密度，通过计算类与类之间的距离来衡量类间分离度。其中是加权项，可以平衡类内紧密度

7、和类间分离度之间的相对重要性，在本文中，取值为。、分别是类与数据集的标准偏差。2基于密度的聚类有效性指标（DensityBasedIndex）由于对于一个特定的聚类算法，不同的输入参数会导致不同的聚类划分。而对某一个特定的数据集而言，只有一个划分结果是最优的。此处的最优划分是指，相比其他划分，它和数据集原本的真实划分是最接近的。因此，本课题研究的目标是定义一个新的聚类有效性指标，用来评估不同聚类划