Approximation Reduction Based on Similarity Relation

Knowledge reduction is one of the most important tasks in rough set theory, and most types of reductions in this area are based on complete information systems. Though one of the extended relations, similarity relation, has been presented in incomplete information systems, which do exist in real world, its reduction approach has not been examined. In this paper, based on similarity relation, the upper and lower approximation reduction are defined in incomplete information systems. The judgment theorems with respect to the consistent sets of the upper and lower approximation reduction are studied, their discernibility matrices are obtained and the approaches of the upper and lower approximation reduction based on discernibility matrices are presented. To overcome its drawback of NP-hard time complexity, two heuristic algorithms based on significance of attributes are proposed.