加权K 近邻和多簇合并的密度峰值聚类算法

陈 磊，吴润秀，李沛武，赵 嘉

南昌工程学院 信息工程学院，南昌 330099

聚类分析是数据挖掘的重要技术。它根据数据点间的相似性将数据集划分成类簇，使得属于同一类簇的样本具有较高相似性，不同类簇间的样本存在显著差异。聚类可以揭示数据中隐藏的模式和规律，是认识和了解世界的重要方式，被广泛应用于计算机科学、信息安全、图像处理等研究领域。

由于聚类算法的广泛应用，学者们对聚类算法进行了深入研究并提出了众多的聚类算法。依据对样本的不同处理方式，可分为基于划分的聚类算法、基于层次的聚类算法、基于密度的聚类算法以及基于网格的聚类算法等。最著名的基于划分的聚类算法是-means 算法，该算法实现简单，在凸形结构数据集上具有良好的聚类效果，但-means 算法的聚类结果严重依赖于初始类簇中心的选择，需要指定类簇个数，对噪声点和离群点敏感。BIRCH（balanced iterative reducing and clustering using hierarchies）是一种基于层次的聚类算法，它能够快速对数据集进行聚类，但是该算法的聚类结果与样本的输入顺序有关，属于同一类簇的两样本可能会因为输入顺序相差较远而被分配到不同类簇。DBSCAN（densitybased algorithm for discovering clusters in large spatial databases with noise）是一种典型的基于密度的聚类算法，它可以对任意形状数据进行聚类，不需要预先指定类簇个数，但受核心对象邻域包含的最少样本数和邻域半径参数设置的影响较大且高维数据的聚类效果差。STING（statistical information grid）是一种基于网格的聚类算法，它将样本所在空间按照不同的维度划分成有限个网格单元，所有的处理都以网格单元为对象，这种方法将数据集的聚类操作转变为对数据空间中块的处理，提高了算法效率，但该算法需设置合理的网格粒度，不同的网格粒度大小对聚类精度和聚类效率有重要影响。

2014 年Rodriguez 和Laio在上提出了 一种新的快速搜索和寻找密度峰值的聚类算法，简称密度峰值聚类（density peaks clustering，DPC）算法。该算法只有一个参数，能快速发现任意形状数据的密度峰值。DPC 算法基于两点假设：（1）类簇中心的局部密度很大，并且被密度均不超过它的邻居包围；（2）各类簇中心之间的距离相对较远。

DPC 算法虽然能快速发现任意形状数据的密度峰值（类簇中心），但存在如下缺陷：（1）DPC 有两种局部密度定义方式，没有统一的密度度量准则，两种定义方式的聚类结果差异较大，且人为主观选取的截断距离值对聚类结果影响大；（2）DPC 的分配策略是将非密度峰值分配给距其最近且密度比它大的样本所在类簇，该样本分配方法很容易产生分配连带错误，即一旦某一个样本分配错误，会导致后续一连串的样本分配错误，造成不理想的聚类效果。

由于DPC 算法存在上述缺陷，近年来学者们对其进行了改进。针对局部密度定义存在的问题，纪霞等人提出了一种相对邻域与剪枝策略优化的密度峰值聚类算法（relative neighborhood and pruning strategy optimized density peaks clustering algorithm，RP-DPC）。该算法首先利用相对距离将样本映射到相对邻域中，再从相对邻域来计算各样本的局部密度，从而缩小各样本距离计算及密度统计的范围。薛小娜等人提出了结合K 近邻的改进密度峰值聚类算法（improved density peaks clustering algorithm combining K-nearest neighbors，IDPCA）。IDPCA 算法通过引入相似系数来调节各样本对当前样本的密度贡献权重，并使用带有相似系数的高斯核函数来定义局部密度。在类簇间样本数不均匀的情况下，该局部密度定义能准确找到密度峰值。Du 等人提出了基于K 近邻和主成分分析的密度峰值聚类算法（density peaks clustering based on K-nearest neighbors and principal component analysis，DPC-KNN-PCA）。DPC-KNN-PCA 算法采用样本的K 近邻信息重新定义了样本的局部密度。这种局部密度定义方式将密度计算范围从整个数据集缩减为样本的个近邻，得到的样本密度仅与其个近邻有关，能更加体现样本的局部信息，一定程度上提升了算法对密度不均匀数据的聚类性能。

