Attribute reduction algorithms based on the matroidal structure of rough set

摘要

Rough set is a tool for dealing with uncertainty in information systems. Matroid is a structure that generalizes the notion of linear independence in vector spaces. In this paper, we study attribute reduction algorithms based on the matroidal structure of rough set. Firstly, an approach is proposed to convert a partition into a matrix, then turn this matrix into a matroid. Secondly, several basic concepts of Pawlak rough set are equivalently expressed by matroid. In this way, we establish the matroidal structure of rough set. Consequently, attribute reduction is transformed into the corresponding problem under the matroidal structure. Two attribute reduction algorithms are designed using the matroidal structure. They are equivalent to the discernibility matrix based one and the significance of attributes based one under Pawlak rough set, respectively. This study shows the usefulness of matroidal structure in dealing with attribute reduction.