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

由于基于老差别矩阵的属性约简的定义与基于正区域的属性约简的定义是不一致的,给出一个简化差别矩阵和相应的属性约简的定义,并证明了该定义与基于正区域的属性约简的定义是一致的。由于在简化差别矩阵中,要先求出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｜))｝。

A Complete Reduction Algorithm Based on Simple Discernibility Matrix

Because the definition of attribution reduction based on old discernibility matrix is not the same as the definition of attribution reduction based on positive region,a simple 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 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,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.