On Attribute Reduction Based On Rough Set Theory

The theory of Rough Set proposed by Polish mathematician Pawlak.Z in 1982 is an effective tool to imprecision, vaguenes and uncertainty after the Probability theory, Fuzzy Mathematics and Evidence theory and, without any prior knowledge or additional information while analyzing dataset, acquires a great deal of applications in data mining and knowledge reduction.Attribute reduction, one of the key problems in Rough Set theory, is able to reduce the redundant attributes from the databases, to simplify the knowledge presentations, to improve the efficiency of systems and to support the decision making, on the condition of ensuring the abilities of classification and decision. In this dissertation, attribute reduction is extensively and systematically studied. The contributions of this dissertation are as follows:1. The new definition of discernibility matrix which could effectively dispose the inconsistent decision tables is proposed based on the constraint function, and the method using this discernibility matrix to find decision table's core outperforms the traditional methods obviously.2. Based on proposed reduction condition, ARSDM algorithm for attribute reduction is designed. ARSDM takes into account of reduction conditions as the heuristic information and adopts a paralleled method to delete and sort the elements of discernibility matrix while to generate them, then effectively reduces the overheads of time and space and improves the efficiency of attribute reduction.3. A strategy using threshold computed by random sampling method to reduce the elements of discernibility matrix is proposed, and a -ARDM, an attribute reduction algorithm using this strategy is given all together.4. DARDM, a distributive attribute reduct algorithm is designed, and its correctness is proved in theory.