Main Page | See live article | Alphabetical index

Formal concept analysis

Formal concept analysis is a method of data analysis that finds "natural" clusters of objects and their properties in an input dataset. The clusters are natural in roughly the same sense that definitions in terms of individually necessary and jointly sufficient conditions (or, alternatively, the extensionss of such definitions) are natural.

Given a set of objects O, a set of attributues A, and an indication of which objects have which attributes, concept analysis:

  1. 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.
  2. produces a lattice indicating which concepts are strict subconcepts of which other concepts.

Provided the input objects and input concepts provide a complete description of the world (never true in practice, but perhaps a reasonable approximation), then:

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