An Algorithm for Maximum Distribution Reduction Under Incomplete Information Systems

摘要

Rough set is a new mathematical tool to deal with vagueness and uncertainty. It is important to investigate computational methods for the theory. In this paper, a new knowledge reduction―maximum distribution reduction is presented under incomplete information systems, in which some attribute values are unknown. The maximum decision classes of the neighbors of all objects under an incomplete system remain constant after maximum distribution reduction. To obtain a maximum distribution reduct of incomplete information system, maximum distribution matrix is defined to express the relations between the neighbors of all objects and their maximum distribution decision classes. Using maximum distribution matrix, indispensable or dispensable of an attribute to maximum distribution reduction can be represented with respect to decision classes. Distance between two maximum distribution matrices is defined to represent importance of attributes and thus to obtain minimal maximum distribution reduct. Based on maximum distribution matrix, two algorithms for maximum distribution reduction are proposed and their time complexes are analyzed. Their time complexes are polynomial. Example analysis shows that these two algorithms can find maximum distribution reduct of an incomplete information system.