Research On Rough Sets And Their Matroidal Structure Via Matrices

Classical rough set theory is a mathematical tool to cope with inexact or incomplete knowledge in information systems. The knowledge dealt by this theory is a partition on a universe. But in many practical problems, the knowledge is not a partition on a universe, but a covering. Therefore, in order to deal with this type of knowledge, classical rough set theory is generalized to covering-based rough set theory. From the viewpoints of partitions and coverings, rough set theory is mainly includes classical rough set theory and covering-based rough set theory.However, many practical problems such as attribute reduction in rough set theory are NP-hard. Therefore, most algorithms to solve them are often greedy ones. As a generalization of graph theory and linear algebra, matroid theory provides a well platform for greedy algorithms. Therefore, it is important to combine matroid theory with rough set theory.In this paper, we use matrix approaches to study a matroidal structure of classical rough sets, and also use matrix approaches to investigate covering-based rough sets. There are two contributions of this work as follows:(1) Matrix approaches are applied to a matroidal structure of classical rough sets from the viewpoints of characteristics, operations and axioms. Firstly, a matroid is induced by an equivalence relation on a universe through the circuit axiom, and the matroid is representable whose representable matrix is a matrix representation of the equivalence relation. According to the representable matrix of the matroid, some characteristics of the matroid are presented. In the process of studying these characteristics of the matroid, a quantitative approach to investigate attribute reduction in information systems is proposed. Secondly, contraction and restriction operations of the matroid are investigated through the representable matrix and approximation operators of rough sets. Some interesting relationships are presented among some new matroids which are the results of these operations. These relationships imply especial relationships among approximation operators in classical rough sets. Finally, the matroid belongs to a type of matroids and two axioms of the type of matroids are obtained through matrix approaches.(2) Matrix approaches are applied to covering-based rough sets through graphs. Firstly, a graph is constructed through a covering, which is called bipartite graph associated with a covering. A pair of covering-based upper and lower approximation operators are represented through the graph. Secondly, a matrix of the graph, named bipartite matrix, is proposed. According to the bipartite matrix, we can not only judge whether a covering is unary, but also find reducible elements in the covering. Finally, we regard an adjacency matrix of the graph as a partitioned matrix. We use the partitioned matrix to computer the minimal description and maximal description in covering-based rough sets, and also to study the matrix representations and properties of two covering-based upper approximation operators with the minimal description and maximal description. In addition, we use the power of the adjacency matrix of the graph to obtain reducible elements in the covering, and to computer a covering-based upper approximation operators.To sum up, we fully use matrices, which are computational tools, to investigate a matroidal structure of classical rough sets and study covering-based rough sets. These results further enrich rough set theory and its applications, which establish the foundation for the future work.