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

目前，基于二进制差别矩阵的属性约简算法有如下不足：算法的时间和空间复杂度不理想；所得到的属性约简与由基于正区域的属性约简的定义得到的属性约简不一致。本文给出一个简化的二进制差别矩阵和相应的属性约简的定义，证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化的二进制的差别矩阵中，要先求出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｜））}。

Quick Attribution Reduction Algorithm Based on Simple Binary Discernibility Matrix

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 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 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.