针对分配策略设计存在的不足，Xie 等人提出了一种基于模糊加权K 近邻分配点的密度峰值聚类算法（robust clustering by detecting density peaks and assigning points based on fuzzy weighted K-nearest neighbors，FKNN-DPC）。该算法将样本分为核心样本和离群样本，先从密度峰值开始对每个样本的K近邻进行广度优先搜索来分配核心样本，再使用加权K 近邻技术对第一次未分配样本和离群样本进行分配。这种分配策略能够有效缓解DPC 算法一步分配导致的分配错误传递问题。贾露等人提出了一种物理学优化的密度峰值聚类算法（optimized density peak clustering algorithm in physics，W-DPC）。该算法根据第一宇宙速度建立了两步分配策略对样本进行分配，即必然从属于点的分配和可能从属于点的分配，使得样本的分配更加精确。

针对DPC 算法的局部密度定义和分配策略设计的不足，本文提出了一种加权K 近邻和多簇合并的密度峰值聚类（weighted K-nearest neighbors and multicluster merge density peaks clustering，WKMM-DPC）算法。WKMM-DPC 算法在计算样本的局部密度时采用加权K 近邻思想，引入样本的权重系数，重新定义并计算样本的局部密度，使样本局部密度更加依赖于K 近邻内样本的位置，统一了样本局部密度定义的度量准则；采用一种新的类簇间相似性的度量准则，并据此度量准则，对潜在类簇进行合并，直到潜在类簇个数等于实际类簇个数为止。

1 相关工作

1.1 DPC 算法

DPC 算法定义了两个重要的概念：一个是样本的局部密度ρ，另一个是样本与具有更高局部密度样本的最小距离δ。

对于给定数据集X=[,,…,x]，其中x=[x,x,…,x]，为样本个数，为样本维数。样本x的局部密度表示为ρ，其计算公式如式（1）所示：

其中，d为样本x与x之间的距离，为截断距离。当d-＜0 时，(d-)=1；否则，(d-)=0。

对于小规模数据集，DPC 采用高斯核函数定义样本的局部密度，其计算公式如式（2）所示：

相对距离δ指样本与密度比它高且距离它最近样本的距离。 δ计算公式如式（3）所示：

对于密度最大的样本，δ定义为：

密度峰值通常是局部密度较高且相对距离较大的样本。DPC 算法选择决策值γ较大的样本作为密度峰值，γ的计算公式如下：

找到密度峰值后，DPC 将剩余样本分配给密度比它高且距它最近的样本所在类簇。

1.2 DPC 算法缺陷分析

实验证明，DPC 算法在多数情况下都有不错的聚类性能，但仍然存在以下缺陷：

（1）DPC 算法的样本局部密度定义的度量准则不统一且两者的聚类结果存在较大差异。DPC 算法有两种局部密度定义方式：截断核和高斯核。采用截断核计算大规模数据集时，聚类效果更好，小规模数据集，采用高斯核的效果更佳。然而，没有客观的度量标准来衡量数据集是大规模还是小规模，并且选择不同的密度度量准则会对聚类结果造成较大影响。如图1 所示，取相同值时，分别使用高斯核和截断核对flame 数据集进行聚类的结果可以看出，对于同一数据集，聚类效果依据局部密度定义方式选择的不同而存在较大差异。

图1 DPC 算法对flame数据集的聚类结果(dc=2)Fig.1 Clustering result of DPC for flame dataset (dc=2)

（2）DPC 算法的分配策略易产生分配连带错误。DPC 的分配策略将非密度峰值分配给距其最近且密度比它大的样本所在类簇，该样本分配策略会形成类似“多米诺骨牌效应”，即一旦某一个样本分配错误，会导致后续一连串的样本分配错误。

如图2 所示，样本是数据集S={208,209,…,227}的局部密度极大值点。该样本到其他类簇的密度较大值点（图2 中的样本）的距离小于它到真实类簇的密度较大值点（图2 中的样本）的距离，因此，样本被分配到与样本相同的类簇，致使样本被错误分配。样本分配错误，会导致数据集合S中的样本均被错误分配。这种分配错误不仅与DPC算法的分配策略缺陷有关，也和其局部密度定义方式有关。

