反向近邻构造连通图的聚类算法

龙建武，王 强

重庆理工大学 计算机科学与工程学院，重庆 400054

聚类[1]，作为最常用的无监督学习方法，在数据挖掘与机器学习领域具有广泛的研究和应用。聚类算法的目的是利用簇内数据具有较高的相似度，簇间数据相似度较低的特性将数据集按照某种方式划分成不同的类别[2]。随着人工智能时代的发展，聚类的应用场景越来越广泛，包括数据挖掘[3]、人工智能[4]、文档聚类[5]、模式识别[6]、社交网络[7]和图像分割[8]等领域。目前已经提出了许多应用广泛的聚类算法，根据算法实现方式的不同可以分为：基于划分的方法[9-11]、基于密度的方法[12-15]、基于分层的方法[16-17]、基于图的方法[18-20]等。不同类型的算法各有其特点和应用场景。

K-means 算法[9,21-22]是最典型的基于划分的聚类算法，该算法在初始化聚类中心后，多次迭代将点划分到对应聚类中心所在的簇中。该算法思想简单，但它无法拟合非凸数据以及对噪声数据敏感。Kmeans算法属于硬划分算法，即对于数据集中的每个点，只能将其划分到一个簇中。此外，还有一种软划分算法，如FCM（fuzzy C-means clustering algorithm）[23]，该算法认为数据集中的点相对于每个簇都有一个隶属度，一个点属于不同簇的隶属度之和为1。FCM算法同样具有划分聚类算法的缺陷，即需要初始化聚类中心且无法拟合非凸数据集。

典型的基于密度的算法是DBSCAN（density based spatial clustering of applications with noise）算法[24]，它将数据定义为由稀疏区域分隔开的密集区域，通过设定两个参数邻域半径Eps和密度阈值MinPts进行聚类。孙璐等人[25]提出融合网格划分和DBSCAN的改进聚类算法，采用网格划分技术划分稀疏和密集区域，降低复杂度。Rodriguez等人[26]提出了DPC（clustering by fast search and find of density peaks）算法，通过构造决策图初始化局部密度最大值的点作为聚类中心，再将其他点分配到距离其最近且密度比其更大的聚类中心所在的类中，但该算法无法拟合非凸形状的簇。刘娟等人[15]提出了采用反向最近邻计算出的局部密度和密度自适应距离构建决策图进行聚类的密度峰值聚类算法。

谱聚类算法[19-20]是基于图的聚类算法。该算法利用图论的基础将数据聚类问题转化为图划分问题，其往往具有较高的时间复杂度。Huang等人[27]提出一种可伸缩谱聚类（ultra-scalable spectral clustering，USPEC）算法，通过混合代表选择策略和k近邻快速逼近的方式构造稀疏亲和子矩阵，然后将稀疏子矩阵解释成二部图，对图通过有效的分割进行聚类，但是其随机选择候选代表的方式使得算法稳定性较差。Li等人[28]提出基于图的CutPC（cut point clustering algorithm）算法，通过对去噪后的数据构造自然邻接图进行聚类，但是该算法无法识别部分无噪数据。

针对上述聚类算法不能很好地拟合非凸数据集以及对噪声敏感的缺陷，提出一种反向近邻构造连通图的聚类算法。首先，考虑到噪点对聚类的影响，利用自然邻居搜索达到稳定状态时的反向邻居最大值设计一种密度公式计算点的密度，为有效去噪，利用密度均值和标准差函数设计一种动态的噪声判别器，利用该判别器有效识别噪点，对数据进行去噪；其次，根据“距离越近的点具有越强的相关性”这一特点设计一种通过去噪后数据点的反向邻居数作为限制条件构造反向近邻连通图进行聚类的方法得到初步聚类结果，并根据给定的聚类数合并初始簇得到无噪数据的聚类结果；最后，对噪点划分聚类得到最终的聚类结果。

1 自然邻居

自然邻居的概念首次由Zhu 等人[29-30]提出，其目的是为了解决数据点最近邻范围内的参数选择问题，其思想来源于现实社会中人类之间的友谊，自然社会中，一个人真正拥有多少朋友取决于有多少人把他当作朋友。自然邻居的搜索过程是通过不断地扩大搜索范围寻找数据点反向邻居的过程。基于自然邻居的思想，数据点越密集的地方拥有的反向邻居越多，越稀疏的地方拥有的反向邻居越少。

