Introduction to Formal Concept Analysis
National Research University Higher School of Economics
课程信息
This course is an introduction into formal concept analysis (FCA), a mathematical theory oriented at applications in knowledge representation, knowledge acquisition, data analysis and visualization. It provides tools for understanding the data by representing it as a hierarchy of concepts or, more exactly, a concept lattice. FCA can help in processing a wide class of data types providing a framework in which various data analysis and knowledge acquisition techniques can be formulated. In this course, we focus on some of these techniques, as well as cover the theoretical foundations and algorithmic issues of FCA.
Upon completion of the course, the students will be able to use the mathematical techniques and computational tools of formal concept analysis in their own research projects involving data processing. Among other things, the students will learn about FCA-based approaches to clustering and dependency mining.
The course is self-contained, although basic knowledge of elementary set theory, propositional logic, and probability theory would help.
End-of-the-week quizzes include easy questions aimed at checking basic understanding of the topic, as well as more advanced problems that may require some effort to be solved.
Syllabus - What you will learn from this course
1
Section
Formal concept analysis in a nutshell
This week we will learn the basic notions of formal concept analysis (FCA). We'll talk about some of its typical applications, such as conceptual clustering and search for implicational dependencies in data. We'll see a few examples of concept lattices and learn how to interpret them. The simplest data structure in formal concept analysis is the formal context. It is used to describe objects in terms of attributes they have. Derivation operators in a formal context link together object and attribute subsets; they are used to define formal concepts. They also give rise to closure operators, and we'll talk about what these are, too. We'll have a look at software called Concept Explorer, which is good for basic processing of formal contexts. We'll also talk a little bit about many-valued contexts, where attributes may have many values. Conceptual scaling is used to transform many-valued contexts into "standard", one-valued, formal contexts.
14 videos (Total 66 min), 1 reading, 2 quizzes
14 videos
What is formal concept analysis?4m
Understanding the concept lattice diagram2m
Reading concepts from the lattice diagram4m
Reading implications from the lattice diagram5m
Conceptual clustering6m
Formal contexts and derivation operators8m
Formal concepts2m
Closure operators9m
Closure systems2m
Software: Concept Explorer7m
Many-valued contexts4m
Conceptual scaling schemas3m
Scaling ordinal data3m
1 readings
Further reading10m
2 practice exercises
Reading concept lattice diagrams0m
Formal concepts and closure operators0m
2
Section
Concept lattices and their line diagrams
This week we'll talk about some mathematical properties of concepts. We'll define a partial order on formal concepts, that of "being less general". Ordered in this way, the concepts of a formal concept constitute a special mathematical structure, a complete lattice. We'll learn what these are, and we'll see, through the basic theorem on concept lattices, that any complete lattice can, in a certain sense, be modelled by a formal context. We'll also discuss how a formal context can be simplified without loosing the structure of its concept lattice.
8 videos (Total 98 min), 3 quizzes
8 videos
Supremum and infimum15m
Lattices9m
The basic theorem (I)11m
The basic theorem (II)12m
Line diagrams13m
Context clarification and reduction12m
Context reduction: an example11m
3 practice exercises
Supremum and infimum30m
Lattices and complete lattices0m
Clarification and reduction0m
3
Section
Constructing concept lattices
We will consider a few algorithms that build the concept lattice of a formal context: a couple of naive approaches, which are easy to use if one wants to build the concept lattice of a small context; a more sophisticated approach, which enumerates concepts in a specific order; and an incremental strategy, which can be used to update the concept lattice when a new object is added to the context. We will also give a formal definition of implications, and we'll see how an implication can logically follow from a set of other implications.
13 videos (Total 121 min), 3 quizzes
13 videos
Drawing a concept lattice diagram4m
A naive algorithm for enumerating closed sets2m
Representing sets by bit vectors4m
Closures in lectic order10m
Next Closure through an example10m
The complexity of the algorithm13m
Basic incremental strategy14m
An example10m
The definition of implications10m
Examples of attribute implications7m
Implication inference12m
Computing the closure under implications7m
3 practice exercises
Transposed context30m
Closures in lectic order0m
Implications0m
4
Section
Implications
This week we'll continue talking about implications. We'll see that implication sets can be redundant, and we'll learn to summarise all valid implications of a formal context by its canonical (Duquenne–Guigues) basis. We'll study one concrete algorithm that computes the canonical basis, which turns out to be a modification of the Next Closure algorithm from the previous week. We'll also talk about what is known in database theory as functional dependencies, and we'll show how they are related to implications.
9 videos (Total 67 min), 3 quizzes
9 videos
Pseudo-closed sets and canonical basis12m
Preclosed sets8m
Preclosure operator6m
Computing the canonical basis4m
An example5m
Complexity issues8m
Functional dependencies8m
Translation between functional dependencies and implications5m
3 practice exercises
Implications and pseudo-intents0m
Canonical basis0m
Functional dependencies0m
5
Section
Interactive algorithms for learning implications
What if we don't have a direct access to a formal context, but still want to compute its concept lattice and its implicational theory? This can be done if there is a domain expert (or an oracle) willing to answer our queries about the domain. We'll study an approach known as learning with queries that addresses this setting. We'll get to know a few standard types of queries, and we'll see how an implication set can be learnt in time polynomial of its size with so called membership and equivalence queries. We'll then introduce attribute exploration, a method from formal concept analysis, which may require exponential time, but which uses different queries, more suitable for building implicational theories and representative samples of subject domains.
14 videos (Total 110 min), 3 quizzes
14 videos
Learning binary patterns2m
An easy case7m
The general case8m
Learning implications with queries12m
Membership and equivalence queries for implications16m
A polynomial-time algorithm5m
Learning domain implications with queries4m
Attribute exploration algorithm5m
Attribute exploration of pairs of squares21m
Object exploration4m
Variations of attribute exploration3m
Incompletely specified examples5m
Completing incomplete contexts5m
3 practice exercises
Learning with queries0m
Learning implications with membership and equivalence queries0m
Attribute exploration0m
6
Section
Working with real data
A concept lattice can be exponentially large in the size of its formal context. Sometimes this can be due to noise in data. We'll study a few heuristics to filter out noisy concepts or select the most interesting concepts in a large lattice built from real data: stability and separation indices, concept probability, iceberg lattices. We will also talk about association rules, which is a name for implications that are supported by strong evidence, but may still have counterexamples in data.
11 videos (Total 89 min), 2 quizzes
11 videos
Iceberg lattices5m
Concept stability10m
Separation index7m
Concept probability8m
Nested line diagrams4m
Association rules7m
Support and confidence7m
Frequent closed sets12m
Luxenburger basis17m
Goodbye!1m
2 practice exercises
Concept indices0m
Association rules20m
4.8
83%
Top Reviews
By SG•Jan 25th 2018
The last probability excercise was tough, but worth it.\n\nGo ahead!!
Instructor
Sergei Obiedkov
Associate ProfessorAbout National Research University Higher School of Economics
National Research University - Higher School of Economics (HSE) is one of the top research universities in Russia. Established in 1992 to promote new research and teaching in economics and related disciplines, it now offers programs at all levels of university education across an extraordinary range of fields of study including business, sociology, cultural studies, philosophy, political science, international relations, law, Asian studies, media and communications, IT, mathematics, engineering, and more.
Learn more on www.hse.ru
Frequently Asked Questions
When will I have access to the lectures and assignments?
Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.
What will I get if I pay for this course?
If you pay for this course, you will have access to all of the features and content you need to earn a Course Certificate. If you complete the course successfully, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. Note that the Course Certificate does not represent official academic credit from the partner institution offering the course.
What is the refund policy?
Is financial aid available?
Yes! Coursera provides financial aid to learners who would like to complete a course but cannot afford the course fee. To apply for aid, select "Learn more and apply" in the Financial Aid section below the "Enroll" button. You'll be prompted to complete a simple application; no other paperwork is required.
More questions? Visit the Learner Help Center
