分布的自动阈值密度峰值聚类算法

彭启慧，宣士斌，高 卿

广西民族大学 信息科学与工程学院，南宁530006

聚类分析[1]是数据挖掘和机器学习中的一个基础研究内容。在过去的几十年中，研究人员已提出多种聚类算法。典型算法包括基于分区的K-means[2]和Kmedoids[3]、基于层次的CURE[4]和BIRCH[5]、基于密度的DBSCAN[6]和OPTICS[7]和基于网格的WaveCluster[8]和STING[9]，以及基于模型的统计聚类[10]和基于图论的谱聚类[11]。经典的聚类算法K-means是通过指定聚类中心，然后通过迭代的方式更新聚类中心，在具有凸球形结构的数据集上实现了良好的聚类结果，但由于每个点都被指派到距离其最近的聚类中心，所以导致它不能检测非球面类别的数据分布。虽然有DBSCAN可以对任意形状的分布进行聚类，并且具有很强的抗噪能力，但对于变密度簇和高维数据的聚类效果较差[12-14]，此外，选择半径和阈值也是DBSCAN的难题。Rodriguez和Laio[15]提出的DPC（Clustering by fast search and find of Density Peaks）根据局部密度和密度最近邻可以得到决策图，并根据决策图求得聚类中心。这种算法不仅高效，而且所依赖的参数只有截止距离这一个。虽然DPC算法在某些方面有着明显的优势，但它仍然存在如下的一些情况：

首先，局部密度和距离测量的定义简单[16-17]，因此，当处理具有多尺度，交叉缠绕，各种密度或高维度的复杂数据集时，DPC算法的聚类结果可能较差[18-21]。其次，依据决策图人工选择类中心点，带有较强的主观性[22-23]。第三，由于在大多数情况下每个属性的范围都是未知的，所以通常很难确定截断距离[24-25]。针对DPC存在的问题，研究人员提出了很多DPC的改进和优化方法。Xu等[26]提出用网格距离代替了欧式距离用于解决DPC对距离的测量定义过于简单，且需要计算所有数据点之间的距离这一计算量大的缺点。针对无法有效地对具有任意形状或多流形结构的数据进行分组，Du等[27]提出了使用测地距离（DPC-GD）的密度峰聚类，它将测地距离的概念引入到原始DPC方法中。Liu等[28]针对高维度复杂数据集时，DPC聚类时会掩盖低密度的类别，导致效果不好，提出了一种基于共享最近邻居的密度峰值聚类。类中心的手动选择是CFSFDP在智能数据分析中的一大局限。Bie等[29]提出了一种有效地选择聚类中心的模糊CFSFDP方法。它是使用模糊规则来自动选择类中心，避免人工选择。Wang等[30]提出了一种利用原始数据集中数据场的潜在熵自动提取阈值最优值的新方法。

由于DPC方法中的局部密度定义简单，仅是统计了截断距离内点的数量，而没有考虑截断距离内数据点的具体分布情况，只要是数据点的数量相同，就简单地认定局部密度大小相同，从而导致在某些情况下聚类中心的错判，影响聚类效果。为此，提出了基于分布的自动阈值密度峰值的聚类方法，同时考虑点的数量和分布情况来定义局部密度，自适应确定样本数目权重因子占有的比例。并在预处理阶段，引入了密度分布函数的概念，然后用最大类间差法确定阈值找出聚类中心，最后指派剩余点完成聚类。

1 密度峰值聚类算法的介绍

密度峰值聚类算法DPC是一种基于密度的聚类算法，算法思想是：（1）类中心点拥有比其周围邻近点大的密度值；（2）类中心点到其他比其密度值大的数据点之间的距离较大。当类中心点确定以后，每一个数据点分配给比其密度值大且距离其最近的数据点相同的标记按密度值由大到小依次更新所有数据点的标记直到聚类完成。

其中，χ(⋅)是密度核函数；dij是任意两点之间的距离；dc是距离阈值或者称为截断距离，用于搜索范围的限定，参数dc需要人为提前设定。高斯核密度函数是另一种常用的密度估计方法[31]，被广泛地应用在基于密度的聚类算法分析中，可定义为：

