计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (19): 185-187.

• 数据库与信息处理 • 上一篇    下一篇

基于差别矩阵的属性约简完备算法

蒋 瑜1,王 鹏1,王 燮1,李永礼2   

  1. 1.成都信息工程学院 软件工程系,成都 610225
    2.兰州大学 信息科学与工程学院,兰州 730000
  • 收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2007-07-01 发布日期:2007-07-01
  • 通讯作者: 蒋 瑜

Complete algorithm for attribute reduction based on discernibility matrix

JIANG Yu1,WANG Peng1,WANG Xie1,LI Yong-li2   

  1. 1.Department of Software Engineering,Chengdu University of Information Technology,Chengdu 610225,China
    2.School of Information Science and Engineering,Lanzhou University,Lanzhou 730000,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2007-07-01 Published:2007-07-01
  • Contact: JIANG Yu

摘要: 分析了传统属性频率函数作为属性重要度的不足,重新定义了属性重要度,提出了一种基于差别矩阵属性重要度的属性约简完备算法,即CRABSA(Complete Reduction Algorithm Based on the Significance of Attribute)。该算法采用迭代思想,在每次迭代过程中根据属性重要度SGF(a)选择必要的条件属性加入约简R中。由SGF(a)的定义可知,算法能确保在大多数情况下能得到决策表的最小约简。分析了算法在最坏情况下的时间复杂度,给出了该算法相对Pawlak约简的完备性的证明。

Abstract: This paper investigats the disadvantage of the attribute reduction based on the attribute frequency function p(a),which is defined as the number of occurrences of the attribute a.We redefine the significance of attribute based on discernibility matrix.A complete algorithm for attribute reduction in decision table based on discernibility matrix is introduced,which is called complete reduction algorithm based on the significance of attribute or CRABSA for short.This algorithm using the iteration is to select the indispensable condition attributes according to the significance of attribute SGF(a),and adds the indispensable condition
attributes into the reduction R.According to the definition of the SGF(a),we know that the reduction that this algorithm finds out is smallest reduction at most time.The time complexity of it in the worst case is analysed and the proof of its completeness for Pawlak reduction is given.