最近邻的密度峰值聚类标签传播算法

宋 鹏，葛洪伟+

1.江南大学 人工智能与计算机学院，江苏 无锡 214122

2.江苏省模式识别与计算智能工程实验室（江南大学），江苏 无锡 214122

聚类是机器学习和数据挖掘中的一种基本方法，旨在把一些数据划分成不同的簇，发现数据内部的隐藏结构，要求每个簇内部的相似性高，不同簇之间的相似性低。聚类是一个热门的研究领域，也在现实生活中被广泛应用，扮演着很重要的角色，如机器学习[1]、模式识别[2]、图像处理[3]、生物信息学[4]、蛋白质分析[5]、微阵列分析[6]和社交网络[7]等。到目前为止，已经有很多专家提出了各种聚类算法，可以把这些算法大致分成四类：基于目标的方法[8]、基于模型的方法[9-10]、基于层次的方法[11]和基于密度的方法[12-15]。

近年来，基于密度的聚类方法受到了研究者的广泛关注。这些方法假设簇分布在高密度区域，可以识别具有任意形状的簇，并且需要最少的领域知识就可以将数据划分成不同的簇。DBSCAN（densitybased algorithm for discovering clusters in large spatial databases with noise）[16]是一种著名的基于密度的聚类方法，该方法不需要对数据的分布做出任何假设便可以估计出数据的密度，并且具有识别任意形状聚类、可以处理噪声和离群点、不需要在聚类之前人工预先设定聚类数目等优点。然而，这种方法存在不少缺陷，例如：它不能处理密度不均匀的数据集；对参数敏感，改变参数值就会产生不同的聚类结果；还有无法识别出具有重叠密度的簇。为了解决这些问题，一些优化算法已经被提出，例如：DVBSCAN（density based algorithm for discovering density varied clusters in large spatial databases）[17]、VDBSCA（varied density based spatial clustering of applications with noise）[18]和近些年在Science上提出的密度峰值聚类算法（density peaks clustering，DPC）[19]。该算法与其他方法不同，可以快速识别非球形团簇，并受到了广泛关注。DPC的主要思想是簇中心的密度比其相邻的数据点密度高，假设聚类中心与密度较高的点的距离相对较大。对于每个数据点，首先计算局部密度和基于最小密度的距离，然后绘制二维决策图，再将具有较大局部密度和最小基于密度的距离的数据点识别为聚类中心，最后将数据点分配到与其密度较高的最近邻相同的簇。与其他聚类方法相比，DPC 不需要指定预定义的聚类数目，不需要迭代，能节省聚类时间。但是，DPC的参数截止距离的选取对聚类结果有很大的影响，并且在识别出密度峰值后，将每个点分配给密度较高的最近邻的策略可能会导致“链式反应”。

为解决这些问题，许多专家做了改进工作，如DPCKNN（study on density peaks clustering based on Knearest neighbors and principal component analysis）[20]在密度峰值聚类中引入最近邻的思想计算局部密度，并且使用主成分分析（principal component analysis，PCA）方法来处理高维数据。但是该方法不能识别具有非球形形状的簇和识别重叠的簇。DPC-GD（density peaks clustering using geodesic distances）算法[21]是测地距离与DPC 算法相结合，有效地处理具有复杂形状或多流形结构的数据。然而，该算法不能识别扭曲、折叠或弯曲的簇，并且需要大量的计算资源。基于动态图的密度峰值聚类标签传播算法（dynamic graph-based label propagation for density peaks clustering，DPC-DLP）[22]考虑了实例间的相关性和数据的局部结构，采用了一种新的基于动态图的标签传播方法。但是该算法需要设置的参数太多，严重影响在实际使用中的效果，并且算法在每次迭代时都会使用标签数据，当簇骨干或者在标签传播过程中出现错误时，会把这个错误扩大化，最终导致无法产生正确的聚类结果。另外，当迭代次数过多时，会出现聚类效果恶化的情况。

