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

在大数据时代背景下，各领域数据爆炸式增长，数据类型复杂多样。针对决策系统中基于最大决策熵的属性约简算法在大规模数据集下运行效率低的问题，提出了一种基于启发式的快速属性约简算法。本文提出的算法首先研究了属性和对象在属性约简过程中的变化对其产生影响，其次提出了属性重要度保序性的相关定理。最后通过UCI数据集对提出算法的有效性进行验证，结果表明提出的快速属性约简算法的运行效率更高。

粗糙集理论是用于处理不精确、不一致、不完备信息和知识的有效工具[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)