基于组合加速机制的多特定类快速正域约简.pdf
《基于组合加速机制的多特定类快速正域约简.pdf》由会员分享,可在线阅读,更多相关《基于组合加速机制的多特定类快速正域约简.pdf(10页珍藏版)》请在咨信网上搜索。
1、Hans Journal of Data Mining 数据挖掘数据挖掘,2023,13(3),203-212 Published Online July 2023 in Hans.https:/www.hanspub.org/journal/hjdm https:/doi.org/10.12677/hjdm.2023.133020 文章引用文章引用:张小飞.基于组合加速机制的多特定类快速正域约简J.数据挖掘,2023,13(3):203-212.DOI:10.12677/hjdm.2023.133020 基于组合加速机制的多特定类快速正域约简基于组合加速机制的多特定类快速正域约简 张小飞张小
2、飞 烟台大学计算机与控制工程学院,山东 烟台 收稿日期:2023年5月27日;录用日期:2023年6月27日;发布日期:2023年7月5日 摘摘 要要 信息技术的快速发展给社会带来了海量的高维数据,这些海量数据中隐藏着大量有价值的信息。如何高信息技术的快速发展给社会带来了海量的高维数据,这些海量数据中隐藏着大量有价值的信息。如何高效处理大规模数据并从中提取有效知识已成为计算机领域的研究热点。基于粗糙集理论的属性约简,可效处理大规模数据并从中提取有效知识已成为计算机领域的研究热点。基于粗糙集理论的属性约简,可以在保证数据分类能力不变的前提下,删除冗余属性,从而实现数据的有效降维。在实际应用中,决
3、策以在保证数据分类能力不变的前提下,删除冗余属性,从而实现数据的有效降维。在实际应用中,决策者往往只关注某些特定决策标签的有效信息提取。在多特定类属性约简中,传统的启发式算法约简效率者往往只关注某些特定决策标签的有效信息提取。在多特定类属性约简中,传统的启发式算法约简效率较低。针对该问题,本文从对象、属性和粒度的视角出发,提出了基于组合加速机制的多特定类快速正较低。针对该问题,本文从对象、属性和粒度的视角出发,提出了基于组合加速机制的多特定类快速正域约简算法。最后,实验选取域约简算法。最后,实验选取6组数据集进行实验,从约简长度、参与组数据集进行实验,从约简长度、参与迭代的对象规模、迭代次数和
4、约迭代的对象规模、迭代次数和约简时间四个方面验证了所提算法在多特定类约简中的有效性。简时间四个方面验证了所提算法在多特定类约简中的有效性。关键词关键词 粗糙集,属性约简,粒计算,加速机制粗糙集,属性约简,粒计算,加速机制 A Fast Attribute Reduction Algorithm Based on Fusing Acceleration Mechanism for Multi-Specific Classes Positive Region Xiaofei Zhang School of Computer and Control Engineering,Yantai Univer
5、sity,Yantai Shandong Received:May 27th,2023;accepted:Jun.27th,2023;published:Jul.5th,2023 Abstract The rapid development of information technology has brought massive high-dimensional data to society,which hides a large amount of valuable information.How to efficiently deal with these large-scale da
6、ta and extract effective knowledge from it has become a research hotspot in the field 张小飞 DOI:10.12677/hjdm.2023.133020 204 数据挖掘 of computer science.Attribute reduction based on rough set theory can remove redundant attributes while keeping the ability of data classification unchanging,thus reducing
7、 the dimension of data effectively.In practical applications,decision makers often only focus on the effective in-formation extraction of certain specific decision labels.In the attribute reduction of multi-specific classes,traditional heuristic algorithms have lower reduction efficiency.To solve ab
8、ove problems,this paper proposes a fast attribute reduction algorithm based on fusing acceleration mechanism for multi-specific classes positive region,which is from the perspectives of objects,attributes and granularity.Finally,six datasets were used for experiments.And the experimental results sho
9、w the effectiveness of the proposed accelerating algorithm in this paper for multi-specific decision classes attribute reduction,which is verified from four aspects:reduction length,size of objects in iterations,number of iterations and reduction time.Keywords Rough Set,Attribute Reduction,Granular
10、Computing,Acceleration Mechanism Copyright 2023 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 粗糙集理论1 2是一种处理不精确、不一致信息的有效数学工具,具有极为广泛的应用场景,目前已经成功应用于智能工业3 4、图像处理5 6、智能决策7等
11、多个领域。属性约简8 9是粗糙集理论研究中的关键课题之一。属性约简的核心思想是在保持分类能力不变的前提下,删除冗余属性,从而实现海量数据的有效降维。基于贪心策略的启发式算法是获取属性约简的主要方法之一。传统的启发式属性约简算法效率较低,难以有效地处理大规模数据,为了进一步提高算法的约简效率,许多学者从多种角度对启发式算法的加速机制展开了研究。Qian 等10提出了正向近似的加速策略,通过在算法迭代过程中逐步删除正域的方式,有效提高了算法效率。陈曼如等11从样本和属性的视角出发,通过减少正域样本和算法的迭代次数,设计了基于正区域不变的快速属性约简算法。赵立威等12在序决策系统下通过优化启发式算法
12、中的属性添加策略,构建了基于特征粒的快速约简算法。Chen 等13从对象、属性和粒度视角设计了基于决策系统全部分类的加速机制,提出了基于融合加速机制的通用属性约简加速算法框架。以上算法都是针对决策系统中全部决策类进行属性约简,但在实际应用中,决策者往往对某一个或多个特定类决策类更感兴趣。为此许多学者针对特定类的属性约简问题展开了研究并取得了很多优秀的研究成果。Liu 等14在多种约简目标下建立了基于差别矩阵方法的特定类属性约简,为局部属性约简提供了新的思路。Zhang 等15从信息论和代数角度分析了全部决策类与特定类约简之间的层次联系。Wang等16在邻域决策系统中,针对特定类提出了局部条件熵
13、的定义,并设计了基于条件熵的局部属性约简算法。虽然有大量学者针对启发式算法进行了优化,但在多特定类的属性约简研究中,现有的经典启发式属性约简算法仍存在效率较低的问题,难以有效处理大规模数据。针对该问题,本文从多特定类的视角出发,提出了多特定类正域约简的定义,并结合对象、属性和粒度的加速方法,设计了基于组合加速机制的多特定类快速正域约简算法,并通过实验验证了所提算法的有效性。Open AccessOpen Access张小飞 DOI:10.12677/hjdm.2023.133020 205 数据挖掘 2.基本概念基本概念 给定一个 Pawlak 决策系统(),SU CD=,其中,U 为对象集合
14、,称为论域,C 和 D 分别为条件属性集和决策属性集。(),itf u a表示对象iu在属性ta上的取值。例如表 1 所示的 Pawlak 决策系统中,论域1234,Uu u u u=,条件属性集123,Ca a a=,决策属性 Dd=。Table 1.Pawlak decision system 表表 1.Pawlak 决策系统 U 1a 2a 3a d 1u 2 1 2 1 2u 2 0 1 2 3u 1 2 0 2 4u 0 1 1 3 定义定义 1 1给定一个决策系统(),SU CD=,对于AC,定义 A 上的不可区分关系为:()()()2,|,AijtitjtRu uUaA f u
15、af u a=.AR是一个满足自反、对称和传递的等价关系,根据等价关系AR可导出论域上的一个划分|AiiAU RuuU=,其中,()|,ijijAAuuUu uR=表示对象iu关于属性集 A 的等价类,为方便表示,AU R可简记为U A。基于决策属性 D 对论域形成的划分为12,mU DD DD=,称为决策类集合,集合mcsDU D(1mcsDU D)称为多特定类。下面给出多特定类mcsD上下近似的定义。定义定义 2 1给定一个决策系统(),SU CD=,mcsDU D,对于AC,多特定类mcsD关于属性集 A 的上下近似集合分别为:()|kmcsAmcsiikAADDRDuuD=,()|km
16、csAmcsiikAADDRDuuD=.基于上下近似的概念,以多特定类mcsD为目标概念,通过粗糙集理论可以将论域划分为正域、边界域和负域,定义分别为:()()AmcsAmcsPOSDRD=,()()()AmcsAmcsAmcsBNDDRDRD=,()()AmcsAmcsNEGDURD=.由于mcsDU D且1mcsDU D,因此多特定类具有良好的扩展性,多特定类既可以包含一个决 策类也可以包含多个甚至全部决策类。3.多特定类正域约简多特定类正域约简 在实际应用中,决策者往往更偏好于某一个或多个特定决策标签的有效知识提取,本节将介绍多特定类正域约简的相关概念和算法。定义定义 3 给定一个决策系
17、统(),SU CD=,mcsDU D,AC,对于aA,属性 a 的内部属性张小飞 DOI:10.12677/hjdm.2023.133020 206 数据挖掘 重要度为:()()(),inmcsAmcsmcsAaSiga A DPOSDPOSD=.定义定义 4 给定一个决策系统(),SU CD=,mcsDU D,AC,对于aCA,属性 a 的外部属性重要度为:()()(),outmcsmcsAmcsAaSiga A DPOSDPOSD=.内部属性重要度可以用来评估属性是否冗余,常用于求核和去冗余操作。外部属性重要度往往用于迭代过程中的最佳属性选择。定义定义 5 给定一个决策系统(),SU CD
18、=,mcsDU D,若AC为多特定类mcsD的正域约简,则满足如下条件:1)()()AmcsCmcsPOSDPOSD=;2)AA,()()AmcsCmcsPOSDPOSD。其中,条件 1)保证了约简前后多特定类正域不发生变化,条件 2)则保证了约简属性集中的任一属性都是必要的。基于正向贪婪的多特定类启发式属性约简算法如表 2 所示。该算法的流程图如图 1 所示。在算法 FGARM 中,Step1 为初始化过程;Step2 为迭代选取属性的过程,根据外部属性重要度对属性进行评估,每次选择一个最佳属性添加至约简属性集中,直到满足中止条件为止;Step3 和 Step4 为去冗余和输出约简的过程。T
19、able 2.A forward greedy heuristic attribute reduction algorithm for multi-specific decision classes(FGARM)表表 2.基于正向贪婪的多特定类启发式属性约简算法 输入:决策系统(),SU CD=。输出:多特定类mcsD的一个正域约简 A。Step1:A=;Step2:若()()AmcsCmcsPOSDPOSD:Step2.1:对于bCA,计算(),outmcsSigb A D;Step2.2:令()1arg,outmcsbMax Sigb A D=,1AAb=;Step3:对于aA,如果(),
20、0inmcsSiga A D=,则令 AAa=;Step4:返回约简 A,算法结束。Figure 1.A flow chart of FGARM algorithm 图图 1.算法 FGARM 流程图 张小飞 DOI:10.12677/hjdm.2023.133020 207 数据挖掘 4.多特定类快速正域约简多特定类快速正域约简 算法 FGARM 在计算约简时存在待处理对象规模较大、属性迭代次数过多和待评估属性数目较多等问题,难以高效处理大规模数据。为进一步提高多特定类的约简效率,本节从对象、属性和粒度三个方面分析了多特定类启发式算法的加速机制,提出了基于组合加速机制的多特定类快速正域约简算
21、法。定理定理 1 给定一个决策系统(),SU CD=,mcsDU D,AC,对于aCA,满足:()()()UUUmcsAmcsmcsAaAaPOSDPOSDPOSD=,其中,()()UUAmcsAmcsUUPOSDNEGD=。定理 1 表明,随着属性的增加,边界域中的部分样本会被精确划分至正域,因此可以通过删除正域和负域的方式实现多特定类的对象加速。当所选多特定类为全部决策类时,此时负域为空集,此时算法退化到文献10中的情况,每次迭代过程中仅删除正域中的对象。定义定义 6 给定一个决策系统(),SU CD=,mcsDU D,属性集AC,ATCA=,对于ibAT,若 ()()()12131ATm
22、csmcsmcsbbbbbbPOSDPOSDPOSD且满足 ()()1121imcsmcsbbbiPOSDPOSD=,()()113211iimcsmcsbbbbiiPOSDPOSD=,()()11111iikkmcsmcsbbbbiiPOSDPOSD=,()()111111iikkmcsmcsbbbbiiPOSDPOSD+=,()()11111iiATATmcsmcsbbbbiiPOSDPOSD=,则称()11211,kkATGroup bb bbbb+=为属性1b的属性组。定义 6 为属性组的定义,在启发式算法的迭代过程中,可以通过构造属性组的方式向约简属性集中一次添加多个属性,降低算法的
- 配套讲稿:
如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。