基于修正差别矩阵的高效属性约简算法

An efficient attribute reduction algorithm by modificatory discernibility matrix

为降低基于修正差别矩阵的属性约简算法的复杂度,给出了基于修正差别矩阵的简化差别矩阵,证明了基于该简化差别矩阵的属性约简定义与基于原修正差别矩阵的属性约简定义是等价的.在此基础上设计了一个基于简化差别矩阵的属性约简算法,其空间和时间复杂度分别被降为O(|C|(|U′pos||U/C|))和max{O(|C|2(|Up′os||U/C|)),O(|C||U|log|U|)}.实例说明:用新算法进行属性约简,不仅减少了计算量,而且减少了存储空间,因而是一种高效的属性约简算法.

In order to reduce the time and space complexity of algorithm for attribute reduction based on modificatory discernibility matrix, a simplified discernibility matrix based on modificatory discernibility matrix is proposed. At the same time, it is proved that the definition of attribute reduction based on this simplified discernibility matrix is equivalence to the old definition. On this condition, an algorithm for attribute reduction based on the simplified discernibility matrix is designed. The space and time complexity of the new algorithm are cut down to O（｜C｜（｜U＇pos｜｜U/C｜）） and max{O（｜C｜^2（｜U＇pos｜｜U/C｜））,P（｜C｜｜U｜｜log｜U｜）}. respectively. An example is used to illustrate the efficiency of the new algorithm, which can reduce the amount of computation and storage space.