Matroidal structure of generalized rough sets based on symmetric and transitive relations

摘要

Rough set theory is an effective tool for dealing with vagueness or uncertainty in information systems. It is efficient for data pre-process and widely used in attribute reduction in data mining. Matroid theory is a branch of combinatorial mathematics and borrows extensively from linear algebra and graph theory, so it is an important mathematical structure with high applicability. Moreover, matroids have been applied to diverse fields such as algorithm design, combinatorial optimization and integer programming. Therefore, the establishment of matroidal structures of general rough sets may be much helpful for some problems such as attribute reduction in information systems. This paper studies generalized rough sets based on symmetric and transitive relations from the operator-oriented view by matroidal approaches. We firstly construct a matroidal structure of generalized rough sets based on symmetric and transitive relations, and provide an approach to study the matroid induced by a symmetric and transitive relation. Secondly, this paper establishes a close relationship between matroids and generalized rough sets. Approximation quality and roughness of generalized rough sets can be computed by the circuit of matroid theory. At last, a symmetric and transitive relation can be constructed by a matroid with some special properties.