×

zbMATH — the first resource for mathematics

Characterization and reduction of concept lattices through matroid theory. (English) Zbl 1355.68248
Summary: Concept lattice theory is an efficient tool for data analysis. Reduction of attributes and objects for a context is an important issue in concept lattice theory. We explore the relationships between matroidal spaces and concepts for a given context. With the assistance of matroid theory, we conduct the attribute reduction and object reduction for a context and formulate the concepts for a given context. As a generalization of the linear independence in vector spaces, matroids provide well established platforms for some algorithms such as greedy algorithm.
In this paper, we mainly propose a notion of matroidal space by the family of circuits of a matroid. These relationships characterize the constructions of not only concepts, but also concept lattices. Meanwhile, we demonstrate that reduction of attributes and objects proposed in this paper preserve the original hierarchy order in the concept lattice for a given context.

MSC:
68T30 Knowledge representation
05B35 Combinatorial aspects of matroids and geometric lattices
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B23 Complete lattices, completions
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Beynon, M., Reducts within the variable precision rough sets model: a further investigation, Euro. J. Oper. Res., 134, 592-605, (2001) · Zbl 0984.90018
[2] Birkhoff, G., Lattice theory, (1967), Amer. Math. Soc. Providence · Zbl 0126.03801
[3] Carpineto, C.; Romano, G., Concept data analysis: theory and applications, (2004), John Wiley & Sons Ltd. England · Zbl 1083.68117
[4] Ganter, B.; Stumme, G.; Wille, R., Formal concept analysis: foundations and applications, (2005), Springer-Verlag Berlin Heidelberg · Zbl 1087.68003
[5] Ganter, B.; Wille, R., Formal concept analysis: mathematical foundations, (1999), Springer-Verlag Berlin, Heidelberg, German version: Springer, Heidelberg, 1996 · Zbl 0909.06001
[6] G. Grätzer, Lattice Theory: Foundation, Birkhäuser, Basel, 2011.
[7] Kumar, C.; Srinivas, S., Concept lattice reduction using fuzzy K-means clustering, Expert Syst. Appl., 37, 2696-2704, (2010)
[8] Leung, Y.; Wu, W.; Zhang, W., Knowledge acquisition in incomplete information systems: a rough set approach, Euro. J. Oper. Res., 168, 1, 164-180, (2006) · Zbl 1136.68528
[9] Li, L.; Zhang, J., Attribute reduction in fuzzy concept lattices based on the T implication, Knowl.-Based Syst., 23, 497-503, (2010)
[10] Liu, H.; Liu, L.; Zhang, H., A fast pruning redundant rule method using Galois connection, Appl. Soft Comput., 11, 130-137, (2011)
[11] Mao, H., The relation between matroid and concept lattice, Adv. Math. (China), 35, 3, 361-365, (2006), in Chinese with English summary
[12] Mao, H., On closure axioms for a matroid using Galois connections, Math. Commun., 14, 2, 425-432, (2009) · Zbl 1192.05023
[13] Mi, J.; Leung, Y.; Wu, W., Approaches to attribute reduction in concept lattices induced by axialities, Knowl.-Based Syst., 23, 504-511, (2010)
[14] Oxley, J., Matroid theory, (2011), Oxford University Press New York · Zbl 1254.05002
[15] Pawlak, Z., Rough sets: theoretical aspects of reasoning about data, (1991), Kluwer Academic Publishers Dordrecht, Boston · Zbl 0758.68054
[16] V. Snasel, M. Polovincak, H.M. Dahwa, Concept lattice reduction by singular value decomposition, in: Proceedings of the Spring Young Researcher’s Colloquium on Database and Information Systems, Moscow, Russia, 2007. <http://ceur-ws.org/Vol-256/submission_18.pdf> (accessed 12.10.12).
[17] Tang, J.; She, K.; Zhu, W., Matroidal structure of rough sets from the viewpoint of graph theory, J. Appl. Math., 2012, 27, (2012), Article ID 97392 · Zbl 1259.03069
[18] Wang, S.; Zhu, Q.; Zhu, W.; Min, F., Matroidal structure of rough sets and its characterization to attribute reduction, Knowl.-Based Syst., 36, 155-161, (2012)
[19] Wei, L.; Qi, J.; Zhang, W. X., Attribute reduction theory of concept lattice based on decision formal contexts, Sci. Chin. Ser. F: Inform. Sci.;, 51, 7, 910-923, (2008) · Zbl 1291.68391
[20] Welsh, D. J.A., Matroid theory, (1976), Academic Press London · Zbl 0343.05002
[21] Whitney, H., On the abstract properties of linear dependence, Am. J. Math., 57, 3, 509-533, (1935) · JFM 61.0073.03
[22] R. Wille, Restructuring lattice theory: an approach based on hierarchies of concepts, in: I. Rival (Ed.), Ordered Sets, Dordrecht Boston, Reidel, 1982, pp. 445-470.
[23] Zhang, W. X.; Wei, L.; Qi, J., Attribute reduction theory and approach to concept lattice, Sci. Chin. Ser. F: Inform. Sci., 48, 6, 713-726, (2005) · Zbl 1161.68796
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.