一种启发式知识约简算法

属性约简是Rough集理论中的核心问题之一,找出所有的约简或最小约简是一个NP难题.本文证明了正区域和边界域的一些性质,指出在考虑正区域作为启发信息的同时,还应该考虑在不一致决策表中边界域对约简的影响,综合这两种信息,提出了不一致决策表约简的启发信息.并在此基础上,设计了不一致决策表的启发式约简算法.实验证明,在多数情况下,该算法能够得到决策表的最小或次优约简.

A Heuristic Algorithm of Knowledge Reduction

In rough sets theory, reduction of attributes is an important issue. It has been proved that computing all re- ductions or the minimal reduction of decision table is a NP-hard problem. Now, many algorithms for reduction of at- tributes are still heuristic algorithms. In this paper, new heuristic information is proposed. We consider boundary re- gion (complement of positive region) can affect reducing attributes in inconsistent decision table, so we use not only positive region but also boundary region to calculate this heuristic information. Based on this new heuristic information. We develop heuristic algorithm for reduction of attributes in inconsistent decision table. In order to test efficiency of the algorithm, an example is analyzed and some experiments are made. The analysis and experimental results show that the algorithm is efficient and capable of finding the minimal or suboptimal reduction in most of cases.