Présentation
La classification recouvrante, également dénommée classification en classes chevauchantes ou empiétantes (overlapping clustering en anglais) élargit les contraintes du clustering classique en autorisant chaque donnée à figurer dans plusieurs clusters. Des solutions ont été proposées depuis les années 1980 mais elles se sont principalement limitées à des modèles hiérarchiques avec des contributions significatives, réalisées notamment par des scientifiques français et allemands. Cette restriction aux modèles hiérarchiques peut s'expliquer d'un côté par la difficile transposition des modèles de clustering usuels au contexte recouvrant et d'un autre côté par le fait que les autres modèles proposent des solutions alternatives (les techniques de partitionnement flou par exemple). Mais le contexte applicatif a évolué et les utilisateurs qui se « contentaient » de solutions alternatives par obligation, s'intéressent aujourd'hui à des techniques répondant précisément à leurs attentes en terme de classification recouvrante. C'est le cas en particulier pour la recherche d'information (plusieurs thèmes pour un même document), la chimie (plusieurs fonctions biologiques associées à une même molécule) ou la bioinformatique (plusieurs processus métaboliques associés à un même gène). Ignorer le caractère naturellement recouvrant de ces données peut limiter voire biaiser considérablement l'analyse et donc les connaissances extraites. Parfois même, ce sont les données situées dans les recouvrements qui portent l'information nécessaire aux experts du domaine concerné. Sous la « pression » des domaines d'application demandeurs, une nouvelle vague d'études a été lancée ; elle touche actuellement l'ensemble de la communauté internationale et a déjà débouchée sur quelques avancées théoriques récentes (françaises et américaines notamment), en particulier sur les modèles de partitionnement recouvrants et les modèles de mélanges recouvrants.
Participants
Guillaume Cleuziou (LIFO, Orléans)
Lionel Martin (LIFO, Orléans)
Jacques-Henri Sublemontier (LIFO, Orléans)
Christel Vrain (LIFO, Orléans)
Développements logiciels
PoBOC (Pole-Based Overlapping Clustering) lien provisoire
Algorithme de clustering produisant des classes recouvrantes à partir d'une matrice de distance/dissmilarité entre objets. Le nombre de classes à extraire n'est pas fixé a priori.
Réalisé en 2004 dans le cadre de mes travaux de doctorat, PoBOC a été appliqué avec succès au domaine de la classification de mots.
OKM (Overlapping k-means)
Généralisation de l'algorithme bien connu des k-moyennes, OKM génère k classes recouvrantes à partir d'un ensemble d'objets décrit par des vecteurs d'attributs numériques. OKM a été réalisé en 2007 puis utilisé dans des domaines appliqués tels que la bioinformatique (gènes) ou la recherche d'information (textes, mots) et plus théoriques tels que la théorie des fonctions de croyance (initialisation des fonctions de masse).
Une première librairie R pour OKM est disponible ici
Publications majeures associées
Guillaume Cleuziou, Two variants of the OKM for Overlapping Clustering, in Advances in Knowledge Discovery and Management, Springer. 2010.
Guillaume Cleuziou, An extended version of the k-means method for overlapping clustering, in 19th International Conference on Pattern Recognition (ICPR'2008). Pp. 1-4. 2008
G. Cleuziou, L. Martin et C. Vrain, PoBOC: an Overlapping Clustering Algorithm. Application to Rule-Based Classification and Textual Data, in ECAI, R. López de Mántaras, L. Saitta et IOS Press ed., pp.440-444, Valencia, Spain, Proceedings of the 16th European Conference on Artificial Intelligence, August 22-27, 2004
G. Cleuziou, L. Martin, V. Clavier et C. Vrain, DDOC: Overlapping Clustering of Words for Document Classification, in In the proceedings of the 11th International Conference on String Processing and Information Retrieval, Vol.3246, LNCS, pp.127-128, Padova, Italy, Springer, October, 2004
Guillaume Cleuziou, Lionel Martin et Christel Vrain, Disjunctive Learning with a Soft-Clustering Method, in 13th International Conference on Inductive Logic Programming, LNCS ed., Szeged, Hungary, Springer, September, 2003