基于密度峰值算法的三支聚类.pdf
《基于密度峰值算法的三支聚类.pdf》由会员分享,可在线阅读,更多相关《基于密度峰值算法的三支聚类.pdf(8页珍藏版)》请在咨信网上搜索。
1、第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)摘要:传统的硬聚类要求聚类结果之间必须边界清晰,但在实际划分中常常会遇到信息不充分的情况,如果将对象
2、强行划分到某一类簇,会带来较高的决策风险.为了解决这个问题,三支聚类采用核心域、边界域、琐碎域来表示每一个类簇,把不确定的对象放入边界域中延迟决策,以此降低决策风险,同时针对传统密度峰值算法需要手动选取参数且样本分配策略存在缺陷,提出了基于密度峰值算法的三支聚类,引入自然最近邻算法,自适应地获取每个点的邻居个数以此来定义样本的局部密度,然后基于三支阈值得到核心域和边界域,对于边界域中的数据,通过比较其与聚类中心的距离和密度做进一步划分.在UCI、Sy n t h e t i c 和Shape数据集上的实验结果证明:所提算法能有效提高ACC,ARI,AMI,FMI值,可以显著提升聚类效果.关键词
3、:三支聚类;密度峰值算法;自然最近邻中图分类号: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,Chi
4、na)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 t
5、his 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 unreaso
6、nable 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 eac
7、h 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 t
8、hat 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不充分的
9、情况,如果将信息不充分的数据对象强行划分到某一类簇,会造成误分类的概率增加,导致收稿日期: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
10、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面临
11、的不同类簇的密度差别大、邻域范围难以确定等问题.但DPC算法存在以下不足:截断距离d。需要人工设置,具有随机性;假如一个样本分配错误,就会带来后面一系列的分配错误.为了对DPC算法的优化,文献10 提出利用k-近邻来定义局部密度,且给了两种新的分配策略;文献11计算点到它的k-最近邻点的距离作为局部密度,并使用k最近邻点和模糊加权k-最近邻点依次将剩余的点进行分配;文献12 将k-最近邻引人局部密度计算中并提出了新的分配策略,提高了聚类准确度;文献13提出基于共享最近邻的DPC(SNN-DPC)算法,该算法结合共享最近邻,不仅消除了截断距离对DPC算法的影响,也避免了连带分配错误,但其算法需要
12、人工选择k值,不可以做到自适应.基于上述问题,文中引人了自然最近邻算法,使得每个数据点的邻居数不再依赖于手动设置的参数,而是自适应的根据每个点的自然最近邻获取邻居个数,以此来确定每个点的局部密度和距离,通过决策图选取聚类中心,再融合三支决策思想,满足论文中所给判定条件归入核心域,再将剩余点分配到边界域中,最终得到三支聚类的结果,数据集上的实验结果验证了算法的综合性能,1相关工作1.1密度峰值聚类算法密度峰值算法的核心思想是聚类中心满足以下两点:聚类中心被密度比它低的近邻点包围;聚类中心之间的距离大.选取局部密度大、距最近的较大密度点的距离都很大的数据点作为聚类中心.因此DPC算法有两个待计算量
13、为局部密度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
14、;对于任意数据点计算出其距离8;以p;为横轴,以8;为纵轴构造出决策图;利用决策图,选取p;和S;都相对较大的值标记为聚类中心,选取p;低但S;相对较高的点标记为噪声点;将剩下的点划分到密度比它大且离它最近的数据点所属的簇3:输出:聚类结果.1.2自然最近邻居最近邻算法中比较常用的是k-最近邻和8-最近邻.k-最近邻是人为给定参数k,再找k个距离最小的样本点.8-最近邻是人为给定半径8,再找出每个样本点在其半径8 内的邻居个数.但这两种算法需要人工设定参数,人为因素直接影响结果,而自然最近邻很好的解决了这个问题.自然最近邻居14(natural nearest neighbor,NNN)不需要
15、设定任何参数,依靠数据集自身特点搜索得到,在密度较大的区域的点的邻居多,反之则邻居少.该算法可以很好地反映数据集的分布特征.定义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;,考虑了每个
16、点的邻居信息.得到每个点的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;所属类簇的核心域,反之将样本点,归为边界域.经过上述处理得到核心域和边界域,针对边
17、界域中的数据对象的处理策略是:将其划分到和该点最近的点;在的类簇的边界域中.原则上,此类数据点是属于所属类簇的边界域,但是在计算聚类质量时,将同一类簇的核心域中数据点和边界域中数据点合并作为最终聚类结果,并在此结果集上评价姜冬勤,等:基于密度峰值算法的三支聚类聚类质量.由于边界域中的数据点存在更高概率的误分类,按照这样的计算标准,更加能证明所提出算法的优越性。基于密度峰值算法的三支聚类算法如下:算法3基于密度峰值算法的三支聚类输入:数据集输出:数据点;的所属类簇1:初始化参数:无2:计算任意两个数据点之间的距离;计算每个数据点的自然邻居NNN(x;)以及(8)该点邻居个数nb(x);根据式(8
18、)算出任意数据点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算法进行改进,将改进后的算法与三支聚类相结合,聚类的质量得到了进一步的保证,但三支聚类仅提供了一种进行软聚类的策略,即
19、可以通过制定相对应的规则来规定不同数据簇的核心区域和边界区域,具体的规则实现各有不同,但都不可避免地要进行相关阈值参数选取.由专家经验可得,此阈值参数一般可设置为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 an
20、d 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)更
21、加优秀;同样地,可以看出图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),和原始密度
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 密度 峰值 算法 三支聚类
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。