针对上述问题，本文提出了一种最近邻的密度峰值聚类标签传播算法（nearest neighbor label propagation for density peak clustering，DPC-NLP）。本文提出的算法采用最近邻传播标签，可以在聚类的局部和非线性的情况下取得良好的效果，近似流形结构，充分考虑数据间的结构情况，并在分配的过程中不断更新数据的状态，确保利用更多的信息提高分配的正确率。实验结果表明，与现有的一些算法相比，具有良好的性能。

1 相关工作介绍

1.1 DPC-DLP算法

DPC-DLP算法[22]的核心思想是先在聚类中心附近形成簇骨干，并标记成和聚类中心相同的标签，最后使用基于图的标签传播方法将标签传播到剩余点形成最终的聚类。基于图的动态标签传播方法的主要思想基于这样的假设：如果两个样本在输入数据空间中具有较高的相似性，那么它们在标签空间中也很有可能具有很高的相似性。通过这种方法，可以将标签传播到其相邻的节点上，直到所有的节点都有标签。也可以说成把有标签数据作为监督源，通过无标签数据推出标签。

首先输入数据由加权图G=(V,E,W)表示，其中V对应于所有样本X={x1,x2,…,xn}，E是一组边，W是[0,1]范围内的非负对称权值矩阵，表示顶点xi、xj之间的相似性，定义如下：

其中，d(xi,xj)是欧式距离度量，μ和σ是超参数，σ的定义采用自适应核大小，利用K近邻的平均距离，如下所示：

Avg({kNNd(xi),kNNd(xj)})表示xi、xj之间的平均距离，k和b都是超参数，通过实验获得。

然后建立基于K近邻的图，其中每个节点只连接到它的邻居，权重值定义如下：

然后将权重值标准化，在图上定义一个转移矩阵，如下所示：

其中，Pi,j表示从节点xi和xj的转移概率，。P归一化后是不对称的，但它涵盖了数据空间的结构信息。

最后使用半监督在图中进行标签传播。将数据点分为有标记点和无标记点，有标记点就是之前的核心点（根据聚类中心形成的簇骨干），其余点为未标记点。将标签矩阵定义为Y0=[Yl:Yu]∈Rn×c，Yl是簇的标记矩阵，Yu是未标记矩阵。对簇成员使用二进制标记，如果xi属于第k个簇，那么=1，否则就为0。使用的标签传播是一种半监督（semi-supervised learning，SSL）方法，通过多次迭代将数据的局部结构（即转移矩阵P）与实例之间的相关性(YYT)相结合，将标签分配给未标记的实例。在每次迭代中，未标记的数据点的标签将获得更新，如下所示：

其中，Yt是标签矩阵，Ft是融合图，定义如下：

其中，Ft表示实例YYT和控制相关率α的关系。在每次迭代中，Y使用不同的标签，因此需要按下式重置Y。

1.2 DPC-DLP算法缺陷分析

基于图的动态标签传播算法考虑了标签空间的相关性，并以图的形式进行传播，最终得到了真实有效的标签。相比其他的聚类算法具有良好的效果，但是它在进行标签传播的时候需要设置的参数太多，严重影响在实际中的使用效果。

其次在实际使用中，当簇骨干或者在标签传播中出现错误点时，会把这个错误扩大化，严重影响聚类效果。这个缺陷可以根据式（5）看出，每次迭代都会使用标签矩阵Y，Ft的更新也需要使用标签矩阵Y，这种情况会使错误扩大化。下面通过一个实例来说明这个情况，采用一个人工数据集，此数据集共由三部分组成，两个半圆包围着一个圆，如图1 所示。在簇骨干中有一个错误点（标签传播过程中情况相同），如图2中红圈所示的位置，错把该样本归类为其他的簇，在经过DPC-DLP算法的聚类后，得到如图3所示的结果，从图中可以看出，上半圆的右半部分的点在错误点的影响下，算法把该部分的点都分配到错误点所在的簇，由此可见错误点对此算法的影响很大，并且会产生使错误扩大化的现象。

