|
Lecturer(s)
|
-
Bělohlávek Radim, prof. RNDr. Ph.D., DSc.
|
|
Course content
|
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).
|
|
Learning activities and teaching methods
|
|
Lecture, Demonstration
|
|
Learning outcomes
|
The students become familiar with basic concepts of formal concept analysis.
2. Comprehension Recognize and understand comprehensively principles and methods of formal concept analysis.
|
|
Prerequisites
|
unspecified
|
|
Assessment methods and criteria
|
Oral exam, Written exam
Active participation in class. Completion of assigned homeworks. Passing the oral (or written) exam.
|
|
Recommended literature
|
-
Adamo J.-M. (2001). Data Mining for Association Rules and Sequential Patterns. Sequential and Parallel Algorithms. Springer, New York.
-
Bělohlávek R. (2002). Fuzzy Relational Systems: Foundations and Principles. NY: Kluwer Academic/Plenum Press (Vol.20 of IFSR Int. Series on Systems Science and Engineering).
-
Carpineto C., Romano G. (2004). Concept Data Analysis : Theory and Applications. John Wiley & Sons.
-
Everitt, B. S. (2001). Cluster Analysis, 4th ed.. Edward Arnold.
-
Ganter B., Wille R. (1999). Formal Concept Analysis. Mathematical Foundations. Springer, Berlin.
-
Hand D. J., Mannila H., Smyth P. (2001). Principles of Data Mining. MIT Press, Cambridge, MA.
|