exp(·)称为核函数，dij是数据点i,j之间的距离，dc为截断距离。公式（1）可导致不同的数据点具有相同的局部密度，不利于后续的排序工作，因此本文采用式（2）进行局部密度的计算。

数据点i所对应的最小距离δi是密度值比数据点i大，且距离点i最近的数据点与点j的距离：

正如定义的那样，δi值通常会大于数据点i周围其他邻居点的最小距离值。如果数据点i是局部或者全局密度最大点，这种现象会特别明显。

算法1DPC算法

步骤1计算任意两点之间的距离dij。

步骤2计算每一点的局部密度ρi，将密度点按由高到低排序。

步骤3根据式（3）求得密度距离δi并存储与之对应的标号。

步骤4根据ρi及δi的关系决策图，选取类中心点。

步骤5根据类中心点、数据对象标号及密度边界阈值，将剩余点分到各个类或边界域。

为了选取合适的类中心点，通过借助决策图人工选取类中心点。决策图有两个重要的参数：每一个数据点i的局部密度ρi和到比其密度大距离其最近的数据点的距离δi。通过数据点密度值ρi和最小距离δi的计算，便可以得到相应数据集的决策图如图1。

2 基于分布的自动阈值密度峰值聚类方法

DPC算法在计算局部密度时，只考虑了截断距离内的点个数作为局部密度，没有考虑截断距离内点的分布情况，导致局部密度的真实值有偏差，这不利于类中心选择的最终结果的准确性。除此之外，DPC算法在选择聚类中心时需要人工辅助选择，选择方式在决策图中，利用矩形框选择与其他的点差异最大的一组点为聚类中心，使得算法具有一定的主观性。本章针对DPC算法上述两个不足点提出了优化，使得算法对类中心的划分更为合理，并且可以自动选择聚类中心。

图1 DPC算法的决策图

2.1 基本思路

相比于DBSCAN及其他聚类算法，DPC能够有效发现不同形状、不同密度的簇，并且不用事先指定簇的数量，也没有很多的参数。然而，由于在定义局部密度时只是简单统计半径为dc的邻域内数据点的个数，而没有考虑邻域内数据点的具体分布情况，在某些情况下可能导致错判为密度峰值，使得聚类结果出现错误。如图2所示，以红色小圆点为圆心，半径为dc大小相同的圆圈内，圈内的星星点的个数都是12，右上角的圆圈内星星点的个数分布均匀，左下角的圆圈内星星点全部集中在小部分区域，如果局部密度都为12，显然是不合理的。

图2 样本点分布对比图

因此，本文通过分析半径为dc邻域内数据点的数量以及分布情况，来定义局部密度。基本思想：首先根据公式（1）计算每个点半径为dc邻域内点的个数ni；然后通过反余弦函数得到邻域内所有数据点与x轴正向的夹角，进而得到该邻域数据点的分布情况。将该邻域分成ni个扇形区域，fn是邻域内所有数据点占据了邻域内的扇形区域个数。例如ni=12，则把邻域分成了12个区域，如图3所示，如果这12个点占据了9个扇形区域，则局部分布密度是9；如果这12个点只占据了2个扇形区域，则局部分布密度为2。所以当邻域内点的个数相同时，这些点所占的扇形区域越多，邻域内数据点分布越均匀。

为此，定义基于分布的局部密度ρ′：

图3 基于分布的密度对比图

其中，ni根据公式（1）计算得到半径为dc的邻域内数据点的个数，ρ′是基于分布的局部密度，fn是这些点分配到ni区域中所占据的扇形区域。

2.2 聚类中心自动选择策略

此外，DPC中将那些具有较大密度距离δi且同时具有较大局部密度ρi的点定义为聚类中心。所以综合考虑δi值和ρi值，而这两类值可能处于不同的数量级。因此，对两者做一次归一化[32]再相乘得到密度距离γi。原始数据经过归一化处理后，各指标处于同一数量级。

如果数据存在异常值和较多噪音，数据归一化会使得最优解的寻优过程变得平缓，更容易正确地收敛到最优解。可以间接避免异常值和极端值的影响，故而减少了噪音点[33-35]。

