Massively Distributed Clustering via Dirichlet Process Mixture
Clustering Massivement Distribué via Mélange de Processus de Dirichlet
Résumé
Clustering with accurate results has become a topic of high interest, it is broadly used in many applications such as market research, pattern recognition, data analysis, and image processing. Determining the optimal number of clusters in a dataset is a fundamental issue that opened many directions for research. Multiple methods are then proposed to tackle this bottleneck.Dirichlet Process Mixture (DPM) is a model used for clustering with the advantage of discovering the number of clusters automatically and offering nice properties like, e.g., its potential convergence to the actual clusters in the data. These advantages come at the price of prohibitive response times, which impairs its adoption and makes centralized DPM approaches inefficient.In this thesis, we focus on the problem of parallelizing Dirichlet process mixture to improve performances by exploiting massively distributed environments. Indeed, from the literature, distributing DPM algorithm calls for many issues such as: load balance between computing nodes, communication costs, and the full benefit from DPM properties.In this thesis, we propose two novel approaches for parallel DPM clustering. First, we propose DC-DPM (Distributed Clustering via Dirichlet Process Mixture), a parallel clustering solution that enables clustering of millions of data points while remaining DPM compliant. Our experiments, on both synthetic and real world data, illustrate the high performance of our approach on millions of data points. The centralized algorithm does not scale and has its limit on 100K data points, where it needs more than 7 hours. In this case, our approach needs less than 30 seconds.The second problem we address in this thesis is the high dimensionality of data. In this case, it becomes an important challenge with numerical and theoretical pitfalls. We propose HD4C (High Dimensional Data Distributed Dirichlet Clustering), a distributed clustering solution that addresses the curse of dimensionality by two means. First it gracefully scales to massive datasets by distributed computing. Second, it performs clustering of high dimensional data such as time series (as a function of time), hyperspectral data (as a function of wavelength) etc. Exhaustive experiments are carried out over synthetic and real world datasets to confirm the efficiency of our solution.
La classification non supervisée (ou clustering) a pour objectif d’identifier des classes pertinentes dans les données. elle est largement utilisée dans de nombreuses applications telles que le marketing, la reconnaissance de patterns, l’analyse de données et le traitement d’images. Déterminer le nombre optimal de clusters dans un ensemble de données est un défi fondamental qui a ouvert de nombreuses directions de recherche. De multiples méthodes sont alors proposées pour résoudre ce problème.Le Mélange de Processus de Dirichlet (DPM) est utilisé pour le clustering car il permet de définir automatiquement le nombre de classes, mais les temps de calculs qu’il implique sont généralement trop importants, nuisant à son adoption et rendant inefficaces ses versions centralisées.Dans cette thèse, nous visons le problème de la parallélisation du mélange de processus de Dirichlet pour améliorer ces performances en exploitant des environnements massivement distribués. En effet, d’après la littérature, l’algorithme de DPM distribué fait appel à de nombreux problèmes tels que : l’équilibre de charge entre les nœuds de calcul, les coûts de communication, et le plein bénéfice de propriétés du DPM.Dans cette thèse, nous proposons deux nouvelles approches pour le clustering parallèle via DPM. Tout d’abord, nous proposons DC-DPM (Clustering Distribué via mélange de processus de Dirichlet), une version parallélisée, qui permet le clustering de millions de points de données, ce qui représente un vrai défi. Nos expérimentations, tant sur des données synthétiques que réelles, illustrent la performance de notre approche. Comparativement, l’algorithme centralisé ne passe pas à l’échelle. Son temps de réponse est de plus de 7 heures sur des données de 100K points, quand notre approche prend moins de 30 secondes.Dans un deuxième temps, nous nous intéressons au problème de dimensionnalité de données qui devient un défi important avec les obstacles numériques et théoriques dans ce cas. Nous proposons HD4C (Clustering de Dirichlet Distribué pour des Données de Haute Dimension), une solution de clustering parallèle qui s’adresse à la dimensionnalité par deux moyens. Premièrement, elle s’adapte à des données massives en exploitant les architectures distribuées. Deuxièmement, elle effectue le clustering de données de haute dimension telles que les séries temporelles (en fonction du temps), les données hyperspectrales (en fonction de la longueur d’onde), etc. Nous avons réalisé des expériences exhaustives sur des jeux de données synthétiques et réels pour confirmer l’efficacité de notre solution.
Origine : Version validée par le jury (STAR)