Attention is paid to two basic outputs of formal concept analysis: (i) concept lattices and (ii) non-redundant sets of attribute implications. For both the outputs, the students are acquainted with theoretical background of concept analysis as well as algorithms for computing concept lattices (hierarchies of clusters) and non-redundant bases of attribute implications (particular dependencies between attributes in the input data). A part of the course is devoted to extensions of formal concept analysis based on multiple-values logics and, in particular, fuzzy logic. 1. Formal context and concept lattice Introduction to the formal concept analysis. Formal context, formal concept, concept lattice. Mathematical structures behind the formal concept analysis: Galois connections and closure operators. main theorem of concept lattice. Multiple-valued contexts, ordinal scaling and factorization of concept lattices. 2. Attribute implications Attribute implications: definition of the notion, attribute implications as formulas of first-order predicate logic, truth (validity) of attribute implications in data. Attribute implications generated from data: complete sets of attribute implications, non-redundant bases of contexts, and minimal bases of contexts. Determining minimal bases using pseudo-intents. Relationship between attribute implications and functional dependencies. 3. Algorithms Algorithms for computing concepts and subconcept-superconcept hierarchies. Non-incremental algorithms (Ganter's algorithm, Lindig's algorithm, Titanic). Complexity analysis of the algorithms. Incremental algorithms. Algorithms for computing minimal bases of contexts. 4. Extension of FCA from the point of view of multiple-valued logics Fuzzy contexts, fuzzy concepts, fuzzy concept lattice. Main theorem of fuzzy concept lattices. Reduction methods: reducing the size of fuzzy concept lattice. Factorization of fuzzy concept lattices by similarity relations. Attribute implications in a fuzzy setting: attribute implications as formulas of fuzzy logics, (graded) truth of attribute implications, semantic entailment and its axiomatization. The problem of minimal bases and their computation. 5. Selected applications of formal concept analysis (information retrieval, softwarové inženýrství, neredundantní báze asociačních pravidel, faktorová analýza).
|
-
Adamo J.-M. (2001). Data Mining for Association Rules and Sequential Patterns. Sequential and Parallel Algorithms. New York.
-
Bělohlávek R. (2002). Fuzzy Relational Systems: Foundations and Principles. NY.
-
Carpineto C., Romano G. (2004). Concept Data Analysis : Theory and Applications.
-
Everitt, B. S. (2001). Cluster Analysis, 4th ed.. Edward Arnold.
-
Ganter B., Wille R. (1999). Formal Concept Analysis. Mathematical Foundations. Berlin.
-
Hand D. J., Mannila H., Smyth P. (2001). Principles of Data Mining.
|