密度峰值聚类算法研究现状与分析*

葛丽娜，陈园园，周永权,3**

(1.广西民族大学人工智能学院，广西南宁 530006；2.广西民族大学，网络通信工程重点实验室，广西南宁 530006；3.广西混杂计算与集成电路设计分析重点实验室，广西南宁 530006)

随着现代信息技术的发展，生活中充斥着海量的数据信息，如医疗数据信息、个人消费记录、个人理财记录等，而数据信息的增多，也促使数据挖掘技术不断提高。聚类算法是数据挖掘的关键技术之一。聚类算法是根据数据之间的相似性将数据集样本划分为不同的类簇，每个类簇之间的数据相似性较高，不同的类簇中数据相似性较低。

传统的聚类算法分为基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法、基于网格的聚类算法以及基于模型的聚类算法[1]。基于密度的聚类算法，如基于密度的噪声应用空间聚类(Density-Based Spatial Clustering of Applications with Noise，DBSCAN)算法，其对噪声不敏感，能够发现任意形状的簇，但是该算法对参数ε和Minpts设置敏感，且对于密度不均匀的数据集，该算法不适用[2]。基于密度的聚类算法是以数据集在空间分布上的稠密度为依据进行聚类，无需预先设定类簇数，适合对未知内容的数据集进行聚类。

本文所研究的密度峰值聚类(Clustering by Fast Search and Find of Density Peaks,DPC)算法是2014年意大利学者Rodriguez等[3]提出的。DPC算法由于参数唯一、可以发现任意形状的数据、聚类过程简洁高效等优点，受到各界的广泛关注。目前，DPC算法已经在医学图像处理[4]、分子动力学[5]、文档处理[6，7]、社区检测[8-10]等许多领域中展现出较好的性能。如在生物医学应用方面，为了确定在300 K基准温度下T-REMD模拟过程中采样的主要构象，Kührová等[11]引入了DPC算法，与εRMSD结合，提出了新的算法；Chen等[12]引入DPC算法来识别疾病症状，再利用Apriori算法分别对疾病诊断规则和疾病治疗规则进行关联分析。本文对DPC算法原理进行介绍、分析，并对自适应DPC算法的国内外研究现状进行比较总结，最后给出今后的研究方向。

1 DPC算法原理

DPC算法[3]基于以下假设：每一类簇的聚类中心被与其相邻的密度较低的样本点所包围,这些相邻的样本点距离其他局部密度相对较大的点较远。

设有数据集D={q1,q2,…,qn}，对于每一点qi，由公式(1)计算其局部密度ρi，对于小规模数据集，采用公式(2)计算：

ρi=∑jχ(dij-dc),其中，χ(x)=

(1)

(2)

式中，dc是截断距离，dij是点qi到点qj之间的欧氏距离。

再由公式(3)计算样本点qi的距离δi，δi是样本点qi到其他密度较高样本点之间的最短距离，若qi是密度最高的样本点，则δi为qi到其他样本的最大距离。

(3)

计算出qi的局部密度和距离后，选取聚类中心。在DPC算法中，选取聚类中心的方法有两种，一种是决策图法，另一种是公式法。决策图法是根据样本点的局部密度和距离生成一个决策图，然后选取最佳的聚类中心点。例如，图1中的数据点按密度递减的顺序排列，图2是根据图1中的样本点计算局部密度和距离后得出的决策图[3]。由此可以得出DPC算法决策图选取聚类中心的一般规律：①位于决策图右上方的样本点适合选取为聚类中心，这些点拥有较高的局部密度且距离其他更高密度的点较远；②位于决策图ρ坐标轴附近的样本点具有较近的距离，认为是普通样本点，因为其附近存在更适合选取为聚类中心的样本点；③位于决策图δ坐标轴附近且距离ρ坐标轴相对较远的样本点识别为离群点，这些点拥有较低的密度且距离更高密度点较远。

