Mathematical aspects of concept analysis. (English) Zbl 0885.06001
In this article the author provides a survey of results related to the mathematical aspects of concept analysis.
In an introductory section 1, the subject matter and the basic terminology of contexts, Galois connections, and concepts are introduced. Section 2 contains results about the algebraic problems that arise from the lattice nature of the set of all concepts, in particular, results on the decomposition of concept lattices into smaller ones. Section 3 deals with applications of concepts in data analysis, in particular, on methods of search for dependences between attributes. Algorithmic problems of concept generation are studied in section 4. These include the study of the complexity of enumeration, decision, and classification problems relating to concepts. Section 5 surveys results on the Zarankiewicz problem.
There is an extensive bibliography at the end of the article (100 titles).
A reader with an interest in this article might also consult the book: Formale Begriffsanalyse (1996; Zbl 0861.06001) by B. Ganter and R. Wille.
In an introductory section 1, the subject matter and the basic terminology of contexts, Galois connections, and concepts are introduced. Section 2 contains results about the algebraic problems that arise from the lattice nature of the set of all concepts, in particular, results on the decomposition of concept lattices into smaller ones. Section 3 deals with applications of concepts in data analysis, in particular, on methods of search for dependences between attributes. Algorithmic problems of concept generation are studied in section 4. These include the study of the complexity of enumeration, decision, and classification problems relating to concepts. Section 5 surveys results on the Zarankiewicz problem.
There is an extensive bibliography at the end of the article (100 titles).
A reader with an interest in this article might also consult the book: Formale Begriffsanalyse (1996; Zbl 0861.06001) by B. Ganter and R. Wille.
Reviewer: M.Höft (Dearborn)
MSC:
| 06-02 | Research exposition (monographs, survey articles) pertaining to ordered structures |
| 06B23 | Complete lattices, completions |
| 06B99 | Lattices |
Keywords:
concept analysis; contexts; complete lattices; decomposition; algorithm; complexity; survey; data analysisCitations:
Zbl 0861.06001References:
| [1] | A. Aho and J. Hopcroft,The Design and Analysis of Computer Algorithms, Addison-Wesley (1974). · Zbl 0326.68005 |
| [2] | O. M. Anshakov, D. P. Skvortsov, and V. K. Finn, ”Logical means of the JSM-method of automatic hypothesis generation,”Nauchn. Tekh. Inf., Ser. 2 (Autom. Document. Math. Linguist.), No. 9, 9–17 (1978). · Zbl 0653.68103 |
| [3] | O. M. Anshakov, D. P. Skvortsov, V. K. Finn, and V. G. Ivashko, ”Logical means of the JSM-method of automatic generation: main notions and the system of inference rules,”Nauchn. Tekh. Inf., Ser. 2 (Autom. Document. Math. Linguist.), No. 9, 10–18 (1987). · Zbl 0641.68165 |
| [4] | O. M. Anshakov, V. K. Finn, and D. P. Skvortsov, ”On logical means of formalization of plausible inferences,” In:VIII International Congress of Logic, Methodol., and Phil. of Sci., Abstracts, 212–215, Nauka, Moscow, (1987). |
| [5] | O. M. Anshakov, V. K. Finn, and D. P. Skvortsov, ”On axiomatization of many-valued logics associated with the formalization of plausible reasonings,”Stud. Log.,25, No. 4, 23–47 (1989). · Zbl 0706.03021 |
| [6] | R. Balbes and P. Dwinger,Distributive Lattices, University of Missouri Press (1974). |
| [7] | M. Barbut and B. Monjardet,Ordre et classification,II, Hachette, Paris (1970). |
| [8] | G. D. Birkhoff,Lattice Theory, Amer. Math. Soc. (1979). |
| [9] | J. P. Bordat, ”Calcul pratique du treillis de Galois d’une correspondance,”Math. Sci. Hum., No. 96, 31–47 (1986). · Zbl 0626.06007 |
| [10] | P. Burmeister, ”Merkmalsimplikationen bei unvollständigem Wissen,” In:Arbeitstagung Begriffdanalyse und Künstliche Intelligenz (W. Lex, ed.), Institut für Informatik, Clausthal, pp. 15–46 (1991). |
| [11] | T. Bylander, D. Allemang, M. C. Tanner, and J. R. Josephson, ”the computational complexity of abduction,”Artif. Intell.,49, No. 1, 25–60 (1991). · Zbl 0737.68076 · doi:10.1016/0004-3702(91)90005-5 |
| [12] | M. Chein, ”Algorithme de recherche des sous-matrices premières d’une matrice,”Bull. Math. R.S. Roumanie, No. 13, No. 1, 21–25 (1969). · Zbl 0209.06401 |
| [13] | K. Čulik, ”Teilweise Lösung eines verallgemeinerten Problem von K. Zarankiewicz,”Ann. Polon. Math.,3, No. 1, 165–168 (1956). |
| [14] | J. Duda, ”Boolean concept lattices and good contexts,”Čas. Pest. Mat.,114, No.2, 165–175 (1989). · Zbl 0672.06002 |
| [15] | V. Duquenne, ”Contextual implications between attributes and some representation properties for finite lattices,” In:Beiträge zur Begriffsanalyse (B. Ganter, R. Wille, and K. E. Wolff, eds.), B. I. Wissenschaft-Verlag, Mahnnheim, pp. 213–239 (1987). |
| [16] | V. Duquenne and J.-L. Guigues, ”Familles minimales d’implications informatives résultant d’un tableau de données binaires,”Math. Sci. Hum.,24, No. 95, 5–18 (1986). |
| [17] | B. Efron,Nontraditional Methods of Many-Dimensional Statistical Information, [Russian translation], Moscow (1988). |
| [18] | P. Erdös and J. Spenser,Probability Methods in Combinatorics [Russian tranlation], Moscow (1976). |
| [19] | V. K. Finn, ”Data bases with incomplete information and a new method of automatic hypothesis generation,” In:Dialog and Factographic Information Systems [in Russian], Moscow, pp. 153–156 (1981). |
| [20] | V. K. Finn, ”On machine-oriented formalization of plausible reasoning in the style of F. Backon-J. S. Mill,”Semiotika Informatica, No. 20, 35–101 (1983). · Zbl 0521.03012 |
| [21] | V. K. Finn, ”Plausible inference and plausible reasoning,”Itogi Nauki i Tekhniki, Seriya Teoriya Veroyatnostei, Mat. Statist. Teoret. Kibern.,28, 3–84 (1988). · Zbl 0708.03002 |
| [22] | V. K. Finn, ”JSM-method of automatic generation with an order relation,”Semiotika Informatika, No. 31, 69–103 (1990). |
| [23] | V. K. Finn, ”Plausible reasoning in systems of JSM type,”Itogi Nauki i Tekhniki, Seriya Informatika,15, 54–101 (1991). |
| [24] | J. G. Ganascia, ”CHARADE: A rule system learning system,” In:Proc. of the 10th International Joint Conference on Artificial Intelligence (IJCAI-87), Milan, Italy, August 23–28 (1987), 117–124 (1987). |
| [25] | J. G. Ganascia, ”Improvement and refinement of the learning bias semantic,” In:Proc. of the 8th Europ. Conf. on Artificial Intelligence (ECAI-88), pp. 81–86, (1988). |
| [26] | B. Ganter, ”Two basic algorithms in concept analysis,”preprint 831, Technische Hochshule Darmstadt (1984). · Zbl 1274.68484 |
| [27] | B. Ganter, ”Algorithmen zur Formalen Begriffsanalyse,” In:Beiträge zur Begriffsanalyse, (B. Ganter, R. Wille, and K. E. Wolff, eds.), B. I. Wissenschaftsverlag, Mannheim, 241–254, (1987). |
| [28] | B. Ganter, ”Composition and Decomposition in Formal concept Analysis,” In:Classification and Related Methods of Data Analysis (H. H. Bock, ed.), North-Holland, Amsterdam, 561–566, (1988). |
| [29] | B. Ganter, K. Rindfrey, and M. Skorsky, ”Software for formal concept analysis,” In:Classification as a Tool of Research (W. Gaul and M. Schader, eds.), North-Holland, Amsterdam, 161–167, (1986). |
| [30] | B. Ganter, J. Stahl, and R. Wille, ”Conceptual measurement and many-valued contexts,” In:Classification as a Tool of Research (W. Gaul and M. Schader, eds.), North-Holland, Amsterdam, 169–176, (1986). |
| [31] | B. Ganter and R. Wille, ”Implikationen und Abhängigkeiten zwischen Merkmalen,” In:Die Klassifikation und ihr Umfeld, (P. O. Degens, H.-J. Hermes, and O. Opitz, eds.), Index-Verlag, Frankfurt, 171–185, (1986). |
| [32] | B. Ganter and R. Wille, ”Conceptual scaling,” In:Applications of Combinatorics and Graph Theory to the Biological and Social Sciences (F. Roberts, ed.), Springer, New York, 139–167, (1989). |
| [33] | M. Gary and D. Johnson,Computers and Intractability [Russian translation], Mir, Moscow (1982). |
| [34] | G. Grätzer,General Lattice Theory, Birkhäuser Verlag, Basel-Stuttgart (1978). |
| [35] | A. Guénoche, ”Construction du treillis de Galois d’une relation binaire,”Math. Inf. Sci. Hum., No. 109, 41–53 (1990). · Zbl 0707.06003 |
| [36] | S. M. Gusakova, ”Canonical representation of similarity,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 9, 19–22 (1987). |
| [37] | S. M. Gusakova and V. K. Finn, ”On formalization of local and global similarity,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 6, 16–19 (1986). |
| [38] | S. M. Gusakova and V. K. Finn, ”On new means of formalization of the notion of similarity,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 10, 14–22 (1987). |
| [39] | R. K. Guy, ”A problem of Zarankiewicz,” In:Theory of Graphs, (G. Katona, ed.) Akad. Kiado, Budapest, 119–150 (1968). |
| [40] | R. K. Guy and Š. Znám, ”A problem of Zarankiewicz,”Recent Progr. Combinator., New York-London, 237–243, (1969). |
| [41] | R. M. Haralick, ”The diclique representation and decomposition of binary relations,”J. ACM,21, 356–366 (1974). · Zbl 0293.94020 · doi:10.1145/321832.321834 |
| [42] | S. Hartman, J. Mycielski, and C. Ryll-Nardzewski, ”Système speciaux de points a coordonnees entieres,”Coll. Math.,3, No. 1, 84–85 (1954). |
| [43] | C. Hylten-Cavallius, ”On a combinatorial problem,”Colloq. Math.,6, 59–65 (1958). · Zbl 0086.01202 |
| [44] | U. Kipke and R. Wille, ”Begriffsverbände als Ablaufschemata zur Gegenstandsbestimmung,” In:Die Klassifikation und ihr Umfeld (P. O. Degens, H.-J. Hermes, and O. Opitz, eds.), Indeks-Verlag, Frankfurt, 164–170, (1986). |
| [45] | T. Kovari, V. Sós, and P. Turan, ”On a problem of K. Zarankiewicz,”Colloq. Math.,3, No. 1, 50–57 (1954). |
| [46] | S. O. Kuznetsov, ”Interpretation on graphs and complexity characteristics of a search for specific patterns,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.) No. 1, 23–27 (1989). · Zbl 0737.68065 |
| [47] | S. O. Kuznetsov, ”Introduction to the JSM-method,”Semiotika i Informatika, No. 31, 5–40 (1990). |
| [48] | S. O. Kuznetsov, ”Stability as an estimate of the degree of substantiation of hypotheses derived on the basis of operational similarity,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.) No. 12, 21–29 (1990). · Zbl 0737.68069 |
| [49] | S. O. Kuznetsov, ”JSM-method as a system of machine learning,”Itogi Nauki i Tekhniki, Seriya Informatika,15, 17–54 (1991). |
| [50] | S. O. Kuznetsov, ”Complexity of learning and classification based on a search for set intersection,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.) No. 5, 1–11 (1991). |
| [51] | S. O. Kuznetsov, ”Fast algorithm for construction of all intersections of the objects from a finite semilattice,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist) No. 9, 11–21 (1993). |
| [52] | S. O. Kuznetsov, Algorithmic complexity of the generation of hypotheses and classification based on the search for set intersectionDoklady Akad. Nauk,335, No. 3, 300–303, (1994). (Physics-Doklady,39, 142–145 (1994)). |
| [53] | V. E. Levit, ”Algorithm of search for a submatrix of maximal perimeter that consists of units for the case of 0–1 matrix,”Systems of transmitting and processing of information, Collection of papers of IPPI of Soviet Acad. Sci., 42–45, (1988). |
| [54] | P. Luksch, Skorsky M., and R. Wille, ”On drawing concept lattices with a computer,” In:Classification as a Tool of Research (W. Gaul, and M. Schader, eds.), Elsevier, 269–274, (1986). |
| [55] | P. Luksch and R. Wille, ”Substitution decomposition of concept lattices,” In:Contributions to General Algebra 5 (J. Czermak, G. Eigenthaler, H. K. Kaiser, and W. B. Müller, W. Nobauer, eds.), Holder-Pichler-Tempsky, Wien, 213–220, (1987). · Zbl 0639.06005 |
| [56] | P. Luksch and R. Wille, ”Formal concept analysis of paired comparisons,” In:Classification and Related Methods of Data Analysis (H. H. Bock, ed.), North-Holland, Amsterdam, 567–576 (1988). |
| [57] | P. Luksch and R. Wille, ”A mathematical model for conceptual knowledge systems,” In:Classification, Data Analysis, and Knowledge Organization (H. H. Bock and P. Ihm, eds.), Springer, Heidelberg, 156–162, (1990). |
| [58] | M. Luxenburger, ”Implications partielles dans un contexte,”Math. Inf. Sci. Hum.,29, No. 113, 35–55 (1991). · Zbl 0751.06006 |
| [59] | R. S. Michalski and R. E. Stepp, ”Learning from observation: conceptual clustering,”Machine Learning: an Artificial Intelligence Approach (R. S. Michalski, J. G. Carbonell, and T. M. Mitchell, eds.), Tioga, Palo Alto, California, 41–81, (1983). |
| [60] | M. Mörs, ”A new result on the problem of Zarankiewicz,”J. Comb. Theory, Ser. A,31, No. 2, 126–130 (1981). · Zbl 0472.05018 · doi:10.1016/0097-3165(81)90008-X |
| [61] | E. M. Norris, ”An algorithm for computing the maximal rectangles in a binary relation,”Rev. Roum. de Math. Pures Appliquées,23, No. 2, 243–250 (1978). · Zbl 0389.05003 |
| [62] | M. Novotný and Z. Pawlak, ”Black box analysis and rough top equality,”Bull. Acad. Sci. Math.,33, Nos. 1–2, 105–113 (1985). · Zbl 0569.68045 |
| [63] | M. Novotný and Z. Pawlak, ”Concept forming and black boxes,”Bull. Acad. Sci. Math.,35, Nos. 1–2, 133–141 (1987). · Zbl 0639.06001 |
| [64] | M. Novotný and Z. Pawlak, ”Algebraic theory of independence in information systems,”Fundamenta Informaticae,14, No. 4, 454–476 (1991). · Zbl 0727.68118 |
| [65] | P. Pudlak and F. Springsteel, ”Complexity in mechanized hypothesis formation,”Theor. Comp. Sci.,8, No. 2, 203–225 (1979). · Zbl 0404.68097 · doi:10.1016/0304-3975(79)90045-8 |
| [66] | I. Reiman, ”Über ein Problem von K. Zarankiewicz,”Acta Math. Acad. Sci. Hungar.,9, 269–273 (1958). · Zbl 0084.01303 · doi:10.1007/BF02020254 |
| [67] | K. Reuter and R. Wille, ”Complete congruence relations of concept lattices,”Acta Sci. Math.,51, Nos. 3–4, 319–327 (1987). · Zbl 0668.06005 |
| [68] | S. Roman, ”A problem of Zarankiewicz,”J. Comb. Th. (A),18, No. 2, 187–198 (1975). · Zbl 0296.05014 · doi:10.1016/0097-3165(75)90007-2 |
| [69] | J. Schmidt, ”Zur Kennzeichnung der Dedekind-MacNeilleschen Hülle einer geordneten Menge,”Arch. Math.,7, No. 4, 241–249 (1956). · Zbl 0073.03801 · doi:10.1007/BF01900297 |
| [70] | M. Skorsky, ”How to draw a concept lattice with parallelograms,” In:Klassifikation und Ordnung (R. Wille, ed.), INDEKS-Verlag, Frankfurt, 191–196 (1989). |
| [71] | F. Springsteel, ”Complexity of hypothesis formation problems,”Int. J. Man-Mach. Studies,15, 319–332 (1981). · doi:10.1016/S0020-7373(81)80015-6 |
| [72] | J. Stahl and R. Wille, ”Preconcepts and set representation of contexts,” In:Classification as a Tool of Research, (W. Gaul and M. Schader, eds.), Elsevier, 431–438, (1986). · Zbl 0608.68075 |
| [73] | L. G. Valiant, ”The complexity of computing the permanent,”Theoretical Computer Science,8, No. 2, 189–201 (1979). · Zbl 0415.68008 · doi:10.1016/0304-3975(79)90044-6 |
| [74] | L. G. Valiant, ”The complexity of enumeration and reliability problems,”SIAM J. Comput.,8, No. 3, 410–421 (1979). · Zbl 0419.68082 · doi:10.1137/0208032 |
| [75] | F. Vogt, C. Wachter, and R. Wille, ”Data analysis based on a conceptual file,” In:Classification, Data Analysis, and Knowledge Organization (H. H. Bock and P. Ihm, eds.), Springer, Heidelberg, 131–142, (1990). · Zbl 0727.62007 |
| [76] | M. Wild, ”Implicational bases for finite closure systems,” In:Arbeitstagung, Begriffsanalyse und Künstliche Intelligenz (W. Lex, ed.), 147–169, (1991). |
| [77] | R. Wille, ”Subdirekte Produkte und konjunkte Summen,”J. reine angew. Math.,239/240, 333–338 (1970). · Zbl 0221.08005 |
| [78] | R. Wille, ”Subdirekte Produkte vollständiger Verbände,”J. reine angew. Math.,283/284, 53–70 (1976). · Zbl 0336.06007 · doi:10.1515/crll.1976.283-284.53 |
| [79] | R. Wille, ”Restructuring lattice theory: an approach based on hierarchies of concepts,” In:Ordered Sets (I. Rival, ed.), Reidel, Dordrecht-Boston, 445–470, (1982). |
| [80] | R. Wille, Subdirect decomposition of concept lattices,Algebra Universalis,17, No. 3, 275–287 (1983). · Zbl 0539.06006 · doi:10.1007/BF01194537 |
| [81] | R. Wille, ”Liniendiagramme hierarchischer Begriffssysteme,” In:Anwendungen der Klassifikation: Datenanalyse und Numerische Klassifikation, (H. H. Bock, ed.), INDEKS-Verlag, Frankfurt, 32–51, (1984). |
| [82] | R. Wille, ”Sur la fusion des contexts individuels,”Math. Sci. Hum.,85, 57–71 (1984). · Zbl 0571.06008 |
| [83] | R. Wille, ”Tensorial decomposition of concept lattices,”Order,2, 81–95 (1985). · Zbl 0583.06007 · doi:10.1007/BF00337926 |
| [84] | R. Wille, ”Finite distributive lattices as concept lattices,”Atti Inc. Logica Matematica (Siena),2, 635–648 (1985). · Zbl 0577.06012 |
| [85] | R. Wille, ”Complete tolerance relations of concept lattices,” In:Contributions to General Algebra Proceedings of a Conference, June 21–24, 1984, (B. G. Teubner, ed.), 397–415, (1985). |
| [86] | R. Wille, ”Bedeutungen von Begriffsverbänden,” In:Beiträge zur Begriffsanalyse (B. Ganter, R. Wille, and K. E. Wolff, eds.), B.I.-Wissenschaftsverlag, Mannheim, 161–211, (1987). |
| [87] | R. Wille, ”Subdirect product construction of concept lattices,”Discr. Math.,63, 305–313 (1987). · Zbl 0621.06004 · doi:10.1016/0012-365X(87)90019-7 |
| [88] | R. Wille, ”Dependences between many-valued attributes,” In:Classification and Related Methods of Data Analysis (H. H. Bock, ed.), North-Holland, Amsterdam, 581–586, (1988). |
| [89] | R. Wille, ”Geometric representation of concept lattices,” In:Conceptual and Numerical Analysis of Data (O. Opitz, ed.), Springer, Heidelberg, 239–255, (1989). |
| [90] | R. Wille, ”Knowledge acquisition by methods of formal concept analysis,” In:Data Analysis, Learning Symbolic and Numeric Knowledge (E. Diday, ed.), Nova Sci. Publ., New York-Budapest, 365–380, (1989). |
| [91] | R. Wille, ”Lattices in data analysis: how to draw them with a computer,” In:Algorithms and Order (I. Rival, ed.) Kluwer, Dordrecht-Boston, 33–58, (1989). · Zbl 1261.68140 |
| [92] | R. Wille, ”The skeletons of free distributive lattices,”Discr. Math.,88, Nos. 2–3, 309–320 (1991). · Zbl 0739.06007 · doi:10.1016/0012-365X(91)90017-V |
| [93] | R. Wille, ”Concept lattices and conceptual knowledge systems,”Comput. Math. Appl.,23, No. 6-9, 493–515 (1992). · Zbl 0766.68129 · doi:10.1016/0898-1221(92)90120-7 |
| [94] | M. I. Zabezhailo, ”On some exhaustive search problems that arise in automatic generation of hypotheses by the JSM-method,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 1, 28–31 (1988). |
| [95] | M. I. Zabezhailo, V. G. Ivashko, S. O. Kuznetsov, M. A. Mikheenkova, K. P. Khazanovskii, and O. M. Anshakov, ”Algorithmic and program means of the JSM-method of automatic hypothesis generation,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 10, 1–14 (1987). |
| [96] | M. I. Zabezhailo, ”To the problem of the extension of the JSM-method of automatic hypothesis generation to data with numeric parameters,”Nauchn. Tekh. Inf., Ser. 2 (Automat. Document. Math. Linguist.), No. 11, 11–21 (1992). |
| [97] | K. Zarankiewicz, ”Problem P101,”Colloq. Math.,2, 301 (1951). |
| [98] | S. Znám, ”On a combinatorial problem of K. Zarankiewicz,”Colloq. Math.,11, No. 1, 81–84 (1963) · Zbl 0116.01201 |
| [99] | Š. Znám, ”Two improvements of a result concerning a problem of K. Zarankiewicz,”Colloq. Math.,13, No. 2, 255–258 (1965). · Zbl 0149.02001 |
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.
