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

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

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

蒋瑜¹，王鹏¹，王燮¹，李永礼²

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 Yu¹，WANG Peng¹，WANG Xie¹，LI Yong-li²

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

摘要/Abstract

摘要： 分析了传统属性频率函数作为属性重要度的不足，重新定义了属性重要度，提出了一种基于差别矩阵属性重要度的属性约简完备算法，即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．

蒋瑜¹，王鹏¹，王燮¹，李永礼². 基于差别矩阵的属性约简完备算法[J]. 计算机工程与应用, 2007, 43(19): 185-187.

JIANG Yu¹，WANG Peng¹，WANG Xie¹，LI Yong-li². Complete algorithm for attribute reduction based on discernibility matrix[J]. Computer Engineering and Applications, 2007, 43(19): 185-187.