图2 DPC 算法对Spiral数据集的聚类结果(dc=2)Fig.2 Clustering result of DPC for Spiral dataset (dc=2)

2 WKMM-DPC 算法

通过前文的分析可知，DPC 算法在局部密度定义和分配策略设计方面存在缺陷。针对上述缺陷，本文提出了WKMM-DPC 算法，从局部密度定义和分配策略设计两方面对DPC 算法进行改进。

2.1 局部密度定义

K 近邻（K-nearest neighbours，KNN）是一个理论上比较成熟的机器学习算法，最早由Cover 和Hart 在1968 年提出，已被广泛用于分类、回归、密度估计及模式识别等领域。KNN 的目的就是在所有样本中找到距离目标样本最近的个近邻，通常用欧氏距离表示样本之间的距离。

本文基于加权K 近邻思想，引入样本的权重系数，重新定义样本的局部密度。采用K 近邻思想后，WKMM-DPC 算法只需要确定一个参数，且是一个整数，而DPC 算法需要人为主观选择局部密度定义的度量准则和截断距离，且截断距离的取值无法枚举，因此本文算法的鲁棒性强于DPC算法的鲁棒性。

（样本的权重系数）样本的局部密度定义应尽可能准确反映样本的局部分布。样本的权重系数定义如下：

式中，d表示样本x和样本x之间的欧氏距离，加权的目标是增加样本局部信息的差异化，更加准确地反映样本的相对位置。

（样本的局部密度）基于加权K 近邻思想，新的样本局部密度定义为：

图3 为Aggregation 数据集的真实分布图，Aggregation 数据集由7 个堆状类簇组成，类簇间存在交叉缠绕。图4为DPC和WKMM-DPC算法对Aggregation数据集聚类时的决策图，图中被圈出的点为密度峰值。从图4（a）可以看出，DPC 算法决策图里的密度峰值分布散乱，作为密度峰值的特征不明显，且难以发现第7 个密度峰值。从图4（b）可以看出，WKMMDPC 算法决策图的密度峰值分布紧凑，且易发现所有7 个密度峰值，其中密度峰值的局部密度均接近所有样本局部密度的最大值，由此说明本文算法新定义的局部密度能够更加准确地表征密度峰值的特性。

图3 Aggregation 数据集的真实分布图Fig.3 True distribution of Aggregation dataset

图4 Aggregation 数据集的聚类决策图Fig.4 Decision gragh of Aggregation dataset

2.2 多簇合并策略设计

本节针对DPC 分配策略存在的分配连带错误，提出一种新的类簇间相似性的度量准则，并据此度量准则，设计了一种多簇合并策略。

由式（6）和式（7）计算样本的局部密度ρ，由式（3）和式（4）计算样本的距离δ，通过式（5）计算决策值γ，对进行排序，选择前个样本作为最终生成类簇的密度峰值，选择前(≤)个样本作为潜在的密度峰值。通过DPC 的分配策略，将非密度峰值分配给密度比它高的最近的样本，生成个类簇，最后通过多簇合并策略完成聚类。

（样本间的相似度）用样本间的距离度量定义它们的相似度，新的样本间的相似度如式（8）所示：

其中，ω为样本和样本∈()的相似度，两样本距离越近，相似程度就越高，相似度也就越大，并且样本与其个近邻点以外的样本的相似度为0，这使得样本间的相似度仅与其个近邻样本有关，减小了无关数据的干扰。

（样本到类簇的邻近度）利用样本间的相似度，定义样本到类簇的邻近度，如式（9）所示：

（类簇间的相似度）类簇与类簇间的相似度如式（10）所示：

其中，(C,C)为两类簇之间的相似度，样本∈C到C邻近度的和越大，C和C之间的相似度越大。

针对DPC 算法分配策略存在的连带错误，通过类簇间的相似度进行潜在类簇合并。首先，计算类簇间的相似度，建立类簇相似度矩阵；其次，找到相似度最高的两类簇，将上述两类簇合并，直到潜在类簇个数等于真实的类簇个数为止。

