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

Complete algorithm for attribute reduction based on discernibility matrix

作　　者：蒋瑜[1] 王鹏[1] 王燮[1] 李永礼[2] 

机构地区：[1]成都信息工程学院软件工程系,成都610225 [2]兰州大学信息科学与工程学院,兰州730000

出　　处：《计算机工程与应用》2007年第19期185-187,共3页Computer Engineering and Applications

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

关 键 词：粗糙集 差别矩阵 属性重要度 完备算法 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]