Efficient Attribute Reduction Based on Discernibility Matrix

摘要

To reduce the time complexity of attribute reduction algorithm based on discernibility matrix, a simplified decision table is first introduced, and an algorithm with time complexity O(| C || U | ) is designed for calculating the simplified decision table. And then, a new measure of the significance of an attribute is defined for reducing the search space of simplified decision table. A recursive algorithm is proposed for computing the attribute significance that its time complexity is of O(| U / C |). Finally, an efficient attribute reduction algorithm is developed based on the attribute significance. This algorithm is equal to existing algorithms in performance and its time complexity is O(| C || U | ) + O(| C |~2 | U / C | ).