2.3 算法步骤

输入：数据集data，样本最近邻个数。

输出：聚类结果。

对数据进行归一化；

计算数据集样本间的欧氏距离，并按距离值升序排列；

根据式（7）计算样本的ρ值；

根据式（3）、式（4）计算样本的δ值；

根据式（5）计算样本的决策值，选出潜在类簇的密度峰值集合，将剩余样本分配给密度比它高且距离它最近的样本所在类簇；

根据式（10）计算类簇间的相似度(C,C)，建立相似度矩阵，潜在类簇依次进行合并，直到潜在类簇个数等于真实类簇个数为止。

2.4 算法复杂度分析

DPC 算法的时间复杂度主要由计算样本间的距离矩阵的复杂度，计算每个样本的局部密度的复杂度和计算每个样本的相对距离的复杂度组成。每个部分的时间复杂度均为()，因此总的时间复杂度为()。

本文WKMM-DPC 算法的时间复杂度主要由四部分组成：（1）计算样本间的距离矩阵的复杂度()；（2）计算每个样本的局部密度的复杂度()；（3）计算每个样本的相对距离的复杂度()；（4）合并潜在类簇，其中，合并潜在类簇的过程中需要计算样本间的相似度、样本到类簇的邻近度和类簇间相似度，各部分的时间复杂度都为()，因此合并潜在类簇总时间复杂度为()。因此，本文WKMM-DPC 算法的时间复杂度为()，与DPC 算法的时间复杂度相同。

对于样本规模为的数据集，DPC 算法的空间复杂度为()。WKMM-DPC 算法比DPC 算法增加了存储各样本到其个近邻的距离和分配策略中的识别矩阵，但增加的空间复杂度不高于(||)，且表示类簇数的||通常较小，因此，本文WKMM-DPC 算法的空间复杂度与DPC 算法的空间复杂度相同。

3 实验结果与分析

为验证WKMM-DPC 算法的有效性，本文使用人工数据集和UCI 数据集对其进行测试和评价。表1和表2 详细描述了本文实验所用的数据集。将WKMM-DPC 算法与FKNN-DPC、DPCSA（density peaks clustering based on weighted local density sequenceand nearest neighbor assignment）、FNDPC（robust density peaks clustering algorithm using fuzzy neighborhood）、DPC和DBSCAN算法进行比较。其中DBSCAN和FNDPC算法参照原文献使用Matlab2019a编程实现。DPCSA 算法基于作者提供的源代码在Matlab2019a中实现。DPC 算法基于作者提供的源代码，但由于本文的数据集不包含噪声，删除“Halo”部分。FKNN-DPC算法无法从论文作者处获得源代码，因此参照原文献实现了该算法。

表1 人工数据集Table 1 Synthetic datasets

表2 UCI数据集Table 2 UCI datasets

本文将聚类性能评价常用的调整互信息（adjusted mutual information，AMI）、Fowlkes-Mallows 指 数（Fowlkes-Mallows index，FMI）、调整兰德系数（adjusted Rand index，ARI）作为聚类性能度量标准。其中，FMI和AMI的取值范围为[0，1]，ARI取值范围为[-1,1]，各指标值越接近1，表明算法的聚类性能越优。实验环境：硬件平台为IntelCore™i5-7300 CPU@2.50 GHz 2.50 GHz 处理器，8.0 GB 内存，Win10 64 bit 操作系统，Matlab2019a软件。

3.1 算法参数选择

为客观评价算法的聚类性能，本文对各算法进行参数调优，从而保证各算法的最佳聚类效果。WKMMDPC 及FKNN-DPC 算法的值选择为1～100 间的最优值。DPC 算法依据经验法则，将样本间的距离降序排列，取前1%至2%的距离作为截断距离的值。通过实验发现，并不是所有数据都能在这个范围内取得最好的结果，修改这个百分比以获得最好的聚类效果。DPCSA 算法设置了一个固定参数，它的取值为5。FNDPC 算法的参数在0.01～1.00 之间选取。DBSCAN 算法有和两个参数：从0.01 到1.00 之间选取，步长为0.01；从1 到100 之间选取，步长为1。

3.2 人工数据集实验结果分析

