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

A Complete Reduction Algorithm Based on Simple Discernibility Matrix

作　　者：徐章艳[1] 杨炳儒[2] 宋威[2] 

机构地区：[1]广西师范大学计算机系,桂林541004 [2]北京科技大学信息工程学院,北京100083

出　　处：《计算机工程与应用》2006年第26期167-169,197,共4页Computer Engineering and Applications

摘　　要：由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出IND(C),故设计了一个较好的求IND(C)的算法,其复杂度被降为O(｜C‖U｜)。在此基础上设计了一个完备属性约简算法,其时间复杂度和空间复杂度分别被降为max｛O(｜C｜2(｜U′pos‖U/C｜)),O(｜C‖U｜)｝和max｛O(｜U｜),O(｜C｜(｜U′pos‖U/C｜))｝。Because the definition of attribution reduction inition of attribution reduction based on positive region,a attribution reduction are provided.At the same time,it is same as the definition of attribution reduction based on based on old discernibility matrix is not the same as the defsimple discernibility matrix and the corresponding definition of proved that the above definition of attribution reduction is the positive region.For first computing IND（C） in the simple discernibility matrix,a good algorithm for computing IND（C） is designed,it＇s time complexity is cut down to O（｜C ｜｜ U｜）. On this condition,a complete attribution reduction algorithm is designed,tlme complexity and space complexity of the new algorithm are cut down to max{O（｜C｜2（｜U＇pos｜｜ U/C｜））,O（｜C ｜｜ U｜）}and max{O（｜U｜）,O（｜C｜（｜Upos ｜｜ U/C｜））} respectively.

关 键 词：粗糙集 差别矩阵 简化差别矩阵 属性约简 完备算法 复杂度 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]