由于对于两者在选取聚类中心时需要人工辅助，使得聚类过程中带有一定的随意性和主观性，不利于算法的实现和应用。为此，提出用最大类间差法（Otsu）求出阈值，确定聚类中心，最后指派剩余点到各个簇。其基本思想是：通过统计整个数据集的密度距离γ值直方图特性来实现全局阈值T的自动选取。首先，按密度距离把数据集分成2个部分，一部分密度距离较小（即潜在的非聚类中心），另一部分密度距离较大（即潜在的聚类中心），使得两个部分之间的值差异最大，每个部分之间的差异最小；其次，通过计算方差寻找一个合适的γ值来进行划分。

潜在的非聚类中心点数占整个数据集的比例ω0：

潜在聚类中心点数占整个数据集的比例ω1：

潜在的非聚类中心平均密度距离值μ0：

潜在的聚类中心平均密度距离值μ1：

数据集的总平均密度距离μ：

类间方差g：

将式（11）代入式（12），得到等价类间方差公式：

算法2给出了类中心选取策略的具体步骤。

算法2自动选择聚类中心算法

步骤1先计算整个数据集的密度距离γ值的直方图，即将所有的点按照0～maxγ共10个bin，统计落在每个bin的γ量。

步骤2归一化直方图，即将每个bin中点数量除以总数据集点的数量。

步骤3初始化分类阈值T为0。

步骤4统计密度距离在0～T的个数所占整个数据集的比例ω0，并根据公式（8）非潜在聚类中心的平均γ值μ0；统计T～maxγ密度距离点所占整个数据集的比例ω1，由公式（9）计算潜在聚类中心平均γ值μ1；并根据公式（10）统计整个数据集的平均γ值μ。

步骤5根据公式（11）计算潜在非聚类中心和潜在聚类中心的方差。

步骤6T=T+1转到步骤4，直到T为maxγ时结束迭代。

步骤7将最大g相应的T值作为数据集的全局阈值。

图4 是来自文献[26]的Aggregation数据集，用DPC决策图的方法和使用Otsu算法所得到的聚类中心对比图。绿色的方框代表决策图方法选择出来的聚类中心，红色的圆圈代表Otsu方法得到的聚类中心。可以明显地看到，图4中的1、2、5、6、7区域的类中心几乎没有差别，但在3区域，Otsu方法得到的以红色圈点为类中心的蓝色圆内包含点的个数即密度是13，以绿色圈点为类中心时，所包含的点的个数是10；在4区域红色圈点为类中心时，圆内所包含的点的个数即密度是9，绿色圈点为类中心时，所包含的点是6，且有2个点是在圆圈的边界线上，将会形成光晕点或噪音点。故以红色圈点为类中心显然更合理。

图4 Aggeragation数据集聚类中心对比图

最后，提出基于分布的局部密度和最大类间差法（Otsu）自动选择类中心的策略如算法3：

算法3基于分布的自动阈值密度峰值聚类方法

步骤1计算任意两点之间的距离，根据类数目确定dc。

步骤2根据反三角余弦函数acosθ计算各数据点的密度值ρ′i。

步骤3计算各数据点δi。

步骤4计算各数据点归一化的ρ″i与δ′i的乘积γi。

步骤5利用直方图对数据点的γi值进行分类，找出潜在的聚类中心。

步骤6Otsu算法找到γ的阈值，确定聚类中心的个数。

步骤7根据簇中心点，将剩余点分到各个簇或边界域。

3 仿真实验

为验证算法的有效性，本文使用5类数据集，分别采用DBSCAN、DPC、ADPC-KNN[36]以及改进后的密度峰值聚类4种算法，从聚类结果、正确率两个方面对算法的性能进行了评估及分析，实验环境及参数设置如表1所列。

表1 数据集属性

3.1 实验分析

（1）以788点的Aggregation数据集为例，分别采用DPC算法和改进的搜索密度峰值的聚类中心算法对聚类误差平方和进行对比。Aggregation数据集正确分类是7类。图5（a）是Eps=1.2，MinPts=3.5的DBSCAN算法聚类的结果，虽然没有噪音点，但类中心只有4个，明显不正确；图5（b）是DPC决策图法得到的聚类结果，聚类结果是7个类簇，但很明显聚类效果不好，有很多的噪音点存在；图5（c）是ADPC-KNN得到的聚类结果，是6个类簇，不正确；图5（d）是dc=2改进后的聚类结果图，得到的类别正确，没有光晕点和噪声点，聚类效果很好。

