基于最大决策熵的快速属性约简算法.pdf

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 基于最大基于最大决策熵的决策熵的快速属性快速属性约简算法约简算法 袁袁 梅梅 烟台大学计算机与控制工程学院，山东 烟台 收稿日期：2023年5月27日；录用日期：2023年6月27日；发布日期：2023年7月5日 摘摘 要要 在大数据时代背景下，各领域数据爆炸式增长，数据类型复杂多样。针对决策系统中基于最大决策熵的在大数据时代背景下，各领域数据爆炸式增长，数据类型复杂多样。针对决策系统中基于最大决策熵的属性属性约简算法在大规模数据集下运行效率低约简算法在大规模数据集下运行效率低的的问题，提出了一种基于启发式的快速属性约简算法。本文问题，提出了一种基于启发式的快速属性约简算法。本文提出的提出的算法算法首先研究了属性和对象在属性约简过程中的变化对其产生影响，其次提出了属性重要度保序首先研究了属性和对象在属性约简过程中的变化对其产生影响，其次提出了属性重要度保序性的相关定理。最后通过性的相关定理。最后通过UCI数据集对提出算法的有效性进行验证，结果表明提出的快速属性约简算法数据集对提出算法的有效性进行验证，结果表明提出的快速属性约简算法的运行效率更高。的运行效率更高。关键词关键词 快速快速属性约简算法属性约简算法，粗糙集，最大决策熵，粗糙集，最大决策熵，决策系统，决策系统 Fast Attribute Reduction Algorithm Based on Maximum Decision Entropy Mei Yuan School of Computer and Control 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 based 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 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 Fast 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.引言引言 粗糙集理论是用于处理不精确、不一致、不完备信息和知识的有效工具1 2。如今，学者们对粗糙集理论已经进行了深入探索，相应的属性约简3 4 5 6方法也较为完善。Kryszkiewicz 7在不完备决策系统下引入广义决策保持约简，介绍了相关决策规则的提取，并提出了基于差别矩阵的广义决策保持约简方法。差别矩阵方法虽然可以求出所有约简结果，但其效率相对于启发式算法较低。2002 年王国胤等8从信息论观点出发，将条件信息熵作为启发式信息，设计了启发式属性约简算法；2018 年，Gao 9提出了最大决策熵的启发式属性约简算法。2019 年 Zhang 等10等提出了启发式的广义决策属性约简。现阶段，对于大规模数据集，有关属性约简的快速算法研究已取得许多成果。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 是一个映射函数，: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=，通常简写为 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 的正域和边界域的定义：()()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 ATCD 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 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决策信息系统(),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/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.基于最大决策熵的加速算法基于最大决策熵的加速算法 定理定理 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 上的最大 决策熵。()()()()()()()()()()()()()()()()()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=，CP=，PP，故()()|UUCCMHD PMHD P=。同理可得()()|UUCCMHD PMHD P=。因此()()()()()|UUUCCCMHD PUUMHD PUUMHD P=，所以()(),outerouterUUSiga P C DSiga P C DUU=。因此，若()(),outerouterUUSiga P C DSigb P C D，则()(),outerouterUUSiga P C DSigb P C D。通过表1所示的ACC_HA_MDE算法，可以快速计算基于最大决策熵的属性约简。其中ACC_HA_MDE 在步骤 5 的时间复杂度为()()211biiiO abi=+；而在表 2 所示的 HA_MDE 算法在步骤 4 的时间复杂度为()2O ab。因此，ACC_HA_MDE 的效率更高。袁梅 DOI:10.12677/hjdm.2023.133022 226 数据挖掘 Table 2.Attribute reduction algorithm based on maximum decision entropy(HA_MDE)9 表表 2.基于最大决策熵的属性约简算法9 输入：决策系统。输出：约简结果 Re。1.初始化，core=，Re=;2.计算 U 在 C 和 D 上的等价类；3.计算每个属性的内部属性重要度，并求出核；4.重复：选择属性重要度最大的属性加入 Re；5.去冗余；6.输出 Re。5.实验分析实验分析 实验环境采用Intel Corei3-9100(3.6 GHz)处理器、8 GB内存和Windows10操作系统。算法使用Python语言进行编写，在开发工具 PyCharm2020 上编译运行。为了验证提出算法的有效性，本实验选取了 8 组 UCI 数据集，为了更好验证所提出算法的有效性，需要对数据集进行预处理。首先将数据集使用 WEKA3.8.5 进行等频离散化，并将数据集中名词性数据转化为整数表示。对于缺失数据，利用对应属性下占最多比例的属性值进行替换。表 3 展示了每个数据集的相关信息。在实验过程中，将各数据集按对象数目分成 10 份(每份为10U)，或将各数据集的属性每份分成10C。Table 3.Data set information 表表 3.数据集信息 数据集名称 对象数 特征数 类别数 1 Audiology 200 69 24 2 Glass Identification 214 10 7 3 Chronic-Kidney-Disease 400 24 2 4 Connectionist Bench 528 10 11 5 Hill-valley-with-testing 606 100 2 6 Audit-risk 776 26 2 7 QSAR Biodegradation 1055 41 2 8 Kr-vs-kp 3196 36 2 约简效率对比约简效率对比 本节对 HA_MDE 与 ACC_HA_MDE 两种算法的约简效率进行比较分析，通过 8 组 UCI 数据集进行实验展示。表 4 展示了 HA_MDE 与 ACC_HA_MDE 两种算法的时间以及约简长度。可以看到 7 个数据集的 ACC_HA_MDE 算法的时间比 HA_MDE 算法的消耗的时间少。例如 Audit-risk 数据集，本文提出的算法 ACC_HA_MDE 耗时 0.32 s，而启发式算法 HA_MDE 运行时间为 2.01 s，HA_MDE 运行时间约为ACC_HA_MDE 运行时间的 6.281 倍。而 Hill 数据集，本文提出的算法 ACC_HA_MDE 相对于 HA_MDE袁梅 DOI:10.12677/hjdm.2023.133022 227 数据挖掘 耗时较多，由于该数据集在迭代中删除的正域与属性不够多，使消耗时间增多。由于删除的是冗余属性和对象，所以两种算法的约简长度相同。Table 4.Comparison of time and reduction length of HA_MDE and ACC_HA_MDE algorithms 表表 4.HA_MDE 和 ACC_HA_MDE 两种算法的时间与约简长度比较 数据集名称 HA_MDE ACC_HA_MDE 运行时间/s 约简长度 运行时间/s 约简长度 1 Audiology 4.27 14 1.80 14 2 Glass Identification 0.12 6 0.06 6 3 Chronic-Kidney-Disease 0.48 7 0.22 7 4 Connectionist Bench 0.41 7 0.15 7 5 Hill-valley-with-testing 11.02 14 14.27 14 6 Audit-risk 2.01 8 0.32 8 7 QSAR Biodegradation 14.52 12 3.41 12 8 Kr-vs-kp 9.18 29 2.55 29 图 1 中用实心六边形折线表示 HA_MDE、用实心倒三角形折线表示 ACC_HA_MDE，展示了两种算法在 8 组数据集上随论域大小变化的时间消耗曲线，横坐标表示论域大小，纵坐标表示算法运行时间。从图 1 中可以看到除了 Hill 数据集外，其余 7 个数据集在本文提出的算法 ACC_HA_MDE 运行时间相对于 HA_MDE 运行时间较短。因此，本文提出的 ACC_HA_MDE 算法相对于启发式 HA_MDE 算法提高了算法效率。袁梅 DOI:10.12677/hjdm.2023.133022 228 数据挖掘 Figure 1.Comparison of algorithm reduction efficiency with object increase 图图 1.随着对象增加算法约简效率的比较 6.总结总结 本文针对基于最大决策熵的约简目标提出了在完备决策信息系统下的快速属性约简算法。在每轮迭代中首先删除一部分正域，使数据集中对象数目减少，以提高算法的效率；其次删除冗余属性，可以进一步提高算法的效率。实验选取 8 组 UCI 数据集对提出的算法进行有效性验证，实验结果表明：本文提出算法的效率优于经典算法的效率，实现了对经典算法的优化。基金项目基金项目 本文受烟台市科技计划项目(编号：2022XDRH016)的资助。参考文献参考文献 1 Pawlak,Z.(1982)Rough Sets.International Journal of Computer and Information Sciences,11,341-356.https:/doi.org/10.1007/BF01001956 2 杨习贝,颜旭,徐苏平,于化龙.基于样本选择的启发式属性约简方法研究J.计算机科学,2016,43(1):40-43.3 Chen,H.M.,Li,T.R.,Cai,Y.,Luo,C.and Fujita,H.(2016)Parallel Attribute Reduction in Dominance-Based Neigh-borhood Rough Set.Information Sciences,373,351-368.https:/doi.org/10.1016/j.ins.2016.09.012 4 Wang,C.Z.,Shao,M.W.,Sun,B.Q.and Hu,Q.H.(2015)An Improved Attribute Reduction Scheme with Covering Based Rough Sets.Applied Soft Computing,26,235-243.https:/doi.org/10.1016/j.asoc.2014.10.006 5 Min,F.,Zhang,Z.H.and Dong,J.(2018)Ant Colony Optimization with Partial-Complete Searching for Attribute Re-袁梅 DOI:10.12677/hjdm.2023.133022 229 数据挖掘 duction.Journal of Computational Science,25,170-182.https:/doi.org/10.1016/j.jocs.2017.05.007 6 Miao,D.Q.,Zhao,Y.,Yao,Y.Y.,Li,H.X.and Xu,F.F.(2009)Relative Reducts in Consistent and Inconsistent Deci-sion Tables of the Pawlak Rough Set Model.Information Sciences,179,4140-4150.https:/doi.org/10.1016/j.ins.2009.08.020 7 Kryszkiewicz,M.(1998)Rough Set Approach to Incomplete Information Systems.Information Sciences,112,39-49.https:/doi.org/10.1016/S0020-0255(98)10019-1 8 王国胤,于洪,杨大春.基于条件信息熵的决策表约简J.计算机学报,2002,25(7):759-766.9 Gao,C.,Lai,Z.H.,Zhou,J.,Zhao,C.R.and Miao,D.Q.(2108)Maximum Decision Entropy-Based Attribute Reduc-tion in Decision-Theoretic Rough Set Model.Knowledge-Based Systems,143,179-191.https:/doi.org/10.1016/j.knosys.2017.12.014 10 Zhang,N.,Gao,X.Y.and Yu,T.Y.(2019)Heuristic Approaches to Attribute Reduction for Generalized Decision Pre-servation.Applied Sciences,9,Article 2841.https:/doi.org/10.3390/app9142841 11 徐章艳,刘作鹏,杨炳儒,宋威.一个复杂度为2(),()OmaxC UO CU C的快速属性约简算法J.计算机学报,2006,29(3):391-399.12 Qian,Y.H.,Liang,J.Y.,Pedrycz,W.and Dang,C.Y.(2010)Positive Approximation:An Accelerator for Attribute Reduction in Rough Set Theory.Artificial Intelligence,174,597-618.https:/doi.org/10.1016/j.artint.2010.04.018 13 Du,W.S.and Hu,B.Q.(2018)A Fast Heuristic Attribute Reduction Approach to Ordered Decision Systems.European Journal of Operational Research,264,440-452.https:/doi.org/10.1016/j.ejor.2017.03.029 14 Sang,B.B.,Chen,H.M.,Yang,L.,Zhou,D.P.,Li,T.R.and Xu,W.H.(2021)Incremental Attribute Reduction Ap-proaches for Ordered Data with Time-Evolving Objects.Knowledge-Based Systems,212,Article ID:106583.https:/doi.org/10.1016/j.knosys.2020.106583 15 Dong,L.J.and Chen,D.G.(2020)Incremental Attribute Reduction with Rough Set for Dynamic Datasets with Simul-taneously Increasing Samples and Attributes.International Journal of Machine Learning and Cybernetics,11,1339-1355.https:/doi.org/10.1007/s13042-020-01065-y 16 Shu,W.H.,Qian,W.B.and Xie,Y.H.(2020)Incremental Feature Selection for Dynamic Hybrid Data Using Neigh-borhood Rough Set.Knowledge-Based Systems,194,Article ID:105516.https:/doi.org/10.1016/j.knosys.2020.105516 17 鲍迪,张楠,童向荣,岳晓东.区间值决策表的正域增量式属性约简算法J.计算机应用,2019,39(8):2288-2296.