Online Java Lattice Building Application

Online Java Lattice Building Application
Formal Concept Analysis

Help | FCA | SIMuLLDA | Examples | Create

Formal Concept Analysis

Formal Concept Analysis (henceforth FCA) was developed by Ganter and Wille in Darmstadt (Ganter & Wille, 1996). It is an attempt to give a formal definition of the notion of a 'concept', within the boundaries of a model-theoretic framework.

Usually, research on concepts starts with an intuitive notion of existing, everyday concepts, and then tries to find characterisations of the objects belonging to that concept, for instance in terms of necessary and sufficient conditions. FCA takes a different stance, and tries to give a formal notion of the nature of concepts, independent of any particular concepts.

FCA is a logical framework, which can be explained entirely in terms of abstract formulas, without any reference to the intuitions behind it. However, there is a very clear and simple intuition behind it, and with this intuition, FCA is not only a very elegant, but also a very natural way of defining concepts in a world model. Therefore, I will here try to explain the system in a very hands-on manner, using a very simple toy model.

Figure 1. Toy Model

Imagine that we have a 'world' consisting of only 9 objects. These objects themselves are also extremely simple: they only have a colour and a basic form. The objects of this toy model are represented in the picture, where the objects are numbered from 1-9.

Despite its simplicity and the relative randomness of the model, the objects in this toy model can be divided into naturally occurring classes. For instance, the objects 5 and 6 naturally belong together, and they do so for a very simple reason: they are (all) the objects that are both grey and square at the same time; they constitute the set of grey squares. It is very natural to view this grey-squaredness as a concept, and it is this notion of a concept that FCA tries to formalise.

If this is our notion of a concept, then concepts appear in every model, even in a simple and arbitrary model such as the one in figure 1. Concepts are related to sets of object (2 and 5) and attributes (grey and square), but they are more than just arbitrary sets: 2 and 3 do not naturally form a concept together, for although they are both round, they do not form the set of rounds, since 1 is not included. Also, concepts exist independent of our conceptualisation, and are independent of the kinds of objects and attributes involved.

So we can abstract away from the actual objects in the toy model, and represents the things as well as their attributes as abstract entities. If the objects are represented with the number {1 ... 9} and the attributes (or features) that these objects have (round, square, triangular, white, grey, and black) with the two letter names in {ro, sq, tr, wh, gr, bl}, we can represent the toy model in figure 1 by table 1.

Table 1. Tabular Representation of the Toy Model
	ro	sq	tr	wh	gr	bl
1	x				x
2	x			x
3	x					x
4		x				x
5		x			x
6		x			x
7			x	x
8			x	x
9			x	x

Within this abstract representation, we can say that the objects of the set {5,6} naturally belong together, because they share the attributes in the set {sq, gr}. This can be stated more precisely by saying that the pair <{5,6}, {sq, gr}> constitutes what we call a formal concept (for which 'grey squares' is a useful, though arbitrary name), because all the objects in the set on the left of the pair have all the attributes in the right-hand set and conversely, all the attributes in the right set are shared by the objects in left set. The idea behind FCA is that concepts are precisely all the pairs of objects and attributes that have such a mutual dependency.

Ganter \& Wille \shortcite{ganter96} capture this idea in a formal logical framework, thus precisely defining the idea stated above. Formally, a context (the world) is defined as a set of objects G (Gegenstände), a set of attributes M (Merkmalen), and a relation I between objects and attributes (I ⊆ G x M), where (g,m) ∈ I should be read as 'object g has attribute m'. We define the set of formal concepts B over a context (G, M, I) in the following way:

B (G,M,I) = { < A,B > | A = B' ∧ B = A' }
B' = { g ∈ G | ∀ b ∈ B. (g,b) ∈ I }
A' = { m ∈ M | ∀ a ∈ A. ∈ I }

So a concept is a pair of a set of objects that have common attributes (the extent), and the defining set of attributes that they have in common (the intent). For convenience, for a concept α = <A, B>, we define two functions ext(α) = A and ext(α) = B. The concept is realized by the objects in its extent, and it is defined by the attributes in its intent.

Given these definition, we can determine the set B(G,M,I) of formal concepts over our toy model. There are 13 concepts in total, listed in table 2.

Table 1. Formal Concepts of the Toy Model
Circles	< {1, 2, 3}, {ro}>
Squares	< {4, 5, 6}, {sq}>
Grey Object	< {1, 5, 6}, {gr}>
White Objects	< {2,7,8,9}, {wh}>
Black Objects	< {3,4}, {bl}>
Grey Circles	< {1}, {gr,ro}>
White Circles	< {2}, {wh,ro}>
Black Circles	< {3}, {bl,ro}>
Grey Squares	< {5, 6}, {gr,sq}>
Black Squares	< {4}, {bl,sq}>
White Triangles	< {7,8,9}, {wh,tr}>
Objects (T)	< {1,2,3,4,5,6,7,8,9}, ∅ >
⊥	< ∅, {ro,sq,tr,gr,wh,bl} >

There are three things that should be noticed about this set of concepts. The first is the presence of the penultimate concept 'Objects'. All the objects in figure 1 are objects, so the extent of this concept is {1,2,3,4,5,6,7,8,9}. If we now ask ourselves which attributes all these objects share, the simple truth is that they share no attributes at all. So the intent of this most general concept contains no attributes at all, otherwise put it is the empty set ∅. That this most general concept, usually called top or T, is a formal concept according to the definition above is easy to see: if there are no attributes, then these non-existing attributes are trivially shared by all the objects, and there is no object that doesn't share one of those non-existing attributes.

The second thing to notice is the last concept in the list, the least general concept, called bottom or ⊥. It is the inverse of the top: it is the concept defined by all the attributes at the same time. But since there are no objects that are (for instance) both black and white at the same time, the extent of this concept will be empty. For the record: there can be objects in the extent of ⊥, if there are objects in the context that have all the available attributes, and there also can be attributes in the intent of top, for instance when we add 'flat' as an attribute to all the objects in the model.

The last thing to notice is the absence of the concept 'Triangle'. The reason why there is no such concept is that all the triangles in our toy model happen to be also white. That means that what we would expect to be the concept 'Triangle': <{7,8,9}, {tr}> is not a formal concept, since the right-hand side does not contain all the attributes shared by the left hand side; the projection {7,8,9}' is {tr,wh}. So within the framework of FCA, we have only the more specific concept 'White Triangle'.

Next: Partial Ordering on Formal Concepts