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

廖 倩，李相朋

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

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

廖 倩，李相朋*

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

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

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

1 引言

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

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

现有粗糙集算法的低效性在一定程度上限制了粗糙集理论的广泛应用，故寻求高效的粗糙集算法具有重要的意义。目前许多约简算法都是基于保持正域不变的思想来实现[11,12]，本文基于确定决策规则不变给出属性约简相关结论和属性重要性，提出改进约简算法。改进的算法不需要计算分辨矩阵和正域，并且一次性可删除多个属性，减少计算量，从而提高算法效率。通过实例验证该约简算法有效性和正确性。

2 粗糙集基本概念[11,13]

3 基于决策规则的属性约简和属性重要性

3.1 属性约简

3.2 属性重要性

前面已经提到，很多算法都以属性重要性为启发信息进行属性约简。而我们知道属性约简只是手段，获取决策规则才是最终目的。为了保证决策规则的完整性，下面我们就在决策规则的基础上定义属性重要性。

用式（1）计算属性重要度后，对其进行排序，如果存在多个属性的重要度相同，则这些属性之间可任排。以此排序为启发式信息进行属性约简。

4 属性约简算法

4.1 黄金分割法[14]

黄金分割法是优化计算中的经典算法，以算法简单、效果显著而著称，是许多优化算法的基础。其基本思想是：依照“去坏留好”原则、对称原则、以及等比收缩原则来逐步缩小搜索范围。具体来说，就是在区间，如果x1的结果较好，令a=x1；如果x2的结果较好，令，重新开始。这样每次可将搜索区间缩小0.382倍或0.618倍，直至缩为一点。受该算法的启发，我们将这一方法应用到属性约简算法中。由于在约简算法中取两点进行研究时，判断过程较复杂，会增加算法本身的复杂度。因此，本文只取一个点进行研究，每次也能将搜索空间缩小0.618倍。

4.2 改进的属性约简算法

该算法的基本思想是根据属性的重要性从条件属性中逐渐删除属性重要性小的属性，从而得到一个相对约简。本算法改进的方面有三：一、计算属性重要度。根据定义6计算重要度时，无需生成分辨矩阵，节省空间；二、删除过程。传统约简算法，一次只删除一个属性，本文引入黄金分割的思想，一次性可以删除一个属性集，减少计算量；三、判断标准。传统约简算法基于正区域判断是否是约简集，而本算法根据是否为包含关系来判断。记该算法为算法2，具体步骤如下：

5 实例分析

下面通过一个例子来说明改进的约简算法，表1为某决策表。

表1 决策表

6 结束语

本文深入分析属性约简，提出改进约简算法。总的来说，改进算法以属性重要性为启发信息，基于等价类计算重要性，无需生成分辨矩阵，节省空间；以条件属性集为起点，无需计算核属性，降低复杂度；给出属性约简相关结论判断是否为相对约简，无需计算正域，判断过程更简单高效；引入黄金分割法思想，逐渐删除重要性小的属性集，节省时间。通过实例证明了本算法的有效性。本文算法只适用于一致决策表，应用该算法在不一致决策表中进行属性约简有待做进一步的研究。

[1] PAWLAK Z. Rough sets [J]. Communication of the ACM, 1995, 38(11):89-95.

[2] PAWLAK Z. Rough set theory and its applications to data analysis [J]. Cyberneties and System, 1998, 29(7): 661-668.

[3] Wong S K M, Ziarko W. On optimal decision rules in decision tables[J]. Bulletin of Polish Academy of Sciences, 1985, 33 (11-12):693-696.

[4] 李永华，蒋芸，王小菊. 一种基于Rough集的属性约简的改进算法[J].计算机应用,2008,28(8):2000-2002.

[5] 吴静，邹海. 基于属性重要性的属性约简算法[J].计算机应用与软件，2010,27(2)：255-257.

[6] 王珏，王任，苗夺谦，等. 基于Rough Set理论的“数据浓缩”[J].计算机学报, 1998 , 21 (5): 393-399.

[7] Wang Jue, Wang Ju. Reduction algorithms based on discernibility matrix: The ordered attributes method[J]. Journal of Computer Science & Technology , 2001 , 16 (6) : 489-504.

[8] Hu X H, Cercone N. Learning in relational databases: A rough setapproach[J]. International Journal of Computational Intelligence,1995, 11 (2): 323-338.

[9] Jelonek J, Krawiec K, Slowinski R. Rough set reduction of attributes and their domains for neural networks[J].International Journal of Computational Intelligence , 1995 , 11 (2) : 339-347.

[10] 苗夺谦，胡桂荣. 知识约简的一种启发式算法[J]. 计算研究与发展, 1999 , 36 (6) : 681-684.

[11] 张文修，吴伟志，梁吉业，等. 粗糙集理论与方法[M]. 北京：科学出版社,2001.

[12] 罗来鹏，刘而根，王广超. 基于矩阵的最简决策规则获取[J]. 计算机工程，2008,34(19):41-43.

[13] 吴今培，孙德山. 现代数据分析[M]. 北京:机械工业出版社,2006.

[14] 宋巨龙，钱富才. 基于黄金分割法的全局最优方法[J]. 计算机工程与应用，2005,4:94-95.

Attribute Reduction Algorithm Based on Decision Rule

LIAO Qian, LI Xiang-peng
(College of Mathematics and Computer Science, Wuhan Textile University, Wuhan Hubei 430073, China)

Attribute reduction is one of the key problems of rough set. In this paper, some relative conclusions of attribute reduction and definition of attribute significance were proposed based on decision rule. This paper also gives heuristic algorithm, which used golden-section thinking to improve algorithm efficiency. The algorithm efficiency and correctness have been illustrated with an example.

Attribute Reduction; Decision Rule; Attribute Significance; Golden-section

O236

A

1009－5160(2011)06－0085－05

*

李相朋（1963-），男，教授，研究方向：信息系统与知识发现.