Matroidal And Lattice Approaches To Rough Sets

Since machine learning, pattern recognition and knowledge discovery put forward ahigher demand to the intelligent information processing technology, there are a series ofmethods and tools to process uncertain problems. Rough sets become an irreplaceable oneamong them and have gained great attention all over the world. Classical rough set theory isbased on indiscernibility relation, however, realistic data are usually not organized as anindiscernibility relation. So the applications of the theory are restricted and people are tryingto extend the theory from different viewpoints, such as the expansion of the universe, thegeneralization of models, the combination of other subjects and so on. Both matroids andlattices are an important choice in the combination of rough sets. By matroids and lattices,rough sets are enriched from theory and new mathematical branches are emerged.The combination of rough sets and matroids is a new research topic. More and morescholars at home and abroad are concerned with it and starting to study it. However, theresearch is still in preliminary stage. In order to keep developing and improving the theory, itneeds more people to make their efforts for a long time. There are several hard problems inrough sets, for example, to find the minimal attribute sets, so algorithms are needed to solvethem. Lattices have the potential of providing algorithms for these problems. Therefore, itmakes sense to study rough sets through matroids and lattices. Both matroids and lattices areused to study rough sets in this dissertation. Two types of covering cycle matroids and a typeof covering matroid are respectively established. The graphical representations of them arestudied. Several families are defined by approximation operators of three kinds ofcovering-based rough sets, respectively. Lattices structures about these families areinvestigated. By lattices obtained by generalized rough sets, two special matroidal structuresare established. One is based on regular sets defined by a serial and transitive relation and theother requires the union reduction of a covering to be a partition. The closet-set lattices ofthese two matroids are discussed. Main works are listed as follows:(1) By linking coverings and graphs, three types of matroidal structures related to coverings are constructed and the graphical representations of these matroids are studied. Thecharacteristics of blocks in a covering are intuitively represented by graphs. A connectedgraph related to a covering is obtained, which is convenient for study the graphicalrepresentation of those three matroids. Certain characteristics about two kinds of coveringcycle matroids are formulated by the second type of covering-based approximation operators.Through defining the coarse covering of a covering, a covering matroid is established. Therelationships between those three matroids and the function matroid are studied, which haveimportant theoretical significance in studying matroidial structures of rough sets.(2) Several families are, respectively, defined by the upper and the lower approximationoperators of three types of covering-based rough sets. The lattice structures of these familiesare studied. Two families are defined by the fixed points of the lower approximations aboutthe sixth and the second type of covering-based rough sets, respectively. Sufficient conditionsfor these two families to be distributive lattice, double p algebra and double stone algebra arerespectively investigated. By the definition of a quasi-unary covering, sufficient conditionsfor two families defined respectively by the lower and the upper approximations of the firsttype of covering-based rough sets to be a distributive lattice are studied. Another sufficientcondition for the fixed points of the lower approximations of the second type ofcovering-based rough sets is also given.(3) Lattices are a link between rough sets and matroids. The matroidal structure ofregular sets based on a serial and transitive relation and the matroidal structure based on theunion reduction of a covering to be a partition are respectively established. The family of allthe regular sets based on a serial and transitive relation is proved to be a semimodular lattice.Through the height function of the semimodular lattice, a matroid is established and the rankfunction of the matroid is represented. An approach to obtain the closed-set lattice of thismatroid from the semimodular lattice is proposed. An operator is defined by a covering, andthe family of all the fixed points of the operator is proved to be a lattice. By the closureaxioms of matorids, a sufficient condition for this family to be a closed-set lattice is given.Therefore another matroid with the operator as closure operator is constructed. The modularity of the closed-set lattice of the matroid is studied.To sum up, this dissertation mainly focuses on the extension study of rough sets throughmatroids and lattices. Five types of matroids with respect to rough sets are established. Thegraphical representations of three of these matroids and the closed-set lattices of the other twoare studied, respectively. Several families of subsets are respectively defined byapproximation operators related to the first, second and sixth three types of covering-basedrough sets, and lattices structures of these families are established, respectively. These resultsnot only drive rough sets in the direction of diversity and multi-directions, but also broadenthe application of them. Moreover, they will lay a solid foundation for future research.