基于最大决策熵的快速属性约简算法.pdf
《基于最大决策熵的快速属性约简算法.pdf》由会员分享,可在线阅读,更多相关《基于最大决策熵的快速属性约简算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、Hans Journal of Data Mining 数据挖掘数据挖掘,2023,13(3),222-229 Published Online July 2023 in Hans.https:/www.hanspub.org/journal/hjdm https:/doi.org/10.12677/hjdm.2023.133022 文章引用文章引用:袁梅.基于最大决策熵的快速属性约简算法J.数据挖掘,2023,13(3):222-229.DOI:10.12677/hjdm.2023.133022 基于最大基于最大决策熵的决策熵的快速属性快速属性约简算法约简算法 袁袁 梅梅 烟台大学计算机与控
2、制工程学院,山东 烟台 收稿日期:2023年5月27日;录用日期:2023年6月27日;发布日期:2023年7月5日 摘摘 要要 在大数据时代背景下,各领域数据爆炸式增长,数据类型复杂多样。针对决策系统中基于最大决策熵的在大数据时代背景下,各领域数据爆炸式增长,数据类型复杂多样。针对决策系统中基于最大决策熵的属性属性约简算法在大规模数据集下运行效率低约简算法在大规模数据集下运行效率低的的问题,提出了一种基于启发式的快速属性约简算法。本文问题,提出了一种基于启发式的快速属性约简算法。本文提出的提出的算法算法首先研究了属性和对象在属性约简过程中的变化对其产生影响,其次提出了属性重要度保序首先研究了
3、属性和对象在属性约简过程中的变化对其产生影响,其次提出了属性重要度保序性的相关定理。最后通过性的相关定理。最后通过UCI数据集对提出算法的有效性进行验证,结果表明提出的快速属性约简算法数据集对提出算法的有效性进行验证,结果表明提出的快速属性约简算法的运行效率更高。的运行效率更高。关键词关键词 快速快速属性约简算法属性约简算法,粗糙集,最大决策熵,粗糙集,最大决策熵,决策系统,决策系统 Fast Attribute Reduction Algorithm Based on Maximum Decision Entropy Mei Yuan School of Computer and Contr
4、ol Engineering,Yantai University,Yantai Shandong Received:May 27th,2023;accepted:Jun.27th,2023;published:Jul.5th,2023 Abstract In the era of big data,data in various fields is growing explosively,and data types are complex and diverse.Aiming at the low efficiency of attribute reduction algorithm bas
5、ed on maximum decision entropy in decision system under large data sets,a fast attribute reduction algorithm based on heuristic is proposed.The algorithm proposed in this paper firstly studies the influence of the changes of attributes and objects in the process of attribute reduction,and then puts
6、forward the related theorem about the rank preservation of attributes.Finally,the effectiveness of the pro-posed algorithm is verified by the UCI data set,and the results show that the proposed fast attribute reduction algorithm is more efficient.袁梅 DOI:10.12677/hjdm.2023.133022 223 数据挖掘 Keywords Fa
7、st Attribute Reduction Algorithm,Rough Set,Maximum Decision Entropy,Decision System 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.引言引言 粗糙集理论是用于处理不精确、不一致、不完备信
8、息和知识的有效工具1 2。如今,学者们对粗糙集理论已经进行了深入探索,相应的属性约简3 4 5 6方法也较为完善。Kryszkiewicz 7在不完备决策系统下引入广义决策保持约简,介绍了相关决策规则的提取,并提出了基于差别矩阵的广义决策保持约简方法。差别矩阵方法虽然可以求出所有约简结果,但其效率相对于启发式算法较低。2002 年王国胤等8从信息论观点出发,将条件信息熵作为启发式信息,设计了启发式属性约简算法;2018 年,Gao 9提出了最大决策熵的启发式属性约简算法。2019 年 Zhang 等10等提出了启发式的广义决策属性约简。现阶段,对于大规模数据集,有关属性约简的快速算法研究已取得
9、许多成果。2006 年,徐章艳等11提出了基于基数排序的快速属性约简算法;2010 年,Qian 等12提出了正域加速属性约简算法,2018 年,Du 等13在序决策系统下提出了快速属性约简算法。另外,增量式属性约简算法14 15 16 17利用已有的信息进行增量更新,不需要重新计算,从而实现算法效率的提高。本文从对象和属性的角度考虑研究,通过理论分析和实验结果均表明了该算法的有效性。2.基本概念基本概念 定义定义 1 1信息系统是由四元组(),ISU AT V f=组成,其中 U 表示论域,是非空有限对象组成的集合;AT 表示非空有限属性集合;pV表示属性pAT的值域,有pP ATVV=;f
10、 是一个映射函数,:f UATV为论域 U 中的每一个对象在pAT 上都有一个值。若ATCD=,其中 C 表示非空有限的条件属性集合,D 表示非空有限的决策属性集合,且CD,则四元组记为(),DSU ATCD V f=称为决策信息系统。定义定义 2 1四元组(),DSU ATCD V f=为一个决策信息系统,对任意非空属性集合PAT,有 P 在 U 上的不可区分关系定义为:()()()(),|,IND Px yUUp xp ypP=(1)不可区分关系()IND P是一个满足自反性、对称性和传递性的等价关系。由不可区分关()IND P导出对论域 U 的划分为()|PU IND PxxU=,通常简
11、写为 U/P,其中 Px表示包含 x 的等价类,易得()IND Ppp Pxx=。定义定义 3 1决策信息系统的四元组(),DSU ATCD V f=,由决策属性 D 导出 U 的划分为()12,1mU DD DDmU=,对PC,决策类 U/D 关于条件属性集 P 的下近似和上近似的定义为:()()()()12,mP U DP DP DP D=(2)Open AccessOpen Access袁梅 DOI:10.12677/hjdm.2023.133022 224 数据挖掘 ()()()()12,mP U DP DP DP D=(3)决策类 U/D 关于条件属性集 P 的正域和边界域的定义:(
12、)()iPiDU DPOSU DP D=(4)()()()iiPiiDU DDU DBNDU DP DP D=(5)定义定义 4 9决策信息系统(),DSU ATCD V f=,U 在 C 以及 D 上的划分分别为 12,mU CU UU=,12,nU DY YY=,其中mU C=,nU D=。对于任意一个等价类iUU C,该等价类的最大包含度以及最大决策分别定义为:()()()()()12|max|,|,|iiiniMP D UP Y UP YUP YU=(6)()()()()1|,|ijiiMD D Ufy DyYP Y UMP D U=(7)定义定义 5 9决策信息系统(),DSU AT
13、CD V f=,U 在 C 以及 D 上的划分分别为 12,mU CU UU=,12,nU DY YY=,其中mU C=,nU D=。C 相对于 D 的最大包含度的概 率分布定义为:()()()()()()()()()()1122|,1|,|,1|,|,1|mmMS D CMP D UMP D UMP D UMP D UMP D UMP D U=(8)定义定义 6 9决策信息系统(),DSU ATCD V f=,若QC,Q 相对于 D 的最大包含度的概率分布定义为()()()()()()()()()()1122|,1|,|,1|,|,1|mmMS D QMP D UMP D UMP D UMP
14、 D UMP D UMP D U=,那么对于任意一个等价类iUU Q的最大决策熵以及 B 相对于 D 的最大决策熵分别定义为:()()()()()()()1|1|log|1log11iiiiiiMP D UMP D UMH D UP UMP D UMP D Ummm=+(9)()()1|miiMH D BMH D U=(10)3.基于最大决策熵的启发式约简基于最大决策熵的启发式约简 定义定义 7 9决策信息系统(),DSU CD V f=,若QC,qQ,q 的内部属性重要度定义为:()()(),|innerUUUCCSigq Q C DMPD QqMPD Q=(11)定义定义 8 9决策信息系
15、统(),DSU CD V f=,若QC,qCQ,q 的外部属性重要度定义为:()()(),|outerUUUCCSigq Q C DMPD QMPD Qq=(12)定义定义 9 9决策信息系统(),DSU CD V f=,QC,qQ,若(),0innerUSigq Q C D,则 q 为核属性;若(),0innerUSigq Q C D=,则 q 为冗余属性。定义定义 10 9决策信息系统(),DSU CD V f=,若QC是 C 的一个约简,当且仅当满足以下两个 条件:1)()()|MH D QMH D C=;2)对QQ,有()()|MH D QMH D C。袁梅 DOI:10.12677/
16、hjdm.2023.133022 225 数据挖掘 Table 1.Fast reduction algorithm based on maximum decision entropy(ACC_HA_MDE)表表 1.基于最大决策熵的快速约简算法 输入:决策系统。输出:约简结果 Re。1.初始化,core=,Re=;2.计算 U 在 C 和 D 上的等价类;3.计算每个属性的内部属性重要度,并求出核;4.令Recore=,1i=,1UU=,1CC=,delC=;5.重复:选择属性重要度最大的属性加入 Re,并在该过程中删除冗余属性和对象;6.去冗余;7.输出 Re。4.基于最大决策熵的加速算法
17、基于最大决策熵的加速算法 定理定理 1 决策信息系统(),DSU CD V f=,PC,若,a bCPP,其中,CCP=,()()()|,UUCCPc MHD PMHDPccCP=,(),CPUUPOSU D=,并且()(),outerouterUUSiga P C DSigb P C D,则()(),outerouterUUSiga P C DSigb P C D。证明:若121,ppmU PU UUUU+=,12,nU DY YY=,其中()1,CppmPUUUPOSU D+。因此对每个等价类(),CiPUPOSU D,存在决策类 Y,使iiUYU=。用()|UCMHD P表示在 U 上的
18、最大 决策熵。()()()()()()()()()()()()()()()()()111|1|log|1log111|1|log|1log111|log|1miiUCiiiipiiiiiiiiiMP D UMP D UMHD PP UMP D UMP D UmmmMP D UMP D UP UMP D UMP D UmmmUP UMP D UMP D UmU=+=+=+()()()1|1|log11|piiiUCMP D UMP D UmmUMHD PU=由于(),CPUUPOSU D=,所以(),CPPOSU D=,又因为CCP=,其中()()()|,UUCCPc MHD PMHDPccCP
- 配套讲稿:
如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。