基于简化的二进制差别矩阵的快速属性约简算法  

Quick Attribution Reduction Algorithm Based on Simple Binary Discernibility Matrix

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

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

出　　处：《计算机科学》2006年第4期155-158,共4页Computer Science

摘　　要：目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出IND（C），故设计了一个较好的求IND（C）的算法，其复杂度被降低为O（｜U‖U｜）。在此基础上设计了一个快速属性约简算法，其时间复杂度和空间复杂度分别被降为max{O（｜C｜^2（｜U＇pos‖U/C｜））,O（｜C‖U｜）}和max{O｜U｜},O（｜C｜（｜U＇pos‖U/C｜））}。At present, the attribution reduction algorithm based on binary discernibility matrix has the following short comings, it＇s time complexity and space complexity are not good; the attribution reduction acquired from this algorithm is not the one acquired from definition of attribution reduction based on positive region. In this paper, a simple binary discernibility matrix and the corresponding definition of attribution reduction are provided. At the same time, it is proved that the above definition of attribution reduction is the same as the definition of attribution reduction based on positive region. For first computing IND（C） in the simple binary discemihility 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 quick attribution reduction algorithm is designed, time 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｜（｜U＇pos‖U/C｜））} respectively.

关 键 词：粗糙集 二进制差别矩阵 简化的二进制差别矩阵 核 复杂度 

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