Four matroidal structures of covering and their relationships with rough sets. (English) Zbl 1316.05025
Summary: Covering is a common form of data representation, and covering-based rough sets serve as an efficient technique to process this type of data. However, many important problems such as covering reduction in covering-based rough sets are NP-hard so that most algorithms to solve them are greedy. Matroids provide well-established platforms for greedy algorithm foundation and implementation. Therefore, it is necessary to integrate covering-based rough set with matroid. In this paper, we propose four matroidal structures of coverings and establish their relationships with rough sets. First, four different viewpoints are presented to construct these four matroidal structures of coverings, including 1-rank matroids, bigraphs, upper approximation numbers and transversals. The respective advantages of these four matroidal structures to rough sets are explored. Second, the connections among these four matroidal structures are studied. It is interesting to find that they coincide with each other. Third, a converse view is provided to induce a covering by a matroid. We study the relationship between this induction and the one from a covering to a matroid. Finally, some important concepts of covering-based rough sets, such as approximation operators, are equivalently formulated by these matroidal structures. These interesting results demonstrate the potential to combine covering-based rough sets with matroids.
MSC:
| 05B35 | Combinatorial aspects of matroids and geometric lattices |
| 03E72 | Theory of fuzzy sets, etc. |
References:
| [1] | Abu-Donia, H.; Salama, A., Generalization of Pawlakʼs rough approximation spaces by using δβ-open sets, International Journal of Approximate Reasoning, 53, 1094-1105 (2012) · Zbl 1264.54005 |
| [2] | Bianucci, D.; Cattaneo, G.; Ciucci, D., Entropies and co-entropies of coverings with application to incomplete information systems, Fundamenta Informaticae, 75, 77-105 (2007) · Zbl 1108.68112 |
| [3] | Chen, D.; Wang, C.; Hu, Q., A new approach to attribute reduction of consistent and inconsistent covering decision systems with covering rough sets, Information Sciences, 177, 3500-3518 (2007) · Zbl 1122.68131 |
| [4] | Cong, G.; Tan, K.; Tung, A.; Xu, X., Mining top-k covering rule groups for gene expression data, (Proc. ACM SIGMOD (2005)), 670-681 |
| [5] | Csajbk, Z., Approximation of sets based on partial covering, Theoretical Computer Science, 412, 5820-5833 (2011) · Zbl 1230.68194 |
| [6] | Estaji, A.; Hooshmandasl, M.; Davva, B., Rough set theory applied to lattice theory, Information Sciences, 200, 108-122 (2012) · Zbl 1248.06003 |
| [7] | Ganivada, A.; Dutta, S.; Pal, S. K., Fuzzy rough granular neural networks, fuzzy granules, and classification, Theoretical Computer Science, 412, 5834-5853 (2011) · Zbl 1223.68093 |
| [8] | Hu, Q.; Yu, D.; Liu, J.; Wu, C., Neighborhood rough set based heterogeneous feature subset selection, Information Sciences, 178, 3577-3594 (2008) · Zbl 1154.68466 |
| [9] | Huang, A.; Zhu, W., Matrix approach to rough sets through representable matroids over a field (2012) |
| [10] | Jensen, R.; Shen, Q., Semantics-preserving dimensionality reduction: rough and fuzzy-rough-based approaches, IEEE Transactions on Knowledge and Data Engineering, 16, 1457-1471 (2004) |
| [11] | Kahramanli, S.; Hacibeyoglu, M.; Arslan, A., A boolean function approach to feature selection in consistent decision information systems, Expert Systems with Applications, 38, 8229-8239 (2011) |
| [12] | Lai, H., Matroid Theory (2001), Higher Education Press: Higher Education Press Beijing |
| [13] | Li, F.; Yin, Y., Approaches to knowledge reduction of covering decision systems based on information theory, Information Sciences, 179, 1694-1704 (2009) · Zbl 1179.68193 |
| [14] | Li, Q.; Zhu, W., Matroidal structure of regular set based on serial and transitive relation (2012) |
| [15] | Li, X.; Liu, S., Matroidal approaches to rough set theory via closure operators, International Journal of Approximate Reasoning, 53, 513-527 (2012) · Zbl 1246.68233 |
| [16] | Li, Y., Some researches on fuzzy matroids (2007), Shaanxi Normal University, (in Chinese) |
| [17] | Liu, G.; Sai, Y., A comparison of two types of rough sets induced by coverings, International Journal of Approximate Reasoning, 50, 521-528 (2009) · Zbl 1191.68689 |
| [18] | Liu, Y.; Zhu, W.; Zhang, Y., Relationship between partition matroid and rough set through \(k\)-rank matroid, Journal of Information and Computational Science, 9, 2151-2163 (2012) |
| [19] | Ma, L., On some types of neighborhood-related covering rough sets, International Journal of Approximate Reasoning, 53, 901-911 (2012) · Zbl 1246.03068 |
| [20] | Meng, Z.; Shi, Z., A fast approach to attribute reduction in incomplete decision systems with tolerance relation-based rough sets, Information Sciences, 179, 2774-2793 (2009) · Zbl 1191.68667 |
| [21] | Min, F.; He, H.; Qian, Y.; Zhu, W., Test-cost-sensitive attribute reduction, Information Sciences, 181, 4928-4942 (2011) |
| [22] | Min, F.; Liu, Q.; Fang, C., Rough sets approach to symbolic value partition, International Journal of Approximate Reasoning, 49, 689-700 (2008) · Zbl 1184.68518 |
| [23] | Oxley, J. G., Matroid Theory (1993), Oxford University Press: Oxford University Press New York |
| [24] | Pomykala, J. A., Approximation operations in approximation space, Bulletin of the Polish Academy of Sciences. Mathematics, 35, 653-662 (1987) · Zbl 0642.54002 |
| [25] | Qin, K.; Pei, Z., On the topological properties of fuzzy rough sets, Fuzzy Sets and Systems, 151, 601-613 (2005) · Zbl 1070.54006 |
| [26] | Su, L.; Zhu, W., Some characteristics of matroids through rough sets (2012) |
| [27] | Sun, B.; Gong, Z.; Chen, D., Fuzzy rough set theory for the interval-valued fuzzy information systems, Information Sciences, 178, 2794-2815 (2008) · Zbl 1149.68434 |
| [28] | Tang, J.; She, K.; Zhu, W., Matroidal structure of rough sets from the viewpoint of graph theory, Journal of Applied Mathematics, 2012, 1-27 (2012) · Zbl 1259.03069 |
| [29] | Wang, C.; Chen, D.; Wu, C.; Hu, Q., Data compression with homomorphism in covering information systems, International Journal of Approximate Reasoning, 52, 519-525 (2011) · Zbl 1217.68240 |
| [30] | Wang, J.; Zhu, W., Rough sets and matroidal contraction (2012) |
| [31] | Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Matroidal structure of rough sets and its characterization to attribute reduction, Knowledge-Based Systems, 36, 155-161 (2012) |
| [32] | Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Quantitative analysis for covering-based rough sets through the upper approximation number, Information Sciences, 220, 483-491 (2013) · Zbl 1291.68390 |
| [33] | Wang, S.; Zhu, W., Matroidal structure of covering-based rough sets through the upper approximation number, International Journal of Granular Computing, Rough Sets and Intelligent Systems, 2, 141-148 (2011) |
| [34] | Wang, S.; Zhu, W.; Min, F., Transversal and function matroidal structures of covering-based rough sets, (Rough Sets and Knowledge Technology (2011)), 146-155 |
| [35] | West, D. B., Introduction to Graph Theory (2002), Pearson Education |
| [36] | Yang, B.; Zhu, W., Matroidal structure of generalized rough sets based on symmetric and transitive relations (2012) |
| [37] | Yao, Y.; Yao, B., Covering based rough set approximations, Information Sciences, 200, 91-107 (2012) · Zbl 1248.68496 |
| [38] | Zakowski, W., Approximations in the space \((u, \pi)\), Demonstratio Mathematica, 16, 761-769 (1983) · Zbl 0553.04002 |
| [39] | Zhang, Y.; Li, J.; Wu, W., On axiomatic characterizations of three pairs of covering based approximation operators, Information Sciences, 180, 274-287 (2010) · Zbl 1186.68470 |
| [40] | Zhu, W., Topological approaches to covering rough sets, Information Sciences, 177, 1499-1508 (2007) · Zbl 1109.68121 |
| [41] | Zhu, W., Relationship among basic concepts in covering-based rough sets, Information Sciences, 179, 2478-2486 (2009) · Zbl 1178.68579 |
| [42] | Zhu, W.; Wang, F., Reduction and axiomization of covering generalized rough sets, Information Sciences, 152, 217-230 (2003) · Zbl 1069.68613 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
