Clustering avec Dirichlet Process Mixture Model en Java

• 7 juillet 2014
• Vassilis Vryniotis
• . 1 commentaire

Dans les articles précédents, nous avons discuté en détail Modèles de mélanges de procédés Dirichlet et comment ils peuvent être utilisés dans l'analyse en grappes. Dans cet article, nous présenterons une implémentation Java de deux modèles DPMM différents: le modèle Dirichlet Multivariate Normal Mixture qui peut être utilisé pour regrouper des données gaussiennes et le Dirichlet-Multinomial Mixture Model qui est utilisé pour regrouper des documents. Le code Java est open source sous licence GPL v3 et peut être téléchargé gratuitement depuis Github.

Mise à jour: le Datumbox Machine Learning Framework est désormais open-source et gratuit pour download. Consultez le package com.datumbox.framework.machinelearning.clustering pour voir l'implémentation de Dirichlet Process Mixture Models en Java.

Implémentation du Dirichlet Process Mixture Model en Java

Le code implémente le Dirichlet Process Mixture Model avec Gibbs Sampler et utilise Apache Commons Math 3.3 comme bibliothèque matricielle. Il est sous licence GPLv3 alors n'hésitez pas à l'utiliser, à le modifier et à le redistribuer librement et vous pouvez télécharger l'implémentation Java depuis Github. Notez que vous pouvez trouver toutes les parties théoriques de la méthode de clustering dans les 5 articles précédents et les commentaires Javadoc détaillés pour l'implémentation dans le code source.

Ci-dessous, nous listons une description de haut niveau du code:

1. Classe DPMM

Le DPMM est une classe abstraite et agit comme une base pour les différents modèles différents, implémente le Processus de restaurant chinois et contient le Sampler de Gibbs effondré. Il a la méthode publique cluster () qui reçoit l'ensemble de données sous forme de liste de points et est responsable de l'exécution de l'analyse de cluster. D'autres méthodes utiles de la classe sont getPointAssignments () qui est utilisé pour récupérer les attributions de cluster une fois le clustering terminé et getClusterList () qui est utilisé pour obtenir la liste des clusters identifiés. Le DPMM contient la classe abstraite imbriquée statique Cluster; il contient plusieurs méthodes abstraites concernant la gestion des points et l'estimation du pdf postérieur qui sont utilisées pour l'estimation des attributions de grappes.

2. Classe GaussianDPMM

Le GaussianDPMM est l'implémentation de Dirichlet Multivariate Normal Mixture Model et étend la classe DPMM. Il contient toutes les méthodes nécessaires pour estimer les probabilités sous l'hypothèse gaussienne. De plus, il contient la classe imbriquée statique Cluster qui implémente toutes les méthodes abstraites de la classe DPMM.Cluster.

3. Classe MultinomialDPMM

Le MultinomialDPMM implémente le modèle de mélange Dirichlet-Multinomial et étend la classe DPMM. De la même manière que la classe GaussianDPMM, elle contient toutes les méthodes nécessaires pour estimer les probabilités sous l'hypothèse Multinomial-Dirichlet et contient la classe imbriquée statique Cluster qui implémente les méthodes abstraites de DPMM.Cluster.

4. Classe SRS

La classe SRS est utilisée pour effectuer un échantillonnage aléatoire simple à partir d'une table de fréquences. Il est utilisé par l'échantillonneur Gibbs pour estimer les nouvelles affectations de grappes à chaque étape du processus itératif.

5. Classe de points

La classe Point sert de tuple qui stocke les données de l'enregistrement avec son identifiant.

6. Bibliothèque de mathématiques Apache Commons

La librairie Apache Commons Math 3.3 est utilisée pour les multiplications matricielles et c'est la seule dépendance de notre implémentation.

7. Classe DPMMExample

Cette classe contient des exemples d'utilisation de l'implémentation Java.

Utilisation de l'implémentation Java

L'utilisateur du code est en mesure de configurer tous les paramètres des modèles de mélange, y compris les types de modèles et les hyperparamètres. Dans l'extrait de code suivant, nous pouvons voir comment l'algorithme est initialisé et exécuté:

List<Point> pointList = new ArrayList<>();
//add records in pointList

//Dirichlet Process parameter
Integer dimensionality = 2;
double alpha = 1.0;

//Hyper parameters of Base Function
int kappa0 = 0;
int nu0 = 1;
RealVector mu0 = new ArrayRealVector(new double[]{0.0, 0.0});
RealMatrix psi0 = new BlockRealMatrix(new double[][]{{1.0,0.0},{0.0,1.0}});

//Create a DPMM object
DPMM dpmm = new GaussianDPMM(dimensionality, alpha, kappa0, nu0, mu0, psi0);

int maxIterations = 100;
int performedIterations = dpmm.cluster(pointList, maxIterations);

//get a list with the point ids and their assignments
Map<Integer, Integer> zi = dpmm.getPointAssignments();

Ci-dessous, nous pouvons voir les résultats de l'exécution de l'algorithme sur un ensemble de données synthétiques composé de 300 points de données. Les points ont été générés à l'origine par 3 distributions différentes: N ([10,50], I), N ([50,10], I) et N ([150,100], I).

Figure 1: Diagramme de dispersion de l'ensemble de données de démonstration

Après avoir exécuté 10 itérations, l'algorithme a identifié les 3 centres de cluster suivants: [10.17, 50.11], [49.99, 10.13] et [149.97, 99.81]. Enfin, comme nous traitons tout de manière bayésienne, nous pouvons non seulement fournir des estimations ponctuelles des centres de grappes, mais aussi leur distribution de probabilité en utilisant le formule .

Figure 2: Diagramme de dispersion des probabilités des centres de grappes

Dans la figure ci-dessus, nous traçons ces probabilités; les zones rouges indiquent une forte probabilité d'être le centre d'une grappe et les zones noires indiquent une faible probabilité.

Pour utiliser l'implémentation Java dans des applications du monde réel, vous devez écrire du code externe qui convertit votre jeu de données d'origine au format requis. De plus, du code supplémentaire peut être nécessaire si vous souhaitez visualiser la sortie comme nous le voyons ci-dessus. Notez enfin que la bibliothèque Apache Commons Math est incluse dans le projet et donc aucune configuration supplémentaire n'est requise pour exécuter les démos.

Si vous utilisez l'implémentation dans un projet intéressant, écrivez-nous et nous présenterons votre projet sur notre blog. De plus, si vous aimez l'article, veuillez prendre un moment et le partager sur Twitter ou Facebook.