Issues On Covering-based Rough Sets Through Matroids

Rough set theory was proposed by Pawlak in1982to deal with the imprecise,indeterminate, incompleteness of data. It has been widely used in artificial intelligence, datamining and so on. In practical application, besides the partition data, there is a large amount ofcovering data. In order to deal with the data better, Zakowski generalized the rough set theoryto covering-based rough set theory in1983. However, compared with other theories, thetheoretical system of covering-based rough sets is still not very rich. Furthermore, there aremany optimization issues related to covering-based rough sets, and how to obtain the optimalsolutions of these issues is what people have always paid attention to. Matroid theory borrowsextensively from linear algebra and graph theory. With abundant theories, it has been widelyused in many fields including combinatorial optimization, network flows and algorithmdesign, especially greedy algorithm design which plays an important role in solvingoptimization issues.In this dissertation, we try to enrich the theoretical system and improve the applicationvalue of covering-based rough sets by using matroids as the research techniques. Some resultslisted as follows have been gotten on several key problems in covering-based rough sets, suchas the matrix representations of covering-based rough sets, the matroidal and the geometriclattice structure of covering-based rough sets, the applications of covering-based rough sets tothe connectedness of graphs and matroids and how to use matroids to solve the optimizationissues related to covering-based rough sets.(1) Enrich the theoretical system. Through reviewing the research status ofcovering-based rough set theory, we find that its theoretical system is still not rich enough.Therefore, Chapter3studies the theory from the viewpoint of the matrix. The maincontributions of this chapter are two-fold. First, we present a matrix representation of the neighborhood. Second, five matrices are defined to represent three types of covering lowerand upper approximation operators defined through neighborhoods. As the matroid is ageneralization of the matrix, Chapter4studies rough sets in terms of matroids. First, a nullityoperator of rough sets is proposed to induce a matroid and then a specific type of matroidcalled a nullity-based matroid is presented. Second, considering the relationship betweennullities and matrices, we present two types of matrices to characterize this type of matroidand its nullity operator. Finally, the dual of this type of matroid is induced by the second typeof the matrix. As is known that all the closed sets of a finite matroid form a geometric lattice,Chapter5induces a matroidal structure of a covering through transversal matroids, and thenuses the obtained structure to construct a geometric lattice structure of the covering.Furthermore, we present another two types of matroidal structures of covering-based roughsets and then obtain the corresponding two types of geometric lattice structures. Finally, therelationship among these three matroidal structures and that of the three geometric latticestructures are studied, respectively. In a word, this dissertation enriches the theoretical systemof covering-based rough sets from the above three aspects.(2) Improve the application value. In different areas, various applications are usinggraph models. Solving the application problems is equal to solve the corresponding issues ofgraph theory. Matroids not only have abundant theories but also have wide applications. Forthe reasons, we aim to improve the application value of covering-based rough sets with theaid of graphs and matroids. In Chapter6, we apply the covering-based rough sets to study theconnectedness of a graph and a matroid. First, we present an approach to inducing a coveringby a graph, and then covering-based rough sets are employed to study the connectedness ofthe graph in terms of covering approximation operators. Second, we construct a graph from amatroid through the circuits and find that the matroid and the graph have the sameconnectedness, which makes us to apply the covering-based rough sets to study theconnectedness of a matroid. Matroids provide well-established platforms for greedy algorithms, and precisely for this reason, they arise naturally in a number of problems incombinatorial optimization. Dependence spaces were introduced as a general abstract settingfor studying the informational dependency. Many reduction issues in the spaces can be solvedefficiently. Therefore, it motives us to apply matroids and dependence spaces to study theissue of attribute reduction related to covering-based rough sets. In Chapter7, a dependencespace of a matroid is constructed, and then the characterizations for the space such asconsistent sets and reducts are studied through the matroid. Finally, the obtained results areapplied to the issues of attribute reduction in information systems. Through studying theabove two aspects, we improve the application value of covering-based rough sets.