图1 测试数据集Fig.1 Testing dataset

图2 错误点位置Fig.2 Location of error point

图3 经过DPC-DLP算法后得到的结果Fig.3 Result of DPC-DLP

另外，DPC-DLP还存在迭代次数过多时，聚类效果恶化的情况。如图4已经取得最优结果，此后还继续迭代，结果如图5 所示，聚类效果会变差。此实验是在除迭代次数外，所有参数都相同的情况下进行的，只增加迭代次数。

图4 DPC-DLP获得的最优结果Fig.4 Optimal result of DPC-DLP

图5 DPC-DLP增加迭代次数得到的结果Fig.5 Result of DPC-DLP by increasing the number of iterations

2 最近邻的密度峰值聚类标签传播算法

本文提出了一种最近邻的密度峰值聚类标签传播算法（DPC-NLP）。采用最近邻传播标签，可以在聚类的局部和非线性的情况下取得良好的效果。假设欧氏空间中某点的邻域也是n维流形中的邻域。在数学上，流形是一个局部逼近欧式空间附近的每一个点的拓扑空间。近似流形空间的一个简单方法是构造K 邻域、ε邻域[23]。ε邻域的条件是两个点之间的距离小于ε，但是对于如何确定合适的ε值是困难的。K 邻域是当两个点为K 邻域的关系时，只有一个参数K相比其他邻域，是比较高效的。

该方法主要有三个步骤：（1）利用局部密度ρ和最小距离δ确定聚类中心，此步骤借鉴DPC-NLP 算法[22]；（2）使用聚类中心形成簇骨干；（3）使用最近邻的标签传播方法将簇的标签传播到剩余样本上。

2.1 确定聚类中心

本节的目的是确定一组聚类中心。聚类中心一般具有如下特点：（1）它们和相邻的样本相比的话，会具有更高的密度；（2）它们都会位于一个密集区域的中心，并且距离其他中心远。为了度量第一个特性，将局部密度ρ定义为每个样本点与其相邻点的平均距离。将每个样本xi的局部密度ρi定义如下：

其中，kNN(xi)是xi的K最近邻，k=[p×n]，p为输入样本的百分数，n为样本数量。

为了度量第二个特性，需要计算出每对样本之间的距离，因此对于每个样本，则计算出它与其他密度较高的样本点之间的最小距离δ，定义如下：

通过式（9）可以使高密度的样本具有高的δ值。在传统的DPC中，通过绘制局部密度ρ和最小距离δ的决策图来确定聚类中心。通过决策图可以使聚类中心不仅具有较大的密度，还保证了两个聚类中心足够远。为了消除人为选择聚类中心带来的影响，有很多方式可以实现自动确定聚类中心。本文使用了一种快速、简单确定聚类中心的方式。首先对样本使用局部密度ρ和最小距离δ进行排序，然后选择前c个样本点作为聚类中心。提出的评分函数如下：

使用此度量，只有与高局部密度和高最小距离值相关联的样本才会被赋予高分。因此，该度量是决策图的适当替代，而不需要任何人力。为了更清楚地显示该度量的有效性，图6（a）给出了两个集群的示例数据。图6（b）中相应的局部密度ρ和δ值绘制决策图，从图中可以看出得分最高的两个样本点被选取为聚类中心。

图6 聚类中心选取示意图Fig.6 Schematic diagram of cluster center selection

2.2 形成簇骨干

此步骤的目的是利用已经确定的聚类中心为未标记的样本分配标签，把每个簇中心的标签传播到未标记的样本上。如果使用欧式聚类计算聚类中心和样本点之间的距离，会增加计算的复杂性，不适合作为标签传播的方法。因此，本文使用邻域结构进行标签传播，并且可以近似流形结构。本节使用K邻域方法构建一个图，其中每个样本点为一个节点，并与它的K近邻相连，最后形成簇骨干。把每个聚类中心的标签分配给它的邻域，如下所示：

