1. Introduction
La classification est une des tâches centrales de l’étape de fouille de données dans le processus d’extraction de connaissances dans les bases de données. Le problème de la classification est traité dans plusieurs communautés de recherche qui se découvrent et s’enrichissent mutuellement : statistiques, reconnaissances de formes, apprentissage automatique, réseaux de neurones et raisonnement à partir de cas. Le terme classification en français désigne à la fois les termes anglais classification (classification supervisée) et clustering (classification non supervisée). Nous nous focalisons sur la classification supervisée qui est un processus comprenant deux phases : apprentissage et classement. La phase d’apprentissage consiste à construire un modèle (ou classifieur) qui décrit un ensemble prédéterminé de classes d’exemples. La phase de classement consiste à utiliser le modèle pour affecter une classe à un nouvel exemple. Il existe de nombreux domaines d’application de ce problème : l’attribution de crédit bancaire, la reconnaissance de gènes, la prédiction de sites archéologiques, le diagnostic médical, etc. Plusieurs méthodes de classification supervisée publiées dans la littérature s’appuient sur des techniques différentes [COR 02, SEB 02] : inférence bayésienne, plus proches voisins, arbres de décision, réseaux de neurones ou treillis de concepts. Nous nous intéressons dans cet article aux méthodes basées sur les treillis de concepts 1 . Parler de classification basée sur les treillis est une façon abusive de désigner le fait que des hypothèses résultant d’une phase d’abstraction des données sont organisées sous la forme d’un treillis. Tout système de classification utilisant cette approche recherche dans cet espace les hypothèses les plus pertinentes pour le concept à apprendre. La structure du treillis permet de restituer le concept décrit par les données dans toute sa complexité et sa diversité.Les treillis de concepts formels (ou treillis de Galois) sont une structure mathématique permettant de représenter les classes non disjointes sous-jacentes à un ensemble d’objets (exemples, instances, tuples ou observations) décrits à partir d’un ensemble d’attributs (propriétés, descripteurs ou items). Ces classes non disjointes sont aussi appelées concepts formels, hyper-rectangles ou ensembles fermés. Une classe maté- rialise un concept (à savoir une idée générale que l’on a d’un objet). Ce concept peut être défini formellement par une extension (exemples du concept) ou par une intension (abstraction du concept). Les premiers travaux formels sur les treillis de concepts se situent en algèbre universelle, à travers les travaux de Birkhoff [BIR 40, BIR 67], et plus tard de Barbut et Monjardet [BAR 70]. Les travaux de Wille [WIL 82, WIL 92], de Duquenne [GUI 86, DUQ 99], de Ganter [GAN 99] ont permis de montrer l’utilité de cette structure pour l’analyse de données. En classification supervisée, l’apprentissage se ramène dans le cas général à un problème de recherche dansl’espace des hypothèses. A ce titre l’espace de versions développé par Mitchell [MIT 82] présente des liens étroits avec le treillis de concepts, tant d’un point de vue structurel que du point de vue de la complexité du modèle. Malgré la complexité exponentielle sous-jacente à la construction de la structure du treillis de concepts, plusieurs méthodes de classification ont été dé- velopées et ont produit des résultats comparables à ceux de méthodes standards, aussi bien en ce qui concerne la précision que l’efficacité en temps. En outre cette structure présente des propriétés particulières qui favorisent son usage pour la fouille de données, notamment pour la recherche de règles d’association [PAS 99] et pour l’apprentissage de concepts [KOU 98]. La problématique de mise en œuvre des algorithmes par niveaux, largement étudiée en fouille de données, et dont une formalisation algé- brique est proposée par Ganascia [GAN 93], est bien présente dans les modélisations réalisées avec cette structure. Certains travaux de recherche se sont inspirés du modèle des espaces des versions pour construire des modèles d’apprentissage à partir des treillis de concepts. CHARADE (Cubes de Hilbert Appliqués à la Représentation et à l’Apprentissage de Descriptions à partir d’Exemples) [GAN 87] est la première méthode à utiliser la correspondance de Galois, pour générer un ensemble de règles d’association non redondantes dont le but peut être restreint à une classe prédéfinie. Pour limiter l’espace de recherche, plusieurs heuristiques sont définies comme des paramètres que l’utilisateur peut sélectionner en fonction des propriétés des règles qu’il souhaite obtenir ou de la nature du problème qu’il traite. Le principe de classement à partir de cet ensemble de règles n’est pas explicitement formulé par l’auteur. L’utilisateur peut ensuite les employer pour construire sa méthode de classement. Ganascia [GAN 00] mentionne un certain nombre d’extensions de CHARADE ayant permis de traiter des applications de grande taille, notamment pour la catégorisation de textes, la découverte médicale, l’apprentissage de caractères chinois et l’extraction de connaissances dans une base de données épidémiologiques.
2. Algorithmes de construction du treillis de Galois
Plusieurs algorithmes de construction du treillis de Galois ont été proposés et ont fait l’objet d’études comparatives [KOU 98, NJI 00, KUZ 01] ou de synthèse [GUé 91]. Etendant l’étude faite par Guénoche [GUé 91], Njiwoua [NJI 00] a présenté six algorithmes de construction du treillis suivant une typologie relative à l’approche (incrémentale ou non) choisie par leurs auteurs et en se limitant au cas du contexte décrit par une matrice binaire. Ces algorithmes sont caractérisés suivant la méthode de construction choisie (ascendante ou descendante). Parmi les algorithmes analysés dont certains sont plus ou moins détaillés, on trouve ceux de Chein [CHE 69], de Ganter [GAN 84], de Bordat [BOR 86], de Godin et al. [GOD 91] (assez proche de l’algorithme de Norris[NOR 78]), d’Oosthuizen [OOS 91], de Carpineto et Romano [CAR 93]. Ils sont comparés dans [NJI 00] suivant différents critères parmi lesquels : la complexité théorique en temps d’exécution dans le pire des cas, la construction ou non du diagramme de Hasse, la technique de mise à jour utilisée (incrémentale ou non) et le type de parcours effectué (descendant ou ascendant). Le treillis de Galois construit dépend non seulement de la taille des éléments (nombre d’exemples et d’attributs), mais aussi pour une taille fixée, de la nature de la relation entre exemples et attributs. Par conséquent, la seule comparaison théorique en terme de complexité des différents algorithmes est faite dans le pire des cas. Cependant les bornes de complexité présentées sont généralement de loin supérieures aux résultats observés en pratique par les différents auteurs, ainsi que dans une étude récente faite par Kuznetsov et Obiedkov [KUZ 01]. Dans leur article, Kuznetsov et Obiedkov [KUZ 01] analysent dix algorithmes de construction du treillis de Galois. Ils présentent une étude de leurs complexités théoriques et une comparaison expérimentale sur des jeux de données artificiels. Dans cette analyse, on constate que l’algorithme de Nourine et Raynaud [NOU 99] qui a la meilleure complexité théorique actuelle dans le pire des cas, n’est pas le plus rapide dans les expérimentations. Les auteurs font des recommandations en fonction de la nature du contexte. Afin de mesurer l’efficacité de ces algorithmes sur les données réelles, Fu et Mephu [FU 03] ont comparé une implémentation de quatre algorithmes sur les données couramment utilisées pour tester les méthodes d’apprentissage [BLA 98]. Il en résulte que l’algorithme de Ganter (NextClosure) est en général le plus efficace sur ces données, ainsi que dans le pire des cas, lorsqu’il s’agit de générer simplement les concepts du treillis. Fu et Mephu discutent aussi de l’efficacité des algorithmes en fonction du nombre d’attributs par rapport au nombre d’objets.
4. GRAND
GRAND (GRAph-based iNDuction) est le système développé par Oosthuizen [OOS 88], qui s’adapte à l’apprentissage supervisé et non supervisé.
Il construit un pseudo-treillis d’exemples-attributs qui contient l’ensemble des gé- néralisations les plus spécifiques de l’espace des versions. Tous les concepts du treillis complet sont présents dans le pseudo-treillis à l’exception du supremum ou de l’infi- mum si chacun d’eux correspond à l’ensemble vide. Certains nœuds sont rajoutés tels que les nœuds-attributs et les nœuds-exemples. Ceux-ci ne correspondent pas toujours à des concepts formels. Dans le cas d’attribut universel (attribut commun à tous les exemples) le supremum est bien présent dans le pseudo-treillis. De même que dans le cas où au moins un exemple possède l’ensemble des attributs (exemple universel), l’infinimum est representé. La classe des exemples est un attribut comme les autres (voir la figure 3 pour une illustration sur l’exemple courant). Oosthuizen [OOS 91] représente un nœud uniquement par son intension. Il considère alors trois types de nœuds : 1) Les nœuds-attributs, il s’agit des éléments de . Ce sont les éléments maximaux du treillis. Le nœud correspondant est le plus général contenant l’attribut considéré. 2) Les nœuds-exemples, il s’agit des éléments de , représentés par leurs proprié- tés. Ce sont les éléments minimaux du treillis. Le nœud correspondant est le plus spécifique contenant l’exemple considéré. 3) Les nœuds-intermédiaires ou concepts. Un nœud intermédiaire hérite des attributs de tous ses majorants (ascendants) et des exemples de tous ses minorants (descendants). Il est possible grâce à un paramètre, de prendre en compte des exemples qui vérifient partiellement les hypothèses construites. Il en découle une plus grande souplesse dans la description des concepts. Il est aussi possible de préciser le nombre minimum d’exemples que doit couvrir un nœud pour être utilisé dans la phase de classement.
11. Conclusion
Dans cet article, après avoir défini le problème de la classification, nous avons présenté le treillis de concepts (ou de Galois) et plusieurs systèmes de classification basés sur cette structure mathématique. A travers les expérimentations pratiques de chacun de ses systèmes, on peut conclure que le treillis de Galois offre un cadre tant pour la classification supervisée que pour la classification non supervisée. En effet, la construction du treillis peut se faire en tenant compte ou non de la classe des éléments du contexte. L’utilisation du treillis de Galois permet de décomposer le concept à caractériser en sous-concepts. Il est alors plus aisé de rechercher une bonne caractérisation d’un ensemble réduit de données. Dans cette approche, les nœuds du treillis qui caractérisent chacun un sous-concept, possèdent une double représentation. L’une est constituée par l’hypothèse qui généralise les exemples du sous-concept concerné (l’intension). L’autre utilise l’ensemble des exemples du sous-concept (l’extension). C’est une instanciation du concept qui peut s’intégrer dans un mécanisme de généralisation basée sur les exemples. Il est donc possible, avec cette structure, de choisir la représentation adéquate en fonction du problème posé. Pour chaque concept, on dispose de ses exemples concrets et de sa caractérisation. Nous avons aussi constaté que la qualité de la connaissance issue du treillis est liée au choix des concepts (nœuds) à utiliser. La notion de concept formel est comparable à la notion d’hyperrectangle de dimension qui sous-tend des systèmes tels que NGE [WET 94] ou Tabata [BRé 98]. En outre Ying et Wang [YIN 02] présentent un modèle algébrique général de conjectures et d’hypothèses basé sur les treillis et extrapolent sur le fait que des techniques futures en extraction de connaissances s’appuiront sur ce modèle pour aider les chercheurs en physique quantique dans leurs travaux de recherche.
