Formal concept analysis
From Wikipedia, the free encyclopedia
Formal concept analysis 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.
Contents |
[edit] The concept lattice
We take as givens 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 (Oi, Ai) such that
- Oi ⊆ O
- Ai ⊆ A
- every object in Oi has every attribute in Ai
- for every object in O that is not in Oi, there is an attribute in Ai that that object does not have
- for every attribute in A that is not in Ai, there is an object in Oi that does not have that attribute
These concepts can be partially ordered by inclusion: if (Oi, Ai) and (Oj, Aj) are concepts, we define a partial order ≤ by saying that (Oi, Ai) ≤ (Oj, Aj) whenever Oi ⊆ Oj. Equivalently, (Oi, Ai) ≤ (Oj, Aj) whenever Aj ⊆ Ai. 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 (Oi, Ai) and (Oj, Aj) is the concept with objects Oi ∩ Oj; it has as its attributes the union of Ai, Aj, and any additional attributes held by all objects in Oi ∩ Oj. The least upper bound of (Oi, Ai) and (Oj, Aj) is the concept with attributes Ai ∩ Aj; it has as its objects the union of Oi, Oj, and any additional objects that have all attributes in Ai ∩ Aj.
[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; the full set of concepts for these objects and attributes is shown in the illustration.
[edit] See also
[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 3540278915.
- Ganter, Bernhard; Wille, Rudolf; Franzke, C. (translator) (1998). Formal Concept Analysis: Mathematical Foundations. Springer-Verlag, Berlin. ISBN 3540627715.
