廖 倩，李相朋

（武汉纺织大学 数学与计算机学院，湖北 武汉 430073）

基于决策规则的属性约简算法

廖 倩，李相朋*

（武汉纺织大学 数学与计算机学院，湖北 武汉 430073）

属性约简是粗糙集的核心问题之一。本文基于决策规则给出属性约简相关结论和属性重要性，提出启发式约简算法，引入黄金分割法思想，提高算法效率，并以实例验证算法有效性和正确性。

属性约简；决策规则；重要性；黄金分割

1 引言

粗糙集理论[1,2]是由Z.pawlak于1982年提出的，它是一种刻画不完整性和不确定性的数学工具，能有效地分析和处理不精确、不一致、不完整等各种不完备信息，并从中发现隐含的知识，揭示潜在的规律。目前，粗糙集理论已被广泛应用在机器学习与知识发现、数据挖掘、决策支持与分析等方面。

信息系统是粗糙集理论的主要研究对象，属性约简是信息系统的核心问题之一。所谓属性约简就是在保持分类能力或决策能力不变的情况下，删除冗余属性。由于求所有约简已被证明是NP完全问题[3]，故很多算法[4,5]一般采用启发式信息找出最优或次优约简，这些算法的共同特点是利用属性的重要性作为启发式信息。因此，如何有效的计算属性的重要性，对提高算法效率是非常重要的。目前对属性重要性的度量主要有基于分辨矩阵属性频率[6,7]、基于正区域[8,9]和基于信息熵[10]等方法。然而，这些方法的复杂度较高，影响约简算法的效率。

现有粗糙集算法的低效性在一定程度上限制了粗糙集理论的广泛应用，故寻求高效的粗糙集算法具有重要的意义。……