Converse approximation and rule extraction from decision tables in rough set theory

In this paper, the concept of a granulation order is proposed in an information system. The converse approximation of a target concept under a granulation order is defined and some of its important properties are obtained, which can be used to characterize the structure of a set approximation. For a subset of the universe in an information system, its converge degree is monotonously increasing under a granulation order. This means that a proper family of granulations can be chosen for a target concept approximation according to user requirements. As an application of the converse approximation, an algorithm based on the converse approximation called REBCA is designed for decision-rule extraction from a decision table, which has a time complexity of O (frac(m, 2) | C |² | U | log₂ | U |), and its practical applications are illustrated by two examples. © 2007 Elsevier Ltd. All rights reserved.