# Formal concept analysis

### From Wikipedia, the free encyclopedia

**Formal concept analysis** is a principled way of automatically deriving an ontology from a collection of objects and their properties. The term was introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkhoff and others in the 1930's.

## Contents |

## [edit] Intuitive description

Formal concept analysis refers to both an unsupervised machine learning technique and, more broadly, a method of data analysis. The approach takes as input a matrix specifying a set of objects and the properties thereof, called attributes, and finds both all the "natural" clusters of attributes and all the "natural" clusters of objects in the input data, where

- a "natural"
*object*cluster is the set of all objects that share a common subset of attributes, and - a "natural"
*property*cluster is the set of all attributes shared by one of the natural object clusters.

Natural property clusters correspond one-for-one with natural object clusters, and a **concept** is a pair containing both a natural property cluster and its corresponding natural object cluster. The family of these concepts obeys the mathematical axioms defining a lattice, and is called a **concept lattice** (in French this is called a **Treillis de Galois** because the relation between the sets of concepts and attributes is a Galois connection).

Note the strong parallel between "natural" property clusters and definitions in terms of individually necessary and jointly sufficient conditions, on one hand, and between "natural" object clusters and the extensions of such definitions, on the other. Provided the input objects and input concepts provide a complete description of the world (never true in practice, but perhaps a reasonable approximation), then the set of attributes in each concept can be interpreted as a set of singly necessary and jointly sufficient conditions for defining the set of objects in the concept. Conversely, if a set of attributes is *not* identified as a concept in this framework, then those attributes are not singly necessary and jointly sufficient for defining *any* non-empty subset of objects in the world.

## [edit] Example

Consider *O* = {1,2,3,4,5,6,7,8,9,10}, and *A* = {composite,even,odd,prime,square}. The smallest concept including the number 3 is the one with objects {3,5,7}, and attributes {odd,prime}, for 3 has both of those attributes and {3,5,7} is the set of objects having that set of attributes. The largest concept involving the attribute of being square is the one with objects {1,4,9} and attributes {square}, for 1, 4 and 9 are all the square numbers and all three of them have that set of attributes. It can readily be seen that both of these example concepts satisfy the formal definitions below

The full set of concepts for these objects and attributes is shown in the illustration. It includes a concept for each of the original attributes: the composite numbers, square numbers, even numbers, odd numbers, and prime numbers. Additionally it includes concepts for the even composite numbers, composite square numbers (that is, all square numbers except 1), even composite squares, odd squares, odd composite squares, even primes, and odd primes.

## [edit] Contexts and concepts

A *(formal) context* consists of a set of objects *O*, a set of attributes *A*, and an indication of which objects have which attributes. Formally it can be regarded as a bipartite graph *I* ⊆ *O* × *A*.

composite | even | odd | prime | square | |
---|---|---|---|---|---|

1 | √ | √ | |||

2 | √ | √ | |||

3 | √ | √ | |||

4 | √ | √ | √ | ||

5 | √ | √ | |||

6 | √ | √ | |||

7 | √ | √ | |||

8 | √ | √ | |||

9 | √ | √ | √ | ||

10 | √ | √ |

A *(formal) concept* for a context is defined to be a pair (*O*_{i}, *A*_{i}) such that

*O*_{i}⊆*O**A*_{i}⊆*A*- every object in
*O*_{i}has every attribute in*A*_{i} - for every object in
*O*that is not in*O*_{i}, there is an attribute in*A*_{i}that the object does not have - for every attribute in
*A*that is not in*A*_{i}, there is an object in*O*_{i}that does not have that attribute

*O _{i}* is called the

*extent*of the concept,

*A*the

_{i}*intent*.

A context may be described as a table, with the objects corresponding to the rows of the table, the attributes corresponding to the columns of the table, and a Boolean value (in the example represented graphically as a checkmark) in cell (*x*, *y*) whenever object *x* has value *y*:

