An efficient algorithm for Pawlak reduction based on simplified discernibility matrix.

Since the definition of attribute reduction based on classic discernibility matrix differs from that of it based on positive region, a new simplified discernibility matrix and the corresponding definition of attribute reduction were proposed. At the same time, it proves that the proposed definition is identical to its definition based on positive region. For computing simplified discernibility matrix, the indiscernibility relation, which is also called equivalence relation, should usually be calculated at first, so a new algorithm for computing equivalence relation was designed with radix sorting, whose temporal complexity is O(| C|| U|). Furthermore, an efficient attribute reduction algorithm is proposed, whose temporal complexity and spatial complexity are cut down to max( O(| C|| U′|| U′|, O(| U|| C|)) and max( O(| C|| U′|| U′|, O(| U|)) respectively. At last, an example is used to illustrate efficiency of the new algorithms. [ABSTRACT FROM AUTHOR]