图1 数据分布图Fig.1 Distribution map of data

图2 决策图Fig.2 Graph of decision

DPC算法中选取聚类中心的另一种方法是公式法，根据公式(4)计算γ的值，并将其值进行降序排序，选取前k个样本作为聚类中心(k为预先指定的簇数)。将局部密度值与距离相乘是为了寻找局部密度较高且距离较远的样本点。但是，该公式未考虑样本点邻域结构的影响。

γi=ρi×δi。

(4)

选出聚类中心后，将剩余样本点分配到距离其最近且拥有较高密度的样本点所在的类簇。

DPC算法的具体流程如算法1所示：

算法1 密度峰值聚类算法流程 输入:数据集D=q1,q2,…,qn{},簇数k 输出:聚类划分结果 1.根据数据集样本点总数确定截断距离dc 2.根据公式(1)或(2)计算样本局部密度ρ 3.根据公式(3)计算样本距离δ 4.由计算出的局部密度和距离生成决策图,根据决策图或公式(4)选取聚类中心 5.将剩余样本点分配到距离其最近的局部密度较高点所在的类簇中 6.返回聚类划分结果图

2 自适应DPC算法的优化

在DPC算法中，截断距离dc并不是算法自动设定的，而是按照文献[3]中提出的经验策略设定dc的值使得邻域样本点数为总样本点数的1%-2%。而在实际应用中，按照文献[3]中所提的方法设定截断距离的值，并不是所有的聚类问题都适用。图3所示是DPC算法在不同的dc取值下对同一数据集进行聚类的结果。由图3可以看出，虽然对类簇数没有影响，但是普通样本点和异常点的划分随着dc的取值变化而发生变化。

图3 不同dc取值下的聚类结果Fig.3 Clustering results when takes different values

在聚类中心选取阶段，虽然根据决策图选取聚类中心能够得到较好的聚类结果，但是若数据集较为复杂，人工难以选取合适的聚类中心，而聚类中心一旦选择错误，会导致非聚类中心点分配错误。图4为DPC算法对数据集Aggregation进行聚类时生成的决策图。由图4可以看出，符合聚类中心要求的点不容易确定，手动选取易造成聚类中心个数选取错误。由于DPC算法聚类无需迭代，若聚类中心选取错误，会引起剩余样本点分配出现错误，最终导致聚类效果不佳。

图4 对Aggregation数据集聚类的决策图Fig.4 Decision graph of aggregation data set

目前，针对DPC算法过程不能实现自适应的问题，主要的改进方法有3种：①针对参数dc的改进，使得dc值能够自适应选取；②对计算局部密度ρ和距离δ的公式进行改进，避免参数dc的使用；③在选取聚类中心时，采用不同的方式使得聚类中心自适应选取，不需要人为参与。

2.1 参数dc的改进

第1种改进方式主要是针对参数dc的选取。由于原来的dc值是人为设定的，淦文燕等[13]提出了Improved Clustering Algorithm that Searches and Finds Density Peaks (ICADEP)算法。该算法引入密度估计熵，提出新的参数优化方法，使得参数dc能够自适应选取最优值且聚类结果与核函数的类型无关，达到了更精确的聚类效果。但是该方法仍然需要人为参与选取聚类中心，为了解决这一问题，有学者引入K近邻思想[14-16]，即在聚类过程中计算样本点的近邻密度，提出新的计算dc的公式，实现dc的自动计算取值。Liu等[15]提出一种新的基于K近邻的计算dc的算法。该算法不仅使得dc的值自适应选择且聚类中心的选取准确、不遗漏，并能够更好地区分核心区域和边界区域。该算法的截断距离计算公式如下：

(5)

(6)

