×

Geometric lattice structure of covering-based rough sets through matroids. (English) Zbl 1264.05027

Summary: Covering-based rough set theory is a useful tool to deal with inexact, uncertain, or vague knowledge in information systems. Geometric lattices have been widely used in diverse fields, especially search algorithm design, which plays an important role in covering reductions.
In this paper, we construct three geometric lattice structures of covering-based rough sets through matroids and study the relationship among them. First, a geometric lattice structure of covering-based rough sets is established through the transversal matroid induced by a covering. Then its characteristics, such as atoms, modular elements, and modular pairs, are studied. We also construct a one-to-one correspondence between this type of geometric lattices and transversal matroids in the context of covering-based rough sets. Second, we present three sufficient and necessary conditions for two types of covering upper approximation operators to be closure operators of matroids.
We also represent two types of matroids through closure axioms and then obtain two geometric lattice structures of covering-based rough sets. Third, we study the relationship among these three geometric lattice structures. Some core concepts such as reducible elements in covering-based rough sets are investigated with geometric lattices. In a word, this work points out an interesting view, namely, geometric lattice, to study covering-based rough sets.

MSC:

05B35 Combinatorial aspects of matroids and geometric lattices
PDF BibTeX XML Cite
Full Text: DOI arXiv

References:

[1] Z. Pawlak, “Rough sets,” International Journal of Computer and Information Sciences, vol. 11, no. 5, pp. 341-356, 1982. · Zbl 0525.04005
[2] A. Skowron and J. Stepaniuk, “Tolerance approximation spaces,” Fundamenta Informaticae, vol. 27, no. 2-3, pp. 245-253, 1996. · Zbl 0868.68103
[3] R. Slowinski and D. Vanderpooten, “A generalized definition of rough approximations based on similarity,” IEEE Transactions on Knowledge and Data Engineering, vol. 12, no. 2, pp. 331-336, 2000.
[4] G. Liu and W. Zhu, “The algebraic structures of generalized rough set theory,” Information Sciences, vol. 178, no. 21, pp. 4105-4113, 2008. · Zbl 1162.68667
[5] Y. Y. Yao, “On generalizing pawlak approximation operators,” in Proceedings of the 1st International Conference on Rough Sets and Current Trends in Computing (RSCTC ’98), vol. 1424 of Lecture Notes in Artificial Intelligence, pp. 298-307, 1998. · Zbl 0955.68505
[6] Y. Y. Yao, “Relational interpretations of neighborhood operators and rough set approximation operators,” Information Sciences, vol. 111, no. 1-4, pp. 239-259, 1998. · Zbl 0949.68144
[7] Y. Y. Yao, “Constructive and algebraic methods of the theory of rough sets,” Information Sciences, vol. 109, no. 1-4, pp. 21-47, 1998. · Zbl 0934.03071
[8] W. Zhu and F. Wang, “A new type of covering rough sets,” in Proceedings of IEEE International Conference on Intelligent Systems, pp. 444-449, London, UK, September 2006.
[9] K. Qin, Y. Gao, and Z. Pei, “On covering rough sets,” in Proceedings of the 2nd International Conference on Rough Sets and Knowledge Technology (RSKT ’07), vol. 4481 of Lecture Notes in Computer Science, pp. 34-41, 2007.
[10] S. Wang, P. Zhu, and W. Zhu, “Structure of covering-based rough sets,” International Journal of Mathematical and Computer Sciences, vol. 6, pp. 147-150, 2010.
[11] S. Wang, Q. Zhu, W. Zhu, and F. Min, “Quantitative analysis for covering-based rough sets through the upper approximation number,” Information Sciences, vol. 220, pp. 483-491, 2013. · Zbl 1291.68390
[12] L. Wang, X. Yang, J. Yang, and C. Wu, “Relationships among generalized rough sets in six coverings and pure reflexive neighborhood system,” Information Sciences, vol. 207, pp. 66-78, 2012. · Zbl 1250.68261
[13] Y. Yao and B. Yao, “Covering based rough set approximations,” Information Sciences, vol. 200, pp. 91-107, 2012. · Zbl 1248.68496
[14] L. Wang, X. Liu, and J. Cao, “A new algebraic structure for formal concept analysis,” Information Sciences, vol. 180, no. 24, pp. 4865-4876, 2010. · Zbl 1222.68386
[15] R. Wille, “Restructuring lattice theory: an approach based on hierarchies of concepts,” in Ordered Sets, I. Rival, Ed., pp. 445-470, Reidel, Dordrecht, The Netherlands, 1982. · Zbl 0491.06008
[16] Y. Y. Yao and Y. Chen, “Rough set approximations in formal concept analysis,” in Proceedings of the 23rd International Meeting of the North American Fuzzy Information Processing Society, pp. 73-78, June 2004.
[17] G. Birhoff, Lattice Theory, American Mathematical Society, Rhode Island, RI, USA, 1995.
[18] H. Lai, Matroid Theory, Higher Education Press, Beijing, China, 2001.
[19] J. G. Oxley, Matroid Theory, Oxford University Press, New York, NY, USA, 1993.
[20] J. Edmonds, “Matroids and the greedy algorithm,” Mathematical Programming, vol. 1, pp. 127-136, 1971. · Zbl 0253.90027
[21] E. Lawler, Combinatorial Optimization: Networks and Matroids, Dover Publications, 2001. · Zbl 1058.90057
[22] S. Wang and W. Zhu, “Matroidal structure of covering-based rough sets through the upper approximation number,” International Journal of Granular Computing, Rough Sets and Intelligent Systems, vol. 2, pp. 141-148, 2011.
[23] S. Wang, W. Zhu, and F. Min, “Transversal and function matroidal structures of covering-based rough sets,” in Proceedings of the 6th International Conference on Rough Sets and Knowledge Technology (RSKT ’11), pp. 146-155, 2011.
[24] S. Wang, Q. Zhu, W. Zhu, and F. Min, “Matroidal structure of rough sets and its characterization to attribute reduction,” Knowledge-Based Systems, vol. 36, pp. 155-161, 2012.
[25] W. Zhu and S. Wang, “Matroidal approaches to generalized rough sets based on relations,” International Journal of Machine Learning and Cybernetics, vol. 2, no. 4, pp. 273-279, 2011.
[26] W. Zhu, “Relationship between generalized rough sets based on binary relation and covering,” Information Sciences, vol. 179, no. 3, pp. 210-225, 2009. · Zbl 1163.68339
[27] W. Zhu and F. Wang, “On three types of covering rough sets,” IEEE Transactions on Knowledge and Data Engineering, vol. 19, pp. 1131-1144, 2007. · Zbl 05340316
[28] W. Zhu, “Topological approaches to covering rough sets,” Information Sciences, vol. 177, no. 6, pp. 1499-1508, 2007. · Zbl 1109.68121
[29] W. Zhu and F.-Y. Wang, “Reduction and axiomization of covering generalized rough sets,” Information Sciences, vol. 152, pp. 217-230, 2003. · Zbl 1069.68613
[30] J. A. Pomykała, “Approximation operations in approximation space,” Bulletin of the Polish Academy of Sciences, vol. 35, no. 9-10, pp. 653-662, 1987. · Zbl 0642.54002
[31] Z. Y. Xu and Q. Wang, “Properties of covering rough sets model,” Journal of Henan Normal University, vol. 33, no. 1, pp. 130-132, 2005. · Zbl 1091.03509
[32] W. \DZakowski, “Approximations in the space (u,\pi ),” Demonstratio Mathematica, vol. 16, no. 3, pp. 761-769, 1983. · Zbl 0553.04002
[33] Y.-L. Zhang, J. Li, and W.-Z. Wu, “On axiomatic characterizations of three pairs of covering based approximation operators,” Information Sciences, vol. 180, no. 2, pp. 274-287, 2010. · Zbl 1186.68470
[34] G. Hu, X. Xiao, and W. Zhang, “Study on conditions of neighborhoods forming a partition,” in Proceedings of the 9th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD ’12), pp. 256-259, May 2012.
[35] Z. Yun, X. Ge, and X. Bai, “Axiomatization and conditions for neighborhoods in a covering to form a partition,” Information Sciences, vol. 181, no. 9, pp. 1735-1740, 2011. · Zbl 1216.68299
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.