一种新的完全决策表属性约简的高效算法

A New and Efficent Algorithm to Attribute Reductionin Incomplete Decision Table

属性约简是粗糙集理论的核心问题之一,也是粗糙集有效算法研究的焦点。为获得最简明的规则集,通常希望能找出最小的属性约简集,但得到最优解是NP-hard的问题,通常采取启发式的算法得到近似最优解。文中研究了不完全决策表的属性约简,提出一种衡量不完全决策表属性重要性的标准,依此给出了一种新的进行属性约简启发式算法。对寻找对象的相似类的步骤则在排序和二分查找的基础上提出了一种新的高效的算法,这样就相应地使得属性约简的效率得到提高。此算法较好地解决了不完全决策表的属性约简问题。

Attribute reduction is one of the most important issues and the focus of the research on efficient algorithms in rough sets. To obtain the most concise rule set from a decision table, the attribute reduction should have the least cardinality. But this is a NP-hard problem and heuristic algorithms of multinomial time complexity are introduced to get the approximately best solution. The paper studies the attribute reduction incomplete decision tables and a criterion to weigh the importance of attributes in incomplete decision tables is defined and a new attribute reduction algorithm based on the criterion is introduced. An efficient algorithm to seek the set of objects similar to the considered object based on sort and binary search is also advanced in the paper and the efficiency of the attribute reduction algorithm is improved accordingly. The work of the paper solve the attribute reduction problem satisfiedly.