基于Seeds集和成对约束的半监督三支聚类集成_姜春茂.pdf
《基于Seeds集和成对约束的半监督三支聚类集成_姜春茂.pdf》由会员分享,可在线阅读,更多相关《基于Seeds集和成对约束的半监督三支聚类集成_姜春茂.pdf(8页珍藏版)》请在咨信网上搜索。
1、2023-05-10计算机应用,Journal of Computer Applications2023,43(5):1481-1488ISSN 1001-9081CODEN JYIIDUhttp:/基于Seeds集和成对约束的半监督三支聚类集成姜春茂1,吴鹏2,李志聪2*(1.福建工程学院 计算机科学与数学学院,福州 350118;2.哈尔滨师范大学 计算机科学与信息工程学院,哈尔滨 150025)(通信作者电子邮箱)摘要:聚类集成使用合适的策略融合多个具有差异性的基聚类成员,能够有效提高聚类结果的稳定性、鲁棒性和准确率。当前聚类集成的研究较少利用已知的先验信息,面对复杂数据时难以刻画对象与
2、类簇之间明确的归属关系。因此,提出一种基于Seeds集和成对约束的半监督三支聚类集成方法。首先,基于已有的标签信息提出一种新的三支标签传播算法构造基聚类成员;其次,提出一种半监督三支聚类集成框架集成基聚类成员,构造出一致性相似矩阵,并利用成对约束信息对该矩阵进行优化调整;最后,将三支谱聚类作为一致性函数对相似矩阵进行聚类,得到最终集成结果。在多个 UCI 真实数据集上的实验结果表明,与基于类簇的相似分区算法(CSPA)、超图分区算法(HGPA)、元类簇算法(MCLA)、标签传播算法(LPA)、Cop-Kmeans等半监督聚类集成算法相比,所提方法的归一化互信息(NMI)、调整兰德系数(ARI)
3、和F测度在绝大多数据集上取得了最优值,获得了相对更好的聚类集成结果。关键词:三支决策;聚类集成;三支聚类;成对约束;半监督;Seeds集中图分类号:TP391 文献标志码:ASemi-supervised three-way clustering ensemble based on Seeds set and pairwise constraintsJIANG Chunmao1,WU Peng2,LI Zhicong2*(1.School of Computer Science and Mathematics,Fujian University of Technology,Fuzhou Fuj
4、ian 350118,China;2.College of Computer Science and Information Engineering,Harbin Normal University,Harbin Heilongjiang 150025,China)Abstract:Using appropriate strategies,clustering ensemble can effectively improve the stability,robustness and precision of clustering results by fusing multiple base
5、cluster members with differences.Current research on the clustering ensemble rarely uses known priori information,and it is difficult to describe belonging relationships between objects and clusters when facing complex data.Therefore,a semi-supervised three-way clustering ensemble method was propose
6、d on the basis of Seeds set and pairwise constraints.Firstly,based on the existing label information,a new three-way label propagation algorithm was proposed to construct the base cluster members.Secondly,a semi-supervised three-way clustering ensemble framework was designed to integrate the base cl
7、uster members to construct a consistent similarity matrix,and this matrix was optimized by using pairwise constraint information.Finally,the three-way spectral clustering was employed as a consistency function to cluster the similarity matrix to obtain the final clustering results.Experimental resul
8、ts on several real datasets in UCI show that compared with the semi-supervised clustering ensemble algorithms including Cluster-based Similarity Partitioning Algorithm(CSPA),HyperGraph Partitioning Algorithm(HGPA),Meta-CLustering Algorithm(MCLA),Label Propagation Algorithm(LPA)and Cop-Kmeans,the pro
9、posed method achieves the best results on most of the datasets in terms of Normalized Mutual Information(NMI),Adjusted Rand Index(ARI)and F-measure.Key words:three-way decision;clustering ensemble;three-way clustering;pairwise constraint;semi-supervised;Seeds set0 引言 聚类分析是一种典型的无监督机器学习方法。聚类分析因为不需要给定样
10、本的标签信息,仅通过衡量数据之间的关系就能识别数据中潜在的结构特征而受到广泛的关注。但单一的聚类算法往往采用某种理想化的数据分布假设,如K-means算法假设样本均匀分布在球形的样本空间中,当样本分布不均匀或存在较多的噪点时,聚类效果不佳。不同的聚类算法往往存在较大的差异性,即使相同的聚类算法在参数不同时,聚类结果也往往存在差异。这限制了聚类分析的适用性。聚类集成旨在融合多个不同的基聚类成员,从而获得一个统一的数据划分。研究表明,相较于单一的聚类算法,聚文章编号:1001-9081(2023)05-1481-08DOI:10.11772/j.issn.1001-9081.2022071094收
11、稿日期:2022-07-19;修回日期:2022-10-03;录用日期:2022-11-04。基金项目:黑龙江省自然科学基金资助项目(LH2020F031);福建工程学院科研启动基金资助项目(GY-Z220212)。作者简介:姜春茂(1972),男,辽宁庄河人,教授,博士,CCF 高级会员,主要研究方向:三支决策与三支计算、云计算、大数据挖掘;吴鹏(1997),男,山东烟台人,硕士研究生,主要研究方向:三支决策;李志聪(1972),男,黑龙江绥化人,副教授,硕士,CCF会员,主要研究方向:数据挖掘。第 43 卷计算机应用类集成能够有效提高聚类结果的稳定性、鲁棒性和准确率。Strehl等1将集成
12、学习引入聚类分析中,提出了聚类集成的概念。由于缺乏先验的标签信息,聚类集成的研究要比分类集成更加困难,其中的关键问题是如何生成多个具有差异性的基聚类,以及如何对多个基聚类结果进行融合,获得更好的聚类集成结果。Strehl等将超图划分引入聚类集成,提出了三种基于超图划分的聚类集成算法,分别是基于类簇的相似 分 区 算 法(Cluster-based Similarity Partitioning Algorithm,CSPA)、元类簇算法(Meta-CLustering Algorithm,MCLA)和超图 分 区 算 法(HyperGraph Partitioning Algorithm,HG
13、PA)。Zhou 等2提出了基于投票的聚类集成方法。Fred 等3提出了证据积累的概念,通过在基聚类结果中构建共协关系矩阵,分析对象间的相似性,并利用层次聚类得到了聚类结果。Wang等4将传统的成对约束(即必须链接或不能链接)扩展为模糊成对约束,进而提出了一种带有模糊配对约束的半监督 模 糊 聚 类(Semi-Supervised Fuzzy clustering with Pairwise Constraints,SSFPC)。当前聚类集成的研究以非监督聚类集成为主,未能充分利用已知的先验信息,导致难以得到更加优质的聚类集成结果。半监督聚类集成利用少量已知的先验信息,如少量标签信息或成对约束
14、信息等提高聚类集成的质量。Ma等5利用共识函数中的约束信息,提出了基于Chameleon的半监督选择性聚类集成(Semi-supervised Selective Clustering Ensemble based on Chameleon,SSCEC)和基于Ncut的半监督选择性聚类 合 集(Semi-supervised Selective Clustering Ensemble based on Ncut,SSCEN)方法。SSCEC 使用 Chameleon 算法作为共识函数,并在子图分割和子图组合中处理约束信息;SSCEN使用归一化切割算法作为共识函数,并在图的二分法过程中处理约束信
15、息。实验结果表明,这两种半监督成员选择聚类组合算法优于其他半监督算法。Xiao等6设计了一种基于贝叶斯网络的半监督聚类集成模型,并通过变分法对模型进行了推理和求解。这些研究推动了半监督聚类集成的发展,但有一个值得注意的问题是:当前关于半监督聚类集成的研究依然以硬聚类为主。在硬聚类的结果中,对象与类簇之间存在明确的归属关系,即对象确定属于该类簇或对象确定不属于该类簇。在现实的复杂数据中,对象与类簇之间的关系通常是模糊和不确定性的,对象与类簇之间缺乏明确的归属关系。当可用信息不足时,强制将对象划分到某一类簇容易引起较高的误分类代价。因此现有的聚类集成算法难以精确地刻画类簇的结构特征。Yu等7将三支
16、决策的思想引入聚类分析,并提出了三支聚类算法。不同于传统的硬聚类结果,三支聚类通过一对集合呈现一个类簇,即核心域和边界域。核心域中的数据表示确定属于该类簇,边界域中的数据表示可能属于该类簇。琐碎域表示核心域和边界域并集的补集,用来描述确定不属于该类簇的对象。三支聚类能够更加精确地刻画类簇边界模糊的现象,能够有效描述对象与类簇之间的不确定性关系。自三支聚类提出以来,多种研究成果已经涌现。如 Wang等8借鉴数学形态学中的收缩和扩张思想,提出了一种基于数学形态学的三支聚类算法;Yu 等9将证据理论引入聚类分析中,提出了一种基于证据理论的密度峰值三支聚类算法;Afridi等10针对含有缺失值的数据,
17、提出了一种基于博弈粗糙集的三支聚类算法;Yu等11将低秩矩阵和主动学习引入多视图聚类中,提出了一种基于低秩表示的多视图主动三支聚类算法;Jiang等12利用阴影集和多粒度粗糙集的思想提出了一种三支聚类集成方法,在众多 UCI(University of California,Irvine)数据集上的实验效果良好。在聚类集成中,标签信息和成对约束信息有助于改善集成效果,然而,很少有人考虑或同时考虑这两种类型的先验知识。此外,传统的基聚类结果是二支聚类,难以精确地刻画类簇的结构特征,使得在集成阶段可能丢失一些重要信息。为了解决上述问题,本文提出了一种基于Seeds集和成对约束的半监督三支聚类集成(
18、Seeds-set based Three-Way Clustering Ensemble,STWCE)方法。首先,基于标签传播算法(Label Propagation Algorithm,LPA),STWCE方法利用标签信息构建具有差异性的基聚类成员集合;然后提出一种新的方法来构建一致性相似矩阵,并利用成对约束信息对相似矩阵进行调整;最后,使用三支谱聚类对相似矩阵聚类,得到最终集成后的聚类结果。本文主要工作总结如下:1)将三支决策理论引入半监督聚类集成,利用不同类型的先验信息设计了一种三支标签传播算法来生成基聚类成员。2)通过在均匀的成对空间中比较不同区域的对象来区别基聚类成员所做出的贡献,
19、即采用一种新的规则对基聚类成员进行不同的权重表示;并通过将不同基聚类成员结果进行统一表示,有效解决了未对齐的问题。3)使用基于三支决策思想的谱聚类方法对一致性相似矩阵进行聚类,使集成结果收敛于全局最优解。每个类簇由一对集合进行表示,更好地表现出对象与类簇之间的归属关系。1 相关工作 1.1聚类集成给定一组数据U=x1,x2,xn,n表示数据样本的个数。聚类集成通过在数据U上重复执行m次聚类得到一组基聚类结果=1,2,m,式中i=Ci1,Ci2,Cik是第i次基聚类的结果,Cij表示第i次基聚类的第j个类簇。聚类集成主要包括两个步骤:基聚类的生成和一致性函数的设计。在第一步中,主要工作是使用不同
20、的生成机制生成一组不同的聚类结果,例如不同参数下的同一算法12、选择不同算法13和选择不同的对象子集14-15等;第二步是聚类集成的关键步骤,对得到的基聚类成员进行集成来得到最终的聚类结果。现有的聚类集成方法主要分为三类:基于图的方法16、基于数据点间相似度的方法17和基于特征的方法18。基于图的方法将聚类集成问题表示成超图的形式,并调用图划分算法求解;基于数据点间相似度的方法通过建立样本间的相似矩阵,再基于相似度聚类的方法来得到聚类结果;基于特征的方法则使用每个基聚类成员内各样本的聚类标签作为新的特征来得到最后的聚类结果。1.2三支聚类的基本形式传统的聚类算法是一种硬聚类或者说二支聚类的结果
21、,即对象和类簇之间的关系是明确的,对象确定属于该类簇或对象确定不属于该类簇。给定一组数据U=x1,x2,xn,二支聚类通过单个集合Ci表示一个类簇。所划分的类簇内具有较高的相似性,而类簇间具有较高的相异性。给定一组1482第 5 期姜春茂等:基于Seeds集和成对约束的半监督三支聚类集成类簇集合C=C1,C2,Ck,将U中所有的对象划分到k个类簇中,并且k个类簇满足如下条件:1)类簇不能为空,即每个类簇至少包含一个对象:Ci(i=1,2,k);2)有的类簇的并集为对象的集合:i=1kCi=U;3)每一个对象只能属于一个类簇,即类簇之间的交集为空:Ci Cj=(i j)。不同于二支聚类,三支聚类
22、将每个类簇用一对集合进行表示:Ci=Co(Ci),Fr(Ci),即类簇Ci由核心域Co(Ci)和边界域Fr(Ci)两个子集组成。类簇Ci的琐碎域表示为Tr(Ci)=U-Co(Ci)-Fr(Ci),表示由确定不属于类簇Ci的对象组成的集合。类簇Ci的三个域满足如下条件:1)Co(Ci)Fr(Ci)Tr(Ci)=OB;2)Co(Ci)Fr(Ci)=;3)Co(Ci)Tr(Ci)=;4)Fr(Ci)Tr(Ci)=。上述4个条件说明任何一个类簇的核心域、边界域和琐碎域之间的并集为论域OB,且核心域、边界域和琐碎域两两互不相交。三支聚类的k个类簇满足如下条件:1)Co(Ci)=(i=1,2,k);2)i
23、=1k()Co(Ci)Fr(Ci)=OB;3)Co(Ci)Co(Cj)=。上述三个条件说明任意一个类簇的核心域不为空,所有类簇的核心域和边界域的并集为论域OB,任意两个类簇的核心域的交集为空。1.3半监督聚类按照不同的监督信息,半监督聚类可分为基于成对约束信息的半监督聚类和基于标签信息的半监督聚类。成对约束信息有 must-link 和 cannot-link:must-link 指两个对象属于同一个类别;cannot-link指两个对象不属于同一个 类 别。Wagstaff 等19将 成 对 约 束 的 思 想 运 用 到 传 统K-means算法中,提出了Cop-Kmeans算法;Zhen
24、g等20将成对约束思想引入层次聚类算法,在层次聚类中也可以使用成对约束;Yang等21通过对cannot-link进行广度搜索来解决Cop-Kmeans 中的约束冲突问题,并通过 MapReduce 降低计算复杂度。相较于成对约束信息,标签信息可以直接判断数据点的类别。Qin等22系统性回顾了半监督聚类,尤其是对基于约束信息的半监督聚类方法;Zhou等23提出了标签传播算法,该算法是基于图的半监督聚类的代表性算法;Yu等24同时考虑特征空间和样本空间的渐进式子空间的方法以获得更准确的半监督聚类结果;Fang 等25提出了一种基于低秩表示的半监督子空间聚类方法,将低秩表示框架与高斯场和谐函数结合
25、,通过融合标签信息完成相似矩阵的构造和子空间聚类。半监督聚类算法在很多领域等都有着广泛的应用。在以上研究中,只使用了单一的监督信息来辅助聚类。然而,先验信息不仅有成对约束,还存在标签信息,不同类型的先验信息具有不同的意义,因此,如何融合不同类型的先验信息达到聚类结果的目的有着重要的研究意义。2 基于Seeds集和成对约束的半监督三支聚类集成方法 本章首先阐述了基于Seeds集和成对约束的半监督三支聚类集成(STWCE)方法的基本思想,然后详细介绍了该方法的关键步骤。2.1STWCE的基本思想图 1 给出了 STWCE 方法的基本框架,其中:p为打标问询次数,P为最大问询次数。由图 1 可知,该
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 Seeds 成对 约束 监督 三支聚类 集成 姜春茂
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。