J4 ›› 2010, Vol. 37 ›› Issue (6): 1111-1118.doi: 10.3969/j.issn.1001-2400.2010.06.024

• 研究论文 • 上一篇    下一篇

一种基于属性-值树的求核与约简方法

王晓帆1,2;王宝树1;柴慧敏1
  

  1. (1. 西安电子科技大学 计算机学院,陕西 西安  710071;
    2. 西安理工大学 计算机学院,陕西 西安  710048)
  • 收稿日期:2010-05-19 出版日期:2010-12-20 发布日期:2011-01-22
  • 通讯作者: 王晓帆
  • 作者简介:王晓帆(1976-),男,讲师,西安电子科技大学博士研究生,E-mail: wangxfok@xaut.edu.cn.
  • 基金资助:

    国家部委预研基金资助项目(51315080202)

Algorithm based attribute-value-tree for calculation of core and attribute reduction

WANG Xiao-fan1,2;WANG Bao-shu1;CHAI Hui-min1   

  1. (1. School of Computer Science and Technology, Xidian Univ., Xi'an  710071, China;
    2. School of Computer Sci. and Tech., Xi'an Univ. of Tech., Xi'an  710048, China)
  • Received:2010-05-19 Online:2010-12-20 Published:2011-01-22
  • Contact: WANG Xiao-fan

摘要:

为快速计算粗糙集的一个属性约简与核,提出一种基于属性-值树模型的改进约简与求核算法,并证明了算法的完备性.该算法充分利用树型结构,引进树的合并方法,使得计算复杂度从O(|U||C|2)降低为O(|U||C|),提高了计算效率(其中|U|和|C|分别代表对象个数和属性个数).

关键词: 粗糙集, 决策表, 属性约简, 属性-值树

Abstract:

In order to get attribute reduction or calculate the core of rough sets quickly, a new algorithm of attribute reduction and computing core is brought forward based on the attribute-value-tree model and its correctness is proved. The greatest advantage of the algorithm is that the time and space complexity are reduced efficiently by using the method of merging trees. The computational complexity of reduction is changed from O(|U||C|2) to O(|U||C|) where |U| and |C| are the numbers of objects and attributes.

Key words: rough sets, decision table, attribute reduction, attribute-value-tree

中图分类号: 

  • TP14