表3 给出了6 种聚类算法对表1 所示8 个人工数据集聚类结果的三种评价指标AMI、ARI、FMI 的值。表3 中的“—”表示没有对应值，Arg-为各算法的最优参数，加粗的值表示较好的实验结果。

表3 6 种聚类算法在8 个人工数据集上的聚类性能Table 3 Performance of 6 clustering algorithms on 8 synthetic datasets

从表3 可以看出，处理Pathbased 数据集时，WKMM-DPC 算法聚类效果低于DBSCAN 和FKNNDPC 算法聚类效果，但要好于其余算法。处理D31数据集时，WKMM-DPC 算法的聚类效果优于DBSCAN算法，略低于其余聚类算法。剩余的Spiral、Jain、Flame、Aggregation、S2 和R15 数据集上，WKMMDPC算法的聚类效果优于或持平与之比较的算法。

图5～图12 展示了人工数据集的聚类结果，相同颜色的点属于同一聚类。除DBSCAN 外，其他方法的聚类中心用“六角星”表示，DBSCAN 算法中的“叉”代表该算法的噪声点。

图5 6 种算法对Aggregation 数据集的聚类结果Fig.5 Clustering results of 6 algorithms on Aggregation dataset

图6 6 种算法对Flame数据集的聚类结果Fig.6 Clustering results of 6 algorithms on Flame dataset

图7 6 种算法对Jain 数据集的聚类结果Fig.7 Clustering results of 6 algorithms on Jain dataset

图8 6 种算法对Pathbased 数据集的聚类结果Fig.8 Clustering results of 6 algorithms on Pathbased dataset

图9 6 种算法对Spiral数据集的聚类结果Fig.9 Clustering results of 6 algorithms on Spiral dataset

图10 6 种算法对R15 数据集的聚类结果Fig.10 Clustering results of 6 algorithms on R15 dataset

图11 6 种算法对D31 数据集的聚类结果Fig.11 Clustering results of 6 algorithms on D31 dataset

图12 6 种算法对S2 数据集的聚类结果Fig.12 Clustering results of 6 algorithms on S2 dataset

图5 显示了6 种算法对Aggregation 数据集的聚类结果。Aggregation 数据集由7 个堆状类簇组成，其特征较为明显，但类簇间存在交叉缠绕。WKMMDPC 算法的聚类性能最好，它能够完全正确地发现密度峰值并完成聚类。对于DBSCAN 算法，虽然可以比较准确地完成聚类，但存在一些噪声点。DPCSA算法不能对Aggregation 数据集最右边的两类簇进行准确聚类，产生了较明显的聚类错误。

图6 显示了6 种算法对Flame 数据集的聚类结果。DBSCAN 算法会将一些边界点识别为噪声点。FKNN-DPC 算法可以正确地找到密度峰值，但有两个样本被分配错误。WKMM-DPC、DPC、DPCSA 和FNDPC 算法均能准确找到密度峰值并正确分配剩余样本。

图7 显示了6 种算法对Jain 数据集的聚类结果。Jain 数据集由两个月牙形的类簇组成，且样本密度分布不均匀。从图7 可以看出，由于下面类簇样本比较密集，DPC 和DPCSA 算法均在下面的类簇中找到两个密度峰值，从而导致密集类簇中的部分样本错误分配。DPSCAN、FKNN-DPC 和FNDPC 算法均不能对Jain 数据集进行准确聚类，WKMM-DPC 算法可以同时发现正确的密度峰值和完成聚类。

图8 显示了6 种算法对于Pathbased 数据集的聚类结果。Pathbased 数据集是一个复杂的流形数据集，由3 个类簇组成，其特别之处在于一个环型类簇包围了其余两个类簇，由于环型类簇之间联系紧密，剩余的样本分配很容易发生错误。DBSCAN 算法和FKNN-DPC 算法对Pathbased 数据集的聚类效果较好，剩余聚类算法对Pathbased 数据集的聚类效果均不太理想。

图9 显示了6 种算法对Spiral 数据集的聚类结果。Spiral 数据集是由3 个螺旋类簇组成的流形数据集。除了密度峰值的选取不同，所有的聚类算法都能正确地分配剩余的样本。