其中，peak是一组确定的聚类中心，kNN(peakj)是簇中心xj的一组邻居。也就是每个中心和它的邻居被定义为图中的主干。

2.3 最近邻标签传播

本节提出了一种最近邻的标签传播方式。通过这种方法，标签将传播到其相邻节点，直到所有节点都具有一个标签。因为K近邻可以近似流形结构，并且反映出数据的局部信息。

标签传播的过程为：首先统计剩余每个点的K邻域中各有几个点属于这c个簇，从中找出其中最大的个数，并把该点分配到最大数所在的簇，之后再重新统计，循环上述步骤，如果属于这c个簇点个数为0，则把k增加1，继续统计、分配，直到所有点都分配完毕。算法流程如算法1所示。

算法1最近邻标签传播

最近邻的标签传播过程中，每次只传播一个样本的标签，不断更新数据的状态，利用数据的最新状态来传播标签，确保利用更多的信息提高分配的正确率。之后充分考虑出现错误点对聚类结果带来的影响，因此该样本的标签是由它最近邻内拥有最多数量的标签决定，即使出现孤立的错误点，也不会对该点的标签产生影响，大大提高了算法的鲁棒性。为了更好验证本文提出的DPC-NLP算法在簇骨干或者传播过程中出现错误点后的效果，在图7中给出了效果图。如图7（a）所示，此图为错误点所在的位置，从图中可以看出在每个簇中都存在多个错误点，图7（b）是经过DPC-NLP 算法的运行后得到的结果，从图中可以看出错误点对本文算法的后续运行没有影响，可以得到正确的结果，具有很好的鲁棒性。

图7 DPC-NLP算法鲁棒性实验示意图Fig.7 Schematic diagram of DPC-NLP algorithm robustness experiment

DPC-NLP 算法在标签传播过程中，是不需要进行迭代的，因此就不会存在因迭代次数增加，聚类效果变差的情况。

DPC-NLP算法的详细算法步骤如算法2所示。

算法2DPC-NLP

输入：X，数据矩阵n×m；p，样本的百分数；k，分配时最近邻的个数。

输出：Y，标签矩阵n×1。

1.开始算法

2.计算近邻k=[p×n]

3.利用式（8）计算局部密度ρi

4.利用式（9）计算最小距离δi

5.利用式（10）计算评分score

6.根据score选择聚类中心

7.为聚类中心指定标签

8.将簇中心的标签分配给最近的邻居，形成簇主干。

9.运用算法1分配剩余点。

2.4 时间复杂度分析

本节主要分析所提出方法的时间复杂度。将点的总数设为n，簇中心数设为c，邻居数设为k。根据上一节算法2的介绍，所提出方法的时间复杂度取决于三个主要步骤：（1）识别聚类中心（第2～7 行）；（2）形成聚类主干（第8 行）；（3）最近邻标签传播（第9行）。

算法为了确定聚类中心，需要计算每个数据点之间的距离，时间复杂度为O(n2)，然后计算局部密度ρi和最小距离δi，时间复杂度为O(n2)，再计算每个点的score，时间复杂度为O(n)，之后对数据点进行排序选取聚类中心，时间复杂度为O(nlbn)，因此总体的时间复杂度为O(n2+n2+n+nlbn)，因为在计算过程中存储了距离矩阵，时间复杂度可以降低到O(n2)。在形成簇骨干时，需要把簇中心的标签传播到其最近邻，时间复杂度为O(ck)。

根据最近标签传播算法1的步骤，首先在最坏的情况下，该算法需要分配所有的点，因此，有一个乘数O(n)。然后扫描所有点，时间复杂度为O(n)。之后最多有n个未分配点，每个点有k个邻居，时间复杂度为O(kn)。最后寻找最大值的时间复杂度为O(cn)。因此，算法1的总体时间复杂度为基本循环O(n)乘以循环中的最高复杂度O(kn)或O(cn)，则总体时间复杂度是O(kn2)或O(cn2)，可以合并为O((k+c)n2)。

