On Five Types Of Matroidal Structures Of Rough Sets

Rough set theory is a mathematical tool to deal with fuzzy and uncertain knowledge, andit approximatively depicts and processes uncertain or imprecise knowledge through the lowerapproximation operator and the upper approximation operator based on the existingknowledge base. Rough set theory has been widely applied to medicine, machine learning,decision analysis, intelligent control and other fields, especially in the field of data mining.Rough set theory provides a theoretical guidance and support in many steps of data mining,such as data preprocessing, attribute reduction, attribute value reduction and rule processing.The attribute reduction problem in rough set theory is NP hard. Big data are huge,dynamic, multi-dimensional and heterogeneous, so rough sets can not effectively solve somepractical problems without the help of other theories in the big data. While matroid theory isan important tool to deal with NP hard problems, and it has been applied to the Greedyalgorithm design. Many optimization problems are to get development and promotion throughmatroidal approaches. Therefore, it is important to combine rough set theory and matroidtheory to solve the optimal solution in the attribute reduction problem of rough sets.In this thesis, we establish five types of matroidal structures of rough sets, and make asystematic and in-depth investigation on these structures. We first propose partition-circuitmatroids of classical rough sets, and then induce its two generalized models: parametricmatroids of classical rough sets and non-intersection matroids of generalized rough sets; Then,we establish2-circuit matroids of generalized rough sets which are the dual matroids ofpartition-circuit matroids of classical rough sets; Finally neighborhood matroids ofgeneralized rough sets are presented in order to break through the restriction of relations.(1) Partition-circuit matroid of classical rough set. We establish a partition-circuitmatroid of a classical rough set, whose circuit family is the partition determined by theequivalence relation on the universe. We also prove that the lower approximation of any independent set of the partition-circuit matroid of the classical rough set is empty set. Aquantitative tool, namely the lower approximation number, is defined, and its connection withthe existing quantitative tool: upper approximation number is investigated. Moreover, we usethese two tools to study the partition-circuit matroid of the classical rough set and its dualmatroid.(2) Parametric matroid of classical rough set. Through introducing a parameter (i.e. asubset of a universe), the independent set family of a matroid is constructed by the sets whoselower approximation with respect to a classical rough set is contained in the parameter. Wecall this matroid the parametric matroid of the classical rough set. In fact, the parametricmatroid of the classical rough set is not a simple generalized model of a partition-circuitmatroid of the classical rough set, but it is the sum of a partition-circuit matroid of anotherclassical rough set and a free matroid. Based on this result, any parametric matroid of aclassical rough set is further represented through the lower approximation number.(3) Non-intersection circuit matroid of generalized rough set. As another generalizationof a partition-circuit matroid of a classical rough set, non-intersection circuit matroid of ageneralized rough set is a matroid whose circuit family is the family of all minimalneighborhoods of a serial and transitive relation which is degenerated from the equivalencerelation. We also discuss the relationship between non-intersection circuit matroid of ageneralized rough set and a parametric matroid of a classical rough set which is ageneralization of a partition-circuit matroid of a classical rough set. Moreover, in order tofurther understand the non-intersection matroid of a generalized rough set, we establish the Itype of rough set of a matroid.(4)2-circuit matroid of generalized rough set. The family of definable sets with respectto a generalized rough set based on serial relations is proved to satisfy the closed set axiom ofmatroids. Especially, the definable sets with respect to a generalized rough set based on areflexive relation remain unchanged through the closures of the reflexive relation. Based on these results, the closure operator of a2-circuit matroid of a generalized rough set based on areflexive relation is proved to be the upper approximation operator of the classical rough setbased on the equivalence closure of the reflexive relation. Moreover, the duality between2-circuit matroids of generalized rough sets and partition-circuit matroids of classical roughsets is investigated.(5) Neighborhood matroid of generalized rough set. The four types of matroids above areinduced by equivalence relations, serial and transitive relations, serial relations, respectively.We point that serial relations are the weakest relations which can induce matroidal structures.Through the notions of successor and predecessor neighborhoods of relations, we establish apair of matroids of generalized rough sets based on arbitrary relations to breakthrough thelimitation of serial relations. These two matroids are called successor neighborhood matroidof generalized rough set and predecessor neighborhood matroid of generalized rough set,respectively. Furthermore, any predecessor neighborhood matroid of a generalized rough setbased on a relation is proved to be the successor neighborhood matroid of the generalizedrough set based on the inverse of the relation.