Projet C : énumérer les concepts formels avec l’algorithme In-Close
L3 Mathématiques-Informatique, Programmation (C). Projet à réaliser en binôme.
1 Prérequis
S’inscrire à un groupe sur : https://im2ag-moodle.univ-grenoble-alpes.fr/course/view.php?id=682
Un projet git sera ensuite créé par l’enseignant pour chaque groupe. Vous déposerez votre code dans ce dépot git.
La structure de votre projet sera la suivante :
inclose/
|-- Makefile
|-- README.md rapport du projet
|-- include/
| |-- bitset.h type word, WORD_BITS, WORD_MAX
| |-- context.h FormalContext, ctx_read, ctx_free
| |-- enumeration.h Concept, concept_cb, enum_naive, enum_inclose, enum_inclose_arena
| |-- pool.h structure Pool (arena)
| `-- read_utils.h utilitaires de lecture (fournis)
|-- src/
| |-- read_utils.c (fourni, ne pas modifier)
| |-- context.c
| |-- enum_naive.c
| |-- enum_inclose.c
| `-- enum_inclose_arena.c
|-- tests/
| `-- compare.c programme de test et de comparaison
`-- data/ contextes de test (.ctx)
Un squelette de ce projet (en-têtes, utilitaires fournis, Makefile, fonctions à écrire vides) vous est fourni.
2 Présentation et objectifs
L’analyse formelle de concepts (FCA, Formal Concept Analysis) part d’un simple tableau de 0 et de 1 : des objets en lignes (animaux, clients, documents…), des attributs en colonnes (“vole”, “a acheté le produit X”…). Elle cherche tous les groupes maximaux d’objets qui partagent exactement les mêmes attributs. Ces groupes s’appellent des concepts formels ; ils forment un treillis, très utilisé en fouille de données, en classification et en extraction de règles.
Le nombre de concepts peut être exponentiel : énumérer ces concepts est donc un problème de recherche exhaustive où tout se joue sur l’élagage et sur la qualité de l’implémentation.
L’objectif de ce travail est d’implémenter en C l’algorithme In-Close (S. Andrews), le valider face à un algorithme de référence naïf, puis mesurer et comparer ses performances.
3 L’analyse formelle de concepts
Un contexte formel est un triplet \((G, M, I)\) : \(G\) un ensemble d’objets, \(M\) un ensemble d’attributs et \(I \subseteq G \times M\) une relation d’incidence. On note \((g, m) \in I\) lorsque l’objet \(g\) possède l’attribut \(m\).
Pour \(A \subseteq G\) et \(B \subseteq M\), on définit les deux opérateurs de dérivation :
- \(A' = \{\, m \in M \mid \forall g \in A,\ (g, m) \in I \,\}\) : les attributs communs à tous les objets de \(A\) ;
- \(B' = \{\, g \in G \mid \forall m \in B,\ (g, m) \in I \,\}\) : les objets qui possèdent tous les attributs de \(B\).
Un concept formel est un couple \((A, B)\) tel que \(A' = B\) et \(B' = A\). \(A\) est son extent, \(B\) son intent. De manière équivalente, les extents sont exactement les ensembles \(A\) vérifiant \(A'' = A\) (les ensembles “fermés”).
Pour un attribut \(j\), on note \(j' = \{j\}'\) l’ensemble des objets qui possèdent \(j\) : c’est la colonne de \(j\) dans le tableau (col[j] dans le code).
3.1 Exemple fil rouge
Cinq animaux (objets 0 à 4) et cinq attributs (0 à 4) :
| objet | 0 pattes | 1 fourrure | 2 aboie | 3 vole | 4 plumes |
|---|---|---|---|---|---|
| 0 Chat | \(\times\) | \(\times\) | |||
| 1 Chien | \(\times\) | \(\times\) | \(\times\) | ||
| 2 Moineau | \(\times\) | \(\times\) | |||
| 3 Pingouin | \(\times\) | ||||
| 4 Chauve-souris | \(\times\) | \(\times\) |
Les colonnes sont donc : \(0' = \{0,1\}\), \(1' = \{0,1,4\}\), \(2' = \{1\}\), \(3' = \{2,4\}\), \(4' = \{2,3\}\).
Voici les 8 concepts que doit produire votre programme sur cet exemple, au format “extent | intent” (ordre des lignes libre) :
0 1 2 3 4 |
0 1 4 | 1
0 1 | 0 1
1 | 0 1 2
2 4 | 3
2 3 | 4
2 | 3 4
4 | 1 3
Pour des raisons d’optimisation, on pourra omettre le concept avec un extent vide.
4 L’algorithme In-Close
L’algorithme In-Close permet de découvrir automatiquement tous les concepts formels présents dans un contexte formel, sans produire de doublons. Cet algorithme repose sur trois idées principales:
- Les concepts sont construits progressivement en ajoutant les attributs un par un.
- La fermeture est calculée de manière incrémentale.
- Il évite de générer des doublons en utilisant un test de canonicité.
4.1 Parcours de l’arbre de recherche
Les concepts s’énumèrent en parcourant un arbre de recherche. Chaque noeud de l’arbre est un concept en cours de construction. Il est décrit par trois éléments :
- \(A\) : son extent, connu exactement dès la création du noeud ;
- \(B\) : son intent, connu seulement en partie à la création, et complété pendant le traitement du noeud ;
- \(y\) : un indice d’attribut. Dans ce noeud, on n’a le droit d’ajouter que les attributs ayant un undice supérieur ou égal à \(y\).
La racine de l’arbre de recherche est le noeud \((G, G')\) avec \(y = 0\) dont l’extent contient tous les objets.
Traiter un noeud \((A, B, y)\) consiste à examiner, pour tout \(j \in [y, m[\), ce qui se passe lorsque l’on ajoute l’attribut \(j\) à \(B\) et que l’ensemble des objets correspondant devient \(C = A \cap j'\). Trois cas sont possibles :
\(C = A\) : tous les objets de \(A\) possèdent déjà \(j\). L’attribut \(j\) doit donc faire partie de l’intent du concept courant : on l’ajoute à \(B\). Il n’y a pas d’enfant de créé.
\(C = \emptyset\) : plus aucun objet. On ignore ce candidat (l’algorithme ne produit que des concepts qui ont au moins un objet).
dans les autres cas, \(C\) est un sous-ensemble strict non vide de \(A\) : \(C\) est l’extent d’un concept enfant, mais avant de parcourir le sous-arbre, il faut vérifier qu’on ne l’a pas déjà obtenu par un autre chemin : c’est le test de canonicité (section suivante).
Quand la boucle sur \(j\) est terminée, \(B\) est complet et \((A, B)\) est un concept.
Remarque. Si aucun objet ne possède tous les attributs, le couple \((\emptyset, M)\) est aussi un concept au sens de la définition, mais l’algorithme ne le produit pas (cas 2). C’est le cas de l’exemple, d’où ses 8 concepts et non 9.
4.2 Le test de canonicité
Un même concept peut être atteint par plusieurs chemins, selon l’ordre dans lequel on ajoute les attributs. Sur l’exemple, le concept du chien, \((\{1\}, \{0,1,2\})\), s’obtient :
- en ajoutant d’abord “pattes” (attribut 0), puis “aboie” (attribut 2) ;
- ou directement depuis la racine en ajoutant “aboie” (attribut 2).
Sans précaution, ce concept serait produit deux fois, et dans un grand contexte certains concepts seraient produits un nombre exponentiel de fois.
Le test de canonicité permet de retenir que les candidats obtenus par ajout d’attribut le plus petit possible. On verifie donc pour chaque candidat extent formé par ajout d’un attribut \(j\) à un intent \(B\) qu’il n’existe pas d’attribut \(i\), avec \(i<j\) et \(i \not \in B\), permettant de former le même candidat.
Exemple. Considérons le noeud \((A=\{0,1,4\}, B = \{1\}, y = 2)\). En ajoutant l’attribut \(j = 2\) on obtient le candidat extent \(C = A \cap j' = \{1\}\). Ce candidat aurait néamoins pu être obtenu à partir d’une branche précédante contenant l’attribut \(0\) (\(<j\)), le candidat est donc rejeté.
4.3 Pseudo-code
Voici le pseudo code l’algorithme In-Close et du test de canonicité. Dans les algoritmes suivants, col[j] représente la colonne de l’attribut \(j\) (i.e. \(j'\)) et \(m\) le nombre d’attributs.
InClose(A, B, y):
enfants = liste vide
pour j de y a m-1:
C = A inter col[j]
si C == A:
B = B union {j} // j appartient a l'intent du concept courant
sinon si C est non vide et EstCanonique(C, B, j):
enfants.ajouter((C, j))
sortir (A, B) // B est maintenant complet
pour chaque (C, j) dans enfants:
InClose(C, (B inter [0, j-1]) union {j}, j+1)
EstCanonique(C, B, j):
pour k de 0 a j-1 avec k hors de B:
si C inclus dans col[k]: retourner faux
retourner vrai
Appel initial : InClose(G, ensemble vide, 0)
Cette version collecte d’abord les enfants puis les traite. On peut aussi descendre immédiatement dans chaque enfant retenu, sans liste d’enfants : l’ensemble des concepts produits est le même, seul l’ordre de sortie change (c’est ce que fait la version avec arena de la section « In-Close » du travail à réaliser).
4.4 Déroulement sur l’exemple
Notons \((A, B)\) chaque noeud avec son intent final. Voici l’arbre de recherche complet de l’exemple :
({0,1,2,3,4}, {}) racine
|-- j=0 : ({0,1}, {0,1})
| `-- j=2 : ({1}, {0,1,2})
|-- j=1 : ({0,1,4}, {1})
| |-- j=2 : rejeté (doublon de ({1}, {0,1,2}))
| `-- j=3 : ({4}, {1,3})
|-- j=2 : rejeté (doublon de ({1}, {0,1,2}))
|-- j=3 : ({2,4}, {3})
| `-- j=4 : ({2}, {3,4})
`-- j=4 : ({2,3}, {4})
5 Travail à réaliser
5.1 Lecture de fichier de contexte et représentation en mémoire
Le format Burmeister est un format textuel utilisé pour représenter et stocker des contextes formels. Les fichiers de contexte au format Burmeister possèdent généralement l’extention .ctx et comprennent les lignes suivantes:
- un marqueur, généralement la lettre
B - une ligne vide
- le nombre d’objets du contexte
- le nombre d’attributs du contexte
- une ligne vide
- la liste de noms des objets du contexte, un par ligne
- la liste des noms d’attributs du contexte, un par ligne
- La matrice de la relation binaire etre objet et attribut. Chaque ligne représente un objet, le caractère
Xindique la présence de la relation tandis que le.signifie l’absence de relation.
Le contenu du fichier au format Burmeister de l’exemple fil rouge est le suivant :
B
5
5
Chat
Chien
Moineau
Pingouin
Chauve-souris
pattes
fourrure
aboie
vole
plumes
XX...
XXX..
...XX
....X
.X.X.
En mémoire un contexte formel sera représenté par une structure où la relation binaire sera représentée de manière compactée en utilisant un tableau de bits, appelé “bitset” (utilisant des mots de 64 bits).
La définition de structure suivante sera utilisée :
typedef uint64_t word;
typedef struct {
size_t nb_obj; // nombre d'objets
size_t nb_att; // nombre d'attributs
size_t nb_word_obj; // nombre de mots pour un extent (bitset d'objets)
size_t nb_word_att; // nombre de mots pour un intent (bitset d'attributs)
/* Matrice d'incidence binaire "transposée"
incidence[i*nb_word_obj] représente l'attribut i
*/
word *incidence;
/* Noms des objets et des attributs (facultatifs) */
char **obj_names; // obj_names[j] : le nom de l'objet j
char **att_names; // att_names[i] : le nom de l'attribut i
} FormalContext;Le tableau incidence stocke la liste des extents des différents attributs : l’extent de l’attribut d’indice i est stocké à l’adresse incidence[i*nb_word_obj] et occupe nb_word_obj * sizeof(word) octets. L’objet g correspond au bit g % 64 du mot incidence[i*nb_word_obj + g/64]. Attention : un extent occupe nb_word_obj mots, un intent nb_word_att mots.
Compléter la fonction suivante permettant de lire et charger un contexte formel donné au format Burmeister:
FormalContext *ctx_read(FILE *f); Afin de faciliter la lecture du fichier, plusieurs fonctions utilitaires ainsi que le code pour l’analyse du fichier sont fournies. Il faut seulement s’occuper d’allouer le contexte et de le remplir avec les bonnes informations.
Développer également la fonction de libération de la mémoire occupée par un contexte :
void ctx_free(FormalContext *ctx);Questions à se poser : Quels sont les avantages et inconvénients d’un bitset par rapport à un tableau d’indices triés ? Dans quels cas (densité, taille de \(G\)) l’un l’emporte-t-il ?
5.2 Algorithme de référence naïf
Dans un premier temps, on développera une recherche naïve. Son principe est le suivant: pour chaque sous-ensemble \(B\) de \(M\) (\(m \leq 20\) en pratique), on calcule \(B'\) puis \(B''\) ; le sous-ensemble \(B\) est un intent si et seulement si \(B'' = B\), et il donne alors le concept \((B', B)\). On ne gardera que les concepts d’extent non vide.
Cet algorithme est en \(\Theta(2^m)\) : il est inutilisable en pratique, mais il fait office d’oracle pour tester In-Close sur de petits contextes.
La fonction de recherche naïve aura la signature suivante:
size_t enum_naive(const FormalContext *ctx, concept_cb cb, void *user);Le paramètre concept_cb cb représentera un pointeur vers une fonction de “callback” qui sera appelée sur chaque concept enuméré. Le fonction retournera le nombre de concepts trouvés.
La fonction de callback sera basée sur les défintions suivantes :
typedef struct {
const word *extent; /* bitset d'objets */
const word *intent; /* bitset d'attributs */
} Concept;
typedef void (*concept_cb)(const FormalContext *ctx, const Concept *c, void *user);Les bitsets pointés par Concept ne sont valides que pendant l’appel au callback (ils peuvent être réutilisés ensuite) : pour conserver un concept, il faut en faire une copie.
Le paramètre void *user de type opaque sera optionnel et servira par exemple à passer en paramètre une structure de donner pour stocker les concepts.
5.3 In-Close
Proposer deux versions de In-Close, de même signature que la fonction d’énumération naïve :
size_t enum_inclose(const FormalContext *ctx, concept_cb cb, void *user);
size_t enum_inclose_arena(const FormalContext *ctx, concept_cb cb, void *user);La première allouera la mémoire nécessaire dynanimquement à chaque niveau de récursion, tandis que la deuxième utilisera une pile mémoire (appelée arena), allouée au départ et ayant une capacité suffissante pour stocker tous les candidats d’une branche de l’arbre de recherche (i.e. accueillir au moins \(m+1\) concepts, où \(m\) est le nombre d’attributs).
La structure suivante est fournie pour représenter l’arena :
typedef struct {
size_t stride; // nb_word_obj + nb_word_att
size_t levels; // nombre de niveaux (nb_att + 2)
word mem[]; // levels * stride mots : [extent | intent] par niveau
} Pool;5.4 Test et validation expérimentale
Proposer un exécutable de test qui permet de comparer les différentes algorithmes (énumération naïve, in-close, in-close avec arena) sur des petits contextes générés de manière aléatoire.
Tester également vos algorithmes sur les jeux de données fournis dans le réperoire data. Les contextes nom20magic04.cxt et inter10crx_nomissing.cxt permettront de tester le passage à l’échelle de vos implémentations.
Le programme de test devra vérifier que les différentes approches produisent les mêmes ensembles de concepts et produire une comparaison des temps d’execution des différents algorithmes.
5.5 Diagramme de Hasse
A venir…
5.6 Rendu
Le dépôt Git (ou dépôt moodle ?) contenant le code, le Makefile, les jeux de tests et un fichier README.md qui servira de rapport sur le projet (cf. le template fourni).