综上所述，整个DPC-NLP 算法的时间复杂度是O(n2+ck+(k+c)n2)，因为k≪n，c≪n，所以整个算法的时间复杂度为O(n2)。

3 实验与分析

与目前主流的聚类算法，如FCM（fuzzy C-means clustering algorithm）[24]、DPC-KNN[20]、IDPC（improved density peaks method for data clustering）[25]、DPC-DLP[22]通过一系列实验进行比较，来验证DPC-NLP 算法的性能。实验在一台装有CPU 型号为AMD Ryzen 5 3600、运行内存16 GB、Windows 10 64位操作系统和Matlab 2018a编程环境的PC机上进行。

3.1 数据集

本次实验共在21 个数据集上进行，其中4 个人工数据集和17个真实数据集，其中9个低维数据集、8 个高维数据集。二维人工数据集的样本数量和具有的簇个数如表1 所示。低维数据集的具体情况如表2 所示。高维数据集的具体情况如表3 所示。这些数据集广泛应用于验证聚类算法性能。

表1 人工数据集Table 1 Synthetic datasets

表2 低维数据基本情况Table 2 Low-dimensional datasets

表3 高维数据基本情况Table 3 High-dimensional datasets

3.2 评价指标

为了更好地比较实验结果，本文使用的评价指标为兰德系数（Rand index，RI）、调整兰德系数（adjusted Rand index，ARI）、归一化互信息（normalized mutual information，NMI）和F-measure 指标，以上四个指标都是其值越大，证明该算法的聚类效果越好。

兰德系数（RI）评价同一样本在两种分类结果中是否被分到同一类别，取值范围为[0,1]，定义如下：

其中，a表示在真实类别和聚类结果中都是同一类别的样本对数，b表示在真实类别和聚类结果中都是不同类别的样本对数是所有可能的样本组合对。

为了实现“在聚类结果随机产生的情况下，指标应该接近零”，调整兰德系数（ARI）被提出，取值范围为[-1,1]，它具有更高的区分度，定义如下：

归一化互信息（NMI）用来衡量真实标签与实际聚类结果分布的吻合情况，范围为[0,1]，定义如下：

其中，MI表示互信息，H表示信息熵，F(H(Y),H(C))通常取算数平均，即F(H(Y),H(C))=。

F-measure 又称F-score，是精确度与召回率的加权调和平均，取值范围为[0,1]，定义如下：

其中，P为精确度，R为召回率。

3.3 结果

3.3.1 在人工数据集上的结果

本小节的目的是比较在4 个人工数据集上本文提出的DPC-NLP算法和DPC-DLP算法的效果。图8是比较了两种算法在Aggregation 数据集上的结果。此数据集具有7 个大小不同并且分布不均匀的集群组成，其中两处具有连接点，这种情况的聚类算法的考验是很大的。结果表明，本文算法可以为数据分配正确的标签。本文算法只有1 个点出现了错误聚类的情况，并且这个点在两个簇的连接处。而DPCDLP 有5 个点聚类错误，也是在同样的位置上，不能正确分类连通的点。图9 是比较两种算法在Flame数据集上的结果，此数据集也是上下两部分连通在一起。本文算法对于此数据集全部聚类正确，而DPCDLP算法再次反映出不能很好分类出连通处的点。

图8 DPC-DLP和DPC-NLP在Aggregation数据集上的结果Fig.8 Result of DPC-DLP and DPC-NLP on Aggregation dataset

图9 DPC-DLP和DPC-NLP在Flame数据集上的结果Fig.9 Result of DPC-DLP and DPC-NLP on Flame dataset

CMC数据集是DPC-DLP文章里人工数据集，图10 是比较两种算法在此数据集上的结果，两种算法都在此数据集上聚类正确，没有错误点。

