No-Mean Clustering Algorithm

Ce mémoire présente un algorithme d'agrégation (clustering) Bayésien de données, l'algorithme no-mean (sans-moyennes). L'agrégation de données est un domaine de l'intelligence artifielle qui consiste à regrouper des objets dans différentes classes de manière non-supervisée, i.e. sans connaissance a priori sur la nature des classes. Les applications de l'agrégation de données sont nombreuses, de la classification de génomes à la comparaison d'objets mécaniques en passant par la compression de données ou la reconnaissance de formes. L'objectif étant de regrouper les objets de telle sorte que tous les objets d'une même classe soient similaires entre eux. On compare pour cela leurs caractéristiques (features) à l'aide de différentes méthodes.Une des méthodes les plus connues à l'heure actuelle est l'algorithme k-means (k-moyennes). Les causes de son succès sont multiples. Celui-ci est en effet très simple à implémenter, ce qui en fait un outil rapide mais néanmoins efficace. Son principal inconvénient provient de la forte dépendance du résultat à l'initialisation de l'algorithme. Pour un même jeu de données, plusieurs passages de l'algorithme k-means peuvent mener à des résultats différents et souvent sous-optimaux. Les alternatives à cette technique sont nombreuses. On peut citer l'algorithme d'espérance-maximisation pour les modèles de mélanges ou encore les techniques d'agrégation hierarchisées. Ces techniques souffrent bien souvent d'un compromis rapidité-performance où l'optimisation de modèles plus réalistes se fait au coût de calculs plus lourds. Notre objectif est simple : améliorer la performance de k-means tout en gardant la même complexité de calcul, via une approche Bayésienne.Pour cela nous avons tout d'abord montré comment l'algorithme k-means est relié à un modèle de mélanges de Gaussiennes. La minimisation de la variance intra-cluster par k-means est un cas particulier de certains algorithmes qui maximisent la vraisemblance de tels mélanges. Plus précisément, l'optimisation d'un regroupement de données par k-means revient à ajuster un mélange de Gaussiennes à l'aide de l'algorithme d'espérance-maximisation.Sur cette base, nous avons ensuite montré qu'en considérant que les moyennes des agrégats suivaient une distribution normale multi-variée, k-means est également un cas particulier d'échantillonnage de Gibbs appliqué à l'ajustement d'un modèle Bayésien. Cette méthode échantillonne les moyennes d'un groupe en fonction des objets dans celui-ci puis échantillonne le nouveau groupe d'un objet en fonction des moyennes nouvellement calculées. Le recuit simulé est une méthode qui consiste modifier les paramètres d'une distribution dans l'échantillonnage de Gibbs pour diminuer progressivement la variabilité de cet échantillonage. Pour une diminution logarithmique des paramètres d'échelle des distributions dans l'échantillonage, le recuit simulé assure une convergence vers le maximum de ces distributions, i.e., les points les plus probables. Dans notre cas, l'application du recuit simulé permet de faire transiter l'échantillonnage de Gibbs vers le k-means, mais en ayant guidé celui-ci vers des conditions initiales favorables.