Formal concept analysis, is a term introduced by Rudolf Wille in 1984, and builds on applied lattice and order theory that was developed by Birkoff and others in the 1930's. Formal concept analysis is both a unsupervised machine learning technique but also broadly refers to 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 Rudolf Wille (born 1937) is a German mathematician, and was from 1970 to 2003 Professor in the Mathematics department at TU Darmstadt. ... Data analysis is the act of transforming data with the aim of extracting useful information and facilitating conclusions. ...

• 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 or Galois lattice. The name lattice is suggested by the form of the Hasse diagram depicting it. ...

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. For other uses, see Definition (disambiguation). ... In any of several studies that treat the use of signs, for example, linguistics, logic, mathematics, semantics, and semiotics, the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of the ideas, properties...

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). The lattice is drawn as a Hasse diagram.

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 Image File history File links Concept_lattice. ... Image File history File links Concept_lattice. ... The integers are commonly denoted by the above symbol. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... In mathematics, a square number, sometimes also called a perfect square, is an integer that can be written as the square of some other integer; in other words, it is the product of some integer with itself. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... In the mathematical discipline known as order theory, a Hasse diagram (pronounced HAHS uh, named after Helmut Hasse (1898–1979)) is a simple picture of a finite partially ordered set, forming a drawing of the transitive reduction of the partial order. ... A composite number is a positive integer which has a positive divisor other than one or itself. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... In mathematics, a square number, sometimes also called a perfect square, is an integer that can be written as the square of some other integer; in other words, it is the product of some integer with itself. ... In mathematics, any integer (whole number) is either even or odd. ... In mathematics, a prime number (or a prime) is a natural number which has exactly two distinct natural number divisors: 1 and itself. ... In mathematics, a square number, sometimes also called a perfect square, is an integer that can be written as the square of some other integer; in other words, it is the product of some integer with itself. ...

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.

Definition of concepts

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. Look up attribute in Wiktionary, the free dictionary. ...

A concept 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 that 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. In any of several studies that treat the use of signs, for example, linguistics, logic, mathematics, semantics, and semiotics, the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of the ideas, properties... Intension refers to the meanings or characteristics encompassed by a given word. ...

The concept lattice

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) 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. In mathematics, a partially ordered set (or poset for short) is a set equipped with a special binary relation which formalizes the intuitive concept of an ordering. ... The name lattice is suggested by the form of the Hasse diagram depicting it. ...

See also

• Biclustering
• Concept mining
• Conceptual clustering
• Data clustering
• Ontology (computer science)

Biclustering is a data mining technique that allows simultaneous clustering of rows and columns. ... It has been suggested that Taxonomic classification be merged into this article or section. ... Conceptual clustering is a machine learning paradigm for unsupervised classification. ... Clustering is the classification of objects into different groups, or more precisely, the partitioning of a data set into subsets (clusters), so that the data in each subset (ideally) share some common trait - often proximity according to some defined distance measure. ... In both computer science and information science, an ontology is a data model that represents a set of concepts within a domain and the relationships between those concepts. ...

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". F. Faulbaum StatSoft '93: 429–438, Gustav Fischer Verlag. 

External links

• Lecture notes by Gerd Stumme describing formal concept analysis for computer scientists
• A Formal Concept Analysis Homepage
• Knowledge, Visualization and Ordering Homepage