Abstract
In many real world applications, information blocks form a covering of a universe. Covering-based rough set theory has been proposed to deal with this type of information. It is more general and complex than classical rough set theory, hence there is much need to develop sophisticated structures to characterize covering-based rough sets. Matroids are important tools for describing graphs and linear independence of matrix theory. This paper establishes two matroidal structures of covering-based rough sets. Firstly, the transversal matroidal structure of a family of subsets of a universe is constructed. We also prove that the family of subsets of a universe is a covering if and only if the constructed transversal matroid is a normal one. Secondly, the function matroidal structure is constructed through the upper approximation number. Moreover, the relationships between the two matroidal structures are studied. Specifically, when a covering of a universe is a partition, these two matroidal structures coincide with each other.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Zhu, W.: Relationship among basic concepts in covering-based rough sets. Information Sciences 17, 2478–2486 (2009)
Zhu, W., Wang, F.: Reduction and axiomization of covering generalized rough sets. Information Sciences 152, 217–230 (2003)
Bartol, W., Miro, J., Pioro, K., Rossello, F.: On the coverings by tolerance classes. Information Sciences 166, 193–211 (2004)
Bianucci, D., Cattaneo, G., Ciucci, D.: Entropies and co-entropies of coverings with application to incomplete information systems. Fundamenta Informaticae 75, 77–105 (2007)
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)
Min, F., He, H., Qian, Y., Zhu, W.: Test-cost-sensitive attribute reduction. In: To Appear in Information Sciences (2011)
Yao, Y., Zhao, Y.: Attribute reduction in decision-theoretic rough set models. Information Sciences 178, 3356–3373 (2008)
Hu, Q., Pan, W., An, S., Ma, P., Wei, J.: An efficient gene selection technique for cancer recognition based on neighborhood mutual information. International Journal of Machine Learning and Cybernetics 1, 63–74 (2011)
Li, F., Yin, Y.: Approaches to knowledge reduction of covering decision systems based on information theory. Information Sciences 179, 1694–1704 (2009)
Qian, Y., Liang, J., Pedrycz, W., Dang, C.: Positive approximation: An accelerator for attribute reduction in rough set theory. Artificial Intelligence 174, 597–618 (2010)
Wu, W.: Attribute reduction based on evidence theory in incomplete decision systems. Information Sciences 178, 1355–1371 (2008)
Hu, Q., Yu, D., Liu, J., Wu, C.: Neighborhood rough set based heterogeneous feature subset selection. Information Sciences 178, 3577–3594 (2008)
Wang, S., Min, F., Zhu, W.: Quantitative analysis for covering-based rough sets on boolean algebra. Submitted to Information Sciences (2011)
Wang, S., Zhu, W.: Matroidal structure of covering-based rough sets through the upper approximation number. To Appear in International Journal of Granular Computing, Rough Sets and Intelligent Systems (2011)
Wang, S., Zhu, W., Zhu, P.: Abstract interdependency in rough sets. Journal of Nanjing University 46, 507–510 (2010) (in Chinese)
Zhu, W., Wang, S.: Matroidal approaches to generalized rough sets based on relations. To Appear in International Journal of Machine Learning and Cybernetics (2011)
Kondo, M.: On the structure of generalized rough sets. Information Sciences 176, 589–600 (2005)
Li, J.: Topological methods on the theory of covering generalized rough sets. Pattern Recognition and Artificial Intelligence 17, 7–10 (2004) (in Chinese)
Zhu, W.: Topological approaches to covering rough sets. Information Sciences 177, 1499–1508 (2007)
Qin, K., Pei, Z.: On the topological properties of fuzzy rough sets. Fuzzy Sets and Systems 151, 601–613 (2005)
Davvaz, B.: Roughness based on fuzzy ideals. Information Sciences 176, 2417–2437 (2006)
Deng, T., Chen, Y., Xu, W., Dai, Q.: A novel approach to fuzzy rough sets based on a fuzzy covering. Information Sciences 177, 2308–2326 (2007)
Liu, G., Sai, Y.: Invertible approximation operators of generalized rough sets and fuzzy rough sets. Information Sciences 180, 2221–2229 (2010)
Hong, T., Tseng, L., Chien, B.: Mining from incomplete quantitative data by fuzzy rough sets. Expert Systems with Applications 37, 2644–2653 (2010)
Wang, S., Zhu, P., Zhu, W.: Structure of covering-based rough sets. International Journal of Mathematical and Computer Sciences 6, 147–150 (2010)
Yao, Y.: Constructive and algebraic methods of theory of rough sets. Information Sciences 109, 21–47 (1998)
Yao, Y., Zhang, J.P.: Interpreting fuzzy membership functions in the theory of rough sets. In: Ziarko, W.P., Yao, Y. (eds.) RSCTC 2000. LNCS (LNAI), vol. 2005, pp. 82–89. Springer, Heidelberg (2001)
Zhu, W.: Relationship between generalized rough sets based on binary relation and covering. Information Sciences 179, 210–225 (2009)
Zhu, W., Wang, F.: On three types of covering rough sets. IEEE Transactions on Knowledge and Data Engineering 19, 1131–1144 (2007)
Zhu, F., Wang, F.: Some results on covering generalized rough sets. Pattern Recognition and Artificial Intelligence 15, 6–13 (2002)
Lai, H.: Matroid theory. Higher Education Press (2001)
Li, Y.: Some researches on fuzzy matroids. PhD thesis, Shaanxi Normal University (2007)
Mao, H.: The relation between matroid and concept lattice. Advance in Mathematics 35, 361–365 (2006)
Maffioli, F., Salvi, N.Z.: On some properties of base-matroid. Discrete Applied Mathematics 154, 1401–1407 (2006)
Jones, S., McGuinness, S.: Defining matroids through sequential selection. European Journal of Combinatorics 28, 469–480 (2007)
Lawler, E.L.: Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York (2001)
Edmonds, J.: Matroids and the greedy algorithm. Mathematical Programming 1, 127–136 (1971)
Qian, Y., Liang, J., Li, D., Zhang, H., Dang, C.: Measures for evaluating the decision performance of a decision table in rough set theory. Information Sciences 178, 181–202 (2008)
Min, F., Liu, Q.: A hierarchical model for test-cost-sensitive decision systems. Information Sciences 179, 2442–2452 (2009)
Min, F., Liu, Q., Fang, C.: Rough sets approach to symbolic value partition. International Journal of Approximate Reasoning 49, 689–700 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wang, S., Zhu, W., Min, F. (2011). Transversal and Function Matroidal Structures of Covering-Based Rough Sets. In: Yao, J., Ramanna, S., Wang, G., Suraj, Z. (eds) Rough Sets and Knowledge Technology. RSKT 2011. Lecture Notes in Computer Science(), vol 6954. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-24425-4_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-24425-4_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-24424-7
Online ISBN: 978-3-642-24425-4
eBook Packages: Computer ScienceComputer Science (R0)