Introduction to Formal Concept Analysis
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.
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.
Computing the canonical basis4:05
An example5:51
Complexity issues8:53
Sergei Obiedkov
Let's see how this algorithm works on this simple example.
This is a formal context for attributes a, b, c, d, and
has four options, let's compute its canonical basis, L.
So initially L is going to be empty, and
our algorithm starts with an empty set A.
And then it enumerates all other pre-closed set,
well A itself is pre-closed, why?
The empty set is always pre-closed, it's either closed or pseudo-closed.
If a set is not closed, then what can go wrong for it not to be pseudo closed?
It must contain a pseudo closed proper subset but
empty set has no proper subsets.
So empty set is always pseudo-closed even if it's not closed and
in any case, it is always pre-closed.
So we start with an empty set and we compute its closure, A''.
In this case, it's empty set again so
next closure returns of the next pre-closed set.
The next pre-closed set in this case is {d}, now what's the closure of {d}?
Let's look at the objects that have d, it's this one and this one,
and they have nothing more in common.
So the closure of {d} is {d} again, okay,
the next pre-closed set is {c}, and it's also closed.
Then we have {c,d} Okay,
and now there's only one object that has both c and d, it's the first object and
it also has a, so the closure of {c,d} is {a,c,d}.
And so we add the first implication
to our basis, cd implies a.
Or I could write cd implies acd, but it's the same.
So cd implies a.
That's our first implication.
Let's continue.
The logical next set after cd is b.
But it is closed, so nothing interesting here.
The next set is {b,d} and it's closed again.
{b,c} is also closed.
And then we would normally consider bcd or
I mean bcd is dialectical next set after bc.
But this set is no longer pre-closed because it's not closed under our
current set of implications L.
The pre-closure of bcd is its closure under L, and this includes a.
So it's a, b, c, d.
So the cd is pre-closed, and the next closure would not return it as the next
pre-closed set, it would ignore it.
So we're not going to see it in our algorithm computing the canonical basis.
And thus the next set is going to be a.
Now the closure of a in this context is ac.
We have two objects that have a and they both have c.
And this gives us the second implication, a implies c.
Let's continue, then we have ad but ad is not pre-closed.
The pre-closure of ad is acd, so when I'm going to see ad, what else then ac.
And ac is closed.
Then acd.
And it is closed again.
Then we will have ab, but next closure will compute the pre-closure of ab.
So the closure under L, the closure of ab under L is abc,
because of this implication.
A implies b.
So the next set is the next pre-closed set, pre-closed set, is abc.
What's the closure of abc?
Well, there is no option that has all attributes from this set.
All the three attributes, a, b, and c.
And therefore the closure of a, b,
c is the set of all attributes, a, b, c, and d.
And this gives us the third implication,
a, b, c implies d.
Okay and then next set is a, b, c,
d which is equal to M so the algorithm stops.
And this is the basis, the canonical implication basis of this formal context.
If you want to,
you can manual check that all these three sets are indeed pseudo closed.