定义1（k近邻）对于数据集D中的一点a，若点b是其第k个最近邻居，则点a的k近邻定义为：

其中，dist(a,b)表示数据点a和b之间的欧式距离。

定义2（反向邻居）对于数据集D中的一个点a，其反向邻居定义如下：

其中，d是D中的一个点，点a是点d的k近邻，点a的反向邻居为D中一组点d的集合。

定义3（自然特征值λ）自然邻居搜索过程是被动查找所有数据点反向邻居的过程。当满足以下两个条件之一时，自然邻居搜索达到稳定状态：（1）自然邻居搜索范围由k=1 到n逐渐扩大的过程中，若在连续两次迭代过程中，拥有反向邻居的数据点的个数保持不变；（2）数据集D中的任意一个点都拥有反向邻居。若满足上述两个条件中的任意一个，则自然邻居搜索停止，此时的状态定义为自然邻居稳定状态。自然邻居搜索达到稳定状态时的k值定义为自然特征值λ，具体如下：

其中，k初始化为1，后续逐渐递增，直至自然邻居搜索达到稳定状态。nbk(xi)是数据集D中的点xi第k次迭代时的反向邻居数量，函数f(x)用来统计D中拥有反向邻居的点的个数，定义如下：

自然邻居搜索过程的算法如算法1所示，自然邻居搜索达到稳定状态时的自然特征值能够克服传统的KNN 算法k值选取不合理的情况，在数据挖掘和聚类分析领域具有良好的性能。

算法1自然邻居搜索过程

2 提出的方法

由于目前的许多聚类方法在非凸数据集上的聚类效果较差，而现有的基于图的方法如谱聚类算法常常具有较高的时间复杂度，因而限制了其在聚类分析领域的应用。本文通过对自然邻居思想的理解，发现自然邻居搜索过程是不断扩大搜索范围寻找数据点反向邻居的过程，考虑到核心区域的点拥有较多的反向邻居，而边缘区域的点拥有的反向邻居较少或为0，提出一种反向近邻构造连通图的聚类算法。通过对去噪后数据构造反向近邻连通图来识别数据结构特征，进行聚类。构造反向近邻连通图进行聚类的方式只需考虑数据点与周围一定范围内的其他点之间的联系，具有较高的计算效率。

算法分为三部分：首先，利用自然邻居搜索达到稳定状态时所有数据点的反向邻居数最大值设计密度公式计算点的密度，并构建一种动态的噪声判别器利用给定的噪声参数计算出合适的噪声阈值进行去噪。然后，提出一种反向近邻构造连通图进行聚类的方法，利用自然邻居搜索达到稳定状态时数据点的反向邻居数作为限制条件构造反向近邻连通图，记录构图完成时的极大连通子图个数，得到初步聚类结果，并通过给定的聚类数对得到的初步聚类结果按照簇间距离从小到大合并聚类。最后，对噪点划分聚类，得到最终的聚类结果。

2.1 反向密度去噪

聚类数据中，大部分数据集都包含噪点，这也导致很多对噪点比较敏感的聚类方法如K-means 算法的聚类效果较差。为解决这个问题，必须采用合适的方法识别噪声数据。

传统的聚类算法如DPC 算法[26]采用的是ε近邻的方式来计算密度，通常有两种计算方式：第一种采用的是计算截断距离dc范围内数据点的个数作为点的密度，但这种计算方式得出的密度是离散值，通常无法取得较好的聚类效果，并且由于数据分布的多样性，难以人为给出合理的截断距离dc值。另一种方式采用高斯核函数计算密度，虽然能够保证计算得到连续的密度值，但是这种密度计算方式仍然没有解决截断距离dc难以给定的缺陷。

由于稠密区域比稀疏区域点的密度更大，具有自适应性特点的k近邻方式相比难以确定合适取值的ε近邻更具优势。基于上述观点，使用数据点k近邻方式相比ε近邻计算密度的效果更好。传统的k近邻方式通常需要人为给定k值，而数据的复杂多样性又导致往往难以给定合理的k取值，因此，使用一种能够针对不同数据集自动确定k取值的方式计算密度就显得尤为重要。

