Formal concept analysis
|
|
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" property cluster is a set of properties in the input matrix that are individually necessary and jointly sufficient for picking out some non-empty subset of the objects in the input data, and
- a "natural" object cluster is a set of objects in the input matrix that can be picked out exactly by one of the natural property clusters.
There's a one-to-one correspondence between natural property clusters and natural object clusters, and a concept is a pair containing both a natural property cluster and its corresponding natural object cluster.
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.
...it also gives you a lattice.
| Contents |
Formal presentation
Given a set of objects O, a set of attributes A, and an indication of which objects have which attributes, concept analysis:
- finds all the "concepts" in the input dataset, where a concept is defined as an (Oc ⊆ O, Ac ⊆ A) pair such that A) every object in Oc has every attribute in Ac and B) every object in O (not Oc) that has every attribute in Ac is in Oc.
- produces a lattice indicating which concepts are strict subconcepts of which other concepts.
Misc
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.
- if a set of attributes is not identified as a concept by the algorithm, then those attributes are not singly necessary and jointly sufficient for defining any non-empty subset of objects in the world.
...
See also
Further reading
- [1] (http://www.aifb.uni-karlsruhe.de/WBS/gst/FBA03.shtml): a set of lectures describing formal concept analysis for computer scientists
- A Formal Concept Analysis Homepage (http://www.fcahome.org.uk/)de:Formale Begriffsanalyse