Clustering met Dirichlet Process Mixture Model in Java

• 7 juli 2014
• Vasilis Vryniotis
• . 1 reactie

In de vorige artikelen hebben we de Dirichlet procesmengselmodellen en hoe ze kunnen worden gebruikt bij clusteranalyse. In dit artikel presenteren we een Java-implementatie van twee verschillende DPMM-modellen: het Dirichlet Multivariate Normal Mixture Model dat kan worden gebruikt om Gauss-gegevens te clusteren en het Dirichlet-Multinomial Mixture Model dat wordt gebruikt voor het clusteren van documenten. De Java-code is open source onder de GPL v3-licentie en kan gratis worden gedownload van GitHub.

Update: het Datumbox Machine Learning Framework is nu open-source en gratis voor Download. Bekijk het pakket com.datumbox.framework.machinelearning.clustering om de implementatie van Dirichlet Process Mixture Models in Java te zien.

Dirichlet Process Mixture Model implementatie in Java

De code implementeert het Dirichlet Process Mixture Model met Gibbs Sampler en gebruikt de Apache Commons Math 3.3 als een matrixbibliotheek. Het is gelicentieerd onder GPLv3, dus voel je vrij om het te gebruiken, het aan te passen en vrij te verspreiden en je kunt de Java-implementatie downloaden van GitHub. Merk op dat je alle theoretische delen van de clustermethode kunt vinden in de vorige 5 artikelen en gedetailleerde Javadoc-opmerkingen voor implementatie in de broncode.

Hieronder geven we een beschrijving op hoog niveau van de code:

1. DPMM-klasse

De DPMM is een abstracte klasse en fungeert als basis voor de verschillende modellen, implementeert de Chinees restaurantproces en bevat de Ingestorte Gibbs-sampler​ Het heeft de openbare methode cluster () die de dataset ontvangt als een lijst met punten en verantwoordelijk is voor het uitvoeren van de clusteranalyse. Andere nuttige methoden van de klasse zijn de getPointAssignments () die wordt gebruikt om de clustertoewijzingen op te halen nadat het clusteren is voltooid en de getClusterList () die wordt gebruikt om de lijst met geïdentificeerde clusters op te halen. De DPMM bevat de statische geneste abstracte klasse Cluster; het bevat verschillende abstracte methodes betreffende het beheer van de punten en de schatting van de posterieure pdf die gebruikt worden voor de schatting van de clusteropdrachten.

2. GaussianDPMM-klasse

De GaussianDPMM is de implementatie van Dirichlet Multivariate Normal Mixture Model en breidt de DPMM-klasse uit. Het bevat alle methoden die nodig zijn om de waarschijnlijkheden te schatten onder de veronderstelling van Gauss. Bovendien bevat het de statische geneste klasse Cluster die alle abstracte methoden van de klasse DPMM.Cluster implementeert.

3. MultinomialDPMM-klasse

De MultinomialDPMM implementeert het Dirichlet-Multinomial Mixture Model en breidt de DPMM-klasse uit. Net als de GaussianDPMM-klasse, bevat het alle methoden die nodig zijn om de waarschijnlijkheden te schatten onder de aanname Multinomial-Dirichlet en bevat het de statische geneste klasse Cluster die de abstracte methoden van DPMM.Cluster implementeert.

4. SRS-klasse

De SRS-klasse wordt gebruikt om Simple Random Sampling uit te voeren vanuit een frequentietabel. Het wordt door de Gibbs Sampler gebruikt om de nieuwe clustertoewijzingen in elke stap van het iteratieve proces te schatten.

5. Puntenklasse

De klasse Point dient als een tupel die de gegevens van de record samen met de id opslaat.

6. Apache Commons-wiskundebibliotheek

De Apache Commons Math 3.3 lib wordt gebruikt voor matrixvermenigvuldigingen en het is de enige afhankelijkheid van onze implementatie.

7. DPMMExample klasse

Deze klasse bevat voorbeelden van het gebruik van de Java-implementatie.

Met behulp van de Java-implementatie

De gebruiker van de code kan alle parameters van de mengmodellen configureren, inclusief de modeltypes en de hyperparameters. In het volgende codefragment kunnen we zien hoe het algoritme wordt geïnitialiseerd en uitgevoerd:

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();

Hieronder kunnen we de resultaten zien van het uitvoeren van het algoritme op een synthetische dataset die uit 300 gegevenspunten bestaat. De punten werden oorspronkelijk gegenereerd door 3 verschillende distributies: N ([10,50], I), N ([50,10], I) en N ([150,100], I).

Figuur 1: Scatterplot van demo-dataset

Het algoritme identificeerde na 10 iteraties de volgende 3 clustercentra: [10.17, 50.11], [49.99, 10.13] en [149.97, 99.81]. Omdat we tenslotte alles op een Bayesiaanse manier behandelen, zijn we niet alleen in staat om schattingen van de clustercentra op één punt te geven, maar ook hun kansverdeling door de formule .

Figuur 2: Scatter Plot van waarschijnlijkheden van de centra van clusters

In de figuur hierboven plotten we die kansen; de rode gebieden duiden op een hoge kans om het centrum van een cluster te zijn en zwarte gebieden duiden op een lage waarschijnlijkheid.

Om de Java-implementatie in toepassingen in de echte wereld te gebruiken, moet u externe code schrijven die uw oorspronkelijke dataset in het vereiste formaat converteert. Bovendien kan aanvullende code nodig zijn als u de uitvoer wilt visualiseren zoals we hierboven zien. Merk ten slotte op dat de Apache Commons Math-bibliotheek is opgenomen in het project en dat er dus geen extra configuratie nodig is om de demo's uit te voeren.

Als u de implementatie in een interessant project gebruikt, laat het ons weten en we zullen uw project op onze blog vermelden. Als je het artikel ook leuk vindt, neem dan even de tijd en deel het op Twitter of Facebook.