6 种算法得到的R15 数据集的聚类结果如图10所示。R15 数据集包含15 个类簇。最外层的7 个类簇距离较远，所有的聚类算法都能正确聚类这7 个类簇，最里面的8 个类簇彼此相邻且交叉缠绕，因此这8个类簇的样本容易被错误分配。从图10 可以看出，所有聚类算法都能较好地对R15 数据集进行聚类，只是最里面8 个类簇的个别样本会产生分配错误。

图11 显示了6 种算法对D31 数据集的聚类结果。各算法对该数据集均能获得较好的聚类效果，FKNN-DPC 算法的聚类效果最好，但是DBSCAN 算法却将一些点标记为噪声点，使得最终的聚类结果有所偏差。

图12 显示了6 种算法对S2 数据集的聚类结果。S2 数据集包含15 个类簇。其中，WKMM-DPC 算法的聚类效果最好，而DBSCAN 算法却将右下角的三个簇合并成了一个簇，并且将许多的边界点标记为噪声点，其余的聚类算法均能达到较好的聚类效果。

Friedman 检验是一种显著性差异检验方法，其秩均值体现了算法的综合表现。为展现算法的综合性能，采用Friedman 检验分别对AMI、ARI、FMI 评价指标进行了秩均值检验。实验中，秩均值越大，对应算法综合的性能越好。人工数据集中的三种聚类评价指标的Friedman 检验值如表4 所示。

由表4 可知，在3 种聚类评价指标上，WKMMDPC 算法的秩均值均排行第一，FKNN-DPC 排行第二。综合分析可知，6 种比较的聚类算法中，WKMMDPC 算法的综合性能最优。

表4 3 种评价指标在人工数据集上的Friedman 检验值Table 4 Friedman test value of 3 evaluation indices on synthetic datasets

3.3 UCI数据集实验结果分析

为进一步验证WKMM-DPC 算法的聚类性能。在8 个UCI数据集上将WKMM-DPC 算法与另外5 种聚类算法进行比较。6 种算法对UCI 数据集的聚类结果如表5 所示。实验结果表明，处理Wine 数据集时，WKMM-DPC 算法的聚类效果低于FNDPC 和FKNN-DPC 算法。处理Seeds 数据集时，WKMMDPC 算法的聚类效果低于FKNN-DPC、FNDPC 和DPC 算法。处理Waveform 数据集时，WKMM-DPC算法的聚类效果略逊于FNDPC 算法，但好于其余算法。剩余的Ecoli、Libras、Dermatology 和Glass 数 据集，WKMM-DPC 算法的聚类效果都要优于与之比较的算法。

表5 6 种聚类算法在8 个UCI数据集上的聚类性能Table 5 Performance of 6 clustering algorithms on 8 UCI datasets

UCI 数据集上的三种聚类评价指标的Friedman检验值如表6 所示。由表6 可知，3 种聚类评价指标上，WKMM-DPC 算法的秩均值均排行第一，FKNNDPC 排行第二。综合分析可知，在6 种比较的聚类算法中，WKMM-DPC 算法的综合性能最优。

表6 3 种评价指标在UCI数据集上的Friedman 检验值Table 6 Friedman test value of 3 evaluation indices on UCI datasets

4 结束语

DPC 算法存在局部密度定义的度量准则不统一和分配策略易产生分配连带错误的问题，针对这两个问题，本文提出了一种加权K 近邻和多簇合并的密度峰值聚类算法。WKMM-DPC 算法结合加权K近邻的思想，重新定义了局部密度，增强了样本与其个最近邻样本之间的联系，解决了DPC 算法局部密度定义的度量准则不统一的问题。同时，WKMMDPC 算法采用了多簇合并策略，缓解了DPC 算法分配策略存在的分配连带错误。在人工数据集及UCI数据集上的实验结果表明，WKMM-DPC 算法能够更加准确地找到数据集的密度峰值和处理各种形状的数据集，且算法的聚类性能优异。随着大数据时代的到来，数据正向海量数据、高维样本方向发展，传统基于样本间的距离度量定义相似度的方式面临算法时空复杂性高等弊端，因此，研究新的更高级度量样本间相似性的方式将是今后的研究热点和难点。