基于代数粒的聚类方法.pdf
《基于代数粒的聚类方法.pdf》由会员分享,可在线阅读,更多相关《基于代数粒的聚类方法.pdf(9页珍藏版)》请在咨信网上搜索。
1、 基于代数粒的聚类方法*肖振国1,陈林书1,孙少杰1,梅本霞1,柳媛慧2,赵 磊3(1.湖南科技大学计算机科学与工程学院,湖南 湘潭 4 1 1 2 0 1;2.湖南科技大学外国语学院,湖南 湘潭 4 1 1 2 0 1;3.湖南警察学院信息技术(网监)系,湖南 长沙 4 1 0 1 3 8)摘 要:聚类,是机器学习的主要任务之一,也是粒计算理论的核心任务,即信息粒化。目前,基于粒计算的聚类算法中,大多数只基于粒属性进行聚类,而没有考虑粒结构,尤其是在代数结构应用广泛的信息领域。从粒计算的角度,提出一种基于代数粒的聚类方法。基于二元代数运算定义代数粒;提出一种基于代数粒的聚类方法,通过粒集的同
2、余划分和粒结构的同态映射进行粒度聚类;将提出的聚类方法与容差邻域模型和商空间模型进行对比分析。结果表明,该新型方法具有更好的结构完备性和应用鲁棒性。基于代数粒的聚类方法从结构上丰富和扩展了粒度计算理论,为粒计算与机器学习的融合研究提供了理论依据。关键词:粒计算;聚类;粒化;粗糙集;商空间模型中图分类号:T P 3 0 1文献标志码:Ad o i:1 0.3 9 6 9/j.i s s n.1 0 0 7-1 3 0 X.2 0 2 4.0 1.0 1 6A c l u s t e r i n g m e t h o d b a s e d o n a l g e b r a i c g r a
3、 n u l a r i t yX I AO Z h e n-g u o1,CHE N L i n-s h u1,S UN S h a o-j i e1,ME I B e n-x i a1,L I U Y u a n-h u i2,Z HAO L e i3(1.S c h o o l o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,H u n a n U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y,X i a n g t a n 4 1 1
4、 2 0 1;2.S c h o o l o f F o r e i g n L a n g u a g e s,H u n a n U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y,X i a n g t a n 4 1 1 2 0 1;3.D e p a r t m e n t o f I n f o r m a t i o n T e c h n o l o g y(N e t w o r k S u p e r v i s i o n),H u n a n P o l i c e C o l l e g e,
5、C h a n g s h a 4 1 0 1 3 8,C h i n a)A b s t r a c t:C l u s t e r i n g i s t h e m a i n t a s k o f m a c h i n e l e a r n i n g,a n d i s a l s o t h e c o r e w o r k o f g r a n u l a r c o m-p u t i n g,n a m e l y i n f o r m a t i o n g r a n u l a t i o n.A t p r e s e n t,m o s t o f g
6、r a n u l a r c o m p u t i n g b a s e d c l u s t e r i n g a l g o-r i t h m s o n l y u t i l i z e t h e g r a n u l e f e a t u r e s w i t h o u t t a k i n g t h e g r a n u l e s t r u c t u r e i n t o a c c o u n t,e s p e c i a l l y i n t h e i n f o r m a t i o n f i e l d w h e r e a
7、l g e b r a i c s t r u c t u r e i s w i d e l y u s e d.F r o m t h e p e r s p e c t i v e o f g r a n u l a r c o m p u-t i n g,t h i s p a p e r p r o p o s e s a c l u s t e r i n g m e t h o d b a s e d o n a l g e b r a i c g r a n u l a r i t y(CMAG).F i r s t l y,t h e a l-g e b r a i c g
8、r a n u l a r i t y i s n e w l y f o r m u l a t e d w i t h t h e g r a n u l e s t r u c t u r e o f a n a l g e b r a i c b i n a r y o p e r a t o r.S e-c o n d l y,t h e CMAG i s p r o p o s e d w i t h g r a n u l e s o f i n c o r p o r a t i n g c o n g r u e n c e p a r t i t i o n a n d g
9、 r a n u l e s t r u c t u r e o f h o m e o m o r p h i c p r o j e c t i o n.F i n a l l y,t h e CMAG i s e x p e r i m e n t a l l y c o m p a r e d w i t h t h e t o l e r a n c e d o m a i n m o d e l a n d t h e q u o t i e n t s p a c e m o d e l,a n d t h e r e s u l t s s h o w t h a t t h
10、e CMAG h a s b e t t e r s t r u c t u r a l c o m-p l e t e n e s s a n d p r a c t i c a l r o b u s t n e s s.T h e CMAG c a n e n r i c h a n d e x t e n d t h e g r a n u l a r c o m p u t i n g t h e o r y f r o m g r a n u l e s t r u c t u r e,a n d w i l l p r o v i d e a t h e o r e t i c
11、a l b a s i s f o r t h e c o m b i n a t i o n o f g r a n u l a r c o m p u t i n g m e t h o d s a n d m a c h i n e l e a r n i n g t h e o r y.K e y w o r d s:g r a n u l a r c o m p u t i n g;c l u s t e r i n g;g r a n u l a t i o n;r o u g h s e t;q u o t i e n t s p a c e m o d e l*收稿日期:2 0
12、 2 2-0 5-1 7;修回日期:2 0 2 2-0 8-1 3基金项目:湖南省教育厅科学研究项目(2 1 C 0 9 4 6);湖南省教育厅教学改革研究项目(HN J G-2 0 2 2-0 7 8 6,HN J G-2 0 2 2-0 7 9 2);湖南科技大学教学改革研究项目(2 0 2 1-7 6-9,2 0 2 1-7 6-2 6)通信地址:4 1 1 2 0 1 湖南省湘潭市湖南科技大学计算机科学与工程学院A d d r e s s:S c h o o l o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g,
13、H u n a n U n i v e r s i t y o f S c i e n c e a n d T e c h n o l o g y,X i a n g t a n 4 1 1 2 0 1,H u n a n,P.R.C h i n a C N 4 3-1 2 5 8/T PI S S N 1 0 0 7-1 3 0 X 计算机工程与科学C o m p u t e r E n g i n e e r i n g&S c i e n c e第4 6卷第1期2 0 2 4年1月 V o l.4 6,N o.1,J a n.2 0 2 4 文章编号:1 0 0 7-1 3 0 X(2
14、0 2 4)0 1-0 1 5 0-0 91 引言粒计算作为智能计算研究领域中信息处理的一种新理念和新方法,其本质是通过选择合适的粒度来寻找一种较好的、近似的解决问题的方案,并且在此 过程中去除 繁冗,降低 问题求解的 复杂性1,2。粒化,作为粒计算中的核心工作,主要是将未分组的粒子(细粒度)聚类为分组(粗粒度)。聚类,作为机器学习的最重要任务之一,旨在将相似的对象分组在一个聚类中,它主要包括数据预处理和知识聚类这2个步骤3。从这个角度来看,粒计算中的粒化与机器学习中的聚类任务是相同的。近年来,越来越多的研究人员也开始逐渐从粒计算的角度研究聚类方法。粒计算中的粒度包括3个部分:粒子、粒属性和粒
15、结构。粒子是粒计算的基本计算单元,因其相似性、相邻性和一致性而内部不可区分。粒属性为同一粒度上所有粒子所共有的一组公共特征。粒结构描述了同一粒度上所有粒子之间的结构关系。目前大部分粒计算模型都是基于粒属性进行聚类,而没有考 虑粒结构,例 如表1中 的容差邻 域模型4,5和 粗 糙 集 理 论6,7。表1中 的 商 空 间 理论8,9和代数商模型1 0 1 2虽然分别引入了拓扑粒结构和代数粒结构,但仅从粒层上讨论粒度的转换方法,而没有研究相应的粒度聚类方法。事实上,代数粒结构广泛应用于包括数字编码、形式语言、电子电路设计等在内的信息与通信领域。例如,汉明编码是一种以模2运算为代数粒结构的典型应用
16、1 2。但是,目前系统地讨论代数粒结构的文献非常有限。T a b l e 1 B r i e f i n t r o d u c t i o n t o t h e r e s e a r c h o f g r a n u l a r c o m p u t i n g a n d c l u s t e r i n g m o d e l表1 对粒计算与聚类模型研究的简述模型粒属性粒结构聚类关系聚类类型容差邻域模型是无相容关系覆盖粗糙集理论是无等价关系划分商空间理论否拓扑结构等价关系划分代数商模型否代数结构未讨论未讨论 基于以上分析,本文在作者前期工作1 0 1 5 的基础上,从粒计算的角
17、度提出一种基于代数结构的聚类方法,主要工作有以下3个方面:(1)基于代数二元算子,建立代数粒模型,为代数结构的粒度数据提供形式化描述方法。(2)通过同余关系粒化,从粒计算的角度提出一种基于代数粒的聚类方法,通过粒集的同余划分和粒结构的同态映射进行粒度聚类。该方法为代数结构的粒度聚类提供一种新型方法,从结构上丰富了粒度计算理论。(3)将基于代数粒的聚类方法与容差邻域模型和商空间模型进行对比分析。实验结果表明,基于代数粒的聚类方法具有更好的结构完备性和应用鲁棒性。2 相关知识2.1 粒计算与聚类粒计算,最早是由L i n6在1 9 9 7年提出的,粒计算被视为与粒子相关的所有理论、策略、方法、技术
18、和工具2,现已广泛应用于机器学习1 6、知识获取1 7、复杂问题解决1 8、图像处理、模式识别、智能控制、人工神经网络和语言动态系统等领域。作为粒计算的关键工作之一,粒化可以分为变量粒化(聚类)、概念粒化(聚合)和值粒化(量化)。在数据预处理的过程中,粒化将原始数据转换成具有不同行和列 语义的表,其 中行对应于 原始元组的 组(粒),列表示关于每个组内原始值的聚类信息。聚类,是对一组对象进行分组的任务,使同一组(一类)中的对象比不同组(聚类)中的对象在某种意义上更相似。聚类是数据挖掘的主要任务,也是统计数据分析的常用技术,应用于许多领域,包括图像处理1 9、机器学习2 0、服务计算2 1、模式
19、识别、信息检索、生物信息学、数据压缩和计算机图形学。基于粒属性的聚类,是一种旨在创建聚类树的分层聚类算法,其最终目的是降低维度、冗余和存储需求。目前大多数粒计算聚类方法都是基于粒属性的,例如:容差邻域模型4,5基于容差关系进行粒化,并且根据粒属性的值将粒集聚集成类;粗糙集理论6,7粒化基于等价关系,粒集根据等价划分被聚类。然而,上述基于粒属性的聚类方法仅考虑粒属性,即它预先假设粒度上的所有粒子都是独立的,它们之间没有任何结构关系。基于粒结构的聚类,是近年来出现的基于粒结构的 粒 计 算 聚 类 方 法,如 表1所 示。Z h a n g等人8,9提出了商空间理论,将粒结构指定为拓扑结构,通过同
20、余关系进行粒化,为不同粒子之间的变换和分解提供了理论支持。W a n g等人2 2,2 3将粒定义为一个七元组G=(C,Rc,Ri,Ro,B,),151肖振国等:基于代数粒的聚类方法粒结构是由内部关系Rc、输入关系Ri和输出关系Ro组成的开放系统,为粒系统提供了一个强有力的建模概念。C h e n等人1 0 1 2提出粒计算的代数商模型,将粒结构看作一个代数运算,并通过同余关系进行粒化。但是,上述研究仅将粒结构分别指定为拓扑序和代数运算,而没有从粒计算角度研究相应的聚类方法。2.2 粒度体系结构粒度,是粒计算中最基本和最重要的概念。图1给出了论域U=ui|i=1,2,P 上的粒度三元组定义(U
21、N,FQ,S),其中,P是论域U中元素个数,粒集UN=vi|i=1,2,N中的粒子vi是U的子集,N表示粒子数量,粒属性FQ=fj|j=1,2,Q,Q表示属性数量,粒结构S表示粒集UN上粒子之间的结构关系。F i g u r e 1 A r c h i t e c t u r e o f g r a n u l a r i t y(UN,FQ,S)图1 粒度(UN,FQ,S)的体系结构一般地,问题空间都是从最复杂的原始最细(离散空间上)粒度开始求解,下面提出的新型聚类方法,就是从细粒度到粗粒度进行聚类。因此,下文所指的原始粒度(UN,FQ,S)对应的粒集UN=vi|i=1,2,N,就是论域U=
22、ui|i=1,2,N上的最细粒度UN=ui|i=1,2,N。粒属性FQ是所有粒子相互共有的一组特征,目前已有成熟的聚类算法,如划分聚类(k-M e a n s、围绕 中 心 点 的 划 分 聚 类P AM(P a r t i t i o n i n g A-r o u n d M e d o i d)、层次聚类(自底向上的层次聚类AGN E S(A g g l o m e r a t i v e N e s t i n g)、自顶向下的层次聚类D I ANA(D I v i s i v e ANA l y s i s)和密度聚类D B S C AN(D e n s i t y-B a s e
23、d S p a t i a l C l u s t e r i n g o f A p p l i c a t i o n s w i t h N o i s e),本质上都是基于粒属性离散值的距离度量,进而对样本集进行聚类。基于粒属性的聚类方法,作者在文献1 2,1 5 中另有讨论。本文不讨论粒属性,仅从粒结构上讨论信息粒化和聚类方法。因此,粒度(UN,FQ,S)可以简单地表示为二元组(UN,S)。并且,由于粒结构作为代数被广泛应用于信息和通信领域,所以UN中的粒结构S被特指为代数二元算子(x,y),即粒度简化为二元组(UN,)。2.3 基于粒计算的聚类方法图2展示了聚类过程的典型步骤,以及
24、本文工作的重点,即从粒计算的角度设计新型聚类方法的框架。图2下层是一个通用的聚类过程,包括从源数据中选择特征、预处理数据、聚类方法选择和验证聚类结果以及在应用中将最终聚类结果解释为知识表示4个步骤。图2上层给出了本文提出的基于代数粒的聚类方法的主要内容,包括代数粒定义的预处理和粒度粗化过程的聚类方法,对应于机器学习视角下的特征选择和聚类方法选择。F i g u r e 2 C l u s t e r i n g p r o c e s s f r o m t h e p e r s p e c t i v e o f g r a n u l a r c o m p u t i n g图2 粒计
25、算视角下的聚类过程图2上层的粒度定义到粒度粗化的过程,本质上是粒计算中的粒化过程,它旨在将未分组的粒子(细粒度)聚集成几个部分(粗粒度),而这也正是粒度聚类过程。例如,3 5岁、2个月、1 3天的客户可以被聚类成3 5岁客户的粗粒度,并且也可以被继续聚类成中年(3 05 5岁)客户的更粗粒度。在本文的设计中,数据预处理是生成信息粒度,从粒度计算角度看,其目标是在粒化之前的信息格式化和粒度创建。聚类方法对应粒计算的粒化过程,即将具有模糊或不确定性的不同粒子进行聚类。因此,预处理和聚类方法对应于粒化过程中的粒度定义和粒度粗化过程。3 本文方法基于图2中的通用聚类框架和新型聚类方法,本节从粒计算的角
- 配套讲稿:
如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。