属性约简的一种贪心算法

A GREEDY ALGORITHM FOR ATTRIBUTE REDUCTION

属性约简是粗糙集理论研究的关键问题之一 ,现已证明寻找一个决策表的最优约简是 NP- hard问题 .首先在粗糙集理论的基础上 ,给出决策表中属性重要性的两种度量 ,并以此为启发式信息 ,提出了一种基于粗糙集的属性约简贪心算法 ;最后 ,实验结果表明 ,该算法在大多数情况下能有效地获得决策表的最优约简 .

Attribute reduction is one of the key topics in the rough set theory field. It has been proven that computing the optimal reduction of decision table is an NP-hard problem. Firstly , based on the rough set theory, two types of significance of attribute in a decision table are defined. Then, an algorithm which uses rough set theory with greedy heuristic information is proposed. Finally, the experimental result shows that the algorithm can obtain the optimal attribute reduction of a decision table efficiently in most c ases.