Estimation robuste des modèles de mélange sur des données distribuées

Un état de l’art sur les méthodes de clustering

Tâche de clustering

La classification implique que les données soient étiquetées, en supposant a priori que les groupes existent (classes). Le problème peut être posé de la manière suivante : considérons l’existence d’un ensemble d’individus X et un autre ensemble Y regroupant les étiquettes associées à chaque individu. Il consiste à apprendre une fonction (modèle) f entre X et Y , telle que Y = f(X).

La procédure de classification supervisée est composée donc de deux étapes : en première étape, un modèle est construit à partir d’un ensemble d’exemples étiquetés par leur classe (phase d’apprentissage). Dans la deuxième étape, les étiquettes des nouveaux objets peuvent être prédites à partir de modèle préalablement appris.

Le clustering implique seulement les données non étiquetées sans aucune information a priori. Il sert à regrouper les objets ayant les mêmes propriétés. Chaque groupe (nommé cluster) doit vérifier deux propriétés principales : une similarité élevée entre ses objets, et une similarité faible avec les autres clusters.

Il existe aussi l’apprentissage semi-supervisé qui utilise un ensemble de données étiquetées et non étiquetées. Il se situe entre l’apprentissage supervisé (toutes les données sont étiquetées) et l’apprentissage non-supervisé (données non étiquetées). Il consiste à construire un classifieur en se basant sur les données étiquetées et à exploiter les données sans étiquettes pour améliorer les performances. Après avoir présenté d’une manière très générale les techniques d’apprentissage (supervisée, non supervisée, semi-supervisée), nous nous concentrons par la suite sur la tâche de clustering. Nous allons montrer d’abord quelles sont les différentes propriétés à examiner sur les algorithmes de clustering.

Critère de choix d’un algorithme de clustering 

Dans le domaine de clustering, il existe très peu de connaissances a priori sur la structure interne de données. Il est donc difficile, même pour un expert, de faire un choix parmi les nombreuses méthodes disponibles. Plusieurs études ont été réalisées afin d’identifier le meilleur algorithme qui peut satisfaire en même temps, l’ensemble des axiomes de bases comme : type de données, formes de clusters, données atypiques [1]. Toutes ces études sont arrivées à la même conclusion : aucun algorithme de clustering n’est meilleur que les autres. Dans la suite, nous allons décrire un ensemble de propriétés liées aux algorithmes de clustering :

– manipulation des données d’entrée (numériques, catégoriques ou mixte) ;
– fonctionnement avec une grande masse de données (passage à l’échelle) ;
– découvrement de clusters avec de formes arbitraires. Celle-ci forme la propriété la plus importante pour choisir une des méthodes de clustering, mais il n’est pas facile de trouver un algorithme qui peut découvrir toutes les formes, en particulier si les données sont catégoriques ;
– traitement des données de grandes dimensions ;
– gestion du problème de présence de données atypiques dans le jeu de données en études ;
– utilisation d’un nombre limité de paramètres définis par les utilisateurs (c’est-à-dire les paramètres en entrée). Ces paramètres peuvent influencer directement les résultats de clustering comme par exemple le nombre de clusters, l’initialisation de clusters, la définition des seuils ;
– réalisation de clustering dur ou flou. Les méthodes de clustering dur consistent à attacher chaque élément à un seul cluster. Les méthodes hiérarchiques correspondent à ce type de clustering [50, 72]. En revanche, les méthodes de clustering flou permettent au même objet, d’être dans plusieurs clusters avec des degrés d’appartenance différents. Le degré d’appartenance d’un objet varie entre 0 et 1. Pour un objet et un cluster donné , plus le degré est proche de 1, plus la tendance d’être liée à ce cluster est forte. Ce type d’algorithmes est très utile dans les cas où les clusters sont chevauchés. Les méthodes probabilistes sont des exemples de méthodes de clustering flou [28]. Il est toujours possible d’obtenir un clustering dur à partir de clustering flou, en associant chaque objet, au cluster dont le degré d’appartenance est maximal.

Les différentes techniques de clustering

Il n’est pas facile de présenter un état de l’art exhaustif de toutes les méthodes existantes. Cependant, nous décrivons dans cette section les principaux types d’approches de clustering. Elles sont regroupées selon des caractéristiques communes. Nous pouvons distinguer : les méthodes hiérarchiques, les méthodes basées sur la densité de points, les méthodes par partitionnement. Notre objectif est de mettre en valeur les différentes propriétés de chaque approche et de pouvoir ainsi motiver notre choix. Nous présentons rapidement les différentes techniques. Mais nous détaillons en particulier les modèles probabilistes (un type de méthode par partitionnement).

Vue générale de notre technique de clustering

Le but de notre approche est de réduire un modèle de mélange en un autre modèle avec un nombre plus petit de composantes. Les résultats des processus de réduction est donc un modèle de mélange (ou modèle de clusters) en regroupant les composantes similaires dans le modèle initial. Nous supposons d’abord que ce modèle est estimé à partir d’un ensemble de données en appliquant un algorithme d’estimation probabiliste (comme EM [28]). Ensuite l’algorithme de réduction est effectué en itérant entre ces deux étapes :

– calculer la distance entre les composantes de modèle initial et réduit afin de trouver les plus proches entre elles ;

– mettre à jour les paramètres du modèle réduit selon les résultats obtenus dans l’étape précédente ;

Notre approche est réalisée donc d’une façon itérative. Elle est appliquée à des composantes de modèles plutôt que des données. Dans la suite nous présentons les différentes techniques de clustering en mettant en valeur leurs propriétés.

Clustering hiérarchique

Les méthodes hiérarchiques , consistent à construire une hiérarchie de clusters, c’est-à-dire un arbre binaire de clusters, nommé dendrogramme . Ce dendrogramme illustre comment les clusters sont liés entre eux. Il permet de représenter les changements dans les clusters par plusieurs niveaux de granularité. Un noeud i à un niveau donné contient ses clusters enfants (fusionnement de ces deux clusters pour former le cluster de i ou division de cluster i en deux clusters enfants) et constitue une partition des objets de ses clusters parents. Les méthodes hiérarchiques sont classées en deux types d’approches, les approches ascendantes et les approches descendantes.

Table des matières

1 Introduction générale
1.1 Contexte : sources de données multiples, modèles probabilistes de mélanges
1.2 Objectif, contributions et plan du document
2 Un état de l’art sur les méthodes de clustering
2.1 Introduction
2.2 Tâche de clustering
2.3 Critère de choix d’un algorithme de clustering
2.4 Les différentes techniques de clustering
2.5 Modèle de mélange
2.6 Modèle du mélange gaussien
2.7 Estimation de paramètres des modèles de mélange
2.8 Problème de la détection des données atypiques
2.9 Conclusion
3 Agrégation robuste des modèles de mélange
3.1 Introduction
3.2 Approximation de la distribution de Student
3.3 Similarité entre des mélanges de Student
3.4 Algorithme de réduction des modèles de mélange
3.5 Algorithme de réduction de mélange de Student
3.6 Expériences
4 État de l’art sur le clustering distribué
4.1 Introduction
4.2 Algorithme de clustering distribué
4.3 Présentation des algorithmes distribués
4.4 Clustering basé sur les modèles probabilistes
4.5 Estimation robuste distribuée
4.6 Diffusion de l’information dans le réseau
4.7 Protocole de gossip
4.8 Conclusion
5 Estimation décentralisée de modèles de mélange
6 Conclusion

Lire le rapport complet