粗糙集属性约简的完备算法

An attribute reduction algorithm of rough set based on discernable matrix

属性约简是Rough Set理论研究中的核心内容之一,现已经证明寻找决策表的最小约简是NP-hard问题。为了快速有效地得到最小约简,本文利用决策表的一些特点提出了一种完备算法,并给出了该算法的复杂度,最后通过实例分析表明,在多数情况下该算法能够得到决策表的最小约简。

Attribute reduction is one of the most important topics in the research on Rough Set theory. It has been proved that the computation of the optimal （minimal） reduction of decision table is a NP- hard problem. In order to get the optimal reduction rapidly and effectively, a way for removing the redundancy attributes is proposed in this paper, and the complexity of this algorithm is analyzed. The experimental results show that this algorithm can find the optimal reduction for most decision tables.