A rough set approach to the characterization of transversal matroids

作者：Xu, Guoye^*; Wang, Zhaohao^*

来源：International Journal of Approximate Reasoning, 2016, 70: 1-12.

DOI：10.1016/j.ijar.2015.12.001

• Approximation operator
• Covering
• Rough set
• Transversal matroid

Rough sets are efficient for data pre-processing during data mining. However, some important problems such as attribute reduction in rough sets are NP-hard and the algorithms required to solve them are mostly greedy ones. The transversal matroid is an important part of matroid theory, which provides well-established platforms for greedy algorithms. In this study, we investigate transversal matroids using the rough set approach. First, we consttuct a covering induced by a family of subsets and we propose the approximation operators and upper approximation number based on this covering. We present a sufficient condition under which a subset is a partial transversal, and also a necessary condition. Furthermore, we characterize the transversal matroid with the covering-based approximation operator and construct some types of circuits. Second, we explore the relationships between closure operators in transversal matroids and upper approximation operators based on the covering induced by a family of subsets. Finally, we study two types of axiomatic characterizations of the covering approximation operators based on the set theory and matroid theory, respectively. These results provide more methods for investigating the combination of transversal matroids with rough sets.

• 出版日期2016-3
• 单位山西师范大学