Open source et architecture logicielle

Pierre Schwartz vient de publier sur Developpez.com un article sur l’algorithme K-Means qui est passionnant et qui vulgarise cette méthode de partitionnement des données de façon magistrale. Aussi j’ai souhaité implémenter son algorithme en Java.
Le périmètre se limite à une population dont les individus sont caractérisés par 2 grandeurs ce qui permet de rester dans un plan euclidien.
En première intention je vois l’utilisation de 3 objets :
- DataSet (la population) qui possèdera toutes les méthodes de l’algorithme K-Means
- Point (un individu)
- Centroide (le centre d’un cluster)

Le test devrait s’effectuer de cette facon :

Code java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
 
public class Test {
	public static void main(String[] args) {
		System.out.println("Début de l'algo K-Means");
		//création du dataset
                DataSet dataset = new DataSet(); 
                //injection de la population dans le dataset
		dataset.addData(new Point(1,1));
		dataset.addData(new Point(1,2));
		dataset.addData(new Point(2,2));
		dataset.addData(new Point(4,1));
		dataset.addData(new Point(1,-1));
		dataset.addData(new Point(1,-2));
		dataset.addData(new Point(-2,2));
		dataset.addData(new Point(-4,-1));
		dataset.addData(new Point(5,-1));
		dataset.addData(new Point(1,7));
		dataset.addData(new Point(-2,-8));
		dataset.addData(new Point(-4,6));
		//initialisation de 3 centroides
		dataset.addCentroide(new Centroide(new Point(-1,-2)));
		dataset.addCentroide(new Centroide(new Point(1,4)));
		dataset.addCentroide(new Centroide(new Point(0,1)));
		//l’algo k-means
		dataset.kMeans();
		System.out.println("Fin de l'algo K-Means");
	}
}

Et si nous mettions dans l’algo un espion d’affichage des valeurs des centroides pour chaque étape nous obtiendrions :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
Début de l'algo K-Means
Centroide étape 1 : [center=Point [x=-1.0, y=-2.0], center=Point [x=1.0, y=4.0], center=Point [x=0.0, y=1.0]]
Centroide étape 2 : [center=Point [x=-1.0, y=-3.0], center=Point [x=-0.3333333333333333, y=5.0], center=Point [x=1.8, y=1.0]]
Centroide étape 3 : [center=Point [x=-1.6666666666666667, y=-3.6666666666666665], center=Point [x=-1.6666666666666667, y=5.0], center=Point [x=2.3333333333333335, y=0.6666666666666666]]
Centroide étape 4 : [center=Point [x=-3.0, y=-4.5], center=Point [x=-1.6666666666666667, y=5.0], center=Point [x=2.142857142857143, y=0.2857142857142857]]
Fin de l'algo K-Means

Je laisse les lecteurs vérifier que mes valeurs sont correctes.
Je pars du principe que l’algo K-Means est composé de 3 étapes :
1/ Initialisation des centroïdes
2/ Assignation d’un cluster à chaque centroïde
3/ Recalcul des coordonnées de chaque centroïde pour le positionner en barycentre de son cluster

On boucle sur les 2 dernières étapes tant que calcul de barycentration ne converge pas.

Je proposerai dans un prochain billet (la partie 2) les objets Point et Centroide.