Développements de Méthodes de Classification basées sur l’Analyse de Concepts Formels sous la Plateforme WEKA

Cet article traite du développement de méthodes de classification basées sur l’Analyse de Concepts Formels (ACF) intégrées dans la plateforme WEKA. Il s’adresse aux étudiants et chercheurs en informatique décisionnelle, fouille de données et apprentissage automatique qui souhaitent comprendre comment exploiter l’ACF pour améliorer les techniques de classification dans un environnement logiciel reconnu.

La question

Le travail s’intéresse à la problématique de la classification dans le contexte de la fouille de données, en particulier à l’intégration de méthodes basées sur l’Analyse de Concepts Formels sous la plateforme WEKA. La question principale est de savoir comment développer et implémenter efficacement des algorithmes de classification supervisée fondés sur l’ACF, tels que IPR (Induction de Règles de Production) et BCF (Boosting de Concepts Formels), tout en tirant parti des capacités de WEKA. Cette problématique est importante car la masse croissante de données nécessite des outils performants pour extraire des connaissances exploitables, notamment par classification, afin d’aider à la prise de décision.

Concepts de base

L’informatique décisionnelle et la fouille de données (data mining) visent à extraire des connaissances à partir de grandes quantités de données. La classification est une tâche clé qui consiste à attribuer une classe à un objet à partir d’un ensemble d’exemples étiquetés.

L’Analyse de Concepts Formels (ACF) est une approche théorique qui permet de regrouper conceptuellement des données en identifiant des concepts formels, c’est-à-dire des paires d’ensembles d’objets et d’attributs liés par une relation binaire. Ces concepts sont organisés dans une structure appelée treillis de Galois, qui représente les relations hiérarchiques entre concepts.

L’ACF est utilisée en fouille de données pour construire des règles d’association et pour la classification supervisée. Par exemple, l’algorithme IPR extrait des concepts un par un en optimisant localement une fonction d’entropie, puis génère des règles de classification à partir des concepts pertinents associés à une classe majoritaire.

Deux types d’apprentissage sont distingués :

• Apprentissage supervisé : à partir d’une base d’apprentissage étiquetée, on construit un classifieur capable d’attribuer une classe à un nouvel objet.
• Apprentissage non supervisé : à partir d’un ensemble de données non étiquetées, on cherche à découvrir des structures ou groupes (clustering).

Les plateformes de fouille de données comme WEKA, TANAGRA et ORANGE offrent des environnements pour appliquer ces méthodes. WEKA, écrit en Java, est particulièrement adapté pour intégrer des méthodes basées sur l’ACF, bien qu’il présente certaines limites en termes de gestion mémoire et temps de calcul sur de très grandes bases.

Approche

Le projet a choisi d’intégrer les méthodes IPR, BCF et AdaBoostM2 sous la plateforme WEKA, en raison de sa richesse fonctionnelle et de sa capacité à gérer l’apprentissage supervisé. L’approche consiste à :

• Étudier les algorithmes existants basés sur l’ACF, notamment IPR et BCF, qui utilisent le treillis de concepts pour générer des règles de classification.
• Analyser les plateformes de fouille de données disponibles, comparer leurs fonctionnalités et performances, et sélectionner WEKA comme environnement d’intégration.
• Concevoir et réaliser l’implémentation des méthodes choisies sous WEKA, en tenant compte des contraintes techniques et des besoins d’intégration.
• Effectuer des tests de réception et unitaires pour valider le bon fonctionnement des algorithmes, en comparant les résultats obtenus avec ceux d’autres implémentations.

Par exemple, l’algorithme IPR extrait des concepts pertinents en calculant l’entropie de Shannon sur des pseudo-concepts, puis génère des règles telles que :

A ^ B → C1
B ^ C → C2
C ^ D → C2

où A, B, C, D sont des attributs et C1, C2 des classes. La pertinence d’un pseudo-concept est mesurée par son entropie, et en cas d’égalité, la structure contenant le plus d’exemples est favorisée.

Résultats

Le travail a permis de :

• Comprendre et maîtriser le domaine de la fouille de données et le processus d’extraction de connaissances.
• Découvrir et comparer les plateformes de fouille de données, en particulier WEKA, TANAGRA et ORANGE, en fonction de critères fonctionnels et expérimentaux.
• Implémenter avec succès les méthodes IPR, BCF et AdaBoostM2 sous WEKA, validant ainsi leur intégration technique.
• Valider les résultats obtenus par une comparaison avec d’autres expériences d’implémentation, notamment en termes de classification, d’ensemble de concepts formels et de règles générées.

Une comparaison expérimentale a montré que TANAGRA est plus performant en temps de calcul et consommation mémoire pour certaines opérations, tandis que WEKA est très rapide dans les opérations nécessitant un accès rapide aux variables pour un même individu.

Limites et questions ouvertes

Le travail souligne plusieurs limites et pistes d’amélioration :

• Les performances de WEKA peuvent être limitées par le temps de calcul et la gestion mémoire sur de très grandes bases de données.
• La qualité visuelle des fichiers de trace générés lors de l’exécution pourrait être améliorée pour faciliter l’analyse.
• La capacité des classifieurs pourrait être encore optimisée, notamment en affinant la notion de degré de pertinence dans le calcul des concepts formels.
• La publication et la diffusion des méthodes développées sous WEKA restent à réaliser pour un usage plus large.

Glossaire

• Analyse de Concepts Formels (ACF) : méthode théorique pour regrouper des données en concepts formels, associant objets et attributs dans un treillis.
• Classification supervisée : tâche d’apprentissage consistant à attribuer une classe à un objet à partir d’exemples étiquetés.
• Concept formel : paire (ensemble d’objets, ensemble d’attributs) liée par une relation binaire dans l’ACF.
• Entropie de Shannon : mesure d’incertitude utilisée pour évaluer la pertinence d’un concept dans IPR.
• IPR (Induction de Règles de Production) : algorithme basé sur l’ACF qui extrait des concepts et génère des règles de classification.
• BCF (Boosting de Concepts Formels) : méthode d’apprentissage supervisé utilisant l’ACF pour améliorer la classification.
• Treillis de Galois : structure mathématique représentant les relations hiérarchiques entre concepts formels.
• WEKA : plateforme logicielle en Java pour la fouille de données et l’apprentissage automatique.
• Apprentissage supervisé : apprentissage à partir de données étiquetées pour construire un classifieur.
• Apprentissage non supervisé : découverte de structures dans des données non étiquetées, par exemple le clustering.