Efficient Attribute Reduction Algorithm Based on Skowron Discernibility Matrix

The elements of discernibility matrix are used as the heuristic information by all the existing attribute reduction algorithms based on discernibility matrix. The time and space complexities of this kind of algorithms are O(\C\ 2 |U\ 2 ). To lower the time and space complexities, the simplified decision table and simplified discernibility matrix is introduced, and proved that the non-empty elements of simplified discernibility matrix are the same as that of the old discernibility matrix. Then, using the frequency of attribute appearing in the simplified discernibility matrix as heuristic information, an efficient attribute reduction algorithm based on the Skowron discernibility matrix is proposed, the time and space complexities are cut down to O(\C\\U\) +O(\C\ 2 |U/C\) and O(\U\) respectively. Finally, an example is used to illustrate the effectiveness of the new algorithm.