The Reduction Theory Of Covering Rough Sets And Its Application

Widely applied to natural sciences, social sciences and engineering, rough set theory en-joys its unique advantages in various areas such as data mining, artificial intelligence, manage-rial decisions and diagnosis predictions. Current researches regarding rough sets mainly focus on three aspects:generalizations of rough sets, design of its reduction algorithm, and its appli-cations. Among them, the reduction of rough sets is no doubt the most important, special, and widely applied theory. As an important development of Pawlak's rough sets, generalized cover-ing rough sets is getting more attention recently. Limited in the raise of covering approximate operators, the research on covering reduction theory is far from being developed.The present dissertation contributes to the literature in several ways. In terms of covering granular reduction, studied by Zhu and Wang is limited to the applications on the first and third types of covering rough sets. But it suffers from either over-reduction or inefficient reduction for the rest. This dissertation proposed a new definition of approximation space, established a systematic granular reduction theory being applicable to all existing seven covering rough set models, and developed corresponding covering granular reduction algorithm.For covering attribute reduction of information system, the dissertation designed the algo-rithm for attribute reduction based on the new approximation spaces. Since there is only one attribute reduction algorithm designed by Tsang et al. specifically for the fifth type of covering rough set model based on traditional discernibility matrix, with the absence for other types, we find that the attribute reduction methods for the sixth and seventh types of covering rough sets on the basis of the approximation space theory is consistent with that of the fifth type. As to the former four types of models, it is proved that the discernibility matrix is inapplicable. Motivated by this reason, this dissertation construct the method of relative family based on the approxima-tion spaces for the first time, which can not only solve the problems of attribute reduction and relative attribute reduction for the first to the fourth types of models, but also be applicable to the rest three types. Therefore, with a consolidated and consistent algorithm of relative family, the attribute reductions of all seven types of covering rough sets are solved eventually.Topology is one of the most classical mathematical theories. With an endogenous con-nection between covering and topology, study on topological features of covering is valuable in both theory and practice. However, previous studies focus more on topological characteris-tics of approximation operators and topological structure of rough granular, without topological features of covering reduction involved. We find the N-reduction of coverings is actually the minimal subset of topology, and the quasi-representative covering, representative covering and unary covering possess good features of granular reduction. In addition, this dissertation reveals the connections among these three specific coverings.Finally, this dissertation examines the simplification of reduction algorithm, including lowering the orders of discernibility matrix and element reduction of information family. This dissertation for the first time introduces the topological separation into rough set theory to de-scribe the classification power of knowledge base, and transforms knowledge bases to satisfy the separation and realize the order-decreased discernibility matrix of knowledge bases. This method significantly simplifies the reduction processes for the covering information system without satisfying the separation. On this basis, this dissertation designs a reduction method for information family elements, further simplifying the objects of reduction. For the reduc-tion algorithm of NP hard problems, these two steps of reduction shortens the calculation time essentially.In summary, this dissertation has developed theories and algorithms of granular reduction, attribute reduction of information system and relative attribute reduction of decision system for existing seven pairs of covering approximation operators. It contributes to both rough sets theory and granular computing.