Matroidal structure of rough sets and its characterization to attribute reduction

摘要

Rough sets are efficient for data pre-processing in data mining. However, some important problems such as attribute reduction in rough sets are NP-hard, and the algorithms to solve them are almost greedy ones. As a generalization of the linear independence in vector spaces, matroids provide well-established platforms for greedy algorithms. In this paper, we apply matroids to rough sets through an isomorphism from equivalence relations to 2-circuit matroids. First, a matroid is induced by an equivalence relation. Several equivalent characterizations of the independent sets of the induced matroid are obtained through rough sets. Second, an equivalence relation is induced by a matroid. The relationship between the above two inductions is studied. Third, an isomorphism from equivalence relations to 2-circuit matroids is established, which lays a sound foundation for studying rough sets using matroidal approaches. Finally, attribute reduction is equivalently formulated with rank functions and closure operators of matroids. These results show the potential for designing attribute reduction algorithms using matroidal approaches.