The partial order on concepts

Loading...

From the course by National Research University Higher School of Economics

Introduction to Formal Concept Analysis

19 ratings

National Research University Higher School of Economics

Introduction to Formal Concept Analysis

19 ratings

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.

From the lesson

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.

The partial order on concepts11:09

Supremum and infimum15:33

Meet the Instructors

Sergei Obiedkov
Associate Professor
Faculty of computer science

[MUSIC]

When we think about concepts in our everyday life,

we know that some concepts can be more general than others.

For example, the concept of mammals is more general than the concept of dogs,

because every dog is a mammal.

So dog is a subconcept of mammal, and mammal is a superconcept of dog.

Let's see how we can transfer this to formal concepts.

So assume that we have two formal

concepts, (A1, B1) and (A2, B2).

So we have (A1, B1) and (A2, B2), and they're two formal concepts

of the same formal context, let’s say, (G, M, I).

We say that (A1,

B1) is a subconcept

of (A2, B2)

if A1 is a subset of A2.

And that's a natural definition.

So, if (A1, B1) is the concept of dogs and (A2, B2) is the concept of mammals,

then, by saying that the first is a subconcept of the second,

what we mean is that all dogs are mammals.

Every dog is a mammal, all dogs are mammals,

all dogs form a subset of all mammals.

And we use the following notation to denote that (A1,

B1) is a subconcept of (A2, B2).

We write (A1, B1) is less than or

equal to (A2, B2), so we use this sign.

So this is a natural definition,

but it looks a little bit strange,

because we completely ignore concept intents.

In this definition, we look only at A1, A2, but we ignore B1 and B2.

So is there any condition that should be put on these two sets,

on the concept intents?

Well, let's check.

So suppose that we have two formal concepts, (A1, B1), (A2,

B2), and the first one is indeed a subconcept of the second one.

So, by definition, we have

that A1 is a subset of A2.

If so, then let’s check B1 and B2.

Now, B1 equals A1', because (A1,

B1) is a formal concept.

So, by definition of the formal concept, B1 is A1'.

And A1' is the set of all attributes

shared by all objects from A1.

Similarly, B2 equals A2', because (A2, B2) is a formal concept,

and A2' is the set of all attributes shared by all objects from A2.

Now, let's look at one attribute from this set, from B2.

So this attribute is shared by all objects from A2.

But the set A1 is a subset of A2,

this means that this attribute is also shared by all objects from A1,

but then this attribute must also be included in the first set,

which is the set of all attributes shared by A1 or, in other words, B1.

We have just proved that every attribute from B2 is part of B1, and

therefore B2 is a subset of B1.

So, if A1 is a subset

of A2, then B2 is

a subset of B1.

Now let's check if the reverse is also true.

Suppose that B2 is a subset of B1.

And let's look at A1 and A2.

Well, A1 is B1', because (A1,

B1) is a formal concept, and

B1' is the set of all objects

that have all attributes from B1.

And, similarly, A2

equals B2',

which is the set of all objects

that have all attributes from B2.

Now, let's look at one object from A1.

This object has all attributes from B1.

But since B1 is a superset of B2,

this object must also have all attributes from B2 and

therefore it must be part of this second set, of A2.

So we’ve just proved that A1 is a subset of A2.

And therefore, this relation holds in both directions.

If B2 a subset of B1, then A1 is a subset of A2.

And therefore, we can reformulate this definition, and

we can say that (A1, B1) is a subconcept

of (A2, B2) if B2

is a subset of B1.

These definitions look different, but they are equivalent to each other.

All right, so we've defined some binary relation,

“being a subconcept of”, on our formal concepts.

Let's look at some properties of this relation.

Well, the first property is reflexivity.

If we take a formal concept (A,B), then, by definition,

it's less than or equal to, or it's a subconcept of, itself.

(A,B) is a subconcept of (A,B).

And indeed, this is because A is a subset of A.

This property is called reflexivity.

The second property

is antisymmetry.

If (A1, B1) is a subconcept

of (A2, B2) and, at the same time,

(A2, B2)

is a subconcept of (A1, B1)…

Well, in this case,

(A1, B1) is just the same as (A2, B2), they are equal.

It's the same formal concept.

Well, why so?

Well, because, if

A1 is a subset of A2 and A2 is a subset of A1,

then A1 and A2 are equal.

On the other hand, if B2 is a subset of B1 and B1 is a subset of B2,

then again, B2 and B1 are equal, and therefore (A1, B1) equals (A2, B2).

The third property

is transitivity.

If (A1, B1) is a subconcept of (A2, B2),

which is a subconcept of

(A3, B3),

in this case, (A1,

B1) must be a subconcept of (A3, B3).

Well, indeed, if A1 is a subset of A2,

which is a subset of A3, then A1 is a subset of A3.

Now, every binary relation that satisfies these three properties,

reflexivity, antisymmetry, and transitivity, is called a partial order.

And so we've just proved that formal concepts are partially

ordered with respect to this relation.

The relation of being a subconcept.

[SOUND]

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play