An Attribution Reduction Algorithm Based on Simple Discernibility Matrix

In order to cut down the time and space complexity of the attribution reduction algorithm based on modificatory discernibility matrix,firstly,we gave the definition of simple discernibility matrix,and proved the simple discernibility matrix contains the same information content as the modificatory discernibility matrix.Secondly,we designed an efficient algorithm for computing U/C,and the time complexity of the algorithm was cut down to O∑|C|i=1|k_i||U|.Then we analyzed the shortcomings of attribution reduction algorithm based on modificatory discernibility matrix,using the new efficient algorithm for computing U/C designed an attribution reduction algorithm which is called attribution reduction algorithm based on simple discernibility matrix,and proved that the time and space complexity of the new algorithm are cut down to maxO(|C|~2(|U′_(pos)||U/C|)),O∑|C|i=1|k_i||U| and max{O|C|(|U′_(pos)||U/C|)),O(|U|)} respectively.At the end,an example was used to illustrate the efficiency of the new algorithm.