Matrix approach to spanning matroids of rough sets and its application to attribute reduction

Rough set theory is a granular computing tool used to deal with ambiguity and uncertainty in information systems. However, many optimization problems in rough sets, such as attribute reduction, are NP-hard problems, and most of the algorithms for these problems are greedy. As a complex mathematical structure, matroids provide a powerful tool for solving combinatorial optimization problems related to attribute reduction. Therefore, it is necessary to study the combination of matroids and rough sets. This paper uses rough sets and matrix approaches to spanning matroids. Moreover, the features of spanning matroids are applied to attribute reduction in decision information systems. Firstly, we construct spanning sets based on equivalence relations which can induce matroids called spanning matroids. Secondly, some features of spanning matroids, such as closed sets, bases, are studied by matrix method. Finally, the judgment theorems with the features of spanning matroids are proposed for addressing the problems about attribute reduction in decision information systems. Simultaneously, the sufficient and necessary conditions for distinguishing upper approximation reduction in inconsistent decision information systems are obtained from the viewpoint of spanning matroids. (c) 2021 Elsevier B.V. All rights reserved.