# Formal concept analysis

**Formal concept analysis**, introduced by Rudolf Wille and his students, is a method of data analysis that takes an input matrix specifying a set of objects and the properties thereof, and finds both all the "natural" clusters of *properties* 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 properties, and - a "natural"
*property*cluster is the set of all properties 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** or **Galois lattice**.

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.

## The concept lattice

We take as givens a *(formal) context* consisting of a set of objects *O*, a set of attributes *A*, and an indication of which objects have which attributes.

A *concept* 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 that 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*.

These concepts 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) and a unique least upper bound (join), so this partial order satisfies the axioms defining a lattice. 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}. 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}.

## 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; the full set of concepts for these objects and attributes is shown in the illustration.

## See also

## 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; Franzke, C. (translator) (1998).
*Formal Concept Analysis: Mathematical Foundations*. Springer-Verlag, Berlin. ISBN 3-63311-62767-5.

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

- Karl Erich Wolff (1994). "A first course in Formal Concept Analysis". In F. Faulbaum.
*StatSoft '93*. Gustav Fischer Verlag. pp. 429–438.