为了避免在改进算法的过程中出现需要选取参数的问题，王洋等[17]研究发现计算点势能的方法与DPC算法中计算ρ的方法相似，认为截断距离的最优值等价于电势能计算中的影响因子σ的最优值。而基尼指数G会随σ的改变而改变，因此，将基尼指数G最小时对应的σ作为截断距离的最优值；在聚类中心的选取上，根据γ的排序图中两点间的斜率差的变化来选取聚类中心。最终，该文算法实现了DPC算法的截断距离和聚类中心的自适应选取。

有研究将智能优化算法与DPC算法结合，如朱红等[18]将果蝇优化算法与DPC算法相结合，提出了Density Peaks Clustering Based on Fruit Fly Optimization Algorithm (FOA-DPC)算法。该算法将截断距离dc以及类簇数k作为决策变量，采用果蝇优化算法进行寻优，找到最优值后，采用公式(4)计算γi的值，选取前k个点作为聚类中心，对图像进行分割。

2.2 局部密度和距离的改进

第2种改进方法的主体是局部密度和距离的计算公式。DPC算法的局部密度和距离的测量是基于截断距离的值，很难得到最优的参数。谢娟英等[19]提出的K-Nearest Neighbors Optimized Clustering Algorithm by Fast search and Finding the Density Peaks (KNN-DPC)算法采用指数核函数，根据样本的K近邻信息重新定义局部密度的计算公式，使得局部密度的计算与参数dc的取值无关，更准确地发现聚类中心。但是，其聚类中心的选择仍是人机交互模式。

Liu等[20]提出了Shared-Nearest-Neighbors-based Clustering by Fast Search and Find of Density Peaks (SNN-DPC)算法。该算法提出了共享最近邻SNN和共享最近邻相似度Sim，将Sim引入局部密度的计算中，使得局部密度和距离的计算与截断距离无关，并且提出了新的剩余样本点分配方案，避免DPC算法一步分配策略易导致的“多米诺骨牌效应”的影响。从实验结果来看，SNN-DPC算法的聚类准确性得到了提高。

虽然KNN-DPC算法和SNN-DPC算法避免了参数dc对聚类结果的影响，但是对于稀疏密度相差较大的数据集，其聚类中心较难选取。因此，薛小娜等[21]提出了Improved Density Peaks Clustering Algorithm (IDPCA)。该算法在计算局部密度时引入带有相似性系数的高斯核函数，既避免了截断距离对聚类结果的影响，又使得算法适用于任意数据集。

贾露等[22]提出的Physics Improved Density Peak Clustering Algorithm (W-DPC)引入了物理学中的万有引力定律，用于重新定义局部密度的计算。样本间距离越小，吸引力越大，局部密度越大，从而易于找到高密度点和选择聚类中心，同时还引入第一宇宙速度用于处理剩余样本点。

以上4种改进算法虽然都避免了截断距离对聚类结果的影响，但是都引入了新的参数，如KNN-DPC算法、SNN-DPC算法以及IDPCA算法中都需要预先给定样本近邻K的值，而W-DPC算法需要给出扫描半径r的值。除此之外，这4种算法的聚类中心选取方面均是采用决策图法，需要人为参与。

2.3 聚类中心选取方式的改进

第3种改进方式的主体是聚类中心的选取。王星等[23]提出了Fast Searching Clustering Centers Algorithm based on Linear Regression Analysis (LR-CFDP)算法，该算法利用线性回归模型和残差分析，实现了聚类中心自动选取，解决了算法聚类中心需要人机交互选择的问题，避免了主观影响。

同样是将数学理论用于DPC算法的改进，崔世琦等[24]将高斯核函数的数学性质用于DPC算法的局部密度度量优化，并在聚类中心选取时利用γ值的中位数和绝对中位差求取残差Ri，选取前r个作为潜在聚类中心，计算α显著水平下的检验临界值λi，将原来的潜在聚类中心中λi>Ri的点作为最终的聚类中心，实现了聚类中心的自适应选取，但是对于高维数据集，该算法的性能不理想。因此，江平平等[25]提出了Improved Density Peak Clustering Algorithm based on Grid (G-DPC)算法。该算法采用网格划分法将样本空间划分为均等且不相交的网格单元，聚类中心的选取依据公式(7)和(8)：