本文通过观察，发现聚类数据具备以下特点：“位于稀疏区域的点具有较小的密度，位于稠密区域点的密度较大”。根据数据的这一特点利用自然邻居搜索停止时的反向邻居数设计密度公式计算点的密度信息，然后构建一种动态的噪声识别器利用噪声参数计算合适的噪声阈值对数据集进行去噪。

定义4（反向密度）对于D中的点a，其反向密度计算方式定义如下：

其中，μ为自然邻居搜索达到稳定状态的反向邻居数最大值，定义如下：

λ为该状态下的自然特征值。nbλ(D)表示该状态下所有点的反向邻居数。

本文采取的密度计算方式，对自然邻居搜索达到稳定状态时的反向邻居数最大值μ以及μ近邻的欧式距离之和的比值取对数来计算数据的密度。由于不同数据集自然邻居搜索达到稳定状态时的反向邻居数最大值并不相同，因此本文的密度计算方式能够针对不同数据集得到不同的反向邻居数最大值，从而避免人工选择k值不合理的缺陷。

通过式（5）计算出数据的密度后，观察噪点数据与非噪点数据之间的密度差异，利用密度均值和标准差构造一种动态的噪声判别器，根据提供的噪声参数计算出噪声密度阈值，识别噪点，对数据集进行去噪。

定义5（噪声判别器）对于D中的点a，若点a属于噪点，则点a需要满足的条件定义为：

其中，τ(β)是噪声密度阈值，定义如下：

利用式（8），将数据集中所有密度小于τ(β)的点均识别为噪点。mean(ρ(D))表示数据集D的密度均值，Φ-1(∙)表示标准正态分布的分位数函数，β表示噪声参数，由人工根据数据集的含噪情况给定，β∈[0,1)，σ(∙)表示标准差函数。数据集的噪点越多，识别噪点的噪声阈值τ(β)就越大，因而需要给定较大的噪声参数β。

由于不同数据集的噪点含量并不相同，有些数据集含噪较多，也有些数据集含噪点较少或者不包含噪点。基于这种情况，设计一种能够根据数据集含噪程度调节噪声参数控制去噪比例的噪声识别器就显得尤为重要。本文式（8）中的噪声判别器，通过密度均值获得数据点密度的总体分布，然后利用噪声参数β来调节判别器识别出的噪点数量。上述条件使得噪声判别器针对不同噪点含量的数据集都能达到较好的去噪效果，因此能够适应于各种类型的含噪数据集，解决噪点对聚类过程的影响。

通过上述的噪声判别器设置合适的噪声参数对数据集进行去噪，去噪过程如算法2 所示，去噪后的数据集能很好地保留点之间的结构信息，便于后续进行聚类。例如对于图1中的数据集，该数据集共有1 532 个样本，利用式（8）设置噪声参数为0.12，识别噪点，对数据集进行去噪。该图中红色点表示去噪后保留的数据，灰色点表示噪点，经过去噪后的数据集簇内与簇间的结构信息明显地体现出来。接下来，将去噪后的数据利用2.2节中提出的方法进行聚类。

图1 去噪后的数据可视化效果图Fig.1 Data visualization after denoising

算法2反向密度去噪算法

2.2 反向邻居构图划分聚类

对数据集去噪后，能够得到比较干净的数据。接下来，对得到的数据利用自然邻居搜索过程寻找每个点的反向邻居。由于点的密度各不相同，位于核心区域的点拥有较多的反向邻居，位于边缘的点拥有的反向邻居数目较少，甚至没有反向邻居。例如对于图2中的数据集，将自然邻居搜索过程应用在该数据集上，得到每个点的反向邻居。该数据集在自然邻居搜索达到稳定状态时的自然特征值λ=8，其中点p位于数据集的核心区域，自然邻居搜索停止时该点拥有的反向邻居数为13，而对于点q，由于其位于边缘区域，自然邻居搜索停止时该点仅拥有1个反向邻居。接下来，利用点的反向邻居数作为限制条件构造反向近邻连通图划分聚类。

图2 点p 和q 的反向邻居（点p 和q 的反向邻居数分别为13和1）Fig.2 Reverse neighbors of point p and q(The number of reverse neighbors of points p and q are 13 and 1,respectively)

