Heuristic Algorithm for Attribute Reductions Based on Discernibility Matrix

Attribute reduction is one of the key problems of rough set theory. Quality issues always present in complete algorithm which is based on dicernibility matrix. Based on the complete algorithm, the definition of heuristic information based on information theory are introduced to effectively achieve the complete reduction of attribute. We have used two different definition of heuristic information in our algorithm: conditional information entropy and mutual information. The comparison of reduction quality and efficiency between heuristic algorithm and non-heuristic algorithm is examined and the experimental results show that this method was effective in attribute reduction and can obtain high quality reduction for most decision tables compared to non-heuristic algorithms.