Discernibility Matrix Based Algorithm for Reduction of Attributes

In rough set theory, it has been proved that finding the minimal reduct of information systems or decision tables is a NP-complete problem. Therefore, it is hard to obtain the set of the most concise rules by existing algorithms for reduction of knowledge. In this paper, the method of finding sub-optimal reduct based on discernibility matrix is proposed. In general, our method is better than existing methods with respect to the minimal reduct. However, we find that existing minimal reduct searching algorithms are incomplete for reduction of attributes in information systems or decision tables. Through analysis, we present a conjecture about the completeness of the minimal reduct algorithm.