基于密度峰值算法的三支聚类.pdf

第37 卷第4期2023 年8 月Journal of Jiangsu University of Science and Technology(Natural Science Edition)D0I:10.20061/j.issn.1673-4807.2023.04.012江苏科技大学学报（自然科学版）Vol.37No.4Aug.2023基于密度峰值算法的三支聚类姜冬勤,王平心2*，杨习贝1（1.江苏科技大学计算机学院，镇江2 12 10 0）（2.江苏科技大学理学院，镇江2 12 10 0）摘要：传统的硬聚类要求聚类结果之间必须边界清晰，但在实际划分中常常会遇到信息不充分的情况，如果将对象强行划分到某一类簇，会带来较高的决策风险.为了解决这个问题，三支聚类采用核心域、边界域、琐碎域来表示每一个类簇，把不确定的对象放入边界域中延迟决策，以此降低决策风险，同时针对传统密度峰值算法需要手动选取参数且样本分配策略存在缺陷，提出了基于密度峰值算法的三支聚类，引入自然最近邻算法，自适应地获取每个点的邻居个数以此来定义样本的局部密度，然后基于三支阈值得到核心域和边界域，对于边界域中的数据，通过比较其与聚类中心的距离和密度做进一步划分.在UCI、Sy n t h e t i c 和Shape数据集上的实验结果证明：所提算法能有效提高ACC,ARI,AMI,FMI值，可以显著提升聚类效果.关键词：三支聚类；密度峰值算法；自然最近邻中图分类号：TP391Three-way clustering based on the density peak algorithmJIANG Dongqin,WANG Pingxin*,YANG Xibeil(1.School of Computer,Jiangsu University of Science and Technology,Zhenjiang 212100,China)(2.School of Science,Jiangsu University of Science and Technology,Zhenjiang 212100,China)Abstract:Traditional hard clustering requires clear boundaries between clustering results.However,in the actualdivision scenario,insufficient information is often encountered.Decision-making risk will be increased,if theobject is forcibly divided into a certain type of cluster.In order to solve this problem,three-way clustering usescore region,boundary region,and trivial region to represent a cluster.Uncertain objects are placed in theboundary domain for delayed decision-making,aiming to reduce the risk of decision-making.Simultaneously,the need to manually select parameters and the unreasonable sample allocation strategy constitutes the shortcom-ings of the traditional density peak algorithm.Based on this,a three-way clustering based on the density peak al-gorithm is proposed.First,the natural nearest neighbor algorithm is introduced to adaptively obtain the numberof neighbors of each point to define the local density of the sample.Then the core domain and boundary domainis obtained based on three thresholds.The data in the boundary domain is further divided by comparing its dis-tance and density from the cluster center.Experiments on the UCI,Synthetic and Shape datasets show that theproposed algorithm can effectively increase the value of ACC,ARI,AMI,FMI and significantly improve the clus-tering effect.Key words:three-way clustering,density peak algorithm,natural nearest neighbor传统聚类算法大多属于二支聚类，即类簇之间有着清晰的边界,但在实际应用中常常会遇到信息文献标志码：A文章编号：16 7 3-48 0 7(2 0 2 3)0 4-0 7 2-0 8不充分的情况，如果将信息不充分的数据对象强行划分到某一类簇，会造成误分类的概率增加，导致收稿日期：2 0 2 2-0 1-10基金项目：国家自然科学基金资助项目（6 2 0 7 6 111，6 17 7 30 12）；江苏省高校自然科学基金资助项目（15KJB110004）作者简介：姜冬勤（1996-），女，硕士研究生*通信作者：王平心（198 0-），男，博士，副教授，研究方向为粗糙集、粒计算.E-mail：p i n g x i n _w a n g h o t ma i l.c o m引文格式：姜冬勤，王平心，杨习贝，等.基于密度峰值算法的三支聚类J.江苏科技大学学报（自然科学版），2 0 2 3,37（4）：7 2-7 9.D0I：10.20061/j.issn.1673-4807.2023.04.012.第4期聚类精度降低.针对传统聚类方法的不足，文献1将三支决策的思想引入到聚类分析中并提出了三支聚类算法2-3.不同于传统的硬聚类，三支聚类用核心域和边界域来描述一个簇,能够更加精确的描述类簇的结构特征.基于这一框架,近年来，三支聚类研究也取得了大量的成果4-8.文献9提出了密度峰值聚类（clusteringbyfast searchandfind of density peaks，D PC)91,可以识别任意一个形状的类簇，而且可以自动地确定每个类簇的质心，克服了DBSCAN面临的不同类簇的密度差别大、邻域范围难以确定等问题.但DPC算法存在以下不足：截断距离d。需要人工设置，具有随机性；假如一个样本分配错误，就会带来后面一系列的分配错误.为了对DPC算法的优化,文献10 提出利用k-近邻来定义局部密度，且给了两种新的分配策略;文献11计算点到它的k-最近邻点的距离作为局部密度,并使用k最近邻点和模糊加权k-最近邻点依次将剩余的点进行分配;文献12 将k-最近邻引人局部密度计算中并提出了新的分配策略,提高了聚类准确度；文献13提出基于共享最近邻的DPC(SNN-DPC)算法,该算法结合共享最近邻,不仅消除了截断距离对DPC算法的影响,也避免了连带分配错误，但其算法需要人工选择k值，不可以做到自适应.基于上述问题，文中引人了自然最近邻算法，使得每个数据点的邻居数不再依赖于手动设置的参数,而是自适应的根据每个点的自然最近邻获取邻居个数，以此来确定每个点的局部密度和距离，通过决策图选取聚类中心，再融合三支决策思想，满足论文中所给判定条件归入核心域，再将剩余点分配到边界域中,最终得到三支聚类的结果,数据集上的实验结果验证了算法的综合性能，1相关工作1.1密度峰值聚类算法密度峰值算法的核心思想是聚类中心满足以下两点：聚类中心被密度比它低的近邻点包围；聚类中心之间的距离大.选取局部密度大、距最近的较大密度点的距离都很大的数据点作为聚类中心.因此DPC算法有两个待计算量为局部密度p；和数据点距离8.第i个数据点的局部密度p；为：p;=Zx(dj-d.)姜冬勤，等：基于密度峰值算法的三支聚类式中:X为示性函数,X(x)=i和j的距离;d。为截断距离，由式可以看出,p；等于分布在i的d。邻域范围内的数据点个数.第i个数据点距离是指数据点的局部密度大于pi,且与第i个数据点最近的点与该数据点之间的相对距离：S,=min dii:pj7P;式中：对于密度最高的点,则取;=maxdj具体密度峰值算法流程如下：算法1 DPC算法输入：数据集.输出：每个数据点的所属类簇.1：初始化参数：截断距离d。.2：计算任意两个数据点之间的距离；根据截断距离算出任意数据点的局部密度P;对于任意数据点计算出其距离8；以p；为横轴,以8；为纵轴构造出决策图；利用决策图，选取p；和S；都相对较大的值标记为聚类中心，选取p；低但S；相对较高的点标记为噪声点；将剩下的点划分到密度比它大且离它最近的数据点所属的簇3：输出：聚类结果.1.2自然最近邻居最近邻算法中比较常用的是k-最近邻和8-最近邻.k-最近邻是人为给定参数k,再找k个距离最小的样本点.8-最近邻是人为给定半径8,再找出每个样本点在其半径8 内的邻居个数.但这两种算法需要人工设定参数，人为因素直接影响结果，而自然最近邻很好的解决了这个问题.自然最近邻居14（natural nearest neighbor，NNN）不需要设定任何参数,依靠数据集自身特点搜索得到,在密度较大的区域的点的邻居多，反之则邻居少.该算法可以很好地反映数据集的分布特征.定义1（最近邻)NN（）代表样本点x;的r最近邻,其中r由自然最近邻搜索算法自动生成.定义2（逆近邻)RNN（;）表示样本点x;的r逆最近邻：RNN,(x,)=(x,EXIx;ENN,(x,),i+jl(3)(1)定义3（自然最近邻）NNN（x）表示样本点73xp;peL(i)对于密度最高的点,则可以取：8;=max(8,)很多数据集上的数据点分布并不均匀，通过上述计算方法，在数据点集中的区域缩短了数据点的距离S；,在数据点稀疏的区域放大了数据点之间的距离8；，考虑了每个点的邻居信息.得到每个点的p；和8.值后,生成决策图,并在图中选取p；和；都大的值作为聚类中心.定义9设x;ECI,CI为类簇中心集合,xjENNNm(cs）（x;）,如果满足下式,则归人核心域：INNNa(cg)(x,)nNNNn(a)(x,)/INNN(x,)/3选择出聚类中心后，设聚类中心点x有个自然最近邻居，样本点x是样本点；的自然最近邻居之一且未被划分到核心类簇,样本点x;的自然最近邻居个数为n，如果此时样本点x和样本点x；的共享自然邻居个数大于等于x点自然最近邻居个数的1/3,则将x,归人聚类中心x；所属类簇的核心域,反之将样本点,归为边界域.经过上述处理得到核心域和边界域，针对边界域中的数据对象的处理策略是：将其划分到和该点最近的点；在的类簇的边界域中.原则上，此类数据点是属于所属类簇的边界域，但是在计算聚类质量时,将同一类簇的核心域中数据点和边界域中数据点合并作为最终聚类结果,并在此结果集上评价姜冬勤，等：基于密度峰值算法的三支聚类聚类质量.由于边界域中的数据点存在更高概率的误分类,按照这样的计算标准,更加能证明所提出算法的优越性。基于密度峰值算法的三支聚类算法如下：算法3基于密度峰值算法的三支聚类输入：数据集输出：数据点；的所属类簇1:初始化参数：无2:计算任意两个数据点之间的距离；计算每个数据点的自然邻居NNN（x;）以及(8)该点邻居个数nb(x)；根据式(8)算出任意数据点x；的局部密度p;；根据式(9)和式(10)得到任意数据点；距离;；以p；为横轴,以8,为纵轴构造出决策图；构建决策图，选取p；和S.都大的值标记为聚类中心 CI=Co(C,),Co(C)1;取x;E CI,x,E NNNb(c)(x;),满足式(11),(9)qeL(i)(10)(11)75则;归人;所在类簇的核心域Co(;）；剩下的点归类到是它的最近邻并且密度大于它的数据点在的簇的边界域.3：输出：数据点x；的所属类簇2.2算法分析使用自然最近邻算法对DPC算法进行改进，将改进后的算法与三支聚类相结合，聚类的质量得到了进一步的保证，但三支聚类仅提供了一种进行软聚类的策略,即可以通过制定相对应的规则来规定不同数据簇的核心区域和边界区域,具体的规则实现各有不同，但都不可避免地要进行相关阈值参数选取.由专家经验可得，此阈值参数一般可设置为1/2、1/3或1/4.文中选取1/3作为三支聚类的阅值，在人工数据集Aggregation上验证不同阅值的聚类质量，以证明该参数的合理性及鲁棒性.图1显示不同阈值下的聚类结果，表1则对应着不同阅值下的性能评价结果，包括准确率（accuracy，ACC）、调整兰德指数（adjusted rand index，A R I）、调整互信息（adjusted mutual information，A M I）和FM 指数(fowlkes and mallows index,FMI).从图1中的6 个子图中可以看出，当阈值由1/2减小为1/7 时，聚类的效果由差到好再到差，即存在一个聚类效果峰值,这个峰值对应的阈值恰好为1/3.由图1(a)可以看出原本属于C3的数据对象被错误地分配到了C2,同样地，C5和C6也存76在这样的问题；观察图1（b）、（c）和（d），着眼于C3,图1(b)的聚类结果要稍逊于图1（c）,因为其在C3存在3个数据对象的误判,但在C4上,图1（b)的聚类结果要明显好于图1(c）,图1（c)在C4上存在15个点左右的误判,图1（d)相较于图1（c）,在 C3上多了3个数据对象的误判,综合看来,三者之中图1(b)更加优秀;同样地,可以看出图1(b)要优于图1(e)和(f).3025F20F1510F530r2520151053025201510江苏科技大学学报（自然科学版）生区分粒度的变化.由专家经验可得这个阈值在1/2至1/Max（n b（;）产生，通过实验证明选取1/3作为阈值具有一定的优越性和鲁棒性。2.3复杂度分析2.3.1空间复杂度分析每个数据对象到所有数据对象（包括自身）的空间复杂度，即存储距离矩阵为O（N）其中N为数据对象总个数,存储每个数据对象的自然邻居个数的空间复杂度为O（N*s u p k），s u p k 为稳定状态时的搜索次数.所以3W-DPC算法空间复杂度为O(N）,和原始密度峰值算法一样.105H1020(a)阀值为1/21020()阀值为1/42023年2.3.2时间复杂度分析301030r1510530301510f耀20(b)阀值为1/31020(d)阀值为1/530303W-DPC算法时间复杂度主要取决于：（1）每个数据对象的距离矩阵,其时间复杂度为0(N);（2）每个数据对象的自然邻居,因为将数据放人k-d树,使用了k-d进行搜索,搜索i的第r个近邻时间复杂度为O（l o g（N），因此时间复杂度为 O(supk*N*log(N);（3）局部密度p，由自然最近邻集合可知时间复杂度为0(suph*N)；（4）数据点距离8,时间复杂度为O（N）找到5图1不同三支阅值下3W-DPC在Aggregation上结果Fig.1Results of 3W-DPC on Aggregationunder different thresholds表1不同阈值聚类结果Table 1(Clustering result under different thresholds阅值AMI1/20.803 91/30.95951/40.947 51/50.941 91/60.939 51/70.939 5由表1可以看出，当阈值选取为1/3时，各项指标表现最为优异，与图1分析一致.且仔细观察可知，当阈值选取小于1/6 时，各项性能指标不会随着阈值的减小而变化.分析式（11）可得，阈值与因子NNN（x）相乘作为判定的条件，当两者相乘的结果小于1，便不会对数据集区分出粒度，式（11)的效果也就等价于如果x,与核心点x；存在交集，则将归人核心点所属类簇，虽然这样也属于是三支聚类的一种策略，但是设置的区分粒度太大,聚类效果可能不好，通过分析,结合自然邻居的特性可知，当阈值小于1/Max（n b（x），便不会产51020(e)阀值为1/630ARI0.751 70.968 30.952.70.946 90.943 20.943 210(阀值为1/7FMIACC0.913 90.958 10.975 10.984 80.962 90.973 40.958 40.970 80.955 40.968 30.955 40.968 32030中心点并将剩余点分配到其属于的类簇，时间复杂度为O（N）,所以总的时间复杂度为O（N）,与未该改进前的DPC算法相同.3实验仿真选用2 组Synthetic数据集、5组UCI数据集和4组Shape(人工)数据集17 进行实验.数据集如表24.不同的数据集有不同预处理方式，对于UCI数据集，由于该数据集中会出现不是数字或者为空的属性,也就是类别型属性，这类属性往往存在离散值问题，既想保留尽可能多的数据信息，同时也要考虑到字符数据的离散程度,所以需要将不是数字的属性进行One-hot编码，然后，进行归一化处理,使得每个维度所占比重相同.对于Shape数据集和Synthetic数据集，由于不会出现不是数字的属性，所以只进行归一化处理，表2 Synthetic数据集Table 2Synthetic dataset数据集个数A13000S15 000维度22类簇数目2015第4期数据集ZooIrisWineDermatologySegmentationGesture Phase Segmentation表4Shape数据集Table 4Shape dataset数据集个数Pathbased300R15600Aggregation788D313100数据集算法3W-DPCA1SNN-DPCDPC3W-DPCS1SNN-DPCDPCTable 6Experimental results on UCI datasets数据集算法3W-DPCZooSNN-DPCDPC3W-DPCIrisSNN-DPCDPC3W-DPCWineSNN-DPCDPC3W-DPCDermatologySNN-DPCDPC3W-DPCSegmentationSNN-DPCDPC3W-DPCGesture Phase SegmentationSNN-DPCDPC姜冬勤，等：基于密度峰值算法的三支聚类表3UCI数据集Table 3UCI dataset个数维度类簇数目10118150417813366332310191.74331维度类簇数目2321527231表5Synthetic数据集上的实验结果Table 5Experimental results on Synthetic datasets0.960 10.926 20.891 00.971 80.906 00.804 0表6 UCI数据集上的实验结果AMIARI0.889 30.812 70.768 70.796 40.74290.72220.811 60.82380.792 10.801 90.705 10.706 00.888 60.914 90.873.50.899 20.706 50.762 40.874 90.868 20.874 90.868 90.784 00.776 00.685 80.600 60.672 50.577 00.490 00.600 40.885 40.857 10.879 40.806 90.774 10.785 1774实验结果73W-DPC算法与传统DPC,SNN-DPC算法在3数据集上进行实验对比，实验结果如表5 7.3从表5 7 中的实验结果可以看出，在AMI、675AMIFMI、A CC指标上，提出的3W-DPC算法相比于SNN-DPC、D PC算法明显优秀很多.在ARI指标上,也只有 Dermatology数据集,SNN-DPC 比SNN-DPC结果稍好，其余数据集上3W-DPC算法都是比3W-DPC、D PC算法优秀.3W-DPC算法与SNN-DPC、D PC算法的聚类结果相比,有效提升了算法性能.ARI0.94250.866 40.794 20.957 70.811 30.676 9FMI0.945 30.873 60.812 10.960 50.829 30.734 3FMI0.855 60.847 50.730 60.881 90.867 30.805 50.943 50.933 00.783 50.901 50.901 00.822 10.658 90.645 70.441 30.90230.867 30.845 1ACC0.971 70.960 70.958 30.979 20.938 30.921 4ACC0.901 00.881 20.886 10.600 00.593 30.560 00.971 90.951 30.898 90.991 80.950 20.923 80.691 40.648 70.609 50.935 40.915 60.900 678数据集PathbasedR15AggregationD315结论（1）借助自然最近邻算法提出了一种基于改进的DPC算法的三支聚类.该算法首先利用自然最近邻定义共享邻居，确定DPC算法的两个待计算量：局部密度，和数据点距离8；，通过决策图得到密度峰值点，即聚类中心，解决了需要人为指定k值的不足.（2）算法融合了三支聚类,通过阈值将确定的元素划分到核心域，将不确定的元素划分到边界域延迟决策，在多组数据集上进行了实验验证,并与SNN-DPC、D PC算法进行比较，实验结果表明此方法可以提高聚类的精度以及提升算法的性能表现.（3）自然最近邻是一个新兴的邻居概念，有关定义以及应用有待完善，在后续工作中,将讨论如何利用自然最近邻更贴切的定义DPC算法的两个计算量，以及对不确定元素进行更巧妙的分配.参考文献(References)1YAO Y.Tri-level thinking:models of three-way deci-sion J.International Journal of Machine Learningand Cybernetics,2020,11:947-959.2YU H.A framework of three-way cluster analysis C/International Joint Conference on Rough Sets.Berlin:Springer,2017:300-312.3YU H,WANG X,WANG G,et al.An active three-way clustering method via low-rank matrices for multi-view data J.Information Sciences，2 0 2 0，50 7:823-839.4YU H,CHEN L Y,YAO J T,et al.A three-way clus-tering method based on an improved DBSCAN algo-江苏科技大学学报（自然科学版）表7 Shape数据集上的实验结果Table 7 Experimental results on Shape datasets算法3W-DPCSNN-DPCDPC3W-DPCSNN-DPCDPC3W-DPCSNN-DPCDPC3W-DPCSNN-DPCDPC2023年AMIARI0.870 30.910 80.774 40.732 30.504.70.463 40.976 20.963 40.972.90.959 30.945 30.936 10.962 20.970 40.903 20.875 50.854 60.756 90.955 90.935 70.945 70.913 40.926 90.883 0rithm J.Physica A:Statistical Mechanics and itsApplications,2019,535:122289.5 WANGPX,YAOYY.CE3:Athree-way clusteringmethod based on mathematical morphology J.Knowledge-Based Systems,2018,155:54-65.6施虹，杨鑫，王平心.改进的均值插补不完备数据聚类算法J.江苏科技大学学报（自然科学版），2020,34(4):51-56.SHI Hong,YANG Xin,WANG Pingxin.An improvedmean imputation clustering algorithm for incomplete da-ta J.Journal of Jiangsu University of Science andTechnology（Na t u r a l Sc i e n c e Ed i t i o n),2 0 2 0,34(4):51-56.(in Chinese)7YU H,CHEN L Y,YAO J T.A three-way densitypeak clustering method based on evidence theory J.Knowledge-Based Systems,2021,211:106532.8凡嘉琛，王平心，杨习贝基于三支决策的密度敏感谱聚类J山东大学学报（理学版），2 0 2 2，57(11):10-17.FAN Jiachen,WANG Pingxin,YANG Xibei.Density-sensitive spectral clustering based on three-way deci-sion J.Journal of Shandong University(Natural Sci-ence)2022,57(11):10-17.(in Chinese)9RODRIGUEZ A,LAIO A.Clustering by fast searchand find of density peaks J.Science,2014,344(6191):1492.10谢娟英，高红超，谢维信.K近邻优化的密度峰值快速搜索聚类算法J.中国科学：信息科学,2 0 16,46(2):258-280.XIE Juanying,GAO Hongchao,XIE Weixin.K-nea-rest neighbors optimized clustering algorithm by fastsearch and finding the density peaks of a dataset J.SCIENTIA SINICA Informationis，2 0 16，46（2):258-280.(in Chinese)FMI0.940 60.822 60.661 10.965 80.961 90.940 20.97680.902 80.810 40.937 80.916 20.887 4ACC0.970 00.896 70.783 30.981 70.980 00.970 00.986 00.939 10.927 70.958 10.956 20.956 8第4期11XIE J,JIANG W.An adaptive clustering algorithm byfinding density peaks C/Pacific Rim InternationalConference on Artificial Intelligence.Berlin:Springer,2018:317325.12 薛小娜，高淑萍，彭弘铭，等.结合K近邻的改进密度峰值聚类算法J.计算机工程与应用,2 0 18,54(7):36-43.XUE Xiaona,GAO Shuping,PENG Hongming,et al.Improved density peaks clustering algorithm combiningK-Nearest Neighbors J.Computer Engineering andApplications,2018,54(7):36-43.(in Chinese)13 LIU R,WANG H,YU X.Shared-nearest-neighbor-based clustering by fast search and find of densitypeaksJ.Information Sciences,2018,450:200-226.姜冬勤，等：基于密度峰值算法的三支聚类14 1HUANG J,ZHU Q,YANG L,et al.A non-parameteroutlier detection algorithm based on natural neighborJ.Knowledge Based Systems,2016,92:71-77.15 YAO Y Y.The superiority of three-way decisions inprobabilistic rough set models J.Information Sci-ences,2011,181(6):1080-1096.16PASI F,SAMI S.K-means properties on six clusteringbenchmark datasets J.Applied Intelligence,2018,48:4743-4759.17 MAULIK U,BANDYOPADHYAY S.Performance e-valuation of some clustering algorithms and validity in-dicesJ.IEEE Transactions on Pattern Analysis andMachine Intelligence,2002,24(12):1650-1654.（责任编辑：曹莉）79