Analyse formelle de concepts

L'analyse formelle de concepts (en anglais Formal Concept Analysis, FCA) s'attache à étudier les concepts lorsqu'ils sont décrits formellement, c'est-à-dire que le contexte et les concepts sont complètement et précisément définis. Elle a été introduite par Rudolf Wille en 1982 en tant qu'application de la théorie des treillis (voir treillis de Galois). Elle repose sur les travaux antérieurs de M. Barbut et B. Monjardet, sur toute la théorie des treillis et dispose également d'une solide base philosophique.

Un concept peut être défini par son intension et son extension : l'extension est l'ensemble des objets qui appartiennent au concept tandis que l'intension est l'ensemble des attributs partagés par ces objets.

Définitions

Un contexte est un triplet $(G,M,I)$ où $G$ et $M$ sont des ensembles et $I\subseteq G\times M$. Les éléments de $G$ sont appelés les objets et ceux de $M$ les attributs. L'ensemble de couple $I$ est considéré comme une relation et est donc noté $gIm$ au lieu de $(g,m)\in I$ ce qui se dit : « l'objet $g$ possède l'attribut $m$». Les lettres $G$ et $M$ proviennent de l'allemand Gegenstände et Merkmale.

On définit les opérateurs de dérivation pour $A\subseteq G$ et $B\subseteq M$ par $A'=\{m\in M\mid \forall g\in A\cdot gIm\}$ et $B'=\{g\in G\mid \forall m\in B\cdot gIm\}$. L'ensemble $A'$ est l'ensemble des attributs partagés par tous les objets de $A$ et l'ensemble $B'$ est l'ensemble des objets qui possèdent tous les attributs de $B$.

Un concept du contexte $(G,M,I)$ est un couple $(A,B)$ où $A\subseteq G$ et $B\subseteq M$ qui vérifie $A'=B$ et $B'=A$. Pour un concept $(A,B)$, on dit que $A$ est son extension et $B$ son intension.

On définit un ordre (partiel) sur les concepts par $(A_{1},B_{1})\leq (A_{2},B_{2})\Leftrightarrow A_{1}\subseteq A_{2}(\Leftrightarrow B_{2}\subseteq B_{1})$.

On peut utiliser les opérateurs de dérivation pour construire un concept à partir d'un ensemble d'objets $X$ ou d'attributs $Y$ en considérant les concepts $(X'',X')$ et $(Y',Y'')$ respectivement. En particulier pour un objet $g$ on appelle $\gamma g$ le concept objet $(\{g\}'',\{g\}')$ et pour un attribut $m$ on appelle $\mu m$ le concept attribut $(\{m\}',\{m\}'')$.

Exemple

Considérons comme ensemble d'objets les nombres entiers de 1 à 10 : $G=\{1,2,3,4,5,6,7,8,9,10\}$ et comme ensemble d'attributs des propriétés mathématiques : $M=\{pair,impair,compos{\acute {e}},premier,carr{\acute {e}}\}$.

La relation d'incidence $I\subseteq G\times M$ peut être représentée sous forme d'un tableau où les lignes correspondent aux objets et les colonnes correspondent aux attributs.

nombre	composé	pair	impair	premier	carré
1			x		x
2		x		x
3			x	x
4	x	x			x
5			x	x
6	x	x
7			x	x
8	x	x
9	x		x		x
10	x	x

On a $\{3\}'=\{impair,premier\}$ et $\{impair,premier\}'=\{3,5,7\}$. Donc $(\{3,5,7\},\{impair,premier\})$ est un concept formel.

Treillis de concepts

Chaque paire de concepts possède une borne inférieure et une borne supérieure uniques. Étant donné les concepts $(G_{i},M_{i})$et $(G_{j},M_{j})$, leur borne inférieure est $(G_{i}\cap G_{j},(M_{i}\cup M_{j})'')$ et leur borne supérieure est $((G_{i}\cup G_{j})'',M_{i}\cap M_{j})$.

Du fait de l'ordre partiel entre les concepts et des bornes, les conditions sont respectées pour construire un treillis de concepts.

Bibliographie

(en) Bernhard Ganter et Rudolf Wille (en), Formal Concept Analysis : Mathematical Foundations, Berlin, Springer Verlag, 1999, 284 p. (ISBN 978-3-540-62771-5)