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.
Attribute exploration of pairs of squares
Loading...
Del curso dictado por National Research University Higher School of Economics
Introduction to Formal Concept Analysis
18 calificaciones
National Research University Higher School of Economics
18 calificaciones
De la lección
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.
Conoce a los instructores
Sergei ObiedkovAssociate Professor
Faculty of computer science
[SOUND] In this formal context,
objects are pairs of
squares of the same size.
And attributes describe how these squares allocated with respect to each other.
So there may be disjoint like these two.
Or they may overlap.
So they may have an interior point, a common interior point like these two.
Or they may have a common vertex.
Or they may be parallel.
Or they may have a common segment.
Or even a common edge, like this too.
Or maybe they don't have any of these properties.
So the first pair of squares they share a point.
But this is not an interior point, so they don't overlap.
And it's not a common vertex, so they don't have this attribute either.
The last line, the last row of this formal context is
two squares which are exactly in the same position.
So they overlap, they're parallel,
they have a common vertex, a common segment and a common edge.
And this is the concept lattice of this formal context.
The question is whether this concept lattice reflects all possible
combinations of.
Pairs of squares with respect to these six attributes.
And attribute exploration is going to help us answer this question.
So we will go through the implications of this formal context and
check if they're valid in general.
If they are valid in the context of all possible pairs of grass of the same size.
Okay, so, in attribute exploration we have to deal with two.
Well, actually with three closure operators.
The first closure operator is the closure
under the implications we have already computed.
So our initial set of implication is empty, but it will change with time.
So the first closure operator is alpha.
The second closure operator is the closure operator in this formal context.
Let's say, let's denote it by J.
JJ.
The third closure operator is the closure operator in the entire context,
in the context of all pairs of squares.
We denote it by II.
And so the question that our
expert is going to answer
is whether A JJ = A II.
Or in other words whether A implies A JJ.
All right, so the algorithm starts with an empty set.
The closure of the empty set on the L is also empty, because L is empty.
So we have to check if the empty set is closed in this formal context, and it is.
So it makes no sense to ask if empty set implies empty set, set or
of course it does.
We go, we compute the electrical next close set after the empty set.
And this going to be the single element set, common edge.
Now the L for ce is also ce because L is empty and
the closure of ce, well let's look at
the objects that have these attributes ce.
There are only two such objects, and they have in common p a, c v, c s, and c e.
So A JJ equals pa,
cv, cs, ce.
And at this point, we ask the oracle, or we ask the expert,
whether ce indeed implies pa, cv, and cs.
This implication holds in our context, but let's check if it holds in general.
Well what this implication is saying is that,
if two squares have a common edge, then they must also have a common segment.
Well yes of course, because a segment is part of an edge.
If they have a common edge, they must have a common segment.
They must also have a common vertex, sure, and they must be parallel.
This is true indeed, so the expert answers yes.
And we add the implication ce implies pa,
cv, and cs to all set of implications L.
And we go to the next set, the next closed set.
The next set closed under L.
This is going to be cs.
Now the closer of cs on the L(A) is cs.
The closer of cs in the context is, let's look at the object that has cs.
We have three such objects and they share also the attribute parallel.
So the closure is pa, cs.
And now, we have to check the implication that's cs implies pa,
that is if two squares have a common segment then they must be parallel.
And this holds if two squares are not parallel,
they cannot have a common segment.
So the expert answer is yes and we'll add another implications cs implies pa.
Well, what happens next is that we.
To the net closed set after cs.
This is cs, ce.
But now this set is not really closed under the set of implications L.
because it contains ce but it doesn't contain pa.
So L(A) would contain pa and some other attributes but
pa is electrically preceding ce.
And for this reason the next closure algorithm that we use to compute
volactical and next close set on the cs would reject the set cs, ce.
So we don't continue this line.
And the next closure will give us the next set which is common vertex, cv.
Okay, so cv is closed on the L.
The close of cv in our context is also cv, because there's one pair of
squares that has exactly this attribute and nothing else.
Right, so there's nothing to verify here.
No implication to ask the expert.
The next set is going to be cv, ce.
But again, when the same situation as here.
The closure of cv,ce on the accepted implications,
contains the pa and zone exclosure will ignore this set.
The same thing happens with cv,cs it also,
it's closure on the L also contains pa and so
the next set, we're going to consider in our
attribute exploration algorithm is pa.
This is the set returned by next quarter.
And this set, well it turns out to be closed
in our context because we have these two objects.
They both have attribute parallel but they don't share any other attribute.
So pa is closed, again, no implication here.
Well from now on I will skip sets like this one, this one and
this one, those that are rejected by the next closure algorithm.
I will be writing down here only sets that are close on their or
current implications at L.
These are the sets that return by next closure and they are.
Always either intense or intense of our current subcontext.
If the intense were not doing anything,
we just go to the next intent or see you intent.
And if the next closure is intent then we have to verify
the implication where this intent is the premise with our expert.
That's what we're doing here.
Okay, so the next set
is going to be pa, cv.
And pa, cv is closed because of this object.
So nothing to verify.
Next, pa, cv, cs,
We don't consider pa, cv, ce because it will be rejected by our next closure.
L of this set would contain cs and so we won't see it.
So pa, cv, cs, what's the cause of pa, cv, cs?
There are two object that have it and they also share the common edge.
So here we have pa,
cv, cs and ce.
And now we'll ask the expert whether two squares that are parallel,
have a common vertex, and have a common segment also have a common edge.
Well, if this common segment starts in a common vertex, because the squares
are of the same size the common segment should in fact be an edge.
So here the answer is yes.
And we have another third implication,
pa, cv, cs, implies ce.
Okay, then the next set.
The next closed set is the pa, cv, cs, ce.
But it's closed not only under L it's also closed on the context.
This is precisely the intent of this object.
So that's the closure.
Nothing to check here.
So let's go to the next set which is ov and it is also closed.
Okay, the next one is ovcv.
And the quality of ovcv is the intent of the last object.
Because this is the only object that has both attributes.
So here we have ov, pa, cv,
cs, and ce.
Now we have to ask the expert if it's true that
whenever we have square that overlap and share vertex,
they must also be parallel, have a common segment, and a common edge.
Well, here the answer is no and expert gives us a counter example.
So two squares that overlap share a vertex but
are different with respect to all the properties.
So let's say this is one square and
the second square is like this.
So these two squares overlap and they have a common vertex.
But they're not parallel, they don't have a common segment and
they don't share an edge.
This is a counter example and we'll add it to our formal context so
then on this joint, they overlap.
Then, parallel data have a common vertex,
they do have a common vertex, and that's it.
Now, common segment and now common edge.
Before we continue, let's erase what we have here but
let's keep in mind the implications we have already accepted.
Okay, so the next set will be ov, pa,
cs and it's
closure in the context is,
once again the intent of the last of this object.
It's no longer the last object, the one before the last.
So its, the closure is,
ov, pa, cv, cs, ce.
And now, we'll ask the oracle if it's true that whenever we have
two squares that overlap parallel.
And have a common segment, they must also have a common vertex and a common edge.
And again the answer is no because
this is a counter example, so it just has two squares that are parallel.
They have common segments.
They overlap but they don't have a common nature, they don't have a common verdict.
So this is one square and this is the other square.
So we'll add this to our formal context.
So, these two squares overlap,
they're parallel, but that's it.
They don't have a common vertex, they don't have a common segment, and
they don't have a common edge.
Let's continue.
So the next set we'll have to consider is ov, pa, cv.
The closure of ov, pa, cv includes cs and ce, ov, pa, cv, cs, ce.
And we ask the expert if it's true that one two squares overlap,
are parallel, have a common vertex,
they must also have a common edge and a common segment.
And in this case, this is so.
So it's yes.
And we accept, we add a new implication.
ov, pa, cv implies cs and ce.
Common segment and common edge.
Okay, so next, the next interesting set
is going to be di, disjoint, and it's closed.
In our context, then disjoint and common vertex.
Well, we don't have any object in our case,
in our context that has these to attributes,
that's because it's not possible to be disjoint and still had a common vertex.
So the closure of di, cv is M, were off the oracle if this is so, and this is so.
So add this implication di,
cv implies M Next,
the the next set closed under implications from L is di, pa.
The closure of di and pa is just di, pa.
We'll have this object.
Nothing to ask here,
then di, pa, cs.
And the closure of di, pa, cs is again, the set of all attributes M.
And indeed, it's not possible to disjoint and have a common segment.
So this gives us a valid implication di,
pa, cs implies m.
Next, di, ov, yeah,
that's it, di, ov.
Well, again, the closure is M.
And indeed, it's not possible for two stress to be at the same time,
disjoint and nevertheless, overlap.
So we add implication the di, ov, implies M.
And that's it.
So the next closed set is going to be M, and we're finished at this point.
So, what have we done?
We have computed the canonical basis which includes one,
two, three, four, five, six, seven implications.
And this is the canonical basis of this relatively small context.
But it's also the canonical basis of the context of all possible pairs of
squares with respect to these six properties.
We have also added two counter examples to implications
that were valid in a small context in our initial context.
This means that the constant players has also changed.
This object which overlaps parallel, it must go here.
So well, it doesn't have it.
Overlap, common segment and parallel.
Okay, it looks like I forgot to put a cross here.
Okay, now, this is the constant players of all possible
pairs of squares in terms of how they kind of located to each other.
Well, of course, we don't have all possible pairs of squares as labels, but
the structure of the constant players will remain the same
even if we add any other pair of squares.
Every other pair of squares will have a place in this lattice.
We'll have a node where it fits absolutely.
[MUSIC]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
