面向密度分布不均数据的加权逆近邻密度峰值聚类算法.pdf

DOI:10.11992/tis.202212015网络出版地址:https:/ 信息工程学院,江西 南昌 330099;2.南昌工程学院 南昌市智慧城市物联感知与协同计算重点实验室,江西 南昌 330099;3.华中科技大学 人工智能与自动化学院,湖北 武汉 430074）摘 要：针对密度分布不均数据，密度峰值聚类算法易忽略类簇间样本的疏密差异，导致误选类簇中心；分配策略易将稀疏区域的样本误分到密集区域，导致聚类效果不佳的问题，本文提出一种面向密度分布不均数据的加权逆近邻密度峰值聚类算法。该算法首先在局部密度公式中引入基于 sigmoid 函数的权重系数，增加稀疏区域样本的权重，结合逆近邻思想，重新定义了样本的局部密度，有效提升类簇中心的识别率；其次，引入改进的样本相似度策略，利用样本间的逆近邻及共享逆近邻信息，使得同一类簇样本间具有较高的相似度，可有效改善稀疏区域样本分配错误的问题。在密度分布不均、复杂形态和 UCI 数据集上的对比实验表明，本文算法的聚类效果优于 IDPC-FA、FNDPC、FKNN-DPC、DPC 和 DPCSA 算法。关键词：密度峰值聚类；密度分布不均；逆近邻；共享逆近邻；样本相似度；局部密度；分配策略；数据挖掘中图分类号：TP301 文献标志码：A 文章编号：16734785(2024)01016511中文引用格式：吕莉,陈威,肖人彬,等.面向密度分布不均数据的加权逆近邻密度峰值聚类算法 J.智能系统学报,2024,19(1):165175.英文引用格式：LYU Li,CHEN Wei,XIAO Renbin,et al.Density peak clustering algorithm based on weighted reverse nearestneighbor for uneven density datasetsJ.CAAI transactions on intelligent systems,2024,19(1):165175.Density peak clustering algorithm based on weighted reverse nearestneighbor for uneven density datasetsLYU Li1,2，CHEN Wei1,2，XIAO Renbin3，HAN Longzhe1,2，TAN Dekun1,2(1.School of Information Engineering,Nanchang Institute of Technology,Nanchang 330099,China;2.Nanchang Key Laboratory ofIoT Perception and Collaborative Computing for Smart City,Nanchang Institute of Technology,Nanchang 330099,China;3.Schoolof Artificial Intelligence and Automation,Huazhong University of Science and Technology,Wuhan 430074,China)Abstract:For data with uneven density distribution,the density peak clustering algorithm disregards the sparsity differ-ence among intercluster samples,causing an inaccurate selection of the cluster center.Moreover,the allocation strategyeasily divides the samples in sparse areas into dense areas by mistake,leading to a poor clustering effect.Therefore,thedensity peak clustering algorithm based on the weighted reverse nearest neighbor(DPC-WR)against datasets with un-even density distribution is proposed in this paper.First,the weight coefficient based on the sigmoid function is intro-duced to the local density formula to increase the weight of samples in sparse areas.Combined with the concept of re-verse nearest neighbor,the local density of samples is then redesigned to improve the recognition rate of cluster centerseffectively.Second,an improved sample similarity strategy is introduced,which utilizes reverse nearest neighbors andshares this neighbors information between samples to increase the similarity of samples in the same cluster.This effect-ively solves the problem of sample allocation error in sparse areas.Experiments on uneven density distribution,com-plex morphology,and UCI datasets show that the clustering effect of the DPC-WR algorithm outperforms that of IDPC-FA,FNDPC,FKNN-DPC,DPC,and DPCSA algorithms.Keywords:density peak clustering;uneven density distribution;reverse nearest neighbor;shared reverse nearest neigh-bor;sample similarity;local density;distribution strategy;data mining 聚类是数据分析中一种重要的无监督学习方法，致力于揭示看似杂乱无章的未知数据背后隐藏的内在属性和规律，为决策提供支持，并已成收稿日期：20221213.网络出版日期：20230802.基金项目：国家自然科学基金项目(62066030);江西省重点研发计划项目(20192BBE50076，20203BBGL73225);江西省教育厅科技项目(GJJ190958).通信作者：吕莉.E-mail：.第 19 卷第 1 期智能系统学报Vol.19 No.12024 年 1 月CAAI Transactions on Intelligent SystemsJan.2024智能系统学报编辑部版权所有功应用于许多领域，如图像分析1、模式识别2、社会网络挖掘 3、市场统计分析 4 和医学研究5等。传统的聚类算法分为基于划分的6、基于层次的7、基于网格的8、基于模型的9和基于密度的10聚类算法。K-means11是最著名的划分聚类算法，通过多次迭代获得最优聚类中心。K-means 收敛速度快，对大规模数据集的处理效率高，但该算法的性能依赖于初始聚类中心的选择，且对噪声点和异常值敏感。BIRCH(balancediterative reducing and clustering using hierarchies)12是一种基于层次的聚类算法，利用聚类特征树自底向上进行聚类。BIRCH 聚类速度快，能识别噪声点，但不适用于高维和非凸数据。CLIQUE(clustering in quest)13是一种基于网格的聚类算法，把数据空间分为不同的网格，将样本对应到网格中，并进行密度的计算。CLIQUE 适用于高维和大规模数据集，但该算法聚类的准确度较低。EM(expectation maximization)14是一种基于模型的聚类算法，根据极大后验概率估计寻找样本的概率模型参数进行聚类。该算法计算结果稳定、准确，但对初始化数据敏感。DBSCAN(dens-ity-based spatial clustering of applications withnoise)15是典型的基于密度的聚类算法，它将样本分为核心点和噪声点，根据密度可达将核心点聚合到同一个集群中。该算法可以识别任意形状的稠密数据集且对数据集中的异常点不敏感，但不能处理密度差异过大的数据。2014 年，Science 发表了通过快速搜索和寻找密度峰值聚类16(clustering by fast search and find ofdensity peaks,DPC)算法。由于其新颖的设计理念和强大的性能，使得基于密度的聚类算法受到更广泛的关注和应用。DPC 算法基于两点假设：聚类中心周围的样本的局部密度相对较低；不同聚类中心间的距离相对较远。DPC 算法计算过程无需迭代，只需预先设定一个参数来识别聚类中心，但 DPC 算法仍有一些缺点：1）算法局部密度无法准确识别各类簇间样本的疏密差异，易造成类簇中心的误判；2）虽然 DPC 中的分配规则非常有效，但是当聚类过程出现某一个样本被错误分配，就会出现多米诺骨牌效应。针对 DPC 算法易出现类簇中心选取错误的问题，吕莉等17提出二阶 K 近邻和多簇合并的密度峰值聚类算法(density peaks clustering withsecond-order k-nearest neighbors and multi-clustermerging,DPC-SKMM)。DPC-SKMM 算法提出最小二阶 K 近邻的概念，根据 K 近邻和二阶 K 近邻信息重新定义局部密度，凸显聚中心与非聚类中心的密度差异。Sun 等18提出了基于最近邻优化分配策略的自适应密度峰值聚类算法(nearestneighbors-based adaptive density peaks clustering withoptimized allocation strategy,NADPC)。NADPC 算法提出了候选簇心和相对密度的概念，根据候选聚类中心的相对密度和高密度最近邻距离，计算聚类中心的可信度，从而选择聚类中心。赵嘉等19提出了 K 近邻和加权相似性的密度峰值聚类算法(density peaks clustering algorithm with k-nearest neighbors and weighted similarity,DPC-KWS)。DPC-KWS 算法从样本的 K 近邻信息出发，重新定义了局部密度，调整了不同类簇中局部密度的大小。针对分配规则出现的问题，吴润秀等20提出基于相对密度估计和多簇合并的密度峰值聚类算法(density peaks clustering based on relative densityestimating and multi cluster merging,DPC-RD-MCM)。DPC-RD-MCM 算法重新定义了微簇间相似性度量准则，通过多簇合并策略得到最终聚类结果，避免了分配错误连带效应。Ding 等21提出了基于中心和邻居的社区检测算法(communitydetection by propagating the label of center,DCN)。DCN 算法根据样本的邻居传播标签，提出了标签传播的多重策略，有效解决了 DPC 分配策略的多米诺效应。赵嘉等22提出面向流形数据的测地距离与余弦互逆近邻密度峰值聚类算法(densitypeaks clustering algorithm based on geodesic distanceand cosine mutual reverse nearest neighbors for mani-fold datasets,DPC-GDCN)。DPC-GDCN 算法将互逆近邻和余弦相似性相结合，得到基于余弦互逆近邻的样本相似度矩阵，为流形类簇准确分配样本。上述算法均有效提高了 DPC 算法的聚类效果，但忽略了样本间的分布特征，无法对密度分布不均等特定数据集取得较好的聚类效果。因此，本文提出了面向密度分布不均数据的加权逆近邻密度峰值聚类算法(density peak clustering al-gorithm based on weighted reverse nearest neighborfor uneven density datasets,DPC-WR)。DPC-WR 算法充分利用了逆近邻和共享逆近邻信息，算法的主要创新点如下：1）结合 sigmoid 函数及逆近邻思想重新定义了局部密度，平衡了样本间疏密程度的差异，提高了类簇中心的识别率；2）在样本分配策略中，引入逆近邻及共享逆近邻信息，避第 19 卷智能系统学报166 免了稀疏区域样本的错误分配，提高了聚类效果。1 DPC 算法xiiiDPC 是一种高效的密度峰值聚类算法，可以快速找到聚类中心，对多种聚类任务具有良好的适应性。该算法基于聚类中心密度大于邻域密度，聚类中心间的距离相对较远的思想，提出了两种描述样本的密度和距离的方法，即局部密度 和相对距离。X=x1,x2,xnXxini=1设有数据集。对数据集中的每个样本，样本间的欧氏距离为dij=xixj(1)i局部密度 有两种定义方式：i=i,j(dijdc)(2)(x)=1,x jmaxj(dij),其他(4)ii类簇中心由决策图确定，以局部密度为横坐标，相对距离 为纵坐标，建立决策图。理想情况下，聚类中心选取为密度较高且相距较远的样本。定义如下：i=ii(5)nn最后，选取前 个较大的值作为聚类中心，为最终类簇数。2 DPC-WR 算法在聚类算法中，K 近邻和逆近邻在表征密度时起着重要作用。K 近邻能准确反映样本在空间中的局部分布特征。而逆近邻基于全局视角检查它的邻域，数据分布的变化会对样本的逆近邻造成影响，使得算法更容易识别聚类中心和提升算法聚类性能。因此，本文引入逆近邻和共享逆近邻信息，重新定义了局部密度，设计了样本相似度策略，充分考虑了样本的总体分布，使样本的局部一致性和全局一致性得到较好的均衡。2.1 加权逆近邻的局部密度xi,xj Xxixjxjxi定义 1逆近邻23。设样本，在的K近邻集中，那么是 的逆近邻，具体定义如下：RNN(xi)=xj X?xi KNN(xj)(6)xixjij定义 2 隶属度。样本和的隶属度定义如下：ij=expd2ijk1+|R(i)|(7)k|R(i)|xi其中：为样本的近邻数；表示样本的逆近邻数，该值越大，该点的隶属度越大。定义 3加权逆近邻的局部密度。局部密度定义如下：i=jRNN(i)ijij(8)权重系数：ij=RNN(xi,xj)1+exp(|R(i)|)(9)RNN(xi,xj)=1 ,xi RNN(xj)且 xi,xj0 ,其他11+exp(x)其中：为 sigmoid 函数，x 为实数。类簇密度不同时，数据稠密区域与数据稀疏区域的样本对聚类中心选取的贡献程度是不同的。因此，处理密度分布不均数据时，通过引入权重对样本的贡献进行处理，可以达到良好的均衡效果。本文以样本的逆近邻数作为衡量密度的重要指标，引入 sigmoid 函数，对不同类簇中的样本进行权重调整。ijx式(9)中为权重系数，它在 sigmoid 函数的基础上进行重构，分母部分以样本的逆近邻数替代了原函数的变量 值，分子部分采用逆近邻代替实数值，使密度分布不均数据在不同区域具有辨识度。从函数可知，随着逆近邻数逐渐增加，其函数值趋近于 1，说明位于高密度区域的样本所加的权重近似于 1。对于较高密度的样本，被选为聚类中心的概率较大，此时逆近邻数起到关键的作用。当逆近邻数不断减少直至为 0 时，样本的权重将会从 1 发生非线性变化减少到 0.5，这不仅考虑到各样本间细微的影响，还提高了聚类中心与非聚类中心的区分，使式(7)的隶属度定义更为合理。2.2 逆近邻和共享逆近邻的分配策略xiRNN(xi)xjRNN(xj)xixj定义 4共享逆近邻。设样本的逆近邻集为，的逆近邻集为，样本与的共享逆近邻定义如下所示：(xi,xj)=xi X,xj X?RNN(xi)RNN(xj)(10)ij定义 5逆近邻和共享逆近邻的样本邻近度。通过样本间的逆近邻信息，定义了邻近度，其定义如下：167吕莉，等：面向密度分布不均数据的加权逆近邻密度峰值聚类算法第 1 期 ij=edij,xj RNN(xi)edijmax(d),xj RNN(xi)(11)max(d)X其中表示数据集中样本间欧氏距离的最大值。xjxixjxi式(11)中第一行表示当样本位于样本的逆近邻范围内时所赋予的邻近度；第二行表示当样本不处于样本的逆近邻范围时，由于样本间的紧密程度低，若将值赋 0，易忽略未在范围内的样本的细微影响，故其邻近度在逆近邻范围的基础上除以最大距离所得。xixj定义 6样本相似度。基于逆近邻和共享逆近邻，得到样本和的相似度：S(xi,xj)=?(xi,xj)?+RNN(xi,xj)(xi,xj)(12)?(xi,xj)?(xi,xj)(xi,xj)式中：表示集合中样本的个数，的定义如下：(xi,xj)=1kni,j=1(xi,xj)(13)(xi,xj)反映了样本所处空间的紧密程度，分子部分为每个样本的相似度之和，分母部分为归一化参数。式(12)考虑了样本本身及其共享逆近邻样本在定义样本间相似度方面起着重要的作用，因此，只有当样本之间存在逆近邻或共享逆近邻时，才存在相似性。2.3 算法步骤X=xini=1k输入数据集，近邻数C输出聚类结果1）数据归一化；2）计算数据集样本间的欧氏距离；ii3）根据式(8)和式(4)分别计算各样本的局部密度和相对距离；i4）根据式(5)计算各样本的决策值并选取聚类中心；5）根据式(12)计算基于逆近邻和共享逆近邻的样本相似度并构建相似度矩阵；6）对于所有已分配的样本，找到相似度最高的未分配样本并将其分配到已分配样本所在的簇中；7）若所有已分配样本与未分配样本间的相似度为 0，转至步骤 8），否则转至步骤 6）；8）若还存在未分配的样本，则按 DPC 算法分配策略分配；9）输出聚类结果。2.4 算法复杂度分析n kO(n2)设样本规模为，为近邻数。DPC 算法的时间复杂度为24。DPC-WR 算法的时间复杂度主要由以下 6 个部分组成：1）计算样本间距离O(n2)O(n)O(kn)O(n2)O(n2)O(n2)O(n2)O(n2logn)O(n2logn)矩阵的复杂度；2）计算样本的局部密度，包括计算样本间的 K 近邻和样本间的逆近邻与逆近邻数，前者复杂度为，后者为和；3）计算样本相对距离的复杂度；4）计算样本决策值的复杂度；5）计算样本的共享逆近邻与邻近度的复杂度；6）计算样本最坏分配情况的复杂度。综上，DPC-WR 算法的时间复杂度为。3 实验结果与分析 3.1 实验设置kdc为验证 DPC-WR 算法的性能，本文在密度分布不均数据集、复杂形态数据集和 UCI 真实数据集上进行实验。将 DPC-WR 算法与 IDPC-FA25、FNDPC26、FKK-DPC20、DPC16和 DPCSA27算法进行比较。其中，IDPC-FA、DPCSA 和 DPC 算法由原作者提供，FNDPC 和 FKNN-DPC 算法参照原文献编程实现。除了 DPCSA 和 IDPC-FA 无需对参数调优外，其余算法均需要调整参数。DPC-WR 和 FKNN-DPC 算法参数 值的选取是 150 之间的最优值；DPC 算法的截断距离的选取在0.1%5%，步长为 0.1%；FNDPC 算法参数 的选取在 0.011，步长为 0.01。实验环境为Win10 64 bit操作系统，AMD Ryzen 7 5800H with Radeon Graph-ics 3.20 GHz 处理器，16.0GB 内存。本文采用调整互信息（adjusted mutual inform-ation,AMI）28、Fowlkes-Mallows 指数（fowlkes-mallows index,FMI）28和调整兰德系数（adjustedrand index,ARI）29对聚类效果进行评价，其中，3 个指标的最佳结果都为 1，各指标值接近 1 的程度越高，表明聚类结果越好。3.2 密度分布不均数据集的实验结果与分析本文选取了 6 个不同规模的密度分布不均数据集进行实验，其基本特征如表 1 所示。表 1 密度分布不均数据集的基本特征Table 1 Basic characteristics of datasets with uneven dens-ity distribution 数据集样本规模维度类簇数Jain37322Twomoons1 50222Cmc1 00223Ring1 20022LineBlobs26623Ls1 74126 表 2 给出了 6 种算法在密度分布不均数据集上的聚类结果，其中最优结果以粗体表示，“Arg-”第 19 卷智能系统学报168 表示各算法的最优参数取值。“”表示不含参数。DPC-WR 算法在 6 个数据集上均获得最佳的聚类效果。IDPC-FA 算法对 Jain 和 LineBlobs具有较好的聚类效果，对其他数据集的聚类效果较差。FKNN-DPC 算法对 Cmc 和 LineBlobs 数据集聚类效果较好，对其他数据集聚类效果不佳。DPCSA 算法仅对 LineBlobs 数据集具有较好的聚类效果。FNDPC 和 DPC 算法在 6 个数据集上的聚类性能均低于 DPC-WR 和 FKNN-DPC 算法。表 2 6 种算法在密度分布不均数据集上的聚类结果Table 2 Clustering results of six algorithms on datasetswith uneven density distribution 算法JainAMIARIFMIArg-DPC-WR1.000 01.000 01.000 024IDPC-FA1.000 01.000 01.000 0FNDPC0.596 10.725 70.905 10.47FKNN-DPC0.709 20.822 40.935 943DPC0.618 30.714 60.881 90.8DPCSA0.216 70.044 20.592 4算法TwomoonsAMIARIFMIArg-DPC-WR1.000 01.000 01.000 039IDPC-FA0.517 10.610 60.845 8FNDPC1.000 01.000 01.000 00.12FKNN-DPC1.000 01.000 01.000 077DPC0.667 10.762 10.900 54.7DPCSA0.364 70.274 60.660 7算法CmcAMIARIFMIArg-DPC-WR1.000 01.000 01.000 020IDPC-FA0.809 30.842 10.902 7FNDPC0.809 30.842 10.902 70.28FKNN-DPC1.000 01.000 01.000 049DPC0.385 70.266 10.537 75DPCSA0.665 60.576 10.745 4算法RingAMIARIFMIArg-DPC-WR1.000 01.000 01.000 04IDPC-FA0.133 30.088 60.636 2FNDPC0.027 60.010 40.656 60.01FKNN-DPC0.570 20.590 00.800 524DPC0.207 30.181 50.643 10.06DPCSA0.636 20.672 10.838 7 续表 2算法LineBlobsAMIARIFMIArg-DPC-WR1.000 01.000 01.000 04IDPC-FA1.000 01.000 01.000 0FNDPC0.779 40.717 90.814 80.11FKNN-DPC1.000 01.000 01.000 07DPC0.837 50.823 70.884 24.2DPCSA1.000 01.000 01.000 0算法LsAMIARIFMIArg-DPC-WR1.000 01.000 01.000 040IDPC-FA0.707 60.627 40.732 5FNDPC0.756 40.689 80.780 80.37FKNN-DPC0.871 90.817 90.873 548DPC0.766 50.689 40.777 90.91DPCSA0.725 20.599 90.712 9 Friedman 检验30是利用秩实现对多个总体分布是否存在显著差异的非参数检验方法。将对比算法进行检验可以更准确地反映算法间评价指标的差异，秩均值越高则算法的聚类效果越优。从表 3 可以发现，在密度分布不均数据集上聚类评价指标 AMI、ARI 和 FMI 的秩均值排名中，DPC-WR 算法都位列第 1，且秩均值都大于 5.4。表 3 6 种算法在密度分布不均数据集上的秩均值Table 3 Rank mean of the six algorithms on the unevenlydistributed density datasets AMIARIFMI算法秩均值算法秩均值算法秩均值DPC-WR5.42DPC-WR5.42DPC-WR5.42IDPC-FA3.08IDPC-FA3.25IDPC-FA3.08FNDPC2.58FNDPC2.92FNDPC3.25FKNN-DPC4.67FKNN-DPC4.67FKNN-DPC4.67DPC2.67DPC2.33DPC2.17DPCSA2.58DPCSA2.42DPCSA2.42 由于篇幅所限，本文选取了 1 个典型的密度分布不均数据集。图 1 给出了 DPC-WR、IDPC-FA、FNDPC、FKNN-DPC、DPC 和 DPCSA 算法在Jain 数据集上的聚类结果。图中不同的颜色代表不同的类簇，类簇中心用“六角星”表示。Jain 数据集由 2 个稠密程度不同的新月形类簇构成。从图 1 可知，DPC-WR 和 IDPC-FA 算法充分考虑了样本间的密度差，能准确地找到类簇中心；FNDPC 和 FKNN-DPC 算法虽然找到了正确的类簇中心，但样本分配策略存在错误，导致稀疏类簇样本的错误分配；DPC 和 DPCSA 算法没有找到正确的聚类中心，导致聚类效果不佳。169吕莉，等：面向密度分布不均数据的加权逆近邻密度峰值聚类算法第 1 期 3.3 复杂形态数据集的实验结果与分析复杂形态数据集是指具有多尺度、簇类形状多样等结构的数据集。本文选取了 6 个复杂形态的数据集，其基本特征如表 4 所示。表 5 给出了6 种算法在复杂形态数据集上的聚类结果。从表 5 可知，DPC-WR 和 IDPC-FA 算法比其他对比算法的聚类结果更优，都存在 4 个聚类效果较好的数据集。从整体来看，DPC-WR 算法的聚类效果最佳，具体表现在 Flame、R15、Sticks 和 Path-based 数据集。表 4 复杂形态数据集的基本特征Table 4 Basic characteristics of complex 数据集样本规模维度类簇数Flame24022R15600215Aggregation78827D313 100231Sticks51224Pathbased30023 表 6 为 6 种算法在 6 个复杂形态数据集上评价指标的秩均值。从表 6 可以发现，DPC-WR 算法在 AMI、ARI 和 FMI 评价指标的秩均值中位列第一，其次是 IDPC-FA 算法，然后是 FNDPC算法。表 5 6 种算法在复杂形态数据集上的聚类结果Table 5 Clustering results of six algorithms on complexmorphological datasets 算法FlameAMIARIFMIArg-DPC-WR1.000 01.000 01.000 01IDPC-FA1.000 01.000 01.000 0FNDPC1.000 01.000 01.000 00.13FKNN-DPC0.926 70.966 70.984 55DPC1.000 01.000 01.000 02.8DPCSA1.000 01.000 01.000 0算法R15AMIARIFMIArg-DPC-WR0.993 80.992 80.993 332IDPC-FA0.993 80.992 80.993 3FNDPC0.993 80.992 80.993 30.03FKNN-DPC0.993 80.992 80.993 327DPC0.993 80.992 80.993 30.6DPCSA0.988 50.985 70.986 6算法AggregationAMIARIFMIArg-DPC-WR0.992 20.995 60.996 612IDPC-FA1.000 01.000 01.000 0FNDPC0.986 40.991 30.993 20.02FKNN-DPC0.990 50.994 90.996 020DPC0.992 20.995 60.996 64DPCSA0.953 70.958 10.967 3 0.20.40.60.81.0 x(a)DPC-WR00.20.40.60.81.0y0.20.40.60.81.0 x(b)IDPC-FA 00.20.40.60.81.0y0.20.40.60.81.0 x(c)FNDPC00.20.40.60.81.0y0.20.40.60.81.0 x(d)FKNN-DPC 00.20.40.60.81.0y0.20.40.60.81.0 x(e)DPC00.20.40.60.81.0y0.20.40.60.81.0 x(f)DPCSA00.20.40.60.81.0y 图 1 6 种算法在 Jain 数据集上的聚类结果Fig.1 The clustering results of 6 algorithms on Jain dataset第 19 卷智能系统学报170 续表 5算法D31AMIARIFMIArg-DPC-WR0.961 70.946 50.948 250IDPC-FA0.957 50.940 20.942 1FNDPC0.955 50.936 40.938 50.04FKNN-DPC0.965 80.952 20.953 723DPC0.955 40.936 50.938 50.7DPCSA0.955 20.935 30.937 4算法SticksAMIARIFMIArg-DPC-WR1.000 01.000 01.000 03IDPC-FA1.000 01.000 01.000 0FNDPC1.000 01.000 01.000 00.22FKNN-DPC1.000 01.000 01.000 07DPC0.809 40.753 40.823 52DPCSA0.763 40.636 00.744 3算法PathbasedAMIARIFMIArg-DPC-WR0.940 10.959 00.972 75IDPC-FA0.844 20.859 30.906 7FNDPC0.575 10.506 70.706 50.01FKNN-DPC0.930 50.949 90.966 59DPC0.521 20.471 70.666 43.8DPCSA0.707 30.613 30.751 1 表 6 6 种算法在复杂形态数据集上的秩均值Table 6 Rank mean of 6 algorithms on complex morpholo-gical datasets AMIARIFMI算法秩均值算法秩均值算法秩均值DPC-WR4.67DPC-WR4.67DPC-WR4.67IDPC-FA4.42IDPC-FA4.42IDPC-FA4.42FNDPC3.25FNDPC3.08FNDPC3.17FKNN-DPC3.92FKNN-DPC3.92FKNN-DPC3.92DPC2.92DPC3.08DPC3.00DPCSA1.83DPCSA1.83DPCSA1.83 3.4 UCI 数据集的实验结果与分析UCI 数据集又称真实数据集，它是一个常用的标准测试数据集。为了进一步验证 DPC-WR 算法的有效性，本文选取了 8 个真实数据集，对 6 种算法进行实验。其中测试的数据集包括Iris、Wine、Seeds、Ecoli、Inonsphere、Libras、Derma-tology 和 Wdbc。表 7 给出了各数据集的基本特征。表 8 为 6 种算法在 UCI 数据集上的聚类效果。从表 8 可以发现，处理 Seeds 数据集时，DPC-WR算法的聚类效果不及 IDPC-FA、FKNN-DPC 和 DPC算法。处理 Inonsphere 数据集时，DPC-WR 算法的聚类效果低于 FKNN-DPC 算法。处理 Dermato-logy 数据集时，DPC-WR 算法的聚类效果比 DPC-SA 算法好，但略逊于其他算法。剩余的 Iris、Wine、Ecoli、Libras 和 Wdbc 数据集，DPC-WR 算法的聚类效果都优于其他算法。表 7 UCI 数据集的基本特征Table 7 Basic characteristics of UCI datasets 数据集样本规模维度类簇数Iris15043Wine178133Seeds21073Ecoli33688Inonsphere351342Libras3609015Dermatology366336Wdbc569302 表 8 6 种算法在 UCI 数据集上的聚类结果Table 8 Clustering results of six algorithms on UCI data-sets 算法IrisAMIARIFMIArg-DPC-WR0.897 10.909 30.935 69IDPC-FA0.862 30.885 70.923 3FNDPC0.883 10.903 80.935 50.11FKNN-DPC0.883 10.903 80.935 522DPC0.860 60.885 70.923 30.2DPCSA0.883 10.903 80.935 5算法WineAMIARIFMIArg-DPC-WR0.871 60.897 50.931 944IDPC-FA0.767 50.771 30.847 8FNDPC0.789 80.802 50.868 60.26FKNN-DPC0.848 10.883 90.922 98DPC0.706 50.672 40.783 52DPCSA0.748 00.741 40.828 3算法SeedsAMIARIFMIArg-DPC-WR0.716 10.763 50.841 67IDPC-FA0.729 90.767 00.844 4FNDPC0.713 60.754 50.836 10.07FKNN-DPC0.775 70.802 40.868 2