定义6（反向近邻连通图）对于D*中的一个点d，通过自然邻居搜索得到d的反向邻居数目为nb[d]，将点d与其周围nb[d]个近邻的数据点进行连接构造的连通图。

由于不同数据点的反向邻居数各不相同，核心位置的点具有更多的反向邻居，它与周围点之间的联系更密切，而边缘位置的点具有的反向邻居数较少，这也使得它只与自身周围少部分点之间存在联系。基于这种结论，设计一种反向近邻构造连通图的聚类算法，利用点的反向邻居数作为限制条件构造连通图。反向近邻构图与传统的k近邻构图有着明显的区别，传统的k近邻方式进行构图，数据集中的每个点均需要与其最近的k个邻居相连，而反向近邻连通图是对传统k近邻方式构图的一种改进，它利用数据点的反向邻居数作为构造k近邻图k取值的限制条件，也就是说，对于不同的点，在构造反向近邻连通图时所选择的近邻个数是不相同的。位于核心区域的数据点构造反向近邻连通图时选择的近邻个数较多，位于边缘区域的数据点构造反向近邻连通图时选择的近邻个数较少甚至为0。传统k近邻方式构图时对所有点取相同的k值容易导致将本不属于同一个聚类的边缘点进行连接，影响聚类效果，而利用反向邻居数作为限制条件构造连通图能够有效避免k近邻方式构图的缺陷，聚类效果更好。对于去噪后数据集利用反向近邻构图划分聚类的具体算法流程可描述如下：

（1）利用自然邻居搜索的方式寻找去噪后数据集D*的反向邻居数，记录为nb[D*]。

（2）对D*中的每个数据点构造反向近邻连通图，具体方式为：对于D*中的一点d，利用KNN算法对k取值从1 开始，若点d的反向邻居数目nb[d]大于等于k，就将点d与其周围的k近邻范围内的点连接起来，若nb[d]小于k，则不进行连接，随后对k进行加1操作。不断重复该过程，直到k达到所有数据点反向邻居数最大值max(nb[D*])时停止。

（3）统计（2）所得结果中的极大连通子图的个数（number of maximal connected subgraphs，NMCS）得到初步的聚类结果。

（4）利用给定的聚类数将上述得到的簇合并成对应聚类数的聚类结果。

在构造反向近邻连通图时，针对不同数据点构图时选取的近邻个数不同。对于数据集D*中的一个点d，取其nb[d]个近邻的数据点构造反向近邻连通图，其中nb[d]表示自然邻居搜索达到稳定状态时点d的反向邻居个数。当所有数据点构造反向近邻连通图完成时算法停止，统计此时的极大连通子图的个数，得到初步的聚类结果。例如对于图2中的数据集，自然邻居搜索达到稳定状态时该数据集中所有数据点的反向邻居数最大值为15，将每个数据点的反向邻居数作为构造k近邻连通图对应该点k取值的限制条件，利用KNN算法对于k取[1,15]之间的所有整数时，不同k值得到的极大连通子图的数量（NMCS）变化情况如图3（a）～（g）所示。根据图3（g）中的结果，得到反向近邻构图完成时的极大连通子图数量为3，因此利用反向近邻构图划分聚类得到初始聚类数为3。根据初步的聚类结果发现，利用反向近邻连通图进行聚类的过程已经识别出该无噪数据集的基本结构。

图3 不同k 值的NMCS变化情况Fig.3 Change of NMCS for different values of k

利用反向近邻构图划分聚类的过程中可能会产生部分小簇或者孤立点，针对这种情况，根据设定好的聚类数对初始聚类结果进行合并，依次选择簇间距离最近的两个簇合并，直到达到设定的聚类数为止。对于图2中的数据集，其真实聚类数为2，通过构造反向近邻连通图得到的初始聚类结果包含3个簇，利用给定的聚类数依次合并簇间距离最近的簇后得到的聚类结果如图3（h）所示。利用反向近邻构造连通图划分聚类的具体算法如算法3所示。

算法3反向近邻构造连通图划分聚类

2.3 噪点划分聚类

通过构造反向近邻连通图划分聚类得到去噪后数据的聚类结果后，将去掉的噪点划分到对应的聚类中，在划分噪点时，考虑到噪点分布在簇间的范围比较广，单纯将其分配到距离最近的簇所在的类别中可能导致划分不准确，影响聚类结果。因此，考虑数据的密度信息，将噪点分配规则定义如下：

