Computer Engineering and Applications ›› 2013, Vol. 49 ›› Issue (11): 101-104.

Previous Articles     Next Articles

Minimal attribute reduction for rough set based on set enumeration search tree


  1. College of Software Engineering, Chengdu University of Information Technology, Chengdu 610225, China
  • Online:2013-06-01 Published:2013-06-14


蒋  瑜   

  1. 成都信息工程学院 软件工程学院,成都 610225

Abstract: The purpose of this paper is to present an effective approach to achieve minimal attribute reduction. To achieve this goal, in this paper, it introduces a set-enumeration search tree by using total sequence over condition attribute set, and proposes a minimal attribute reduction algorithm, which uses the top-down level-first traversal to search set-enumeration search tree and guarantee that reduction discovered by it is a minimal reduction. To realize performance gains, this algorithm uses core and superset pruning to reduce search space, and uses optimal computing to guarantee that positive region of the same set only computes one time for reducing computing time. The experimental results with UCI data show that the proposed algorithm is effective.

Key words: rough set, minimal reduction, set enumeration search tree, attribute significance, pruning

摘要: 为了寻找一种有效的最小属性约简方法,给出了条件属性集上的属性重要度序关系,基于此序关系构建了属性集上的集合枚举树,提出了一种快速的最小属性约简算法,该算法采用至上而下、层次优先策略搜索集合枚举树寻找属性最小约简。为了提高算法性能,该算法采用核和父集剪枝策略减少搜索空间,采用优化计算来确保同一集合的正域只计算一次。基于UCI数据的实验结果表明,该算法是有效的。

关键词: 粗糙集, 最小约简, 集合枚举树, 属性重要度, 剪枝