计算机工程与应用 ›› 2013, Vol. 49 ›› Issue (11): 101-104.

• 数据库、数据挖掘、机器学习 • 上一篇    下一篇

基于集合枚举树的最小属性约简算法

蒋  瑜   

  1. 成都信息工程学院 软件工程学院,成都 610225
  • 出版日期:2013-06-01 发布日期:2013-06-14

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

JIANG Yu   

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

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

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

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