Formal concept analysis

In information science, formal concept analysis is a principled way of deriving a concept hierarchy or formal ontology from a collection of objects and their properties. Each concept in the hierarchy represents the set of objects sharing the same values for a certain set of properties; and each sub-concept in the hierarchy contains a subset of the objects in the concepts above it. 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 1930s.

Formal concept analysis finds practical application in fields including data mining, text mining, machine learning, knowledge management, semantic web, software development, and biology.

Overview and history

The original motivation of formal concept analysis was the concrete representation of complete lattices and their properties by means of formal contexts, data tables that represent binary relations between objects and attributes. In this theory, a formal concept is defined to a pair consisting of a set of objects (the "extent") and a set of attributes (the "intent") such that the extent consists of all objects that share the given attributes, and the intent consists of all attributes shared by the given objects. In this way, formal concept analysis formalizes the notions of extension and intension.

Pairs of formal concepts may be partially ordered by the subset relation between their sets of objects, or equivalently by the superset relation between their sets of attributes. This ordering results in a graded system of sub- and superconcepts, a concept hierarchy, which can be displayed as a line diagram. The family of these concepts obeys the mathematical axioms defining a lattice, and is called more formally a concept lattice. In French this is called a treillis de Galois (Galois lattice) because of the relation between the sets of concepts and attributes is a Galois connection.

The theory in its present form goes back to the Darmstadt research group led by Rudolf Wille, Bernhard Ganter and Peter Burmeister, where formal concept analysis originated in the early 1980s. The mathematical basis, however, was already created by Garrett Birkhoff in the 1930s as part of the general lattice theory. Before the work of the Darmstadt group, there were already approaches in various French groups. Philosophical foundations of formal concept analysis refer in particular to Charles S. Peirce and the educationalist Hartmut von Hentig.

Motivation and philosophical background

In his article Restructuring Lattice Theory (1982) initiating formal concept analysis as a mathematical discipline, Rudolf Wille starts from a discontent with the current lattice theory and pure mathematics in general: The production of theoretical results - often achieved by "elaborate mental gymnastics" - were impressive, but the connections between neighbouring domains, even parts of a theory were getting weaker.

Restructuring lattice theory is an attempt to reinvigorate connections with our general culture by interpreting the theory as concretely as possible, and in this way to promote better communication between lattice theorists and potential users of lattice theory.

This aim traces back to Hartmut von Hentig, who in 1972 plaided for restructuring sciences in view of better teaching and in order to make sciences mutually available and more generally (i.e. also without specialized knowledge) criticable. Hence, by its origins formal concept analysis aims at interdisciplinarity and democratic control of research.

It corrects the starting point of lattice theory during the development of formal logic in 19th century. Then - and later in model theory - a concept as unary predicate had been reduced to its extent. Now again, the philosophy of concepts should become less abstract by considering the intent. Hence, formal concept analysis is oriented towards the categories extension and intension of linguistics and classical conceptual logic.

FCA aims at the clarity of concepts according to Charles S. Peirce's pragmatic maxim by unfolding observable, elementary properties of the subsumed objects. In his late philosophy, Peirce assumed that logical thinking aims at perceiving reality, by the triade concept, judgement and conclusion. Mathematics is an abstraction of logic, develops patterns of possible realities and therefore may support rational communication. On this background, Wille defines:

The aim and meaning of Formal Concept Analysis as mathematical theory of concepts and concept hierarchies is to support the rational communication of humans by mathematically developing appropriate conceptual structures which can be logically activated.

Example

A concept lattice for objects consisting of the integers from 1 to 10, and attributes composite (c), square (s), even (e), odd (o) and prime (p).

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.

Contexts and concepts

A (formal) context consists of a set of objects O, a set of unary 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

1. O_i ⊆ O
2. A_i ⊆ A
3. every object in O_i has every attribute in A_i
4. for every object in O that is not in O_i, there is an attribute in A_i that the object does not have
5. 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_i the 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.

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. It may be viewed as the Dedekind–MacNeille completion of a partially ordered set of height two in which the elements of the partial order are the objects and attributes of A and in which two elements x and y satisfy x ≤ y exactly when x is an object that has attribute y.

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. 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.

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 A_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.

Recovering the context from the line diagram

The line diagram of the concept lattice 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 line 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.

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 line 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 line 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.

Tools

Many FCA software applications are available today. The main purpose of these tools varies from formal context creation to formal concept mining and generating the concepts lattice of a given formal context and the corresponding association rules. Most of these tools are academic and still under active development. One can find a non exhaustive list of FCA tools in the FCA software website. Most of these tools are open-source applications like ConExp, ToscanaJ, Lattice Miner, Coron, FcaBedrock, etc.

See also

• Biclustering
• Description logic
• Cluster analysis
• Concept mining
• Conceptual clustering
• Factor analysis

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-540-62771-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:10.1007/3-540-44794-6_24, ISBN 978-3-540-42534-2 .

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

• Davey, B.A.; Priestley, H. A. (2002), "3. Formal Concept Analysis", Introduction to Lattices and Order, Cambridge University Press, ISBN 978-0-521-78451-1 .

External links

• A Formal Concept Analysis Homepage
• Demo
• 11th International Conference on Formal Concept Analysis. ICFCA 2013 - Dresden, Germany - May 21-24, 2013