A concept, in this representation, forms a maximal subarray (not necessarily contiguous) such that all cells within the subarray are checked. For instance, the concept highlighted with a different background color in the example table is the one describing the odd prime numbers, and forms a 3 × 2 subarray in which all cells are checked.^{[1]}

## [edit] Concept lattice of a context

The concepts (*O*_{i}, *A*_{i}) defined above can be partially ordered by inclusion: if (*O*_{i}, *A*_{i}) and (*O*_{j}, *A*_{j}) are concepts, we define a partial order ≤ by saying that (*O*_{i}, *A*_{i}) ≤ (*O*_{j}, *A*_{j}) whenever *O*_{i} ⊆ *O*_{j}. Equivalently, (*O*_{i}, *A*_{i}) ≤ (*O*_{j}, *A*_{j}) whenever *A*_{j} ⊆ *A*_{i}.

Every pair of concepts in this partial order has a unique greatest lower bound (meet). The greatest lower bound of (*O*_{i}, *A*_{i}) and (*O*_{j}, *A*_{j}) is the concept with objects *O*_{i} ∩ *O*_{j}; it has as its attributes the union of *A*_{i}, *A*_{j}, and any additional attributes held by all objects in *O*_{i} ∩ *O*_{j}. Symmetrically, every pair of concepts in this partial order has a unique least upper bound (join). The least upper bound of (*O*_{i}, *A*_{i}) and (*O*_{j}, *A*_{j}) is the concept with attributes *A*_{i} ∩ *A*_{j}; it has as its objects the union of *O*_{i}, *O*_{j}, and any additional objects that have all attributes in *A*_{i} ∩ *A*_{j}.

These meet and join operations satisfy the axioms defining a lattice. In fact, by considering infinite meets and joins, analogously to the binary meets and joins defined above, one sees that this is a complete lattice. Conversely, any finite lattice may be generated as the concept lattice for some context. For, let *L* be a finite lattice, and form a context in which the objects and the attributes both correspond to elements of *L*. In this context, let object *x* have attribute *y* exactly when *x* and *y* are ordered as *x* ≤ *y* in the lattice. Then, the concept lattice of this context is isomorphic to *L* itself.^{[2]} This construction may be interpreted as forming the Dedekind–MacNeille completion of *L*, which is known to produce an isomorphic lattice from any finite lattice.

## [edit] Concept algebra of a context

Modelling negation in a formal context is somewhat problematic because the complement (*O*\*O*_{i}, *A*\*A*_{i}) of a concept (*O*_{i}, *A*_{i}) is in general not a concept. However, since the concept lattice is complete one can consider the join (*O*_{i}, *A*_{i})^{Δ} of all concepts (*O*_{j}, *A*_{j}) that satisfy *O*_{j} ⊆ *G*\*O*_{i}; or dually the meet (*O*_{i}, *A*_{i})^{𝛁} of all concepts satisfying *A*_{j} ⊆ *G*\*A*_{i}. These two operations are known as *weak negation* and *weak opposition*, respectively.

This can be expressed in terms of the *derivative* functions. The derivative of a set *O*_{i} ⊆ *O* of objects is the set *O*_{i}' ⊆ *A* of all attributes that hold for all objects in *O*_{i}. The derivative of a set *A*_{i} ⊆ *A* of attributes is the set *A*_{i}' ⊆ *O* of all objects that have all attributes in *O*_{i}. A pair (*O*_{i}, *A*_{i}) is a concept if and only if *O*_{i}' = *A*_{i} and *A*_{i}' = *O*_{i}. Using this function, weak negation can be written as