噪点划分规则（noise division rules，NDR）：针对噪点数据，将其划分到距离其最近的非噪点所在的类别中，同时要求该非噪点的密度大于当前待分配的噪点。

通过将密度信息考虑到噪点划分中，可使得噪点划分的结果更准确，最终的聚类效果更好，噪点划分聚类的原理如算法4所示。

算法4噪点划分聚类

2.4 时间复杂度

对于提出算法，假设数据集有n个对象，经过构建KD 树后自然邻居搜索过程时间复杂度为O(nlgn)，去噪过程需要判断每个点是否为噪点，时间复杂度为O(n)，构造反向近邻连通图时对每个点与其最近的nb[d]点进行连接，时间复杂度为O(nlgn)，噪点划分聚类时需要寻找每个点周围距离最近的高密度点，时间复杂度为O(nlgn)。因此，本文算法的时间复杂度为O(nlgn)。

3 实验

为验证提出方法的有效性，在9个合成数据集和5个真实数据集上进行实验，并将本文方法与其他聚类算法在上述数据集上的聚类结果进行对比。合成数据集来自文献[28]（https://github.com/lintao6/CutPC/tree/master/datasets），真实数据集来自UCI官网（https://archive.ics.uci.edu/ml/index.php）。实验中将所有的数据集进行标准化处理，对比算法包括K-means算法[9]、DBSCAN 算 法[24]、DPC 算 法[26]、USPEC 算 法[27]以 及CutPC算法[28]。

聚类评价指标通常被用来衡量聚类结果的质量，一般来说，聚类评价指标分为两种：内部评价指标和外部评价指标。内部评价指标利用簇的内部结构信息设计不同的内部评价标准对聚类结果的优劣进行评判，而外部评价指标通常需引入外部信息来评价聚类效果，如聚类的真实标签。常用的外部评价指标有聚类精度（cluster accuracy，Acc）、标准化互信息（normalized mutual information，NMI）等，实验中采用上述两种外部评价指标对聚类结果进行评价，以评估提出方法的有效性。

3.1 外部评价指标

聚类精度（Acc）是最常用的聚类外部评价指标之一，它是利用映射后的预测标签与真实聚类标签的差异性对聚类效果进行评估。聚类精度能够直观地评价聚类结果的准确率，得到聚类结果正确数据的比例。具体计算方式定义如下：

其中，n为数据样本个数，ti和pi分别代表真实的聚类标签和预测的聚类标签，map(∙)是一个映射函数，作为预测标签和真实标签的映射，用来解决聚类过程中预测标签和真实标签不匹配的问题，采用匈牙利算法实现。δ(a,b)定义为：

Acc∈[0,1]，Acc的值越大，聚类效果越好。

另一个评价聚类效果的外部指标是标准化互信息（NMI），该指标是评估聚类算法优劣的一个常用的指标，计算方式定义为：

其中，X和Y分别代表真实聚类标签和预测标签的集合，I(X,Y)表示两个随机变量X和Y之间的互信息，H(∙)表示随机变量的熵，NMI 指标的取值范围为[0,1]。NMI 指标利用信息论来量化聚类分区的差异，NMI的值越大，聚类的效果越好。

3.2 合成数据集实验

实验中选择9 个合成数据集来验证提出方法的有效性，9 个合成数据集均包含部分噪点。将5 种对比算法和本文方法应用在合成数据集上进行聚类，对比聚类结果。9个合成数据集的基本信息如表1所示。

表1 9个合成数据集的基本信息Table 1 Basic information of 9 synthetic datasets

由于9个合成数据集均包含部分噪点，需利用提出的去噪方式对数据集进行去噪，去噪后的数据能够体现出簇的结构信息。对9 个合成数据集设置的噪声参数如表2 所示。对于数据集D7，其包含噪点较多，故设置噪声参数为0.18，其他8 个合成数据集设置噪声参数为0.12。去噪前后的数据集可视化效果图如图4所示。观察发现，去噪后的数据集接近理想数据集。为展示提出算法的有效性，实验中与其他5 个算法的聚类效果进行对比，5 种对比算法在9个合成数据集上的参数如表2 所示。其中DBSCAN算法对参数非常敏感，调参过程比较复杂，为得到较好的聚类结果需要对参数精心选取。

