基于聚类质量的两阶段集成算法.pdf
《基于聚类质量的两阶段集成算法.pdf》由会员分享,可在线阅读,更多相关《基于聚类质量的两阶段集成算法.pdf(10页珍藏版)》请在咨信网上搜索。
1、 第6 1卷 第4期吉 林 大 学 学 报(理 学 版)V o l.6 1 N o.4 2 0 2 3年7月J o u r n a l o f J i l i nU n i v e r s i t y(S c i e n c eE d i t i o n)J u l y 2 0 2 3d o i:1 0.1 3 4 1 3/j.c n k i.j d x b l x b.2 0 2 2 2 4 6基于聚类质量的两阶段集成算法闫 晨,杨有龙,刘原园(西安电子科技大学 数学与统计学院,西安7 1 0 1 2 6)摘要:针对现有的集成聚类算法通常默认使用K-m e a n s算法作为基聚类生成器,虽
2、能确保聚类成员的多样性,却忽视了差的基聚类可能会对最终聚类结果造成极大干扰的问题,提出一种基于聚类质量的两阶段集成算法.鉴于K-m e a n s算法运行高效但聚类质量较粗糙,提出首先在生成阶段采用K-m e a n s算法生成基聚类成员,然后通过群体一致性度量筛选出兼具高质量和强多样性的聚类成员,形成候选集成;其次,进一步在集成阶段应用信息熵知识构建基聚类加权的共协矩阵;最后应用一致函数得到最终聚类结果.采用3个指标在1 0个真实数据集上进行对比实验,实验结果表明,该算法在有效提升聚类结果准确度的同时,能保持较好的鲁棒性.关键词:集成聚类;聚类质量;群体一致性;信息熵;一致函数中图分类号:T
3、 P 3 9 1 文献标志码:A 文章编号:1 6 7 1-5 4 8 9(2 0 2 3)0 4-0 8 9 9-1 0T w oS t a g eE n s e m b l eA l g o r i t h mB a s e do nC l u s t e r i n gQ u a l i t yYANC h e n,YANGY o u l o n g,L I UY u a n y u a n(S c h o o l o fM a t h e m a t i c sa n dS t a t i s t i c s,X i d i a nU n i v e r s i t y,X ia n7
4、 1 0 1 2 6,C h i n a)A b s t r a c t:A i m i n ga t t h ep r o b l e mt h a te x i s t i n ge n s e m b l ec l u s t e r i n ga l g o r i t h m su s u a l l yu s e dK-m e a n sa l g o r i t h ma st h eb a s ec l u s t e r i n gg e n e r a t o r,a l t h o u g hi tc o u l de n s u r et h ed i v e r s
5、i t yo fc l u s t e r i n gm e m b e r s,i t i g n o r e dt h a tp o o rb a s ec l u s t e r i n g sm i g h t c a u s e t e r r i b l ed i s t u r b a n c e t o t h e f i n a l c l u s t e r i n gr e s u l t,w ep r o p o s e dat w os t a g ee n s e m b l ea l g o r i t h m b a s e do nc l u s t e r
6、i n gq u a l i t y.C o n s i d e r i n gt h a tK-m e a n s a l g o r i t h mr a ne f f i c i e n t l y,b u t t h e c l u s t e r i n gq u a l i t yw a s r e l a t i v e l y r o u g h,f i r s t l y,w e p r o p o s e d t ou s eK-m e a n s a l g o r i t h mt og e n e r a t eb a s e c l u s t e r i n gm
7、 e m b e r s i n t h eg e n e r a t i o ns t a g e,a n d t h e ns e l e c t e dc l u s t e r i n gm e m b e r sw i t hb o t hh i g hq u a l i t ya n ds t r o n gd i v e r s i t yt h r o u g hg r o u pa g g r e m e n tm e a s u r e t of o r m c a n d i d a t ee n s e m b l e.S e c o n d l y,t h ei n
8、f o r m a t i o n e n t r o p y k n o w l e d g e w a sf u t h e ra p p l i e dt oc o n s t r u c tt h e w e i g h t e d-c l u s t e r i n gc o-a s s o c i a t i o n m a t r i xi nt h ee n s e m b l es t a g e.F i n a l l y,t h ef i n a lc l u s t e r i n gr e s u l tw a so b t a i n e db yu s i n g
9、c o n s e n s u s f u n c t i o n.T h r e e i n d e x e sw e r eu s e df o rc o m p a r a t i v ee x p e r i m e n t so nt e nr e a l d a t a s e t s,a n d t h ee x p e r i m a n t a l r e s u l t s s h o wt h a t t h ea l g o r i t h mc a ne f f e c t i v e l yi m p r o v e t h ea c c u r a c yo f
10、c l u s t e r i n gr e s u l t sw h i l em a i n t a i n i n gg o o dr o b u s t n e s s.K e y w o r d s:e n s e m b l ec l u s t e r i n g;c l u s t e r i n gq u a l i t y;g r o u pa g g r e m e n t;i n f o r m a t i o ne n t r o p y;c o n s e n s u sf u n c t i o n收稿日期:2 0 2 2-0 5-3 1.第一作者简介:闫 晨(1
11、 9 9 7),女,汉族,硕士,从事模式识别和数据挖掘分析的研究,E-m a i l:2 7 9 9 7 0 2 6 0 9q q.c o m.通信作者简介:杨有龙(1 9 6 7),男,汉族,博士,教授,从事高维数据分析与应用的研究,E-m a i l:y l y a n g m a i l.x i d i a n.e d u.c n.基金项目:陕西省自然科学基础研究计划项目(批准号:2 0 2 1 J M-1 3 3).聚类作为数据挖掘中的一种常用算法,能发现未知数据的潜在模式,进一步指导实践,在机器学习、数据挖掘和人工智能等领域应用广泛1-5.聚类的基本思想是根据相似性或距离的大小将数据
12、划分为若干类,再利用人工对各类指定类别,从而便于将数据价值最大化.目前已有很多非常成熟的聚类算法4-5,但这些算法通常仅能处理特定类型的数据,且对参数的依赖性过高,导致聚类效果不佳且应用范围较窄.集成学习6是机器学习领域中一种非常重要的技术,其通过一定规则融合多个模型的结果,期望得到一个更好的结果.集成学习主要分为集成分类和集成聚类.集成聚类6的主要思想是融合多个“好而不同”的聚类结果,得到一个精度和鲁棒性都更强的聚类结果.“好而不同”是指基聚类成员之间应满足本身的聚类质量较好,同时彼此之间的差异性较大的条件,以确保能得到一个更好的一致聚类结果.集成聚类的这一优越性能使得它可以在很大程度上克服
13、单个聚类算法的缺陷,进一步拓宽了聚类的应用.集成聚类算法可分为生成基聚类和集成基聚类两个阶段.目前对集成聚类算法的研究主要关注两个问题:一是如何生成“好而不同”的基聚类成员;二是如何设计集成策略.对于第一个问题,一般采用启发式算法,包括在数据层面对样本或特征加入扰动,算法层面对同一算法设置不同参数或采用不同算法生成基聚类成员.由于谱聚类对小样本具有良好的分簇能力,因此可降低谱聚类的计算复杂度7-1 0,使其应用于大规模数据集.对于第二个问题,目前的研究主要分为基于相似度的集成聚类算法和基于图模型的集成聚类算法.尽管现有的集成聚类算法已取得了较好的效果,但仍存在两个问题:1)多数算法默认使用K-
14、m e a n s算法作为基聚类生成器,然后考虑聚类的效率和多样性,但忽视了其中差的基聚类可能对最终结果造成极大干扰,研究表明,在保证基聚类质量的前提下尽可能增强其多样性,有利于得到一个更好的集成结果1 1-1 3;2)在设计集成策略时常平等地对待所有基聚类或同一基聚类内的所有簇,缺乏对集成信息的深入探索.针对上述问题,本文提出一种基于聚类质量的两阶段集成算法.首先采用K-m e a n s算法生成若干多样化的基聚类成员,然后利用群体一致性度量计算每个基聚类的质量,从中筛选出排名靠前的质量与多样性都较好的基聚类,将其作为集成阶段的候选成员,再进一步在集成阶段利用信息熵估计基聚类质量,构造融合基
15、聚类质量的共协矩阵,最后对该矩阵应用层次聚类算法得到最终聚类结果.1 相关工作在对集成聚类算法的相关研究中,基于相似度的方法和基于图的方法是两种主流的研究方法.基于相似度的方法将集成信息表示为一个共协矩阵,每个元素表示样本对在所有基聚类中同时出现的频率,然后把该矩阵视为相似矩阵,再应用任何一种划分算法得到最终的聚类结果.这类方法概念简单,可解释性强,且易于实现和聚合,因此受到广泛关注.F r e d等1 4提出了共协矩阵的概念,并进一步提出了证据累积聚类(e v i d e n c ea c c u m u l a t i o nc l u s t e r i n g,E A C),但该方法平
16、等地对待参与集成的每个基聚类,忽视了不同基聚类的质量差异对最终结果的影响.针对上述缺陷,W a n g等1 5将每个基聚类的簇规模和样本维数考虑在内,对E A C方法进行改进,提出了一种概率累积的方法,从而能更好地度量样本之间的成对相关性.H u a n g等1 6提出以群策智慧思想估计基聚类质量,之后又提出了利用信息熵估计不同簇对集成的贡献度,得到改进的局部加权共协矩阵1 7.考虑到共协矩阵中存在部分不确定样本对,可能会影响聚类效果,Y i等1 8提出通过设置合理的阈值,从共协矩阵中去掉不可靠样本,再利用矩阵补全技术完全化共协矩阵,最后应用谱聚类得到划分结果.由于共协矩阵本身并不能涵盖全部集
17、成信息,因此Z h o n g等1 9提出从共协矩阵中多次移除部分低频共现元素,对形成的多个矩阵分别进行聚类并设计了一个内部度量,根据该度量选择聚类质量最好的一个作为最终集成结果.Z h o u等2 0利用子空间聚类思想,结合微簇概念,通过构造目标函数,优化学习后得到一个代表点级别上的相似矩阵,划分后得到聚类结果.基于图模型的方法将集成聚类问题转化为图分割问题,进而得到聚类结果.这类算法的关键在于如何构图,包括如何设置图节点以及如何定义边权重.S t r e h l等2 1最早提出了3种基于图的算法,分别是基于样本相似度的算法(c l u s t e r-b a s e ds i m i l
18、a r i t yp a r t i t i o n i n ga l g o r i t h m,C S P A)、超图划分算法009 吉 林 大 学 学 报(理 学 版)第6 1卷(h y p e rg r a p hp a r t i t i o n i n ga l g o r i t h m,HG P A)和 元聚类算法(m e t a-c l u s t e r i n ga l g o r i t h m,MC L A).C S P A以样本为图节点,根据共协矩阵定义样本权重构造图;HG P A以簇为超边,每条超边连接了所有属于该簇的样本;MC L A以簇为图节点,对两个簇计算J
19、 a c c a r d系数并作为边权重建立元图.由于HG P A算法在构图时可能会丢失部分数据信息,F e r n等2 2对其进行了改进,把样本和簇同时作为图节点,若样本属于某个簇,则它们之间的边权重为1,否则为0,提出了一种混合二部图描述算法.为充分利用集成信息,H u a n g等2 3通过在图上进行随机游走,提出了概率轨迹累积聚类和概率轨迹图划分算法;并结合类簇在集成中的不确定性,构造出融合簇可靠性的局部加权二部图1 7.此外,还有一些针对谱聚类的改进算法2 4-2 5,可以应用于较大规模数据集或者高维数据集.上述这些算法均重点关注集成方法的设计,默认使用K-m e a n s算法生成
20、基聚类成员,无法为集成阶段提供一个良好的输入,从而影响最终聚类效果.根据机器学习界公认的G I GO(g a r b a g ei n,g a r b a g eo u t)原理,即差的前提导致差的结论,本文提出对集成聚类算法的两个阶段分别采用不同方法控制基聚类质量,以提升聚类的准确度.2 算法框架假设数据集X=x1,x2,xN 是包含N个样本的数据集,对数据集X进行T次聚类得到T个基聚类,记为初始基聚类集合=1,2,T,其中t=C1t,C2t,Cntt 表示第t个基聚类(t=1,2,T),Clt表示t中的第l个簇,nt表示t包含的簇数.对初始基聚类集合进行初步筛选后,形成候选集成.假 设 算
21、 法 每 次 执 行 时 从 候 选 集 成 中 随 机 选 择M(MT)个 基 聚 类 进 行 集 成,记 为=1,2,M,其中m=C1m,C2m,Cnmm 表示参与集成的第m个基聚类(m=1,2,M),nm表示 基聚类m包含的簇数.将基聚类集合 中所有簇构成的集合表示为C=C1,C2,Cnc,则nc=n1+n2+nM,Ci表示基聚类集合中的第i个簇.2.1 生成阶段K-m e a n s算法强大的多样性使其成为很多集成聚类研究中基聚类生成器的首选,这是因为该算法通过随机选择簇中心进行初始化,经过多次迭代更新簇中心,并寻找最能代表数据分布的质心,最后完成剩余点的分配.对于集成聚类算法,基聚类
22、成员的多样性固然重要,其质量也同样不容忽视.因为差的基聚类可能不仅对集成过程没有帮助,反而会干扰产生的最终聚类结果.研究表明,如果能在保证基聚类质量的前提下尽可能地增强其多样性,则更有利于得到一个好的聚类结果1 1-1 3.鉴于K-m e a n s聚类算法强大的多样性以及聚类过程的高效性,本文采用K-m e a n s生成基聚类成员.但考虑到该算法聚类效果较粗糙,且仅在球状数据集上表现较好,因此首先对其产生的聚类质量进行估计,然后去掉少数质量特别差的基聚类,将剩余的基聚类成员输入集成阶段.这样得到的基聚类兼具高质量和强多样性,更有利于产生一个较好的聚类结果.目前还没有一个公认的度量能量化基聚
23、类质量,借助群体智慧思想可在一定程度上解决该问题.与集成学习的思想类似,通过听取并结合来自多个角度的不同意见,以获得一个更佳的结果.不同于文献1 6 中在集成阶段用其估计基聚类质量,本文利用该度量估计生成阶段每个基聚类成员的质量.即计算一个基聚类与其他所有参与集成的基聚类之间的标准互信息(n o r m a l i z e dm u t u a l i n f o r m a t i o n,NM I)值,通过取平均估计该基聚类与全体集成成员的一致性.先给出一个基聚类t与其他集成成员的一致性(g r o u pa g r e e m e n tm e a s u r e,GAM)为GAM(t)
24、=1T-1t,s,tsNM I(t,s).(1)把群体一致性最大的基聚类作为参考成员,定义基聚类t的标准化群体一致性(n o r m a l i z e dg r o u pa g r e e m e n tm e a s u r e,NGAM)值为NGAM(t)=GAM(t)m a xsGAM(s),(2)其中NGAM的取值范围为0,1,值越大表明基聚类质量越高.随着样本量的增大以及基聚类数目的109 第4期 闫 晨,等:基于聚类质量的两阶段集成算法 增加,若采用NGAM计算所有基聚类成员的质量,运算量会成倍增加.将T个基聚类结果形成的NT阶矩阵,记为矩阵D.若要得到所有基聚类的NGAM值,
25、则需计算T(T-1)/2次NM I.为减少该过程的计算复杂度,本文利用降采样方法估计基聚类质量.先基于矩阵D随机取1 0%样本及相应的聚类结果,形成一个新矩阵,记为矩阵E.由于矩阵E中每列的聚类标签是乱序的,为便于后续计算,因此需采用标签对齐策略得到矩阵F.考虑到一次随机取样得到的结果可能不准确,因此进行3轮随机降采样并取平均NGAM值,结果表明,所得结果与一次降采样的结果基本一致.而且这样计算得到的基聚类质量普遍较高,且在本文所有数据集上得到的NGAM值低于0.5的基聚类个数不超过5%,这可能与本文处理NGAM值时所选取的参照物有关.因此,为节省时间,本文使用一次随机降采样产生的基聚类计算基
- 配套讲稿:
如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。