图5 Aggregation对比图

（2）Flame数据集做的实验，图6（a）是Eps=1.1，MinPts=3的DBSCAN得到的结果；图6（b）是DPC决策图，手动选择的类簇是2，类别正确，但噪音点非常多，几乎占据了一半；图6（c）是ADPC-KNN，噪音点少了很多，但得到的聚类结果是3类，不正确；图6（d）是改进后自动选择聚类中心，得到类簇是2，噪音点只有右下角最边缘的2个点没有归类。

图6 Flame对比图

（3）R15数据集做的实验，图7（a）是Eps=0.11，MinPts=1.1的DBSCAN得到的聚类结果图，图7（b）DPC决策图的类簇是15，类别正确，但噪音点多，对比ADPC-KNN中图7（c），左下角的蓝色区域，DPC明显没有噪音点，但图7（c）和图7（d）比较而言，改进后的图7（d）结果，中间蓝绿区域趋于没有噪音点，整体上噪声点也都明显下降，几乎没有。

（4）Spiral数据集实验，图8（a）是Eps=1，MinPts=3的DBSCAN得到的结果，可以看得到结果图有5个颜色的点，基本上不能形成明显的类簇；图8（b）是DPC聚类得到的结果，虽然可以得到3个类别，但每个螺旋的最后部分都是无法分类的；图8（c）是ADPC-KNN，得到的聚类结果是不正确的；图8（d）是改进后得到的聚类结果图，可以得到3个类簇，并且没有噪音点，全部归类。

（5）Two-moon数据集实验，图9（a）是Eps=1，MinPts=1.1的DBSCAN得到的结果，可以看到结果图有2个颜色的点，虽然可以形成类别，但有太多的噪音点；图9（b）是DPC聚类得到的结果，把其中的一个类分成了两类，明显是不合理的；图9（c）是ADPC-KNN得到的聚类结果，同理把一个类分成了两个类，不合理；图9（d）是改进后得到的聚类结果图，可以得到2个类簇，并且没有噪音点，全部归类。

图7 R15对比图

图8 Spiral对比图

图9 Two-moon对比图

3.2 准确度分析

为考察传统的DBSCAN算法、DPC算法，以及改进后的算法的聚类准确率，本文采用了5类数据集测试，进行了100次蒙特卡罗实验并统计了聚类准确率及F-measure实验结果如图10、11所示。

图10 算法的准确率对比图

由图10、图11可看出，DPC算法，ADPC-KNN及其本文改进后的算法在准确度、F-measure方面都明显高于DBSCAN算法，说明了密度峰值聚类算法的优越性。DPC算法依据局部密度和密度最近邻同时大时作为类簇中心，需要人为选择类簇，带有很大的主观性。DBSCAN算法需要通过判断邻域半径Eps核心点的阈值、MinPts来划分类簇，由于使用了统一的邻域半径，因此当数据密度和类簇间距离分布不均匀时，容易导致簇聚类准确度降低。标准的DPC聚类算法的准确度和F-measure与DBSCAN算法差不多，但都略低于改进后的DPC算法，这是由于，在局部密度及密度峰值时综合考虑了邻域内样本点的具体分布，并且改进后的算法能够自动选取合适的簇中心点，降低了人工辅助决策图的主观性导致的平均误差。

4 结束语

本文提出一种基于分布的自动阈值密度峰值聚类算法。首先，该算法通过由邻域内的数据点个数以及邻域内数据点的具体分布情况来计算数据点的局部密度，然后通过最大类间差法自动聚类。通过实验，分布的自动阈值密度峰值聚类算法在对复杂密度变化大的数据的处理上具有相当大的优越性，在局部密度及密度峰值综合考虑了邻域内样本点的具体分布，并且改进后的算法能够自动选取合适的簇中心点，降低了人工辅助决策图的主观性导致的平均误差，比DPC、DBSCAN、ADPCKNN算法更有效。

图11 算法的F-measure对比