表2 不同聚类算法在9个合成数据集上的参数Table 2 Parameters of different clustering algorithms on 9 synthetic datasets

图4 9个合成数据集去噪后的数据可视化效果Fig.4 Data visualization after denoising of 9 synthetic datasets

对9个合成数据集去噪后，利用去噪后的数据构造反向近邻连通图进行聚类，通过反向近邻连通图得到初步聚类结果后，再根据输入的聚类数将部分较小簇或者孤立点合并，得到去噪后数据对应于给定聚类数的聚类结果，最后对噪点数据划分聚类，得到最终的聚类结果。本文方法在9 个合成数据集上应用后得到的聚类结果可视化效果图如图5 所示。通过观察发现，本文方法在9个合成数据集上均能够准确地区分出不同的簇，聚类效果较好。

图5 数据集D1～D9的最终聚类结果Fig.5 Final clustering results of datasets D1 to D9

此外，将本文方法应用在上述9个合成数据集上的聚类效果和其他5种聚类方法进行对比，并采用Kmeans、DBSCAN、DPC、USPEC、CutPC 共5 种聚类算法作为对比方法进行实验。其中K-means 算法是基于分区的聚类算法，该算法通常无法较好地划分非凸数据集，并且对噪声数据比较敏感。DBSCAN 算法是基于密度的算法，通过对邻域半径Eps和密度阈值MinPts的多次调参进行聚类，但是其往往会因为数据密度不均匀导致聚类效果较差。DPC算法通过计算数据点的密度以及到高密度点的最小距离构造决策图寻找聚类中心进行聚类，但是其同K-means算法一样对非凸数据集拟合较差。USPEC算法在选择候选代表时使用了随机选择策略，因此会导致聚类效果具有随机性，算法稳定性较差。CutPC算法是基于图的方法，但是其只对于特定噪声范围内的数据集有效，无法识别部分无噪数据集。相比而言，本文方法能够避免上述五种对比方法的缺陷，对9个合成数据集的聚类效果较好。

为了更直观地描述本文方法相对其他几种对比算法的优势，实验中采用了外部评价指标聚类精度（Acc）和标准化互信息（NMI）进行聚类效果的评判，6种算法应用在9个合成数据集上的Acc和NMI指标如表3所示。

表3 6种方法应用在9个合成数据集上的Acc和NMITable 3 Acc and NMI of 6 methods applied on 9 synthetic datasets

通过6 种聚类方法在合成数据集上的聚类效果对比，采用聚类精度（Acc）和标准化互信息（NMI）作为验证指标进行聚类效果的验证后发现，其他五种聚类算法由于各自存在的缺陷，无法达到较优的结果，而本文方法先对数据集去噪后，对不包含噪点的数据集进行聚类能够准确识别非凸形状数据集的内部结构信息，在9 个合成数据集上均具有较好的聚类效果。

表4展示了6种聚类算法在9个合成数据集上的运行时间。通过对比发现，本文算法在9个合成数据集上的运行时间相比K-means 算法以及DBSCAN 算法的运行时间稍长，在数据量较小的时候，本文算法的运行时间相比DPC 算法和USPEC 算法具有明显的优势，而在数据量较大的时候，例如对于数据集D9，本文算法的运行时间高于USPEC 算法，但依旧低于DPC算法。此外，不论数据量的大小，本文算法都远低于CutPC算法的运行时间。综上得出，本文方法不仅能在9 个合成数据集上具有比较好的聚类效果，同时还能拥有较快的计算速度。

表4 6种方法应用在9个合成数据集上的运行时间Table 4 Runtime of 6 methods applied on 9 synthetic datasets 单位：s

3.3 真实数据集实验

另外，实验中还将本文方法应用在真实数据上，利用UCI 提供的真实数据集进行本文方法的实验。实验过程中将6 种聚类算法应用在5 个真实数据集上的聚类效果进行对比，5个真实数据集分别为iris、cancer、seeds、banknote 和heart，5 个真实数据集的基本信息如表5所示。

表5 5个真实数据集的基本信息Table 5 Basic information of 5 real datasets

实验中将本文方法和5 个对比算法应用在5 个真实数据集上，不同方法对应5种真实数据集的参数设置如表6所示。和合成数据集一样，仍然采用聚类精度（Acc）和标准化互信息（NMI）两种聚类评价指标进行聚类效果的评估。6 种算法应用在真实数据集上的Acc和NMI指标如表7所示。

