基于幂树的决策表最小属性约简  

Minimal attribute reduction based on power set tree in decision table

作　　者：陈玉明[1] 吴克寿[1] 孙金华[1] 

机构地区：[1]厦门理工学院计算机科学与技术系,厦门361024

出　　处：《南京大学学报（自然科学版）》2012年第2期164-171,共8页Journal of Nanjing University（Natural Science）

基　　金：国家自然科学基金(61103246;61075056;60903203)

摘　　要：粗糙集理论是一种新的处理不精确、不完全与不一致数据的数学理论工具,决策表属性约简是粗糙集理论研究的核心内容之一.针对决策表最小属性约简穷举算法时间复杂度较高问题,从改变决策表属性约简问题的知识表示入手,在决策表中引入树的表示方式,定义幂树表示约简问题空间,给出了旋转和回溯两种剪枝搜索方法.进一步针对决策表提出了基于幂树的最小属性约简完备性算法,该算法在幂树空间中进行穷举搜索,同时采用了旋转和回溯剪枝策略,提高了完备性算法的搜索效率,分析了算法的时间与空间复杂度,指出了完备性最小属性约简算法复杂度的指数级别特点.理论分析和实例表明该方法是有效可行的.Rough set theory is a new mathematical tool to deal with imprecise, incomplete and inconsistent data. Attribute reduction in decision table is one of the core problems in rough set theory. As we know, the time complexity of exhaustive search is high for complete minimal attribute reduction in decision table. From the change of knowledge representations for the attribute reduction problem, the new knowledge representation called power set tree is introduced. The power set tree is an inclined tree displaying all the possible nodes of problem space. Based on the power set tree, the rotation pruning operator and backtracking pruning operator for answering the minimal reduction question are proposed. Furthermore, a new complete algorithm to minimal attribute reduction problem based on power set tree is proposed in decision table. The new algorithm is also an exhaustive method, but using the rotation pruning operator and backtracking pruning operator to improve its search efficiency. And the new algorithm is a complete method which can guarantee to find a minimal reduction. The time and space complexities of the algorithm are also analyzed. And points out that the time and space complexities of complete attribute reduction algorithm show the exponent of growth. Finally, theoretical analysis and an example show that the reduction method is efficient and feasible.

关 键 词：粗糙集 决策表 最小约简 幂树 属性约简 

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论]