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^[1] 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^[2], sur toute la théorie des treillis^[3] et dispose également d'une solide base philosophique^[4].

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.

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

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

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

On définit un ordre (partiel) sur les concepts par ${\displaystyle (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 ${\displaystyle X}$ ou d'attributs ${\displaystyle Y}$ en considérant les concepts ${\displaystyle (X'',X')}$ et ${\displaystyle (Y',Y'')}$ respectivement. En particulier pour un objet ${\displaystyle g}$ on appelle ${\displaystyle \gamma g}$ le concept objet ${\displaystyle (\{g\}'',\{g\}')}$ et pour un attribut ${\displaystyle m}$ on appelle ${\displaystyle \mu m}$ le concept attribut ${\displaystyle (\{m\}',\{m\}'')}$.

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

La relation d'incidence ${\displaystyle 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.

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

Chaque paire de concepts possède une borne inférieure et une borne supérieure uniques. Étant donné les concepts ${\displaystyle (G_{i},M_{i})}$et ${\displaystyle (G_{j},M_{j})}$, leur borne inférieure est ${\displaystyle (G_{i}\cap G_{j},(M_{i}\cup M_{j})'')}$ et leur borne supérieure est ${\displaystyle ((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.

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

• Portail de l’informatique