Editing Formal concept analysis (section)

== Formal contexts and concepts ==
A formal context is a triple {{math|1=''K'' = (''G'', ''M'', ''I'')}}, where ''G'' is a set of ''objects'', ''M'' is a set of ''attributes'', and {{math|1=''I'' ⊆ ''G'' × ''M''}} is a binary relation called ''incidence'' that expresses which objects ''have'' which attributes.<ref name="GW" /> For subsets {{math|1=''A'' ⊆ ''G''}} of objects and subsets {{math|1=''B'' ⊆ ''M''}} of attributes, one defines two ''derivation operators'' as follows:

: {{math|1=''{{prime|A}}'' = {{mset|''m'' ∈ ''M'' | (''g,m'') ∈ ''I'' for all ''g'' ∈ ''A''}} }}, i.e., a set of '''all''' attributes shared by all objects from A, and dually

: {{math|1=''{{prime|B}}'' = {{mset|''g'' ∈ ''G'' | (''g,m'') ∈ ''I'' for all ''m'' ∈ ''B''}} }}, i.e., a set of '''all''' objects sharing all attributes from B.

Applying either derivation operator and then the other constitutes two [[closure operator]]s:

:''A''  ↦ ''{{prime|A}}''{{prime}} = (''{{prime|A}}''){{prime}}  for ''A'' ⊆ G  (extent closure), and

:''B''  ↦ ''{{prime|B}}''{{prime}} = (''{{prime|B}}''){{prime}}  for ''B'' ⊆ M  (intent closure).

The derivation operators define a [[Galois connection]] between sets of objects and of attributes. This is why in French a concept lattice is sometimes called a ''treillis de Galois'' (Galois lattice).

With these derivation operators, Wille gave an elegant definition of a formal concept:
<!--With these derivation operators, it is possible to restate the definition of the term "formal concept" more rigorously:-->
a pair (''A'',''B'') is a ''formal concept'' of a context {{math|(''G'', ''M'', ''I'')}} provided that:

:''A'' ⊆ ''G'',  ''B'' ⊆ ''M'',  ''{{prime|A}}'' = ''B'',  and ''{{prime|B}}'' = ''A''.

Equivalently and more intuitively, (''A'',''B'') is a formal concept precisely when:
* every object in ''A'' has every attribute in ''B'',
* for every object in ''G'' that is not in ''A'', there is some attribute in ''B'' that the object does not have,
* for every attribute in ''M'' that is not in ''B'', there is some object in ''A'' that does not have that attribute.

For computing purposes, a formal context may be naturally represented as a [[(0,1)-matrix]] ''K'' in which the rows correspond to the objects, the columns correspond to the attributes, and each entry ''k''<sub>''i'',''j''</sub> equals to 1 if "object ''i'' has attribute ''j''." In this matrix representation, each formal concept corresponds to a [[maximal element|maximal]] submatrix (not necessarily contiguous) all of whose elements equal 1. It is however misleading to consider a formal context as ''boolean'', because the negated incidence ("object ''g'' does '''not''' have attribute ''m''") is not concept forming in the same way as defined above. For this reason, the values 1 and 0 or TRUE and FALSE are usually avoided when representing formal contexts, and a symbol like × is used to express incidence.