- (
*O*_{i},*A*_{i})^{Δ}= ((*G*\*A*)'', (*G*\*A*)'),

and weak opposition can be written as

- (
*O*_{i},*A*_{i})^{𝛁}= ((*M*\*B*)', (*M*\*B*)'').

The concept lattice equipped with the two additional operations Δ and 𝛁 is known as the *concept algebra* of a context. Concept algebras are a generalization of power sets.

Weak negation on a concept lattice *L* is a *weak complementation*, i.e. an order-reversing map Δ: *L* → *L* which satisfies the axioms *x*^{ΔΔ} ≤ *x* and (*x*⋀*y*) ⋁ (*x*⋀*y*^{Δ}) = *x*. Weak composition is a dual weak complementation. A (bounded) lattice such as a concept algebra, which is equipped with a weak complementation and a dual weak complementation, is called a *weakly dicomplemented lattice*. Weakly dicomplemented lattices generalize distributive orthocomplemented lattices, i.e. Boolean algebras.^{[3]}^{[4]}

## [edit] Recovering the context from the Hasse diagram

The Hasse diagram of the concept lattice (also called, in formal concept analysis, a *line diagram*), encodes enough information to recover the original context from which it was formed. Each object of the context corresponds to a lattice element, the element with the minimal object set that contains that object, and with an attribute set consisting of all attributes of the object. Symmetrically, each attribute of the context corresponds to a lattice element, the one with the minimal attribute set containing that attribute, and with an object set consisting of all objects with that attribute. We may label the nodes of the Hasse diagram with the objects and attributes they correspond to; with this labeling, object *x* has attribute *y* if and only if there exists a monotonic path from *x* to *y* in the diagram.^{[5]}

## [edit] Efficient construction

Kuznetsov & Obiedkov (2001) survey the many algorithms that have been developed for constructing concept lattices. These algorithms vary in many details, but are in general based on the idea that each edge of the Hasse diagram of the concept lattice connects some concept *C* to the concept formed by the join of *C* with a single object. Thus, one can build up the concept lattice one concept at a time, by finding the neighbors in the Hasse diagram of known concepts, starting from the concept with an empty set of objects. The amount of time spent to traverse the entire concept lattice in this way is polynomial in the number of input objects and attributes per generated concept.

## [edit] See also

## [edit] Notes

**^**Wolff, section 2.**^**Stumme, Theorem 1.**^**Wille, Rudolf (2000), "Boolean Concept Logic", in Ganter, B.; Mineau, G. W.,*ICCS 2000 Conceptual Structures: Logical, Linguistic and Computational Issues*, LNAI 1867, Springer, pp. 317–331, ISBN 978-3540678595.**^**Kwuida, Léonard (2004),*Dicomplemented Lattices. A contextual generalization of Boolean algebras*, Shaker Verlag, ISBN 9783832233501, http://hsss.slub-dresden.de/documents/1101148726640-2926/1101148726640-2926.pdf**^**Wolff, section 3.

## [edit] References

- Ganter, Bernhard; Stumme, Gerd; Wille, Rudolf, eds. (2005),
*Formal Concept Analysis: Foundations and Applications*, Lecture Notes in Artificial Intelligence, no. 3626, Springer-Verlag, ISBN 3-540-27891-5

- Ganter, Bernhard; Wille, Rudolf (1998),
*Formal Concept Analysis: Mathematical Foundations*, Springer-Verlag, Berlin, ISBN 3-63311-62767-5. Translated by C. Franzke.

- Carpineto, Claudio; Romano, Giovanni (2004),
*Concept Data Analysis: Theory and Applications*, Wiley, ISBN 978-0-470-85055-8.

- Kuznetsov, Sergei O.; Obiedkov, Sergei A. (2001), "Algorithms for the Construction of Concept Lattices and Their Diagram Graphs",
*Principles of Data Mining and Knowledge Discovery*, Lecture Notes in Computer Science,**2168**, Springer-Verlag, pp. 289–300, doi:.

- Wolff, Karl Erich (1994), "A first course in Formal Concept Analysis", in F. Faulbaum,
*StatSoft '93*, Gustav Fischer Verlag, pp. 429–438, http://www.fbmn.fh-darmstadt.de/home/wolff/Publikationen/A_First_Course_in_Formal_Concept_Analysis.pdf.