Research On Algorithms Of Parallel Reducts In Rough Sets

By defining the concepts of upper approximation and lower approximation, rough sets make the vague degree computable. So it has particular advantages when it was used to deal with incomplete and imprecise data:1) Needing no priori knowledge;2) More objective and precise;3) Highly complementary with other theories of uncertainty. Due to these advantages, rough sets theory has been fully developed and widely used since it was proposed about30years ago.During many years’ development, the availability of rough set theory has been fully verified, and theory framework has been improved as well. But the challenge, how to obtain a stable reduct from a dynamic or increasing data set, has not been successfully solved. Although, dynamic reduct theory has pointed out a very good way to solve the issue, but due to its time complexity of exponential order, dynamic reducts could only be used to obtain reducts from the less-conditional attribute data. The application of dynamic reducts will be greatly limited. Moreover, the method of dynamic reducts is incomplete because the intersection of all of reducts of a family decision subsystems may be empty.To solve the issue that how to obtain a stable reduct from a dynamic or increasing data set, Dayong Deng proposed the parallel reduct theory. Similar to dynamic reducts, parallel reducts divide a decision system into several decision subsystems, and reduce redundant condition attribute(s) from them simultaneously, finally one or more stable reduct(s) would be obtained from the family of decision subsystems. Different from dynamic reduct algorithm’s exhaustive searching among decision subsystems, parallel reducts can judge whether a condition attribute is more important than others with heuristic information in the processing of obtaining parallel reducts, so the time complexity of parallel reduct algorithm is polynomial. The parallel reduct theory is a complete theory, because it can avoid the empty result from its definition. Besides, parallel reduct theory can make use of all achievements of rough sets but dynamic reduct theory can’t. In this thesis we investigate parallel reduct theory deeply, and propose an improved a parallel reduct algorithm. The new algorithm can obtain a parallel reduct, which contains fewer condition attributes, within the same time complexity as the old one. After that, we propose the concept and algorithm of parallel reduct algorithm in information view, and investigate their properties. At last, we discuss the consistency and differences between parallel reducts and dynamic reducts, and unify these two theories. Specifically, we do these jobs as follows:(1) Chapter1overviews rough set theory; Chapter2covers some primary knowledge and concepts of rough sets, analyzes and compares three of the commonly used decision system reduct algorithms which highly associate with parallel reduct theory.(2) Chapter3investigates the concept of parallel reducts and the corresponding algorithm which was proposed by Dayong Deng. Because primary concepts and algorithm framework are defined in algebraic view, parallel reducts in this chapter is also called parallel reducts in algebraic view.(3) Chapter4proposes an improved parallel reduct algorithm in algebraic view. The new algorithm improves the strategy of selecting condition attributes to obtain a more stable result which has fewer condition attributes. Theoretically these two algorithms have same time complexity, but because of fewer algorithm iterations, the running time of the improved algorithm is smaller than that of the original one in experiments.(4) Chapter5proposes the concept of parallel reduct algorithm in information view with the concept of mutual information. Parallel reduct algorithm in information view follows the framework of the parallel reducts in algebraic view, but it changes the importance measure of the attribute. And due to the same framework, parallel reduct algorithm in information view has same time complexity as the algebraic one. The parallel reducts in information view can preserve more classification information than parallel reducts in algebraic view when both of them are used to deal with inconsistent data. Finally we discuss the consistency and differences of these two theories and unify them with dynamic reducts.