表6 6种方法应用在5个真实数据集上的参数Table 6 Parameters of 6 methods applied on 5 real datasets

表7 6种方法应用在5个真实数据集上的Acc和NMITable 7 Acc and NMI of 6 methods applied on 5 real datasets

通过将本文方法与其他5 种对比算法在5 个真实数据集上进行实验得到的聚类精度（Acc）和标准化互信息（NMI）指标结果表明，对于iris 数据集，USPEC算法在两种聚类指标上优于其他5种方法，而对于cancer、seeds、banknote和heart数据集，本文方法的聚类精度（Acc）和标准化互信息（NMI）指标均优于其他5 种对比方法。另外对于iris 数据集，本文方法的聚类结果也接近于最优方法所得结果。综上所述，本文方法在5个真实数据集上的聚类效果优于其他5种对比算法。

表8展示了6种算法在5个真实数据集上进行聚类消耗的时间。通过对比发现：当数据量较小时，本文算法进行聚类时所消耗的时间非常少，例如在对iris、seeds 和heart 数据集聚类时，消耗的时间是6 种聚类方法中最少的；当数据集较大时，比如在对banknote 数据集进行聚类时，所消耗的时间明显增长，接近于DPC和USPEC算法，但仍然远小于CutPC算法消耗的时间，这是由于数据量较大时，在寻找反向邻居的过程、去噪的过程以及合并聚类时需要进行一系列的计算，因而会增加时间的消耗。总的来说，本文方法能够在达到较好聚类效果的同时还能够实现较少的计算时间。

表8 6种方法应用在5个真实数据集上的运行时间Table 8 Runtime of 6 methods applied on 5 real datasets 单位：s

3.4 参数鲁棒性实验

为验证噪声参数β的鲁棒性，实验中对9个合成数据集采用提出的方法在β从0.08～0.20范围内每间隔0.02的取值做一次实验，计算β每次变化时9个合成数据集的Acc和NMI指标的平均值来评价提出算法的参数鲁棒性，噪声参数β在上述范围内改变时的Acc 和NMI 指标均值变化情况如图6 所示。红色折线代表9个合成数据集Acc指标均值的变化情况，蓝色折线代表9 个合成数据集NMI 指标均值的变化情况。

图6 合成数据集的Acc和NMI均值随着β 的变化Fig.6 Changes of Acc and NMI mean values of synthetic datasets with β

观察发现，当噪声参数β在0.08～0.20 范围内变化时，本文方法应用在9个合成数据集上进行聚类的Acc和NMI指标的均值仅在β较大时出现较小的变化。而β较大时聚类指标均值下降的主要原因在于数据集D4的外围环状簇的数据点个数相对于中间3个球形簇较少，噪声参数较大时会去除环状簇内部密度较小点，使得环状簇断开，从而影响聚类效果。总的来说，噪声参数β在一定范围内变化时本文算法依然具有较好的聚类效果。因此，本文方法在参数选择上具有较强的鲁棒性。

4 结束语

本文提出一种反向近邻构造连通图的聚类算法。该算法对去噪后的数据采用反向邻居数作为限制条件构造反向近邻连通图进行初步聚类，然后利用给定的聚类数将初步聚类结果按照簇间距离从小到大合并成对应聚类数的结果，最后划分噪点得到最终的聚类结果。通过构造反向近邻连通图能够避免传统k近邻图由于对每个点取相同的k值导致聚类划分不准确的问题，能够拟合非凸形状等复杂结构的数据集。另外，实验中将本文方法应用在9个合成数据集和5个真实数据集上，并利用两种聚类外部指标进行评价，结果表明，本文方法在合成数据集和真实数据集上均能够取得较好的聚类效果。

然而，当噪声参数设置过小导致去噪不完全时，可能会导致本文方法无法得到较好的聚类结果。这是因为若噪声参数设置过小则会导致构造反向近邻连通图时将不同簇的数据连接，导致簇划分错误，影响最终的聚类结果。另外，需要人工给定聚类数也是本文方法的不足之处，这也是现有的大多数聚类方法存在的共性问题，后续将针对以上问题做进一步的研究。