×

Lattices, closures systems and implication bases: a survey of structural aspects and algorithms. (English) Zbl 1398.68510

Summary: Concept lattices and closed set lattices are graphs with the lattice property. They have been increasingly used this last decade in various domains of computer science, such as data mining, knowledge representation, databases or information retrieval. A fundamental result of lattice theory establishes that any lattice is the concept lattice of its binary table. A consequence is the existence of a bijective link between lattices, contexts (via the table) and a set of implicational rules (via the canonical (direct) basis). The possible transformations between these objects give rise to relevant tools for data analysis.
In this paper, we present a survey of lattice theory, from the algebraic definition of a lattice, to that of a concept lattice, through closure systems and implicational rules; including the exploration of fundamental bijective links between lattices, reduced contexts and bases of implicational rules; and concluding with the presentation of the main generation algorithms of these objects.

MSC:

68T30 Knowledge representation
06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B05 Structure theory of lattices
06B15 Representation theory of lattices
06B23 Complete lattices, completions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Birkhoff, G., Lattice theory, (1940), American Math. Society · JFM 66.0100.04
[2] Grätzer, G., General lattice theory, (1978), Birkahäuser-Verlag and Springer · Zbl 0385.06015
[3] Grätzer, G., Lattice theory: foundation, (2011), Springer Basel · Zbl 1233.06001
[4] Davey, B. A.; Priestley, H. A., Introduction to lattices and orders, (1991), Cambridge University Press
[5] Monjardet, B., La construction des notions d’ordre et de treillis, (Journées nationales de l’Association des Professeurs de Mathématiques de l’Enseignement Public (APMEP), (2008)), La Rochelle, France
[6] Caspard, N.; Leclerc, B.; Monjardet, B., Ensembles ordonnées finis: concepts, Résultats et usages, (2007), Springer · Zbl 1136.06001
[7] Barbut, M.; Monjardet, B., Ordres et classifications: algèbre et combinatoire, (1970), Hachette Paris, 2 tomes
[8] Markowsky, G., Some combinatorial aspects on lattice theory, (Proceedings of Houston Lattice Theory Conference, (1973)), 36-68
[9] Öre, O., Galois connexions, Trans. Amer. Math. Soc., 55, 493-513, (1944) · Zbl 0060.06204
[10] Caspard, N.; Monjardet, B., The lattice of closure systems, closure operators and implicational systems on a finite set: a survey, Discrete Appl. Math., 127, 2, 241-269, (2003) · Zbl 1026.06008
[11] Wille, R., Restructuring lattice theory: an approach based on hierarchies of concepts, (Rival, I., Ordered Sets, (1982), Reidel Dordrecht-Boston), 445-470
[12] Ganter, B.; Wille, R., Formal concept analysis, mathematical foundations, (1999), Springer-Verlag Berlin · Zbl 0909.06001
[13] Mephu-Nguifo, E.; Njiwoua, P., Iglue: a lattice-based constructive induction system, Internat. J. Intell. Data Anal., 4, 4, 1-49, (2000)
[14] Mephu-Nguifo, E.; Duquenne, V.; Liquiere, M., Concept lattice-based knowledge discovery in databases. introduction, J. Exp. Theor. Artif. Intell., 14, 2, 75-79, (2002)
[15] Pasquier, N.; Bastide, Y.; Taouil, R.; Lakhal, L., Pruning closed itemset lattices for association rules, (International Conference on Advanced Databases (BDA), (1998)), 177-196
[16] Visani, M.; Bertet, K.; Ogier, J.-M., Navigala: an original symbol classifier based on navigation through a Galois lattice, Int. J. Pattern Recognit. Artif. Intell., 25, 04, 449-473, (2011)
[17] Agrawal, R.; Srikant, R., Fast algorithms for mining association rules in large databases, (20th International Conference on Very Large Data Bases (VLDB), (1994)), 487-499
[18] Priss, U., Lattice-based information retrieval, Knowledge Organ., 27, 3, 132-142, (2000)
[19] Ferré, S.; Ridoux, O., An introduction to logical information systems, Inf. Process. Manag., 40, 3, 383-419, (2004) · Zbl 1091.68119
[20] Ferré, S., Reconciling expressivity and usability in information access. from file systems to the semantic web, (October 2015), University of Rennes, Habilitation thesis
[21] Adaricheva, K.; Italiano, G. F.; Büning, H. K.; Turán, G., Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl seminar 14201), Dagstuhl Rep., 4, 5, 1-26, (2014)
[22] Morvan, M.; Nourine, L., Simplicial elimination scheme, extremal lattices and maximal antichains lattice, Order, 13, 2, 159-173, (1996) · Zbl 0859.06005
[23] Monjardet, B., Arrowian characterizations of latticial federation consensus functions, Math. Social Sci., 20, 51-71, (1990) · Zbl 0746.90002
[24] Bertet, K., The dependence graph of a lattice, (Ninth International Conference on Concept Lattices and Their Applications, CLA, Malaga, Spain, (2012)), 223-231
[25] Freeze, R.; Jezek, J.; Nation, J. B., Free lattices, vol. 42, (1995), American Mathematical Society Providence, Rhode Island
[26] Nation, J. B., An approach to lattice varieties of finite height, Algebra Universalis, 27, 4, 521-543, (1990) · Zbl 0721.08004
[27] Jónsson, B.; Nation, J. B., A report on sublattices of free lattices, (Colloq. Math. Soc. János Bolyai: Contributions to Universal Algebra, (1975)), 223-257
[28] Adaricheva, K.; Nation, J. B.; Rand, R., Ordered direct implicational basis of a finite closure system, Discrete Appl. Math., 161, 707-723, (2013) · Zbl 1288.06007
[29] Moore, E. H., On a form of general analysis with applications to linear differential and integral equations, (Atti del IV Congresso Internazionale dei Matematici, Roma, (1909)), 98-114
[30] Guigues, J.-L.; Duquenne, V., Familles minimales d’implications informatives résultant d’un tableau de données binaires, Math. Sci. Hum., 95, 5-18, (1986)
[31] Bazin, A., On the enumeration of pseudo-intents in a partial order, (2014), University of Paris 6 France, Ph.D. thesis
[32] Bertet, K.; Monjardet, B., The multiple facets of the canonical direct unit implicational basis, Theoret. Comput. Sci., 411, 22-24, 2155-2166, (2010) · Zbl 1209.68187
[33] Ganter, B.; Kuznetsov, S., Pattern structures and their projections, (Stumme, G.; Delugach, H., Proceedings of the 9th International Conference on Conceptual Structures, ICCS, vol. 2120, (2001)), 129-142 · Zbl 0994.68147
[34] Polaillon, G., Organisation et interprétation par LES treillis de Galois de données de type multivalué, intervalle ou histogramme, (1998), Paris IX-Dauphine France, Ph.D. thesis
[35] Kaytoue, M.; Kuznetsov, S. O.; Napoli, A., Revisiting numerical pattern mining with formal concept analysis, (Proceedings of International Joint Conference on Artificial Intelligence, IJCAI, (2011)), 1342-1347
[36] Nguyen, V. A.; Yamamoto, A., Learning from graph data by putting graphs on the lattice, Expert Syst. Appl., 39, 11172-11182, (2012)
[37] Poezevara, G., Fouille de graphes pour la Découverte de contrastes entre classes: application à L’estimation de la toxicité de molécules, (2012), University of Caen France, Ph.D. thesis
[38] Goralcikova, A.; Koubek, V., A reduct and closure algorithm for graphs, Math. Found. Comput. Sci., 74, 301-307, (1979) · Zbl 0408.68038
[39] Dao, N. B.; Bertet, K.; Revel, A., Reduction dimension of bags of visual words with fca, (The Twelfth International Conference on Concept Lattices and Their Applications, CLA, Kosice, Slovakia, (2014)), 219-230
[40] Norris, E., An algorithm for computing the maximal rectangles in a binary relation, Rev. Roumaine Math. Pures Appl., 23, 2, 243-250, (1978) · Zbl 0389.05003
[41] Ganter, B., Two basic algorithms in concept analysis, (Proceedings of the 8th International Conference on Formal Concept Analysis, ICFCA, (2010), Springer-Verlag), 312-340 · Zbl 1274.68484
[42] Bordat, J.-P., Calcul pratique du treillis de Galois d’une correspondance, Math. Sci. Hum., 96, 31-47, (1986) · Zbl 0626.06007
[43] Godin, R.; Missaoui, R.; Alaoui, H., Learning algorithms using a Galois lattice structure, (Third International Conference on Tools for Artificial Intelligence, (1991), IEEE Computer Society Press San Jose, California), 22-29
[44] Nourine, L.; Raynaud, O., A fast algorithm for building lattices, Inform. Process. Lett., 71, 199-204, (1999) · Zbl 0998.06005
[45] Kuznetsov, S.; Obiedkov, S., Comparing performance of algorithms for generating concept lattices, J. Exp. Theor. Artif. Intell., 14, 2-3, 189-216, (2002) · Zbl 1024.68020
[46] Bertet, K.; Guillas, S.; Ogier, J.-M., Extensions of Bordat’s algorithm for attributes, (Fifth International Conference on Concept Lattices and their Applications, CLA, Montpellier, France, (2007)), 38-49
[47] Demko, C.; Bertet, K., Generation algorithm of a concept lattice with limited object access, (Proceedings of the Eight International Conference on Concept Lattices and Their Applications, CLA, Nancy, France, (2011)), 239-250
[48] Wild, M., Implicational bases for finite closure system, (Lex, W., Arbeitstagung Begriffsanalyse und Künstliche Intelligenz, (1988), TU Clausthal), 147-169
[49] Shock, R. C., Computing the minimum cover of functional dependencies, Inform. Process. Lett., 3, 22, 157-159, (1986) · Zbl 0587.68088
[50] Day, A., The lattice theory of functional dependencies and normal decompositions, Internat. J. Algebra Comput., 02, 409-431, (1992) · Zbl 0798.68049
[51] Babin, M.; Kuznetsov, S. O., Recognizing pseudo-intent is conp-complete, (Proceedings of the 7th International Conference on Concept Lattices and Their Applications, CLA, Seville, Spain, (2010)), 294-301
[52] Distel, F.; Sertkaya, B., On the complexity of enumerating the pseudo-intents, Discrete Appl. Math., 450-466, (2011) · Zbl 1214.68387
[53] Wild, M., Computations with finite closure systems and implications, (Proceedings of the 1st Annual International Conference on Computing and Combinatorics, LNCS, vol. 959, (1995), Springer), 111-120
[54] Bertet, K.; Nebut, M., Efficient algorithms on the family associated to an implicational system, Discrete Math. Theor. Comput. Sci., 6, 315-338, (2004) · Zbl 1062.06004
[55] Rodriguez-Lorenzo, E.; Bertet, K.; Cordero, P.; Enciso, M.; Mora, A.; Ojeda-Aciego, M., From implicational systems to direct-optimal bases: a logic based approach, Appl. Math. Inf. Sci., 9, 2, 1-13, (2015)
[56] Fredman, M. L.; Khachiyan, L., On the complexity of dualization of monotone disjunctive normal forms, J. Algorithms, 21, 618-628, (1996) · Zbl 0864.68038
[57] Kavvadias, D. J.; Stravropoulos, E. C., Monotone Boolean dualization is in co-NP[\(l o g^2 n\)], Inform. Process. Lett., 85, 1-6, (2003)
[58] Ibaraki, T.; Kogan, A.; Makino, K., Functional dependencies in Horn theories, Artificial Intelligence, 108, 1-30, (1999) · Zbl 0914.68185
[59] Pfaltz, J. L.; Taylor, C. M., Scientific discovery through iterative transformations of concept lattices, (Workshop on Discrete Applied Mathematics, in conjunction with the 2nd SIAM International Conference on Data-Mining, (2002)), 65-74
[60] Floch, A. L.; Fisette, C.; Missaoui, R.; Valtchev, P.; Godin, R., Jen: un algorithme efficace de construction de générateurs minimaux pour l’identication de règles d’association, Nouv. Technol. Inf., 1, 1, 135-146, (2003)
[61] Mannila, H.; Räihä, K. J., The design of relational databases, (1992), Addison-Wesley · Zbl 0777.68014
[62] Taouil, R.; Bastide, Y., Computing proper implications, (9th International Conference on Conceptual Structures, Stanford, USA, (2002)), 49-61
[63] Ryssel, U.; Distel, F.; Borchmann, D., Fast algorithms for implication bases and attribute exploration using proper premises, Ann. Math. Artif. Intell., 65, 1-29, (2014) · Zbl 1314.68305
[64] Yevtushenko, S. A., System of data analysis: concept explorer, (Seventh National Conference on Artificial Intelligence, KII, Russia, (2000)), 127-134
[65] Valtchev, P.; Grosser, D.; Roume, C.; Hacene, M. R., Galicia: an open platform for lattices, (Eleventh International Conference on Conceptual Structures, ICCS, Shaker Verlag, (2003)), 241-254
[66] Priss, U., FCA software interoperability, (Sixth International Conference on Concept Lattices and their Applications, CLA, Olomouc, Czech Republic, (2008)), 193-205
[67] Gansner, E. R.; North, S. C., An open graph visualization system and its applications to software engineering, Softw. Pract. Exp., 30, 1203-1233, (1999) · Zbl 1147.68782
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.