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

计算机科学与探索Journal of Frontiers of Computer Science and Technology1673-9418/2023/17(11)-2651-12doi:10.3778/j.issn.1673-9418.2207017反向近邻构造连通图的聚类算法龙建武+，王强重庆理工大学 计算机科学与工程学院，重庆 400054+通信作者 E-mail:摘要：大数据时代的发展使得聚类算法的应用越来越广泛，但是当前大多数聚类算法对噪声数据比较敏感，并且不能识别非凸形状等复杂结构的数据集。针对该问题，提出一种反向近邻构造连通图的聚类算法。首先，设计一种密度计算方式得到数据点的密度，并构建一种动态的噪声判别器对数据进行去噪，从而削弱噪点对聚类过程的影响；其次，考虑到反向邻居更能体现数据点与周围各点之间的联系，设计一种对去噪后数据构造反向近邻连通图来识别簇内数据结构信息的聚类方法，并利用给定的聚类数合并聚类；最后，对噪点划分聚类时，考虑到仅仅将其划分到距离最近的簇可能导致划分结果不准确，设计一种噪点划分方式，将密度信息考虑到噪点划分聚类中，得到最终的聚类结果。为验证提出方法的有效性，将该方法与其他五种聚类算法的聚类结果进行对比，采用外部评价指标Acc和NMI进行聚类结果的评价。实验结果表明，该算法在非凸形状等复杂结构的含噪数据集上的聚类效果优于对比算法。关键词：去噪；反向邻居；反向近邻连通图；聚类文献标志码：A中图分类号：TP301.6Clustering Algorithm for Constructing Connected Graphs with Reverse NearestNeighborsLONG Jianwu+,WANG QiangSchool of Computer Science and Engineering,Chongqing University of Technology,Chongqing 400054,ChinaAbstract:The development of big data era makes the application of clustering algorithms more and more widespread,but most current clustering algorithms are sensitive to noisy data and cannot identify datasets with complex structuressuch as non-convex shapes.To address this problem,a clustering algorithm for constructing connected graph withreverse nearest neighbor is proposed.Firstly,a density calculation is designed to obtain the density of data points,and a dynamic noise discriminator is constructed to denoise the data so as to weaken the effect of noise on theclustering process.Secondly,considering that reverse neighbors better reflect the connection between data pointsand surrounding points,a clustering method is designed to construct reverse nearest neighbor connectivity graphsfor the denoised data to identify data structure information within clusters,and to merge clusters using a givennumber of clusters.Finally,when classifying the noise points into clusters,considering that only classifying theminto the closest clusters may lead to inaccurate classification results,a noise classification method is designed to take基金项目：重庆市教育委员会科学技术研究计划青年项目（KJQN202201148）；国家自然科学基金青年科学项目（61502065）；重庆市科委基础科学与前沿技术研究重点项目（cstc2015jcyjBX0127）；重庆理工大学研究生创新资助项目（gzlcx20223231）。This work was supported by the Young Scientists Project of Science and Technology Research Program of Chongqing Education Com-mission(KJQN202201148),the National Natural Science Foundation of China for Young Scientists(61502065),the Foundation andFrontier Research Key Program of Chongqing Science and Technology Commission(cstc2015jcyjBX0127),and the Graduate Technolo-gy Innovation Foundation of Chongqing University of Technology(gzlcx20223231).收稿日期：2022-07-06修回日期：2022-09-23Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(11)聚类1，作为最常用的无监督学习方法，在数据挖掘与机器学习领域具有广泛的研究和应用。聚类算法的目的是利用簇内数据具有较高的相似度，簇间数据相似度较低的特性将数据集按照某种方式划分成不同的类别2。随着人工智能时代的发展，聚类的应用场景越来越广泛，包括数据挖掘3、人工智能4、文档聚类5、模式识别6、社交网络7和图像分割8等领域。目前已经提出了许多应用广泛的聚类算法，根据算法实现方式的不同可以分为：基于划分的方法9-11、基于密度的方法12-15、基于分层的方法16-17、基于图的方法18-20等。不同类型的算法各有其特点和应用场景。K-means 算法9,21-22是最典型的基于划分的聚类算法，该算法在初始化聚类中心后，多次迭代将点划分到对应聚类中心所在的簇中。该算法思想简单，但它无法拟合非凸数据以及对噪声数据敏感。K-means算法属于硬划分算法，即对于数据集中的每个点，只能将其划分到一个簇中。此外，还有一种软划分算法，如FCM（fuzzy C-means clustering algorithm）23，该算法认为数据集中的点相对于每个簇都有一个隶属度，一个点属于不同簇的隶属度之和为1。FCM算法同样具有划分聚类算法的缺陷，即需要初始化聚类中心且无法拟合非凸数据集。典型的基于密度的算法是DBSCAN（density basedspatial clustering of applications with noise）算法24，它将数据定义为由稀疏区域分隔开的密集区域，通过设定两个参数邻域半径Eps和密度阈值MinPts进行聚类。孙璐等人25提出融合网格划分和DBSCAN的改进聚类算法，采用网格划分技术划分稀疏和密集区域，降低复杂度。Rodriguez等人26提出了DPC（clus-tering by fast search and find of density peaks）算法，通过构造决策图初始化局部密度最大值的点作为聚类中心，再将其他点分配到距离其最近且密度比其更大的聚类中心所在的类中，但该算法无法拟合非凸形状的簇。刘娟等人15提出了采用反向最近邻计算出的局部密度和密度自适应距离构建决策图进行聚类的密度峰值聚类算法。谱聚类算法19-20是基于图的聚类算法。该算法利用图论的基础将数据聚类问题转化为图划分问题，其往往具有较高的时间复杂度。Huang等人27提出一种可伸缩谱聚类（ultra-scalable spectral clustering，USPEC）算法，通过混合代表选择策略和k近邻快速逼近的方式构造稀疏亲和子矩阵，然后将稀疏子矩阵解释成二部图，对图通过有效的分割进行聚类，但是其随机选择候选代表的方式使得算法稳定性较差。Li等人28提出基于图的CutPC（cut point clusteringalgorithm）算法，通过对去噪后的数据构造自然邻接图进行聚类，但是该算法无法识别部分无噪数据。针对上述聚类算法不能很好地拟合非凸数据集以及对噪声敏感的缺陷，提出一种反向近邻构造连通图的聚类算法。首先，考虑到噪点对聚类的影响，利用自然邻居搜索达到稳定状态时的反向邻居最大值设计一种密度公式计算点的密度，为有效去噪，利用密度均值和标准差函数设计一种动态的噪声判别器，利用该判别器有效识别噪点，对数据进行去噪；其次，根据“距离越近的点具有越强的相关性”这一特点设计一种通过去噪后数据点的反向邻居数作为限制条件构造反向近邻连通图进行聚类的方法得到初步聚类结果，并根据给定的聚类数合并初始簇得到无噪数据的聚类结果；最后，对噪点划分聚类得到最终的聚类结果。1自然邻居自然邻居的概念首次由 Zhu等人29-30提出，其目的是为了解决数据点最近邻范围内的参数选择问题，其思想来源于现实社会中人类之间的友谊，自然社会中，一个人真正拥有多少朋友取决于有多少人把他当作朋友。自然邻居的搜索过程是通过不断地扩大搜索范围寻找数据点反向邻居的过程。基于自然邻居的思想，数据点越密集的地方拥有的反向邻居越多，越稀疏的地方拥有的反向邻居越少。定义1（k近邻）对于数据集D中的一点a，若点b是其第k个最近邻居，则点a的k近邻定义为：the density information into account to obtain the final clustering results.To verify the effectiveness of the proposedmethod,the clustering results of proposed algorithm are compared with those of five other clustering algorithms,and the external evaluation metrics Acc(cluster accuracy)and NMI(normalized mutual information)are used toevaluate the clustering results.Experimental results show that the clustering results of the proposed algorithm arebetter than those of comparison algorithms on the noisy datasets with complex structures such as non-convex shapes.Key words:denoising;reverse neighbors;reverse nearest neighbor connectivity graph;clustering2652龙建武 等：反向近邻构造连通图的聚类算法NNk(a)=x D|dist(a,x)dist(a,b)（1）其中，dist(a,b)表示数据点a和b之间的欧式距离。定义 2（反向邻居）对于数据集D中的一个点a，其反向邻居定义如下：RNN(a)=d D|a NNk(d)（2）其中，d是D中的一个点，点a是点d的k近邻，点a的反向邻居为D中一组点d的集合。定义3（自然特征值）自然邻居搜索过程是被动查找所有数据点反向邻居的过程。当满足以下两个条件之一时，自然邻居搜索达到稳定状态：（1）自然邻居搜索范围由k=1到n逐渐扩大的过程中，若在连续两次迭代过程中，拥有反向邻居的数据点的个数保持不变；（2）数据集D中的任意一个点都拥有反向邻居。若满足上述两个条件中的任意一个，则自然邻居搜索停止，此时的状态定义为自然邻居稳定状态。自然邻居搜索达到稳定状态时的k值定义为自然特征值，具体如下：=mink|i=1nf(nbk(xi)=0 ori=1nf(nbk(xi)=i=1nf(nbk-1(xi)（3）其中，k初始化为1，后续逐渐递增，直至自然邻居搜索达到稳定状态。nbk(xi)是数据集D中的点xi第k次迭代时的反向邻居数量，函数f(x)用来统计D中拥有反向邻居的点的个数，定义如下：f(x)=1,x=00,x 0（4）自然邻居搜索过程的算法如算法1所示，自然邻居搜索达到稳定状态时的自然特征值能够克服传统的 KNN 算法 k值选取不合理的情况，在数据挖掘和聚类分析领域具有良好的性能。算法1 自然邻居搜索过程输入:原数据集D。输出:自然特征值，反向邻居数nb。1.Initializing:k=1,nb(i)=0,NN0(i)=,count(1)=N;2.Create a KD-Tree T from the dataset D;/*构造KD树*/3.while true do4.foreachdatapointdinDdo/*遍历D中的每个点*/5.Find the k-th nearest neighborxofdusingT;6.nb(x)=nb(x)+1;/*记录x的反向邻居数*/7.NNk(d)=NNk-1(d)x;8.end for/*记录第k次搜索时拥有反向邻居的点的个数*/9.count(k)=length(find(nbk=0);10.ifcount(k)=0 or count(k)=count(k-1)then11.break;/*若满足条件，则自然邻居搜索停止*/12.end if13.k=k+1;14.end while15.=k;/*搜索停止时的k值即为自然特征值*/16.return,nb2提出的方法由于目前的许多聚类方法在非凸数据集上的聚类效果较差，而现有的基于图的方法如谱聚类算法常常具有较高的时间复杂度，因而限制了其在聚类分析领域的应用。本文通过对自然邻居思想的理解，发现自然邻居搜索过程是不断扩大搜索范围寻找数据点反向邻居的过程，考虑到核心区域的点拥有较多的反向邻居，而边缘区域的点拥有的反向邻居较少或为0，提出一种反向近邻构造连通图的聚类算法。通过对去噪后数据构造反向近邻连通图来识别数据结构特征，进行聚类。构造反向近邻连通图进行聚类的方式只需考虑数据点与周围一定范围内的其他点之间的联系，具有较高的计算效率。算法分为三部分：首先，利用自然邻居搜索达到稳定状态时所有数据点的反向邻居数最大值设计密度公式计算点的密度，并构建一种动态的噪声判别器利用给定的噪声参数计算出合适的噪声阈值进行去噪。然后，提出一种反向近邻构造连通图进行聚类的方法，利用自然邻居搜索达到稳定状态时数据点的反向邻居数作为限制条件构造反向近邻连通图，记录构图完成时的极大连通子图个数，得到初步聚类结果，并通过给定的聚类数对得到的初步聚类结果按照簇间距离从小到大合并聚类。最后，对噪点划分聚类，得到最终的聚类结果。2.1反向密度去噪聚类数据中，大部分数据集都包含噪点，这也导致很多对噪点比较敏感的聚类方法如 K-means算法的聚类效果较差。为解决这个问题，必须采用合适的方法识别噪声数据。传统的聚类算法如DPC算法26采用的是近邻的方式来计算密度，通常有两种计算方式：第一种采用的是计算截断距离dc范围内数据点的个数作为点的密度，但这种计算方式得出的密度是离散值，通常无法取得较好的聚类效果，并且由于数据分布的多2653Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(11)样性，难以人为给出合理的截断距离dc值。另一种方式采用高斯核函数计算密度，虽然能够保证计算得到连续的密度值，但是这种密度计算方式仍然没有解决截断距离dc难以给定的缺陷。由于稠密区域比稀疏区域点的密度更大，具有自适应性特点的k近邻方式相比难以确定合适取值的近邻更具优势。基于上述观点，使用数据点k近邻方式相比近邻计算密度的效果更好。传统的k近邻方式通常需要人为给定k值，而数据的复杂多样性又导致往往难以给定合理的k取值，因此，使用一种能够针对不同数据集自动确定k取值的方式计算密度就显得尤为重要。本文通过观察，发现聚类数据具备以下特点：“位于稀疏区域的点具有较小的密度，位于稠密区域点的密度较大”。根据数据的这一特点利用自然邻居搜索停止时的反向邻居数设计密度公式计算点的密度信息，然后构建一种动态的噪声识别器利用噪声参数计算合适的噪声阈值对数据集进行去噪。定义 4（反向密度）对于D中的点a，其反向密度计算方式定义如下：(a)=lnjNN(a)dist(a,j)（5）其中，为自然邻居搜索达到稳定状态的反向邻居数最大值，定义如下：=max(nb(D)（6）为该状态下的自然特征值。nb(D)表示该状态下所有点的反向邻居数。本文采取的密度计算方式，对自然邻居搜索达到稳定状态时的反向邻居数最大值以及近邻的欧式距离之和的比值取对数来计算数据的密度。由于不同数据集自然邻居搜索达到稳定状态时的反向邻居数最大值并不相同，因此本文的密度计算方式能够针对不同数据集得到不同的反向邻居数最大值，从而避免人工选择k值不合理的缺陷。通过式（5）计算出数据的密度后，观察噪点数据与非噪点数据之间的密度差异，利用密度均值和标准差构造一种动态的噪声判别器，根据提供的噪声参数计算出噪声密度阈值，识别噪点，对数据集进行去噪。定义 5（噪声判别器）对于D中的点a，若点a属于噪点，则点a需要满足的条件定义为：(a)()then2654龙建武 等：反向近邻构造连通图的聚类算法8.Save pointainD;9.end if10.end for11.returnD,(D)2.2反向邻居构图划分聚类对数据集去噪后，能够得到比较干净的数据。接下来，对得到的数据利用自然邻居搜索过程寻找每个点的反向邻居。由于点的密度各不相同，位于核心区域的点拥有较多的反向邻居，位于边缘的点拥有的反向邻居数目较少，甚至没有反向邻居。例如对于图2中的数据集，将自然邻居搜索过程应用在该数据集上，得到每个点的反向邻居。该数据集在自然邻居搜索达到稳定状态时的自然特征值=8，其中点p位于数据集的核心区域，自然邻居搜索停止时该点拥有的反向邻居数为13，而对于点q，由于其位于边缘区域，自然邻居搜索停止时该点仅拥有1个反向邻居。接下来，利用点的反向邻居数作为限制条件构造反向近邻连通图划分聚类。定义 6（反向近邻连通图）对于D*中的一个点d，通过自然邻居搜索得到d的反向邻居数目为nbd，将点d与其周围nbd个近邻的数据点进行连接构造的连通图。由于不同数据点的反向邻居数各不相同，核心位置的点具有更多的反向邻居，它与周围点之间的联系更密切，而边缘位置的点具有的反向邻居数较少，这也使得它只与自身周围少部分点之间存在联系。基于这种结论，设计一种反向近邻构造连通图的聚类算法，利用点的反向邻居数作为限制条件构造连通图。反向近邻构图与传统的 k近邻构图有着明显的区别，传统的k近邻方式进行构图，数据集中的每个点均需要与其最近的k个邻居相连，而反向近邻连通图是对传统k近邻方式构图的一种改进，它利用数据点的反向邻居数作为构造 k近邻图k取值的限制条件，也就是说，对于不同的点，在构造反向近邻连通图时所选择的近邻个数是不相同的。位于核心区域的数据点构造反向近邻连通图时选择的近邻个数较多，位于边缘区域的数据点构造反向近邻连通图时选择的近邻个数较少甚至为0。传统k近邻方式构图时对所有点取相同的 k值容易导致将本不属于同一个聚类的边缘点进行连接，影响聚类效果，而利用反向邻居数作为限制条件构造连通图能够有效避免k近邻方式构图的缺陷，聚类效果更好。对于去噪后数据集利用反向近邻构图划分聚类的具体算法流程可描述如下：（1）利用自然邻居搜索的方式寻找去噪后数据集D*的反向邻居数，记录为nbD*。（2）对D*中的每个数据点构造反向近邻连通图，具体方式为：对于D*中的一点d，利用KNN算法对k取值从 1开始，若点d的反向邻居数目nbd大于等于k，就将点d与其周围的k近邻范围内的点连接起来，若nbd小于k，则不进行连接，随后对k进行加1操作。不断重复该过程，直到k达到所有数据点反向邻居数最大值max(nbD*)时停止。（3）统计（2）所得结果中的极大连通子图的个数（number of maximal connected subgraphs，NMCS）得到初步的聚类结果。（4）利用给定的聚类数将上述得到的簇合并成对应聚类数的聚类结果。在构造反向近邻连通图时，针对不同数据点构图时选取的近邻个数不同。对于数据集D*中的一个点d，取其nbd个近邻的数据点构造反向近邻连通图，其中nbd表示自然邻居搜索达到稳定状态时点d的反向邻居个数。当所有数据点构造反向近邻连通图完成时算法停止，统计此时的极大连通子图的个数，得到初步的聚类结果。例如对于图2中的数据集，自然邻居搜索达到稳定状态时该数据集中所有图2点p和q的反向邻居（点p和q的反向邻居数分别为13和1）Fig.2Reverse neighbors of pointpandq(The number of reverse neighbors of pointspandqare 13 and 1,respectively)图1去噪后的数据可视化效果图Fig.1Data visualization after denoising2655Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(11)数据点的反向邻居数最大值为 15，将每个数据点的反向邻居数作为构造k近邻连通图对应该点k取值的限制条件，利用KNN算法对于k取1,15之间的所有整数时，不同k值得到的极大连通子图的数量（NMCS）变化情况如图 3（a）（g）所示。根据图 3（g）中的结果，得到反向近邻构图完成时的极大连通子图数量为3，因此利用反向近邻构图划分聚类得到初始聚类数为3。根据初步的聚类结果发现，利用反向近邻连通图进行聚类的过程已经识别出该无噪数据集的基本结构。利用反向近邻构图划分聚类的过程中可能会产生部分小簇或者孤立点，针对这种情况，根据设定好的聚类数对初始聚类结果进行合并，依次选择簇间距离最近的两个簇合并，直到达到设定的聚类数为止。对于图2中的数据集，其真实聚类数为2，通过构造反向近邻连通图得到的初始聚类结果包含3个簇，利用给定的聚类数依次合并簇间距离最近的簇后得到的聚类结果如图3（h）所示。利用反向近邻构造连通图划分聚类的具体算法如算法3所示。算法3 反向近邻构造连通图划分聚类输入:去噪后数据集D，聚类数NC。输出:D的聚类结果DCL。1.Initializing:k=1;/*计算D的自然特征值*和反向邻居数nb*/2.*,nb*=NaN-Searching(D);3.2=max(nb*(D)/*D的反向邻居数最大值2*/*从1到2范围内遍历k，对D构造反向近邻连通图*/4.whilek 2do5.for each pointdinDdo6.ifnb*(d)kthen7.Constructing k-nearest neighbor graph for pointd;8.end if9.end for10.k=k+1;11.end while12.Calculate NMCS inD;/*计 算 构 图 完 成 时 的NMCS*/13.whileNMCS NCdo/*合并初始NMCS*/14.Merge the two nearest maximal connected sub-graphs;15.NMCS=NMCS-1;16.end while/*得到D的聚类结果DCL*/17.Assign clustering results toD*CL;18.returnD*CL2.3噪点划分聚类通过构造反向近邻连通图划分聚类得到去噪后数据的聚类结果后，将去掉的噪点划分到对应的聚类中，在划分噪点时，考虑到噪点分布在簇间的范围比较广，单纯将其分配到距离最近的簇所在的类别中可能导致划分不准确，影响聚类结果。因此，考虑数据的密度信息，将噪点分配规则定义如下：噪点划分规则（noise division rules，NDR）：针对噪点数据，将其划分到距离其最近的非噪点所在的类别中，同时要求该非噪点的密度大于当前待分配的噪点。通过将密度信息考虑到噪点划分中，可使得噪点划分的结果更准确，最终的聚类效果更好，噪点划分聚类的原理如算法4所示。图3不同k值的NMCS变化情况Fig.3Change of NMCS for different values ofk2656龙建武 等：反向近邻构造连通图的聚类算法算法4 噪点划分聚类输入:原数据集D，去噪后数据集D，D的聚类结果DCL，D的密度(D)。输出:D的聚类结果DCL。1.Dn=D-D/*Dn表示噪点数据*/*利用D的聚类结果DCL更新DCL*/2.Update theDCLbased on the clustering resultsDCLofD3.N=length(D);4.foriinrange(N)do/*遍历D中的点*/*若D(i)是噪点,根据NDR划分D(i)的类别DCL(i)*/5.ifD(i)Dnthen6.DivideDCL(i)according to NDR;7.end if8.end for9.returnDCL2.4时间复杂度对于提出算法，假设数据集有n个对象，经过构建KD 树后自然邻居搜索过程时间复杂度为O(nlgn)，去噪过程需要判断每个点是否为噪点，时间复杂度为O(n)，构造反向近邻连通图时对每个点与其最近的nbd点进行连接，时间复杂度为O(nlgn)，噪点划分聚类时需要寻找每个点周围距离最近的高密度点，时间复杂度为O(nlgn)。因此，本文算法的时间复杂度为O(nlgn)。3实验为验证提出方法的有效性，在9个合成数据集和5个真实数据集上进行实验，并将本文方法与其他聚类算法在上述数据集上的聚类结果进行对比。合成数据集来自文献28（https:/ 算法24、DPC 算法26、USPEC 算法27以及CutPC算法28。聚类评价指标通常被用来衡量聚类结果的质量，一般来说，聚类评价指标分为两种：内部评价指标和外部评价指标。内部评价指标利用簇的内部结构信息设计不同的内部评价标准对聚类结果的优劣进行评判，而外部评价指标通常需引入外部信息来评价聚类效果，如聚类的真实标签。常用的外部评价指标有聚类精度（cluster accuracy，Acc）、标准化互信息（normalized mutual information，NMI）等，实验中采用上述两种外部评价指标对聚类结果进行评价，以评估提出方法的有效性。3.1外部评价指标聚类精度（Acc）是最常用的聚类外部评价指标之一，它是利用映射后的预测标签与真实聚类标签的差异性对聚类效果进行评估。聚类精度能够直观地评价聚类结果的准确率，得到聚类结果正确数据的比例。具体计算方式定义如下：Acc=1ni=1n(ti,map(pi)（9）其中，n为数据样本个数，ti和pi分别代表真实的聚类标签和预测的聚类标签，map()是一个映射函数，作为预测标签和真实标签的映射，用来解决聚类过程中预测标签和真实标签不匹配的问题，采用匈牙利算法实现。(a,b)定义为：(a,b)=1,a=b0,a b（10）Acc0,1，Acc的值越大，聚类效果越好。另一个评价聚类效果的外部指标是标准化互信息（NMI），该指标是评估聚类算法优劣的一个常用的指标，计算方式定义为：NMI(X,Y)=2I(X,Y)H(X)+H(Y)（11）其中，X和Y分别代表真实聚类标签和预测标签的集合，I(X,Y)表示两个随机变量X和Y之间的互信息，H()表示随机变量的熵，NMI指标的取值范围为0,1。NMI 指标利用信息论来量化聚类分区的差异，NMI的值越大，聚类的效果越好。3.2合成数据集实验实验中选择 9个合成数据集来验证提出方法的有效性，9个合成数据集均包含部分噪点。将 5种对比算法和本文方法应用在合成数据集上进行聚类，对比聚类结果。9个合成数据集的基本信息如表1所示。表19个合成数据集的基本信息Table 1Basic information of 9 synthetic datasets数据集D1D2D3D4D5D6D7D8D9样本数1 0005131 5321 1141 9151 4272 0001 0648 533特征数222222222聚类数4524648272657Journal of Frontiers of Computer Science and Technology计算机科学与探索2023,17(11)由于9个合成数据集均包含部分噪点，需利用提出的去噪方式对数据集进行去噪，去噪后的数据能够体现出簇的结构信息。对 9个合成数据集设置的噪声参数如表 2所示。对于数据集 D7，其包含噪点较多，故设置噪声参数为 0.18，其他 8个合成数据集设置噪声参数为 0.12。去噪前后的数据集可视化效果图如图4所示。观察发现，去噪后的数据集接近理想数据集。为展示提出算法的有效性，实验中与其他 5个算法的聚类效果进行对比，5种对比算法在 9个合成数据集上的参数如表 2所示。其中 DBSCAN算法对参数非常敏感，调参过程比较复杂，为得到较好的聚类结果需要对参数精心选取。对9个合成数据集去噪后，利用去噪后的数据构造反向近邻连通图进行聚类，通过反向近邻连通图得到初步聚类结果后，再根据输入的聚类数将部分较小簇或者孤立点合并，得到去噪后数据对应于给定聚类数的聚类结果，最后对噪点数据划分聚类，得到最终的聚类结果。本文方法在 9个合成数据集上应用后得到的聚类结果可视化效果图如图 5 所示。通过观察发现，本文方法在9个合成数据集上均能够准确地区分出不同的簇，聚类效果较好。此外，将本文方法应用在上述9个合成数据集上的聚类效果和其他5种聚类方法进行对比，并采用K-means、DBSCAN、DPC、USPEC、CutPC共 5种聚类算法作为对比方法进行实验。其中 K-means算法是基于分区的聚类算法，该算法通常无法较好地划分非凸数据集，并且对噪声数据比较敏感。DBSCAN 算法是基于密度的算法，通过对邻域半径Eps和密度阈值MinPts的多次调参进行聚类，但是其往往会因为数据密度不均匀导致聚类效果较差。DPC算法通过计算数据点的密度以及到高密度点的最小距离构造图49个合成数据集去噪后的数据可视化效果Fig.4Data visualization after denoisingof 9 synthetic datasets表2不同聚类算法在9个合成数据集上的参数Table 2Parameters of different clustering algorithms on 9 synthetic datasets数据集D1D2D3D4D5D6D7D8D9K-meansN=4N=5N=2N=4N=6N=4N=8N=2N=7DBSCANEps=1,MinPts=6Eps=5,MinPts=3Eps=0.1,MinPts=10Eps=9,MinPts=5Eps=10,MinPts=23Eps=0.16,MinPts=7Eps=0.025,MinPts=5Eps=0.5,MinPts=5Eps=0.7,MinPts=10DPCN=4N=5N=2N=4N=6N=4N=8N=2N=7USPECN=4N=5N=2N=4N=6N=4N=8N=2N=7CutPC=1=1=1=1=0.9=1=1=1=1Ours=0.12,N=4=0.12,N=5=0.12,N=2=0.12,N=4=0.12,N=6=0.12,N=4=0.18,N=8=0.12,N=2=0.12,N=7图5数据集D1D9的最终聚类结果Fig.5Final clustering results of datasets D1 to D92658龙建武 等：反向近邻构造连通图的聚类算法决策图寻找聚类中心进行聚类，但是其同K-means算法一样对非凸数据集拟合较差。USPEC算法在选择候选代表时使用了随机选择策略，因此会导致聚类效果具有随机性，算法稳定性较差。CutPC算法是基于图的方法，但是其只对于特定噪声范围内的数据集有效，无法识别部分无噪数据集。相比而言，本文方法能够避免上述五种对比方法的缺陷，对9个合成数据集的聚类效果较好。为了更直观地描述本文方法相对其他几种对比算法的优势，实验中采用了外部评价指标聚类精度（Acc）和标准化互信息（NMI）进行聚类效果的评判，6种算法应用在9个合成数据集上的Acc和NMI指标如表3所示。通过 6种聚类方法在合成数据集上的聚类效果对比，采用聚类精度（Acc）和标准化互信息（NMI）作为验证指标进行聚类效果的验证后发现，其他五种聚类算法由于各自存在的缺陷，无法达到较优的结果，而本文方法先对数据集去噪后，对不包含噪点的数据集进行聚类能够准确识别非凸形状数据集的内部结构信息，在 9 个合成数据集上均具有较好的聚类效果。表4展示了6种聚类算法在9个合成数据集上的运行时间。通过对比发现，本文算法在9个合成数据集上的运行时间相比K-means算法以及 DBSCAN算法的运行时间稍长，在数据量较小的时候，本文算法的运行时间相比 DPC 算法和 USPEC 算法具有明显的优势，而在数据量较大的时候，例如对于数据集D9，本文算法的运行时间高于 USPEC 算法，但依旧低于DPC算法。此外，不论数据量的大小，本文算法都远低于CutPC算法的运行时间。综上得出，本文方法不仅能在 9个合成数据集上具有比较好的聚类效果，同时还能拥有较快的计算速度。3.3真实数据集实验另外，实验中还将本文方法应用在真实数据上，利用 UCI提供的真实数据集进行本文方法的实验。实验过程中将 6 种聚类算法应用在 5 个真实数据集上的聚类效果进行对比，5个真实数据集分别为iris、cancer、seeds、banknote 和 heart，5 个真实数据集的基本信息如表5所示。实验中将本文方法和 5 个对比算法应用在 5 个真实数据集上，不同方法对应5种真实数据集的参数设置如表6所示。和合成数据集一样，仍然采用聚类表36种方法应用在9个合成数据集上的Acc和NMITable 3Acc and NMI of 6 methods appliedon 9 synthetic datasets数据集D1D2D3D4D5D6D7D8D9指标AccNMIAccNMIAccNMIAccNMIAccNMIAccNMIAccNMIAccNMIAccNMIK-means0.999 00.995 30.998 10.993 30.721 90.155 40.658 00.537 20.733 70.535 20.844 40.458 10.646 00.552 20.551 70.007 70.724 60.700 6DBSCAN0.948 0