图10 DPC-DLP和DPC-NLP在CMC数据集上的结果Fig.10 Result of DPC-DLP and DPC-NLP on CMC dataset

Spiral 数据集是一个流形数据集，由3 个螺线组成，能够很好地验证算法对流形数据的处理能力。图11 是比较两种算法在此数据集上的结果，从图中可以看出DPC-DLP算法不能发现数据集中的流形结构，导致无法对流形数据集进行聚类。本文算法能够很好地识别出数据集的流形结构，并且全部聚类正确。

图11 DPC-DLP和DPC-NLP在Spiral数据集上的结果Fig.11 Result of DPC-DLP and DPC-NLP on Spiral dataset

3.3.2 在真实数据集上的实验结果

本小节通过在低维和高维数据集上进行一系列实验来验证算法的性能。低维数据集上的结果如表4～表6所示，最好的结果用加粗字标记出来。表4比较了本文算法和FCM、DPC-KNN、IDPC、DPC-DLP的F-measure 指标。从结果中可以看出，本文算法在所有数据集上都取得了最好的效果，并且平均结果高出DPC-DLP 算法0.058 3。表5、表6 为RI 指标和ARI指标的评价结果。从结果中可以看出，在大多数情况下，本文算法都取得了最好的结果，RI 指标和ARI 指标的平均值分别高于DPC-DLP 算法0.044 0和0.352 3。从以上结果可以看出，本文提出的DPCNLP算法的性能在低维数据上远远高于其他先进的聚类算法。

表4 低维数据集上的F-measure指标结果Table 4 F-measure index results on low-dimensional datasets

表5 低维数据集上的RI指标结果Table 5 RI index results on low-dimensional datasets

表6 低维数据集上的ARI指标结果Table 6 ARI index results on low-dimensional datasets

高维数据上的实验结果如表7～表9所示，本文算法分别与FCM、DPC-KNN、IDPC、DPC-DLP 算法比较了RI、ARI 和NMI 指标。在表7 中的RI 指标结果中，只有在Drivface 数据集上和DPC-DLP 算法相差0.002 3，在剩下的数据集都取得最好的结果，并且平均RI 指标值高于DPC-DLP 算法0.043 0。从表8 的ARI 指标结果看出，在大多数情况下，该算法取得了较好的效果，并且ARI 平均指标高于DPC-DLP 算法0.029 0。从表9 的NMI 指标结果看出，除了Yeast 数据集上的结果，在剩下的数据集上都取得了最好的结果。通过以上结果的对比可以看出本文提出的DPC-NLP算法在大多数数据集上可以取得较好的结果，说明在高维数据集上，DPC-NLP具有良好性能。

表7 在高维数据集上的RI指标结果Table 7 RI index results on high-dimensional datasets

表8 在高维数据集上的ARI指标结果Table 8 ARI index results on high-dimensional datasets

表9 在高维数据集上的NMI指标结果Table 9 NMI index results on high-dimensional datasets

4 结束语

本文提出了一种最近邻的密度峰值聚类标签传播算法DPC-NLP。该算法利用最近邻信息将标签传播到剩余点，并形成最终的聚类。该算法充分考虑数据间的结构情况，并在分配的过程中不断更新数据的状态，确保利用更多的信息提高分配正确率。DPC-DLP由三个主要步骤组成：第一步，利用局部密度和最小距离来识别聚类中心。第二步，用K邻域方法构造簇骨干。在这一步中，每个簇中心及其对应的K近邻形成一个簇骨干。第三步，利用一种新的最近邻标签传播将标签传播到其余样本。该方法可以有效地应用于图像聚类、基因表达、生物信息等领域，并发现流形等复杂的数据结构。实验结果表明，相比其他聚类算法，DPC-NLP 具有很好的性能和鲁棒性，并可以处理流形等复杂数据。当然，本文还存在计算局部密度和标签传播时都需要参数设定、计算成本较大等问题，今后将对以上问题进行改进。