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 (O_c ⊆ O, A_c ⊆ A) pair such that A) every object in O_c has every attribute in A_c and B) every object in O (not O_c) that has every attribute in A_c is in O_c.
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

• machine learning
• unsupervised learning

Further reading

• [1]: a set of lectures describing formal concept analysis for computer scientists