ρCi-μ(ρi)≥0，

(7)

(δCi-E(δi))/2≥σ(δi)，

(8)

若网格代表点满足这两个公式，即为所寻聚类中心点,其中ρCi为聚类中心的网格代表点的局部密度值，μ(ρi)是所有网格代表点的局部密度均值，δCi则表示同一类簇中其他代表点与聚类中心的代表点间的最短距离，E(δi)表示所有δi的期望。该算法实现了聚类中心自适应选取。

3 自适应DPC算法指标分析

3.1 聚类准确率(ACC)

准确率[26]是计算算法正确划分的样本数占总样本数的比例，如式(9)所示。准确率的取值区间为[0,1],其值越大，表示算法的聚类结果越接近于正确的划分。

(9)

表1为DPC算法及6种改进算法作用在UCI数据集上的聚类准确率。可以看出，KM-DPC和IDPCA算法在Seeds数据集中取得最优的聚类结果，在Segmentation数据集中表现最佳的是KM-DPC算法；在Iris数据集中，KNN-DPC和SNN-FKNN-DPC两种算法聚类结果最好；其余的3个数据集ACC值最大的均为SNN-FKNN-DPC算法。总体来说，从ACC值来看，6种改进算法均优于DPC算法，而SNN-FKNN-DPC算法则是几个数据集中聚类最优的算法。基于聚类中心自适应改进的AD-PC-WKNN和AKDP算法与原算法相比聚类性能有了一定程度的改进，但是与基于局部密度计算方式改进的其他算法相比，性能优势不够明显。

表1 7种算法在UCI数据集上的聚类准确率Table 1 Clustering accuracy of 7 algorithms on the UCI data set

3.2 Adjusted Mutual Information (AMI)

AMI[31]是基于信息论的聚类度量指标，通过互信息(Mutual information)度量两个事件集合的相关性，如式(10)所示：

AMI(U,V)=

(10)

式中，U=(U1,U2,…,UL)是数据集D的标准划分，V=(V1,V2,…,VL)是优化算法的聚类结果,MuI(U,V)表示事件U与事件V之间的互信息，如式(11)所示，互信息是一种对称度量，用于量化两个分布之间共享的统计信息。E{MuI(U,V)}是U和V之间的期望互信息，如式(12)所示。H(U)和H(V)分别是U和V的熵。

MuI(U,V)=

(11)

E{MuI(U,V)}=

(12)

AMI的取值范围是[-1，1]，其值越接近1，表示算法的聚类结果越优，越接近于真实结果。

由表2可以看出，5种改进算法的AMI值大部分都优于原始的DPC算法。Wine数据集中AMI值最优的是SNN-FKNN-DPC算法，Seeds数据集最优的是W-DPC算法，Libras movement和Waveform数据集中表现最佳的是SNN-DPC算法，Waveform(noise)数据集中KM-DPC算法取得最优的AMI值。关于Iris数据集，KNN-DPC、SNN-FKNN-DPC以及SNN-DPC这3种算法的AMI值均为0.912，原因是该数据集中的簇重叠严重，而这3种算法均是引入近邻思想，受该数据集的特殊邻域环境影响，这3种算法在Iris数据集的AMI值相等。

表2 6种聚类算法在各数据集上的AMI值Table 2 AMI values of six clustering algorithms on each data set

3.3 Adjusted Rand Index (ARI)

兰德指数(Rand Index,RI)只考虑表3所示的a和d两种聚类结果的情况，忽略了b和c两种聚类结果，评价方式较为片面并且没有区分度，其计算公式如式(13)。其中，U=(U1,U2,…,UL)是数据集D的标准划分，V=(V1,V2,…,VL)是优化算法的聚类结果：

(13)

