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.

Abstract

This thesis devises and presents the no-mean algorithm, a Bayesian clustering algorithm. Data clustering is a sub-domain of artificial intelligence which aims to gather observations into different groups in an unsupervised fashion. Clustering has a broad range of applications, including (but not limited to) genome classification, data compression or even pattern recognition. By comparing the objects' features, clustering methods organize objects into classes so that objects within the same class are close to each other.Among these methods, the k-means algorithm is one of the most famous. The k-means has a solid foundation, easy to implement, fast and efficient. However, its strong dependence to initial values is a major issue. Multiple initializations lead to different results and the convergence to the optimal solution is not guaranteed. The expectation-maximization (EM) algorithm for mixture models or hierarchical clustering are examples of alternatives to the k-means algorithm. Improvements are often made at the cost of a speed versus performance trade-off. More realistic models offer better results but are more complex and more difficult to compute. Our main objective is to improve the k-means algorithm performance while keeping the same computational complexity. We show the link between the k-means and Gaussian mixtures. The k-means is a special case of the EM algorithm applied to a mixture of Gaussian distributions. We then prove that if a Gaussian prior is assumed on the cluster centers distribution, the k-means is also a special case of the Gibbs sampling applied to fit a Bayesian model with some priors. The Gibbs sampler consists in the successive sampling of centers and then clusters using the conditional distributions.Simulated annealing progressively decreases the variance of the sampled values of a Gibbs sampler by modifying the parameters of the distribution. For a logarithmic rate of decrease of these parameters, the Gibbs sampler converges to the maximum of the sampled distributions. Simulated annealing applied to our Gibbs sampler pushes it to behave like k-means after enough iterations.Integration of the marginal data distribution over cluster centers allows us to conditionally sample the new cluster of an object, given the current partitioning. In this case, the Gibbs sampler can be applied directly to the clusters, without sampling the cluster means, leading to the no-mean algorithm. Our proposed method, the no-mean algorithm, is the Gibbs sampler coupled with simulated annealing.The computational efficiency of our implementation is the main innovation of this work. The computational complexity for one iteration of the no-mean algorithm is competitive with the k-means. Our implementation allows us to sample new clusters for the Gibbs sampler in a constant time, when a basic implementation would have a higher computational complexity. The no-mean provides satisfactory results on simulated datasets, both in terms of performance and computation time. For a given initialization, our algorithm performs better than the k-means 70% of the time. The increase of performance over the k-means is more important as the number of dimensions and clusters increases.