ARI[32]是基于RI的改进，度量标准划分U和聚类结果V之间的相似程度，如式(14)，也可用式(15)来表示。ARI的取值范围为[-1,1]，数值越高表示聚类划分效果越好。

ARI(U,V)=

(14)

ARI(U,V)=

(15)

式中，nij=|Ui∩Vj|为在U中属于Ui且在V中属于Vj的样本总数，ni·表示在U中属于类簇Ui的样本个数，n·j表示在V中属于类簇Vj的样本个数。

表4是6种改进算法和DPC算法在UCI数据集的ARI值。相比于DPC算法，各改进算法在UCI数据集的ARI值均有所改善，其中，在Iris数据集中，SNN-DPC算法表现最佳；SNN-FKNN-DPC算法在Wine和Libras movement两个数据集的聚类结果相比于其他算法较优；KM-DPC算法在Seeds和Segmentation数据集的ARI值最大；在WDBC数据集中，聚类效果最优的是SNN-DPC算法。

表4 6种算法在UCI数据集的ARI值Table 4 ARI values of 6 algorithms on UCI data set

3.4 F-Measure

F-Measure[33]指标综合了查准率(Precision)和查全率 (Recall)两种评价指标，其优势在于对聚类结果的整体区分能力。一般的聚类结果分布情况总结如表3所示。F-Measure的取值范围为[0,1]，数值越高表示聚类效果越好。

查准率评估聚类结果的精确程度，计算方式如公式(16)所示。查全率评估实验结果的完备程度，计算方式如公式(17)所示。F-Measure的计算方式如式(18)所示。

(16)

(17)

(18)

由表5可以看出，ADPC-KNN算法在Seeds和Libras Movement两个数据集中的F-Measure值较其他算法大，即该算法在这两个数据集中的表现最佳；而在Iris、Wine、Ecoli以及WDBC 4个数据集中聚类结果最优的是SNN-DPC算法。

表5 5种算法在UCI数据集的F-Measure值Table 5 F-Measure values of 5 algorithms on UCI data set

3.5 算法平均运行时间

由表6可以看出，3种改进算法的平均运行时间均大于DPC算法，而由前面的ACC、AMI、ARI以及F-Measure 4个指标可以看出，这些算法的聚类结果都比DPC算法有所改善，但是其运行时间都比DPC算法慢。

表6 4种算法在UCI数据集上的平均运行时间(ms)Table 6 Average running time of 4 algorithms on UCI data set (ms)

由表1、表2、表4、表5及表6的数据可以看出，3种方向上的改进算法相比于原来的算法，聚类性能在一定程度上都得到了提升，但是从整体上来看，针对dc值选取的改进算法以及针对聚类中心选取的改进算法，在数据集上的聚类效果不如基于局部密度计算公式的改进算法。5个表格中的数据集均为规模较小的数据集，说明已改进的算法在处理规模较小、数据分布较为均匀的数据集时聚类效果比较理想。

4 展望

本文主要分析了目前针对DPC算法参数dc及其聚类中心的选取不能自适应的缺陷，研究者对其进行改进的研究工作，并对改进算法的聚类结果指标进行分析。未来可从以下3个方面进行深入研究：

①将智能优化算法与DPC聚类算法有机结合，研究自适应DPC自动聚类算法：目前已有的对于DPC算法的自适应改进方式，主要是针对参数的自适应或者在选取聚类中心时无需人为参与，两者同时达到自适应效果的改进仍然较少，基于此，对DPC算法的自适应研究还可以更加完善；

②DPC算法参数选取的数学理论依据分析：目前参数的选取主要依赖经验策略，缺乏数学理论的支撑；

③高维空间DPC聚类算法理论与方法研究：虽然PDC算法能够识别任意形状簇，但是对于高维数据集，该算法的处理性能不够理想，而现有的针对高维数据的改进方式主要是基于PCA的改进算法，因此，DPC在高维空间的研究有待进一步探索。