[java] Centres mobiles / K-means / Formes fortes

[ToTo13]

Bonjour,

voilà deux classes permettant d'effectuer le calcul des centres mobiles / K-moyennes (en anglais k-means).
La différence entre les centres mobiles et les K-moyennes est que les K-moyennes recalculent le barycentre d'une classe après chaque affectation d'un individu à la dite classe. Cela permet souvent de converger plus rapidement vers la solution.

Ici c'est une version des k-moyennes et une version des centres mobiles dans la réponse suivante.

Cette classe utilise des données contenues dans un fichier tabulé afin d'être générique et ainsi de pouvoir s'appliquer à tous les problèmes

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
 
package rdf.clustering;
 
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
 
import utils.chronometre.Chronometre;
 
import fichiersdossiers.fichiersTabules.FichierTabule;
 
import mathematiques.metriques.Metric;
import mathematiques.primitives.pointstiti.Point3DI;
import mathematiques.primitives.pointstiti.PointND;
import mathematiques.statistiques.StandardizeData;
 
/**
 * <p>Description : Cette classe implemente l'algorithme des K-moyennes (K-Means). Une heuristique est disponible afin que si on le souhaite, aucun cluster
 *  (classe) ne soit vide (sans aucun individu).<br>
 *  Lire "Dat mining et statistiques decisionnelle" par Stephane Tuffery, chez les editions TECHNIP.</p>
 * <p>Packages necessaires : affichages, mathematiques.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * <p>Dernieres modifications :<br>
 * 20 Juillet 2008, 2.0 => Separation entre "Centres mobiles" et "K-means".<br>
 * 30 Avril 2008 => Correction de bugs lies a la standardisation des donnees & Ajout des methodes "ComputeAndReturnBestRepresentant" et du chrono.<br>
 * 29 Avril 2008, 1.2 => Ajout de la possibilite de d'initialiser les barycentre avant calculs.<br>
 * 21 Avril 2008 => Correction de bug majeur pour le cas "UnIndividuParClusterMinimum", ajout d'une securite pour un cas non gere.<br>
 *               => Ajout d'une securite pour le cas des nombre "NaN".<br>
 * 18 Avril 2008, 1.1 => Ajout de la possibilite de passer un fichier tabule dans un constructeur.<br>
 * 24 Octobre 2007 => Ajout d'une metrique en parametre. Elle sera utilisee pour tout ce qui est calcul de distances.<br>
 *                 => Ajout du calcul des erreurs de clustering : Inertie inter classe et intra classe.<br>
 * 15 Octobre 2007 => Creation.</p>
 * 
 * @author Guillaume THIBAULT
 * @version 2.0
 */
 
public class KMeans
{
 
/** Nombre d'iterations qui furent necessaires pour converger lors du dernier calcul.*/
protected int nbIterations = 0 ;
/** L'erreur a minimiser pour pouvoir finir.*/
protected double Epsilon = 1.0 ;
/** Le tableau contenant les donnees sur lesquelles ont va travailler.*/
protected double[][] Tableau = null ;
/** Tableau contenant les barycentres des clusters. Il est utile pour calculer le deplacement entre deux iteraitons.*/
protected double[][] Barycentres = null ;
/** Nombre de cluster (de classes).*/
protected int nbClusters = 0 ;
/** Nombre d'individus (d'instances) sur lesquels on va travailler <=> Nombre de lignes du tableau.*/
protected int nbIndividus = 0 ;
/** Dimensions du probleme <=> Nombre de colonnes <=> Taille du vecteur caracteristique.*/
protected int nbDimensions = 0 ;
/** Tableau qui contiendra pour chaque individu a quel cluster (classe) il appartient.*/
protected int[] ClusterResultat = null ;
/** Tableau contenant la distance entre un individu et le barycentre de sa classe.*/
protected double[] DistanceResultat = null ;
protected double InertieIntraClasse = -1.0 ;
protected double InertieInterClasse = -1.0 ;
/**Tableau contenant tous les clusters (classes).*/
protected Cluster[] Clusters = null ;
/** Metrique a utiser pour le calcul.*/
protected Metric metrique = null ;
/** Tableau contenant l'indice du meilleur representant pour chaque classe.*/
protected int[] BestRepresentant = null ;
/** Classe permettant de standardiser les donnees.*/
protected StandardizeData sd = null ;
 
 
 
/** Un constructeur (le seul) auquel il faut passer imperativement une metrique qui sera celle utilise par cette instanciation.
 * @param metrique La metrique a utiliser pour calculer les distances entre barycentres.*/
public KMeans(Metric metrique)
	{
	if ( metrique == null ) throw new Error("Métrique = null") ;
	this.metrique = metrique ;
	sd = new StandardizeData() ;
	}
 
 
/** Une methode qui va faire les verifications necessaires puis lancer les calculs.
 * @param Tableau Le tableau contenant toutes les valeurs des individus : les individus sont sur les lignes et leurs caracteristiques en colonnes.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(double[][] Tableau, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire,
						double[][] Barycentres,	Chronometre Chrono)
	{
	if ( Tableau == null ) throw new Error("Tableau = null.") ;
 
	this.nbIndividus = Tableau.length ;
	this.nbDimensions = Tableau[0].length ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	this.Tableau = null ;
	this.Tableau = new double[Tableau.length][Tableau[0].length] ;
	for (int i=0 ; i < Tableau.length ; i++)
		for (int d=0 ; d < Tableau[0].length ; d++)
			this.Tableau[i][d] = Tableau[i][d] ;
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, Chrono) ;
	}
 
 
 
/** Une methode qui va faire les verifications necessaires puis lancer les calculs.
 * @param fichier Le fichier tabule contenant toutes les valeurs des individus : les individus sont sur les lignes et leurs caracteristiques en colonnes.
 * @param nbClusters Nombre de clusters (classes) que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(FichierTabule fichier, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire,
						double[][] Barycentres, Chronometre Chrono)
	{
	if ( fichier == null ) throw new Error("fichier = null.") ;
 
	int i, hauteur, largeur ;
	int Largeur = fichier.getLargeur() ;
	int Hauteur = fichier.getHauteur() ;
	int num, ligne, colonne = 0 ; // On remplit le tableau.
	int[] colonneint = null ;
	double[] colonnedouble = null ;
 
	List<Integer> NumColonnes = new Vector<Integer>() ; // On regarde quelles sont les colonnes exploitables : Valide, non nominale et de type int ou double.
	for (i=0 ; i < Largeur ; i++)
		if ( !fichier.isExcludedColumn(i) && !fichier.isNominal(i) &&
			(fichier.getTypeColonne(i) == FichierTabule.INTEGER || fichier.getTypeColonne(i) == FichierTabule.DOUBLE) )
			NumColonnes.add(i) ;
	largeur = NumColonnes.size() ;
	if ( largeur == 0 ) throw new Error("Aucune caracteristique exploitable dans ce fichier.") ;
 
	hauteur = 0 ; // On compte le nombre d'instances (lignes) valides.
	boolean[] Exclude = fichier.getExcluded() ;
	for (i=0 ; i < Exclude.length ; i++)
		if ( !Exclude[i] )
			hauteur++ ;
 
	this.nbIndividus = hauteur ; // On alloue et affecte ce qui doit l'être.
	this.nbDimensions = largeur ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
	Tableau = new double[hauteur][largeur] ;
 
	Iterator<Integer> iter = NumColonnes.iterator() ;
	while ( iter.hasNext() ) // On parcours les colonnes
		{
		num = iter.next() ;
		ligne = 0 ;
		switch ( fichier.getTypeColonne(num) ) // On ajoute les colonnes au tableau.
			{
			case FichierTabule.INTEGER :
				colonneint = fichier.getColumnInt(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonneint[i] ;
				break ;
			case FichierTabule.DOUBLE :
				colonnedouble = fichier.getColumnDouble(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonnedouble[i] ;
				break ;
			default : throw new Error("Type de colonne incorrect.") ;
			}
		colonne++ ;
		}
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, Chrono) ; // On lance le calcul
	}
 
 
 
/** Une methode qui prend en parametre une liste de points, puis la transforme en tableau afin d'effectuer les calculs.
 * Elle va faire les verifications necessaires puis lancer le calcul.
 * @param Liste Une liste de points 2D que l'on va convertir en tableau representant les individus et leurs descripteurs.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.*/
public void Calculer(List<PointND> Liste, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycentres)
	{
	if ( Liste == null ) throw new Error("Liste = null") ;
 
	this.nbIndividus = Liste.size() ;
	this.nbDimensions = Liste.get(0).getDimension() ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	Tableau = null ;
	Tableau = new double[nbIndividus][nbDimensions] ;
 
	int nb = 0 ;
	PointND point = null ;
	Iterator<PointND> iter = Liste.iterator() ;
	while ( iter.hasNext() )
		{
		point = iter.next() ;
		for (int j=0 ; j < nbDimensions ; j++)
			Tableau[nb][j] = point.get(j) ;
		nb++ ;
		}
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, null) ;
	}
 
 
 
/** Une methode qui prend en parametre une liste de points, puis la transforme en tableau afin d'effectuer les calculs.
 * Il va faire les verifications necessaires puis lancer les calculs.
 * @param Liste Une liste de points 2D que l'on va convertir en tableau representant les individus et leurs descripteurs.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.*/
public void Calculer(Vector<Point3DI> Liste, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycentres)
	{
	Tableau = null ;
	Tableau = new double[Liste.size()][2] ;
	for (int i=0 ; i < Tableau.length ; i++)
		{
		Tableau[i][0] = Liste.get(i).getX() ;
		Tableau[i][1] = Liste.get(i).getY() ;
		}
 
	this.nbIndividus = Tableau.length ;
	this.nbDimensions = 2 ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, null) ;
	}
 
 
 
 
 
 
/** Methode qui gere la totalite des calculs.
 * @param nbClusters Le nombre de Clusters que l'on souhaite.
 * @param Epsilon Le seuil d'arret : si la somme des distances entre les anciens barycentres des clusters et les nouveaux est inferieure a Epsilon,
 *  on arrete.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycenters Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
private void Calculer(int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycenters, Chronometre Chrono)
	{
	Clusters = null ;
	ClusterResultat = null ;
	DistanceResultat = null ;
 
	if ( nbClusters < 2 ) throw new Error("Nombre de clusters incorrects : " + nbClusters + " (attendu > 1).") ;
	if ( nbIndividus < nbClusters ) throw new Error("Il y a plus de clusters (" + nbClusters + ") que d'individus (" + nbIndividus + ").") ;
 
	if ( Chrono != null )
		{
		System.out.print("Calcul des k-means => ") ;
		Chrono.setMarqueur() ;
		}
 
	if ( CentrerReduire ) sd.Compute(Tableau) ;
 
	int i, j ;
	Clusters = new Cluster[nbClusters] ;
	for (i=0 ; i < nbClusters ; i++) Clusters[i] = new Cluster(i, nbDimensions) ;
 
	if ( Barycenters == null ) PlacerBarycentresAleatoirement() ;
	else
		{
		if ( Barycenters[0].length != nbDimensions ) throw new Error("Dimension des barycentres différente du nombre de dimensions (caractéristiques).") ;
		if ( Barycenters.length != nbClusters ) throw new Error("Nombre de barycentre différent du nombre de classes (individus).") ;
		if ( CentrerReduire )
			{
			double val ;
			double[] moyennes = sd.getMoyennes() ;
			double[] ecartstypes = sd.getEcartsTypes() ;
			for (i=0 ; i < nbClusters ; i++) // On affecte les barycentres en standardisant les valeurs.
				for (j=0 ; j < nbDimensions ; j++)
					{
					val = Barycenters[i][j] ;
					val = (val - moyennes[j]) / ecartstypes[j] ;
					Clusters[i].getBarycentre().set(j, val) ;
					}
			}
		else
			for (i=0 ; i < nbClusters ; i++)
				Clusters[i].setBarycentre(Barycenters[i]) ;
		}
 
	ClusterResultat = new int[nbIndividus] ;
	DistanceResultat = new double[nbIndividus] ;
 
	Barycentres = new double[nbClusters][nbDimensions] ; // On crée le tableau contenant les barycentres et on copie (sauvegarde) les valeurs.
	double[] bary = null ;
	for (i=0 ; i < nbClusters ; i++)
		{
		bary = Clusters[i].getBarycentre().get() ;
		for (j=0 ; j < nbDimensions ; j++)
			Barycentres[i][j] = bary[j] ;
		}
	bary = null ;
 
	for (i=0 ; i < nbClusters ; i++) Clusters[i].setNbIndividus(0) ;
 
	nbIterations = 0 ;
	while ( Converger(UnIndividuParClusterMinimum) > Epsilon ) nbIterations++ ;
 
	CalculerInertieIntraClasse() ;
	CalculerErreurInterClasse() ;
 
	if ( Chrono != null ) System.out.println(Chrono.getTimeSinceMarqueurSecondes() + "s, " + nbIterations + " itérations") ;
	}
 
 
 
/** Methode qui place aleatoirement le barycentre de chaque cluster pour l'initialisation.*/
private void PlacerBarycentresAleatoirement()
	{
	int x, y ;
	double[] min = new double[nbDimensions] ;
	double[] max = new double[nbDimensions] ;
	double[] barycentre = new double[nbDimensions] ;
 
	for (x=0 ; x < nbDimensions ; x++) min[x] = max[x] = Tableau[0][x] ;
 
	for (x=0 ; x < nbDimensions ; x++)
		if ( Double.isNaN(min[x]) ) throw new Error("NaN, ligne 0, colonne " + x) ;
 
	for (y=1 ; y < nbIndividus ; y++)
		for (x=0 ; x < nbDimensions ; x++)
			{
			if ( Double.isNaN(Tableau[y][x]) ) throw new Error("NaN, ligne " + y + ", colonne " + x) ;
			if ( min[x] > Tableau[y][x] ) min[x] = Tableau[y][x] ;
			if ( max[x] < Tableau[y][x] ) max[x] = Tableau[y][x] ;
			}
 
	for (y=0 ; y < nbClusters ; y++)
		{
		for (x=0 ; x < nbDimensions ; x++)
			barycentre[x] = min[x] + Math.random()*(max[x]-min[x]) ;
		Clusters[y].setBarycentre(barycentre) ;
		}
	}
 
 
 
/** Methode que l'on va iterer jusqu'a converger vers la solution (jusqu'a ce que l'on soit inferieur au critere d'arret).
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @return La distance totale de deplacement entre les anciens barycentres des clusters et les nouveaux.*/
private double Converger(boolean UnIndividuParClusterMinimum)
	{
	if ( nbIterations == 0 ) PremiereIteration(UnIndividuParClusterMinimum) ;
	else TrouverClusterPlusProche(UnIndividuParClusterMinimum) ;
	return CalculerDeplacements() ;
	}
 
 
 
/** Methode qui trouve le Cluster le plus proche de chaque individu.
 * @param UnIndividuParClusterMinimum Est ce que l'on applique l'heuristique ?*/
private void PremiereIteration(boolean UnIndividuParClusterMinimum)
	{
	int i, c ;
	double Distance ;
 
	for (i=0 ; i < nbIndividus ; i++)
		{
		ClusterResultat[i] = 0 ;
		DistanceResultat[i] = metrique.Distance(Tableau[i], Clusters[0].getBarycentre().get()) ;
		if ( Double.isNaN(DistanceResultat[i]) ) throw new Error("NaN trouvé lors d'un calcul de distance => individu " + i + ", cluster 0.") ;
		for (c=1 ; c < nbClusters ; c++)
			{
			Distance = metrique.Distance(Tableau[i], Clusters[c].getBarycentre().get()) ;
			if ( Double.isNaN(Distance) ) throw new Error("NaN trouvé lors d'un calcul de distance => individu " + i + ", cluster " + c + ".") ;
			if ( Distance < DistanceResultat[i] )
				{
				DistanceResultat[i] = Distance ;
				ClusterResultat[i] = c ;
				}
			}
		AjouterIndividu(i, ClusterResultat[i]) ;
		}
 
	if ( UnIndividuParClusterMinimum )
		{
		int nummax ;
		boolean Erreur = true ;
		while ( Erreur )
			{
			Erreur = false ;
			for (c=0 ; c < nbClusters ; c++)
				if ( Clusters[c].getNbIndividus() == 0 ) // Si un cluster n'a pas d'individu
					{
					nummax = 0 ;
					for (i=1 ; i < nbIndividus ; i++) // On trouve l'individu qui est le plus loin (de son cluster).
						if ( DistanceResultat[i] > DistanceResultat[nummax] ) nummax = i ;
					Clusters[c].setBarycentre(Tableau[nummax]) ; // On lui ajoute celui est le plus loin de son cluster.
					Clusters[c].setNbIndividus(1) ; // On met a un son nombre d'individu, car maintenant il en a un.
					Clusters[ClusterResultat[nummax]].DecrementerNbIndividus(1) ; // On decremente le compteur du cluster auquel il appartenait.
					if ( Clusters[ClusterResultat[nummax]].getNbIndividus() == 0 ) Erreur = true ;
					ClusterResultat[nummax] = c ; // On modifie son Cluster d'appartenance.
					DistanceResultat[nummax] = 0.0 ; // Il est SUR son nouveau Cluster, donc sa distance est nulle.
					}
			}
		}
 
	}
 
 
/** Methode qui trouve le Cluster le plus proche de chaque individu.
 * @param UnIndividuParClusterMinimum Est ce que l'on applique l'heuristique ?*/
private void TrouverClusterPlusProche(boolean UnIndividuParClusterMinimum)
	{
	int i, c, ClusterR ;
	double Distance, DistanceR ;
 
	for (i=0 ; i < nbIndividus ; i++)
		{
		ClusterR = 0 ;
		DistanceR = metrique.Distance(Tableau[i], Clusters[0].getBarycentre().get()) ;
		if ( Double.isNaN(DistanceResultat[i]) ) throw new Error("NaN trouvé lors d'un calcul de distance => individu " + i + ", cluster 0.") ;
		for (c=1 ; c < nbClusters ; c++)
			{
			Distance = metrique.Distance(Tableau[i], Clusters[c].getBarycentre().get()) ;
			if ( Double.isNaN(Distance) ) throw new Error("NaN trouvé lors d'un calcul de distance => individu " + i + ", cluster " + c + ".") ;
			if ( Distance < DistanceR )
				{
				DistanceR = Distance ;
				ClusterR = c ;
				}
			}
		AjouterIndividu(i, ClusterR) ;
		SupprimerIndividu(i, ClusterResultat[i]) ;
		ClusterResultat[i] = ClusterR ;
		DistanceResultat[i] = DistanceR ;
		}
	}
 
 
 
/** Methode qui permet d'ajouter un individu a un cluster : incremente son compteur et met a jour son barycentre.
 * @param num Le numero de l'individu.
 * @param cluster Le numero du cluster auquel ajouter l'individu.*/ 
protected void AjouterIndividu(int num, int cluster)
	{
	double nb = Clusters[cluster].getNbIndividus() ;
	double[] barycentre = Clusters[cluster].getBarycentre().get() ;
	for (int i=0 ; i < nbDimensions ; i++)
		barycentre[i] = (barycentre[i]*nb + Tableau[num][i]) / (nb + 1.0) ;
	Clusters[cluster].IncrementerNbIndividus(1) ;
	}
 
 
 
/** Methode qui permet de supprimer un individu d'un cluster : decremente son compteur et met a jour son barycentre.
 * @param num Le numero de l'individu.
 * @param cluster Le numero du cluster auquel ajouter l'individu.*/ 
protected void SupprimerIndividu(int num, int cluster)
	{
	double nb = Clusters[cluster].getNbIndividus() ;
	double[] barycentre = Clusters[cluster].getBarycentre().get() ;
 
	if ( Clusters[cluster].getNbIndividus() <= 0 ) throw new Error("Gros souci...") ; // ---------------------------------------------------------
 
	if ( Clusters[cluster].getNbIndividus() == 1 )
		for (int i=0 ; i < nbDimensions ; i++) barycentre[i] = 0.0 ;
	else
		for (int i=0 ; i < nbDimensions ; i++)
			barycentre[i] = (barycentre[i]*nb - Tableau[num][i]) / (nb - 1.0) ;
	Clusters[cluster].DecrementerNbIndividus(1) ;
	}
 
 
 
/** Methode qui calcule la somme des deplacements des barycentres des clusters.
 * @return La somme des distances (deplacements) entre les anciens barycentres des clusters et les nouveaux.*/
private double CalculerDeplacements()
	{
	int i, j ;
	double Distance = 0.0 ;
	double[] bary = null ;
 
	for (i=0 ; i < nbClusters ; i++) // On calcule la somme des déplacements.
		Distance += metrique.Distance(Clusters[i].getBarycentre().get(), Barycentres[i]) ;
 
	for (i=0 ; i < nbClusters ; i++) // On sauvegarde les nouveaux barycentres.
		{
		bary = Clusters[i].getBarycentre().get() ;
		for (j=0 ; j < nbDimensions ; j++)
			Barycentres[i][j] = bary[j] ;
		}
	bary = null ;
 
	return Distance ;
	}
 
 
 
 
 
 
/** Cette methode calcule l'inertie intra-classe de chaque cluster : La somme du carre des distance entre chaque individu d'une classe et le barycentre 
 *  de cette classe.*/
private void CalculerInertieIntraClasse()
	{
	int i ;
	double[] TabInertieIntraClasse = new double[nbClusters] ;
 
	for (i=0 ; i < nbClusters ; i++)
		{
		TabInertieIntraClasse[i] = 0.0 ;
		Clusters[i].setNbIndividus(0) ;
		}
 
	for (i=0 ; i < nbIndividus ; i++)
		{
		TabInertieIntraClasse[ClusterResultat[i]] += Math.pow(metrique.Distance(Clusters[ClusterResultat[i]].getBarycentre().get(), Tableau[i]), 2.0) ;
		Clusters[ClusterResultat[i]].IncrementerNbIndividus(1) ;
		}
 
	InertieIntraClasse = 0.0 ;
	for (i=0 ; i < nbClusters ; i++)
		{
		TabInertieIntraClasse[i] /= (double)Clusters[i].getNbIndividus() ;
		InertieIntraClasse += TabInertieIntraClasse[i] ;
		Clusters[i].setInertieIntraClasse(TabInertieIntraClasse[i]) ;
		}
 
	TabInertieIntraClasse = null ;
	}
 
 
 
/** Methode qui calcule inertie inter-classe : la somme du carre des distance entre le barycentre de tous les individus et le barycentre de chaque Cluster.*/
private void CalculerErreurInterClasse()
	{
	int i, j ;
	double[] Barycentre = new double[nbDimensions] ;
 
	for (i=0 ; i < nbIndividus ; i++)
		for (j=0 ; j < nbDimensions ; j++)
			Barycentre[j] += Tableau[i][j] ;
 
	InertieInterClasse = 0.0 ;
	for (i=0 ; i < nbClusters ; i++)
		InertieInterClasse += Clusters[i].getNbIndividus() * Math.pow(metrique.Distance(Barycentre, Clusters[i].getBarycentre().get()), 2.0) ;
 
	InertieInterClasse /= (double)nbIndividus ;
	Barycentre = null ;
	}
 
 
 
 
/** Methode permettant de calculer le meilleur representant de chaque classe. Attention le calcul ne peut etre fait dans le cas d'un fichier tabule
 *  contenant des instances non valides.*/
public void ComputeBestRepresentant()
	{
	int i ;
	BestRepresentant = new int[nbClusters] ;
 
	for (i=0 ; i < nbIndividus ; i++)
		BestRepresentant[ClusterResultat[i]] = i ;
 
	for (i=0 ; i < nbIndividus ; i++)
		if ( DistanceResultat[i] < DistanceResultat[BestRepresentant[ClusterResultat[i]]] )
			BestRepresentant[ClusterResultat[i]] = i ;
	}
 
 
 
 
/** Methode qui permet de calculer puis d'extraire les meilleurs representants d'un ensemble d'instances.
 * @return Un fichier tabule contenant le meilleur representant de chaque classe.*/
public FichierTabule ComputeAndReturnBestRepresentant(FichierTabule fichier)
	{
	if ( fichier == null) throw new Error("Le calcul n'a pas été effectué à partir d'un fichier tabulé, donc impossible d'en renvoyer un en résultat.") ;
 
	int i, j, best ;
	int[] Types = null ; 
	FichierTabule Resultat = null ;
	boolean[] Excluded = fichier.getExcluded() ;
 
	for (i=0 ; i < Excluded.length ; i++)
		if ( Excluded[i] )
			throw new Error("Le fichier contient des instances exclues (invalides), on ne peut effectuer le calcul.") ;
 
	Types = fichier.getTypeColonnes() ;
	Resultat = new FichierTabule(nbClusters, Types) ;
 
	ComputeBestRepresentant() ; // On calcule les meilleurs representants.
 
	for (i=0 ; i < nbClusters ; i++)
		{
		best = BestRepresentant[i] ;
		for (j=0 ; j < fichier.getLargeur() ; j++)
			switch ( Types[j] )
				{
				case FichierTabule.INTEGER :
					Resultat.setValue(i, j, fichier.getValueInt(best, j)) ;
					break ;
				case FichierTabule.DOUBLE :
					Resultat.setValue(i, j, fichier.getValueDouble(best, j)) ;
					break ;
				case FichierTabule.STRING :
					Resultat.setValue(i, j, fichier.getValueString(best, j)) ;
					break ;
				case FichierTabule.INCONNU :
					break ;
				default : throw new Error("Type de colonne invalide : " + Types[j]) ;
				}
		}
 
	return Resultat ;
	}
 
 
 
 
 
/** Methode qui permet de calculer puis d'extraire les meilleurs representants d'un ensemble d'instances.<br>
 * Attention : methode ne pouvant pas fonctionner si la source etait un fichier avec des instances exclues (invalides).
 * @return Un tableau de double contenant le meilleur representant de chaque classe.*/
public double[][] ComputeAndReturnBestRepresentants()
	{
	int i, j, best ;
	double[][] Resultat = new double[nbClusters][nbDimensions] ;
 
	ComputeBestRepresentant() ; // On calcule les meilleurs representants.
 
	for (i=0 ; i < nbClusters ; i++)
		{
		best = BestRepresentant[i] ;
		for (j=0 ; j < Tableau[i].length ; j++)
			Resultat[i][j] = Tableau[best][j] ;
		}
 
	return Resultat ;
	}
 
 
 
 
 
 
/* ------------------------------------------------------------ Les getters ------------------------------------------------------------ */
 
/** Methode qui renvoit le tableau contenant des individus etant les meilleurs representants de leurs classes (les plus proches).
 * @return Les numeros d'individus.*/
public int[] getBestRepresentant()
	{
	return BestRepresentant ;
	}
 
/** Methode qui renvoit le tableau contenant les numeros de clusters (classes) auquels appartiennent les instances.*/
public int[] getClusterResultat()
	{
	return ClusterResultat ;
	}
 
/** Methode qui renvoit le tableau contenant tous les clusters.
 * @return Les clusters.*/
public Cluster[] getClusters()
	{
	return Clusters ;
	}
 
/** Methode qui renvoit les distances entres les individus et le barycentre du cluster auquel ils appartiennent.
 * @return Les distances.*/
public double[] getDistanceResultat()
	{
	return DistanceResultat ;
	}
 
public double getEpsilon()
	{
	return Epsilon ;
	}
 
public void setEpsilon(double Epsilon)
	{
	this.Epsilon = Epsilon ;
	}
 
public int getNbClusters()
	{
	return nbClusters ;
	}
 
/** Nombre de dimensions (caracteristiques <=> nb colonnes) du probleme.
 * @return Le nombre de dimensions.*/
public int getNbDimensions()
	{
	return nbDimensions ;
	}
 
/** Nombre d'instances du tableau (de lignes).
 * @return Le nombre de lignes.*/
public int getNbIndividus()
	{
	return nbIndividus ;
	}
 
/** Methode qui retourne l'inertie inter classe de la population, peut egalement etre appele l'erreur inter classe.<br>
 * La somme du carre des distance ponderees entre le barycentre de tous les individus et le barycentre de chaque Cluster.
 * @return L'inertie inter classe.*/
public double getInertieInterClasse()
	{
	return InertieInterClasse ;
	}
 
/** Methode qui retourne l'inertie intra classe de la population : La somme du carre des distance entre chaque individu d'une classe et le barycentre 
 *  de cette classe.
 * @return L'inertie intra classe.*/
public double getInertieIntraClasse()
	{
	return InertieIntraClasse ;
	}
 
public int getNbIterations()
	{
	return nbIterations ;
	}
 
/** Le tableau sur lequel a ete effectue le clustering.
 * @return Le tableau de double.*/
public double[][] getTableau()
	{
	return Tableau ;
	}
}

[ToTo13]

La classe permettant le calcul des centres mobiles :

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
 
package rdf.clustering;
 
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
 
import utils.chronometre.Chronometre;
 
import fichiersdossiers.fichiersTabules.FichierTabule;
 
import affichages.Affichable;
import affichages.Couleur;
import affichages.Dessinable;
import mathematiques.metriques.Metric;
import mathematiques.primitives.pointstiti.Point3DI;
import mathematiques.primitives.pointstiti.PointND;
import mathematiques.statistiques.StandardizeData;
 
/**
 * <p>Description : Cette classe implemente l'algorithme des "centres mobiles", l'ancetre des K-means.
 *  Une heuristique est disponible afin que si on le souhaite, aucun cluster (classe) ne soit vide (sans aucun individu).<br>
 *  Lire "Dat mining et statistiques decisionnelle" par Stephane Tuffery, chez les editions TECHNIP.</p>
 * <p>Packages necessaires : affichages, mathematiques.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * <p>Dernieres modifications :<br>
 * 30 Avril 2008 => Correction de bugs lies a la standardisation des donnees & Ajout des methodes "ComputeAndReturnBestRepresentant" et du chrono.<br>
 * 29 Avril 2008, 1.2 => Ajout de la possibilite de d'initialiser les barycentre avant calculs.<br>
 * 21 Avril 2008 => Correction de bug majeur pour le cas "UnIndividuParClusterMinimum", ajout d'une securite pour un cas non gere.<br>
 *               => Ajout d'une securite pour le cas des nombre "NaN".<br>
 * 18 Avril 2008, 1.1 => Ajout de la possibilite de passer un fichier tabule dans un constructeur.<br>
 * 24 Octobre 2007 => Ajout d'une metrique en parametre. Elle sera utilisee pour tout ce qui est calcul de distances.<br>
 *                 => Ajout du calcul des erreurs de clustering : Inertie inter classe et intra classe.<br>
 * 15 Octobre 2007 => Creation.</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.2
 */
 
public class CentresMobiles
{
 
/** Nombre d'iterations qui furent necessaires pour converger lors du dernier calcul.*/
protected int nbIterations = 0 ;
/** L'erreur a minimiser pour pouvoir finir.*/
protected double Epsilon = 1.0 ;
/** Le tableau contenant les donnees sur lesquelles ont va travailler.*/
protected double[][] Tableau = null ;
/** Nombre de cluster (de classes).*/
protected int nbClusters = 0 ;
/** Nombre d'individus (d'instances) sur lesquels on va travailler <=> Nombre de lignes du tableau.*/
protected int nbIndividus = 0 ;
/** Dimensions du probleme <=> Nombre de colonnes <=> Taille du vecteur caracteristique.*/
protected int nbDimensions = 0 ;
/** Tableau qui contiendra pour chaque individu a quel cluster (classe) il appartient.*/
protected int[] ClusterResultat = null ;
/** Tableau contenant la distance entre un individu et le barycentre de sa classe.*/
protected double[] DistanceResultat = null ;
protected double InertieIntraClasse = -1.0 ;
protected double InertieInterClasse = -1.0 ;
/**Tableau contenant tous les clusters (classes).*/
protected Cluster[] Clusters = null ;
/** Metrique a utiser pour le calcul.*/
protected Metric metrique = null ;
/** Tableau contenant l'indice du meilleur representant pour chaque classe.*/
protected int[] BestRepresentant = null ;
/** Classe permettant de standardiser les donnees.*/
protected StandardizeData sd = null ;
 
 
/** Un constructeur (le seul) auquel il faut passer imperativement une metrique qui sera celle utilise par cette instanciation.
 * @param metrique La metrique a utiliser pour calculer les distances entre barycentres.*/
public CentresMobiles(Metric metrique)
	{
	if ( metrique == null ) throw new Error("Métrique = null") ;
	this.metrique = metrique ;
	sd = new StandardizeData() ;
	}
 
 
/** Une methode qui va faire les verifications necessaires puis lancer les calculs.
 * @param Tableau Le tableau contenant toutes les valeurs des individus : les individus sont sur les lignes et leurs caracteristiques en colonnes.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(double[][] Tableau, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire,
						double[][] Barycentres,	Chronometre Chrono)
	{
	if ( Tableau == null ) throw new Error("Tableau = null.") ;
 
	this.nbIndividus = Tableau.length ;
	this.nbDimensions = Tableau[0].length ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	this.Tableau = null ;
	this.Tableau = new double[Tableau.length][Tableau[0].length] ;
	for (int i=0 ; i < Tableau.length ; i++)
		for (int d=0 ; d < Tableau[0].length ; d++)
			this.Tableau[i][d] = Tableau[i][d] ;
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, Chrono) ;
	}
 
 
 
/** Une methode qui va faire les verifications necessaires puis lancer les calculs.
 * @param fichier Le fichier tabule contenant toutes les valeurs des individus : les individus sont sur les lignes et leurs caracteristiques en colonnes.
 * @param nbClusters Nombre de clusters (classes) que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(FichierTabule fichier, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire,
						double[][] Barycentres, Chronometre Chrono)
	{
	if ( fichier == null ) throw new Error("fichier = null.") ;
 
	int i, hauteur, largeur ;
	int Largeur = fichier.getLargeur() ;
	int Hauteur = fichier.getHauteur() ;
	int num, ligne, colonne = 0 ; // On remplit le tableau.
	int[] colonneint = null ;
	double[] colonnedouble = null ;
 
	List<Integer> NumColonnes = new Vector<Integer>() ; // On regarde quelles sont les colonnes exploitables : Valide, non nominale et de type int ou double.
	for (i=0 ; i < Largeur ; i++)
		if ( !fichier.isExcludedColumn(i) && !fichier.isNominal(i) &&
			(fichier.getTypeColonne(i) == FichierTabule.INTEGER || fichier.getTypeColonne(i) == FichierTabule.DOUBLE) )
			NumColonnes.add(i) ;
	largeur = NumColonnes.size() ;
	if ( largeur == 0 ) throw new Error("Aucune caracteristique exploitable dans ce fichier.") ;
 
	hauteur = 0 ; // On compte le nombre d'instances (lignes) valides.
	boolean[] Exclude = fichier.getExcluded() ;
	for (i=0 ; i < Exclude.length ; i++)
		if ( !Exclude[i] )
			hauteur++ ;
 
	this.nbIndividus = hauteur ; // On alloue et affecte ce qui doit l'être.
	this.nbDimensions = largeur ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
	Tableau = new double[hauteur][largeur] ;
 
	Iterator<Integer> iter = NumColonnes.iterator() ;
	while ( iter.hasNext() ) // On parcours les colonnes
		{
		num = iter.next() ;
		ligne = 0 ;
		switch ( fichier.getTypeColonne(num) ) // On ajoute les colonnes au tableau.
			{
			case FichierTabule.INTEGER :
				colonneint = fichier.getColumnInt(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonneint[i] ;
				break ;
			case FichierTabule.DOUBLE :
				colonnedouble = fichier.getColumnDouble(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonnedouble[i] ;
				break ;
			default : throw new Error("Type de colonne incorrect.") ;
			}
		colonne++ ;
		}
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, Chrono) ; // On lance le calcul
	}
 
 
 
/** Une methode qui prend en parametre une liste de points, puis la transforme en tableau afin d'effectuer les calculs.
 * Elle va faire les verifications necessaires puis lancer le calcul.
 * @param Liste Une liste de points 2D que l'on va convertir en tableau representant les individus et leurs descripteurs.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.*/
public void Calculer(List<PointND> Liste, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycentres)
	{
	if ( Liste == null ) throw new Error("Liste = null") ;
 
	this.nbIndividus = Liste.size() ;
	this.nbDimensions = Liste.get(0).getDimension() ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	Tableau = null ;
	Tableau = new double[nbIndividus][nbDimensions] ;
 
	int nb = 0 ;
	PointND point = null ;
	Iterator<PointND> iter = Liste.iterator() ;
	while ( iter.hasNext() )
		{
		point = iter.next() ;
		for (int j=0 ; j < nbDimensions ; j++)
			Tableau[nb][j] = point.get(j) ;
		nb++ ;
		}
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, null) ;
	}
 
 
 
/** Une methode qui prend en parametre une liste de points, puis la transforme en tableau afin d'effectuer les calculs.
 * Il va faire les verifications necessaires puis lancer les calculs.
 * @param Liste Une liste de points 2D que l'on va convertir en tableau representant les individus et leurs descripteurs.
 * @param nbClusters Nombre de clusters que l'on souhaite.
 * @param Epsilon Seuil d'arret des iterations.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.*/
public void Calculer(Vector<Point3DI> Liste, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycentres)
	{
	Tableau = null ;
	Tableau = new double[Liste.size()][2] ;
	for (int i=0 ; i < Tableau.length ; i++)
		{
		Tableau[i][0] = Liste.get(i).getX() ;
		Tableau[i][1] = Liste.get(i).getY() ;
		}
 
	this.nbIndividus = Tableau.length ;
	this.nbDimensions = 2 ;
	this.nbClusters = nbClusters ;
	this.Epsilon = Epsilon ;
 
	Calculer(nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, null) ;
	}
 
 
 
 
 
 
/** Methode qui gere la totalite des calculs.
 * @param nbClusters Le nombre de Clusters que l'on souhaite.
 * @param Epsilon Le seuil d'arret : si la somme des distances entre les anciens barycentres des clusters et les nouveaux est inferieure a Epsilon,
 *  on arrete.
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @param CentrerReduire Doit on centrer/reduire les donnees pour effectuer le calcul ?.
 * @param Barycentres Liste des barycentres, au cas on l'utilisateur veut preciser une initialisation particuliere. Si null, les barycentres sont places
 *  aleatoirement.
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
private void Calculer(int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, double[][] Barycentres, Chronometre Chrono)
	{
	Clusters = null ;
	ClusterResultat = null ;
	DistanceResultat = null ;
 
	if ( nbClusters < 2 ) throw new Error("Nombre de clusters incorrects : " + nbClusters + " (attendu > 1).") ;
	if ( nbIndividus < nbClusters ) throw new Error("Il y a plus de clusters (" + nbClusters + ") que d'individus (" + nbIndividus + ").") ;
 
	if ( Chrono != null )
		{
		System.out.print("Calcul des centres mobiles => ") ;
		Chrono.setMarqueur() ;
		}
 
	if ( CentrerReduire ) sd.Compute(Tableau) ;
 
	Clusters = new Cluster[nbClusters] ;
	for (int i=0 ; i < nbClusters ; i++) Clusters[i] = new Cluster(i, nbDimensions) ;
 
	if ( Barycentres == null ) PlacerBarycentresAleatoirement() ;
	else
		{
		if ( Barycentres[0].length != nbDimensions ) throw new Error("Dimension des barycentres différente du nombre de dimensions (caractéristiques).") ;
		if ( Barycentres.length != nbClusters ) throw new Error("Nombre de barycentre différent du nombre de classes (individus).") ;
		if ( CentrerReduire )
			{
			double val ;
			double[] moyennes = sd.getMoyennes() ;
			double[] ecartstypes = sd.getEcartsTypes() ;
			for (int i=0 ; i < nbClusters ; i++) // On affecte les barycentres en standardisant les valeurs.
				for (int j=0 ; j < nbDimensions ; j++)
					{
					val = Barycentres[i][j] ;
					val = (val - moyennes[j]) / ecartstypes[j] ;
					Clusters[i].getBarycentre().set(j, val) ;
					}
			}
		else
			for (int i=0 ; i < nbClusters ; i++)
				Clusters[i].setBarycentre(Barycentres[i]) ;
		}
 
	ClusterResultat = new int[nbIndividus] ;
	DistanceResultat = new double[nbIndividus] ;
 
 
	nbIterations = 0 ;
	while ( Converger(UnIndividuParClusterMinimum) > Epsilon ) nbIterations++ ;
 
	CalculerInertieIntraClasse() ;
	CalculerErreurInterClasse() ;
 
	if ( Chrono != null ) System.out.println(Chrono.getTimeSinceMarqueurSecondes() + "s, " + nbIterations + " itérations") ;
	}
 
 
 
/** Methode qui place aleatoirement le barycentre de chaque cluster pour l'initialisation.*/
private void PlacerBarycentresAleatoirement()
	{
	int x, y ;
	double[] min = new double[nbDimensions] ;
	double[] max = new double[nbDimensions] ;
	double[] barycentre = new double[nbDimensions] ;
 
	for (x=0 ; x < nbDimensions ; x++) min[x] = max[x] = Tableau[0][x] ;
 
	for (x=0 ; x < nbDimensions ; x++)
		if ( Double.isNaN(min[x]) ) throw new Error("NaN, ligne 0, colonne " + x) ;
 
	for (y=1 ; y < nbIndividus ; y++)
		for (x=0 ; x < nbDimensions ; x++)
			{
			if ( Double.isNaN(Tableau[y][x]) ) throw new Error("NaN, ligne " + y + ", colonne " + x) ;
			if ( min[x] > Tableau[y][x] ) min[x] = Tableau[y][x] ;
			if ( max[x] < Tableau[y][x] ) max[x] = Tableau[y][x] ;
			}
 
	for (y=0 ; y < nbClusters ; y++)
		{
		for (x=0 ; x < nbDimensions ; x++)
			barycentre[x] = min[x] + Math.random()*(max[x]-min[x]) ;
		Clusters[y].setBarycentre(barycentre) ;
		}
	}
 
 
 
/** Methode que l'on va iterer jusqu'a converger vers la solution (jusqu'a ce que l'on soit inferieur au critere d'arret).
 * @param UnIndividuParClusterMinimum Heuristique pour forcer qu'il y ait au moins un individu par cluster.
 * @return La distance totale de deplacement entre les anciens barycentres des clusters et les nouveaux.*/
private double Converger(boolean UnIndividuParClusterMinimum)
	{
	TrouverClusterPlusProche(UnIndividuParClusterMinimum) ;
	return CalculerBarycentres() ;
	}
 
 
/** Methode qui trouve le Cluster le plus proche de chaque individu.
 * @param UnIndividuParClusterMinimum Est ce que l'on applique l'heuristique ?*/
private void TrouverClusterPlusProche(boolean UnIndividuParClusterMinimum)
	{
	int i, c ;
	double Distance ;
 
	for (i=0 ; i < nbClusters ; i++) Clusters[i].setNbIndividus(0) ;
 
	for (i=0 ; i < nbIndividus ; i++)
		{
		ClusterResultat[i] = 0 ;
		DistanceResultat[i] = metrique.Distance(Tableau[i], Clusters[0].getBarycentre().get()) ;
		if ( Double.isNaN(DistanceResultat[i]) ) throw new Error("NaN trouvé lors d'un calcul de distances => individu " + i + ", cluster 0.") ;
		for (c=1 ; c < nbClusters ; c++)
			{
			Distance = metrique.Distance(Tableau[i], Clusters[c].getBarycentre().get()) ;
			if ( Double.isNaN(Distance) ) throw new Error("NaN trouvé lors d'un calcul de distances => individu " + i + ", cluster " + c + ".") ;
			if ( Distance < DistanceResultat[i] )
				{
				DistanceResultat[i] = Distance ;
				ClusterResultat[i] = c ;
				}
			}
		Clusters[ClusterResultat[i]].IncrementerNbIndividus(1) ;
		}
 
	if ( UnIndividuParClusterMinimum )
		{
		int nummax ;
		boolean Erreur = true ;
		while ( Erreur )
			{
			Erreur = false ;
			for (c=0 ; c < nbClusters ; c++)
				if ( Clusters[c].getNbIndividus() == 0 ) // Si un cluster n'a pas d'individu
					{
 
					nummax = 0 ;
					for (i=1 ; i < nbIndividus ; i++) // On trouve l'individu qui est le plus loin (de son cluster).
						if ( DistanceResultat[i] > DistanceResultat[nummax] ) nummax = i ;
					Clusters[c].setBarycentre(Tableau[nummax]) ; // On lui ajoute celui est le plus loin de son cluster.
					Clusters[c].setNbIndividus(1) ; // On met a un son nombre d'individu, car maintenant il en a un.
					Clusters[ClusterResultat[nummax]].DecrementerNbIndividus(1) ; // On decremente le compteur du cluster auquel il appartenait.
					if ( Clusters[ClusterResultat[nummax]].getNbIndividus() == 0 ) Erreur = true ;
					ClusterResultat[nummax] = c ; // On modifie son Cluster d'appartenance.
					DistanceResultat[nummax] = 0.0 ; // Il est SUR son nouveau Cluster, donc sa distance est nulle.
					}
			}
		}
 
	}
 
 
 
/** Methode qui calcule le nouveau barycentre de chaque Cluster en fonction des individus qui appartiennent aux Clusters.
 * @return La distance totale de deplacement entre les anciens barycentres des clusters et les nouveaux.*/
private double CalculerBarycentres()
	{
	int i, j ;
	double Distance = 0.0 ;
	double[][] Barycentres = new double[nbClusters][nbDimensions] ;
 
	for (i=0 ; i < nbIndividus ; i++) // On calcule la somme pour les nouveaux barycentres.
		for (j=0 ; j < nbDimensions ; j++)
			Barycentres[ClusterResultat[i]][j] += Tableau[i][j] ;
 
	for (i=0 ; i < nbClusters ; i++) // On calcule les nouveaux barycentres en divisant la somme pour le nombre d'individus.
		for (j=0 ; j < nbDimensions ; j++)
			Barycentres[i][j] /= (double)Clusters[i].getNbIndividus() ;
 
	for (i=0 ; i < nbClusters ; i++) Distance += metrique.Distance(Clusters[i].getBarycentre().get(), Barycentres[i]) ;
 
	for (i=0 ; i < nbClusters ; i++) Clusters[i].setBarycentre(Barycentres[i]) ;
 
	Barycentres = null ;
	return Distance ;
	}
 
 
 
/** Cette methode calcule l'inertie intra-classe de chaque cluster : La somme du carre des distance entre chaque individu d'une classe et le barycentre 
 *  de cette classe.*/
private void CalculerInertieIntraClasse()
	{
	int i ;
	double[] TabInertieIntraClasse = new double[nbClusters] ;
 
	for (i=0 ; i < nbClusters ; i++)
		{
		TabInertieIntraClasse[i] = 0.0 ;
		Clusters[i].setNbIndividus(0) ;
		}
 
	for (i=0 ; i < nbIndividus ; i++)
		{
		TabInertieIntraClasse[ClusterResultat[i]] += Math.pow(metrique.Distance(Clusters[ClusterResultat[i]].getBarycentre().get(), Tableau[i]), 2.0) ;
		Clusters[ClusterResultat[i]].IncrementerNbIndividus(1) ;
		}
 
	InertieIntraClasse = 0.0 ;
	for (i=0 ; i < nbClusters ; i++)
		{
		TabInertieIntraClasse[i] /= (double)Clusters[i].getNbIndividus() ;
		InertieIntraClasse += TabInertieIntraClasse[i] ;
		Clusters[i].setInertieIntraClasse(TabInertieIntraClasse[i]) ;
		}
 
	TabInertieIntraClasse = null ;
	}
 
 
 
/** Methode qui calcule inertie inter-classe : la somme du carre des distance entre le barycentre de tous les individus et le barycentre de chaque Cluster.*/
private void CalculerErreurInterClasse()
	{
	int i, j ;
	double[] Barycentre = new double[nbDimensions] ;
 
	for (i=0 ; i < nbIndividus ; i++)
		for (j=0 ; j < nbDimensions ; j++)
			Barycentre[j] += Tableau[i][j] ;
 
	InertieInterClasse = 0.0 ;
	for (i=0 ; i < nbClusters ; i++)
		InertieInterClasse += Clusters[i].getNbIndividus() * Math.pow(metrique.Distance(Barycentre, Clusters[i].getBarycentre().get()), 2.0) ;
 
	InertieInterClasse /= (double)nbIndividus ;
	Barycentre = null ;
	}
 
 
 
 
/** Methode permettant de calculer le meilleur representant de chaque classe. Attention le calcul ne peut etre fait dans le cas d'un fichier tabule
 *  contenant des instances non valides.*/
public void ComputeBestRepresentant()
	{
	int i ;
	BestRepresentant = new int[nbClusters] ;
 
	for (i=0 ; i < nbIndividus ; i++)
		BestRepresentant[ClusterResultat[i]] = i ;
 
	for (i=0 ; i < nbIndividus ; i++)
		if ( DistanceResultat[i] < DistanceResultat[BestRepresentant[ClusterResultat[i]]] )
			BestRepresentant[ClusterResultat[i]] = i ;
	}
 
 
 
 
/** Methode qui permet de calculer puis d'extraire les meilleurs representants d'un ensemble d'instances.
 * @return Un fichier tabule contenant le meilleur representant de chaque classe.*/
public FichierTabule ComputeAndReturnBestRepresentant(FichierTabule fichier)
	{
	if ( fichier == null) throw new Error("Le calcul n'a pas été effectué à partir d'un fichier tabulé, donc impossible d'en renvoyer un en résultat.") ;
 
	int i, j, best ;
	int[] Types = null ; 
	FichierTabule Resultat = null ;
	boolean[] Excluded = fichier.getExcluded() ;
 
	for (i=0 ; i < Excluded.length ; i++)
		if ( Excluded[i] )
			throw new Error("Le fichier contient des instances exclues (invalides), on ne peut effectuer le calcul.") ;
 
	Types = fichier.getTypeColonnes() ;
	Resultat = new FichierTabule(nbClusters, Types) ;
 
	ComputeBestRepresentant() ; // On calcule les meilleurs representants.
 
	for (i=0 ; i < nbClusters ; i++)
		{
		best = BestRepresentant[i] ;
		for (j=0 ; j < fichier.getLargeur() ; j++)
			switch ( Types[j] )
				{
				case FichierTabule.INTEGER :
					Resultat.setValue(i, j, fichier.getValueInt(best, j)) ;
					break ;
				case FichierTabule.DOUBLE :
					Resultat.setValue(i, j, fichier.getValueDouble(best, j)) ;
					break ;
				case FichierTabule.STRING :
					Resultat.setValue(i, j, fichier.getValueString(best, j)) ;
					break ;
				case FichierTabule.INCONNU :
					break ;
				default : throw new Error("Type de colonne invalide : " + Types[j]) ;
				}
		}
 
	return Resultat ;
	}
 
 
 
 
 
/** Methode qui permet de calculer puis d'extraire les meilleurs representants d'un ensemble d'instances.<br>
 * Attention : methode ne pouvant pas fonctionner si la source etait un fichier avec des instances exclues (invalides).
 * @return Un tableau de double contenant le meilleur representant de chaque classe.*/
public double[][] ComputeAndReturnBestRepresentants()
	{
	int i, j, best ;
	double[][] Resultat = new double[nbClusters][nbDimensions] ;
 
	ComputeBestRepresentant() ; // On calcule les meilleurs representants.
 
	for (i=0 ; i < nbClusters ; i++)
		{
		best = BestRepresentant[i] ;
		for (j=0 ; j < Tableau[i].length ; j++)
			Resultat[i][j] = Tableau[best][j] ;
		}
 
	return Resultat ;
	}
 
 
 
 
 
/* ------------------------------------------------------------ Les getters ------------------------------------------------------------ */
 
/** Methode qui renvoit le tableau contenant des individus etant les meilleurs representants de leurs classes (les plus proches).
 * @return Les numeros d'individus.*/
public int[] getBestRepresentant()
	{
	return BestRepresentant ;
	}
 
/** Methode qui renvoit le tableau contenant les numeros de clusters (classes) auquels appartiennent les instances.*/
public int[] getClusterResultat()
	{
	return ClusterResultat ;
	}
 
/** Methode qui renvoit le tableau contenant tous les clusters.
 * @return Les clusters.*/
public Cluster[] getClusters()
	{
	return Clusters ;
	}
 
/** Methode qui renvoit les distances entres les individus et le barycentre du cluster auquel ils appartiennent.
 * @return Les distances.*/
public double[] getDistanceResultat()
	{
	return DistanceResultat ;
	}
 
public double getEpsilon()
	{
	return Epsilon ;
	}
 
public void setEpsilon(double Epsilon)
	{
	this.Epsilon = Epsilon ;
	}
 
public int getNbClusters()
	{
	return nbClusters ;
	}
 
/** Nombre de dimensions (caracteristiques <=> nb colonnes) du probleme.
 * @return Le nombre de dimensions.*/
public int getNbDimensions()
	{
	return nbDimensions ;
	}
 
/** Nombre d'instances du tableau (de lignes).
 * @return Le nombre de lignes.*/
public int getNbIndividus()
	{
	return nbIndividus ;
	}
 
/** Methode qui retourne l'inertie inter classe de la population, peut egalement etre appele l'erreur inter classe.<br>
 * La somme du carre des distance ponderees entre le barycentre de tous les individus et le barycentre de chaque Cluster.
 * @return L'inertie inter classe.*/
public double getInertieInterClasse()
	{
	return InertieInterClasse ;
	}
 
/** Methode qui retourne l'inertie intra classe de la population : La somme du carre des distance entre chaque individu d'une classe et le barycentre 
 *  de cette classe.
 * @return L'inertie intra classe.*/
public double getInertieIntraClasse()
	{
	return InertieIntraClasse ;
	}
 
public int getNbIterations()
	{
	return nbIterations ;
	}
 
/** Le tableau sur lequel a ete effectue le clustering.
 * @return Le tableau de double.*/
public double[][] getTableau()
	{
	return Tableau ;
	}
 
}

Voilà la classe clusters

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
 
package rdf.clustering;
 
import mathematiques.primitives.pointstiti.PointND;
 
/**
 * <p>Description : Classe qui represente un Cluster pour les Kmeans.</p>
 * <p>Packages necessaires : mathematiques.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * <p>Dernieres modifications :<br>
 * 17 Avril 2008 => Correction d'un bug dans le constructeur : "if ( Dimension < 1 )" et ajout JavaDoc.<br>
 * 24 Octobre 2007 => Ajout JavaDoc et DistanceInterClasse pour mesurer l'erreur de clustering.<br>
 * 15 Octobre 2007 => Creation.</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 * @see KMeans
 */
 
public class Cluster
{
 
/** Numero du cluster.*/
private int Numero = 0 ;
/** Dimension du cluster = dimension du barycentre.*/
private int Dimension = 0 ;
/** Nombre d'individus (d'intances) appartenant au cluster.*/
private int nbIndividus = 0 ;
/** Le barycentre du cluster.*/
private PointND Barycentre = null ;
/** Erreur d'inertie entre les membres du cluster.*/
private double InertieIntraClasse = -1.0 ;
 
 
 
 
 
/** Un constructeur qui initialise le Cluster.
 * @param Numero Numero du Cluster.
 * @param Dimension La dimension du Cluster, donc la dimension de son barycentre.*/
public Cluster(int Numero, int Dimension)
	{
	if ( Dimension < 1 ) throw new Error("Dimension incorrecte : " + Dimension + " (attendu > 0).") ;
 
	this.Numero = Numero ;
	this.Dimension = Dimension ;
	Barycentre = new PointND(Dimension) ;
	}
 
 
 
 
 
 
 
/* ------------------------------------------------------------ Les getters & setters ------------------------------------------------------------ */
/**
 * @return Le barycentre.*/
public PointND getBarycentre()
	{
	return Barycentre ;
	}
 
/** Affecte le barycentre.
 * @param barycentre Le barycentre a affecter.*/
public void setBarycentre(PointND barycentre)
	{
	Barycentre.set(barycentre.get()) ;
	}
 
/** Affecte le barycentre de ce Cluster.
 * @param barycentre Le tableau contenant les coordonnees du barycentre.*/
public void setBarycentre(double[] barycentre)
	{
	Barycentre.set(barycentre) ;
	}
 
/** La dimension d'un Cluster est la dimension des individus que le compose. Si les points sont dans R^15 => Dimension = 15
 * @return Le dimension du Cluster.*/
public int getDimension()
	{
	return Dimension ;
	}
 
/** L'inertie dans ce Cluster => Somme{Distance(Xi,B)^2}. On peut egalement l'appeler Erreur Inter Classe.
 * @return L'erreur de distance dans le Cluster.*/
public double getInertieIntraClasse()
	{
	return InertieIntraClasse ;
	}
 
/** Affecte l'inertie intra-classe.
 * @param InertieIntraClasse La nouvelle erreur a affecter.*/
public void setInertieIntraClasse(double InertieIntraClasse)
	{
	this.InertieIntraClasse = InertieIntraClasse ;
	}
 
/**
 * @return Le numero du Cluster.*/
public int getNumero()
	{
	return Numero ;
	}
 
/** 
 * @return Le nombre d'individu qui sont dans ce Cluster.*/
public int getNbIndividus()
	{
	return nbIndividus ;
	}
 
/** Affecte le nombre d'individu a ce Cluster. Aucune verification n'est effectue sur la valeur affectee.
 * @param nbIndividus Le nombre a affecter.*/
public void setNbIndividus(int nbIndividus)
	{
	this.nbIndividus = nbIndividus ;
	}
 
/** Incremente le nombre d'individu appartenant au Cluster. Aucune verification n'est effectuee sur la valeur d'increment.
 * @param Increment De combien doit on incrementer le nombre d'individu.*/
public void IncrementerNbIndividus(int Increment)
	{
	nbIndividus += Increment ;
	}
 
/** Decremente le nombre d'individu appartenant au Cluster. Aucune verification n'est effectuee sur la valeur d'increment.
 * @param Increment De combien doit on decrementer le nombre d'individu.*/
public void DecrementerNbIndividus(int Increment)
	{
	nbIndividus -= Increment ;
	}
}

[ToTo13]

Voilà l'interface pour les métriques, à vous d'utiliser celle que vous préférez :

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
 
package mathematiques.metriques;
 
import mathematiques.matriciel.Vector;
import mathematiques.matriciel.VectorI;
import mathematiques.primitives.pointstiti.Point;
import mathematiques.primitives.pointstiti.PointI;
 
/**
 * <p>Description : Cette interface defini une metrique.</p>
 * <p>Package necessaires : Jama.</p>
 * <p>Dernieres modifications :<br>
 * 7 Mars 2009 => Ajout d'une methode avec des int.<br>
 * 9 Janvier 2009, 1.1 => renommee (traduite) et ajout des methodes permettant le calcul de distance entre vecteurs, points et coordonnees.<br>
 * 21 Octobre 2007 => Creation.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.1
 */
 
public interface Metric {
 
/** Calcule la distance entre les deux vecteurs passes en argument.
 * @param firstVector first input vector
 * @param secondVector second input vector
 * @return La distance.*/
public double Distance(double[] firstVector, double[] secondVector) ;
 
/** Calcule la distance entre les deux vecteurs passes en argument.
 * @param firstVector first input vector
 * @param secondVector second input vector
 * @return La distance.*/
public double Distance(int[] firstVector, int[] secondVector) ;
 
/** Calcule la distance entre les deux vecteurs passes en argument.
 * @param u Le premier vecteur.
 * @param v Le deuxieme vecteur.
 * @return La distance.*/
public double Distance(Vector u, Vector v) ;
 
/** Calcule la distance entre les deux vecteurs passes en argument.
 * @param u Le premier vecteur.
 * @param v Le deuxieme vecteur.
 * @return La distance.*/
public double Distance(VectorI u, VectorI v) ;
 
/** Calcule la distance entre les deux vecteurs passes en argument.
 * @param u Le premier vecteur.
 * @param v Le deuxieme vecteur.
 * @return La distance.*/
public double Distance(Vector u, VectorI v) ;
 
/** Calcule la distance entre les deux points passes en argument.
 * @param u Le premier point.
 * @param v Le deuxieme point.
 * @return La distance.*/
public double Distance(Point u, Point v) ;
 
/** Calcule la distance entre les deux points passes en argument.
 * @param u Le premier point.
 * @param v Le deuxieme point.
 * @return La distance.*/
public double Distance(PointI u, PointI v) ;
 
/** Calcule la distance entre les deux points passes en argument.
 * @param u Le premier point.
 * @param v Le deuxieme point.
 * @return La distance.*/
public double Distance(Point u, PointI v) ;
 
/** Calcule la distance entre les coordonnees 3D de deux points.
 * @param Ux Coordonnee en X du premier point.
 * @param Uy Coordonnee en Y du premier point.
 * @param Uz Coordonnee en Z du premier point.
 * @param Vx Coordonnee en X du deuxieme point.
 * @param Vy Coordonnee en Y du deuxieme point.
 * @param Vz Coordonnee en Z du deuxieme point.
 * @return La distance.*/
public double Distance(double Ux, double Uy, double Uz, double Vx, double Vy, double Vz) ;
 
}

Et la petite classe pour standardiser les données (centrer réduire par l'écart type). Elle fait la même chose que la méthode se trouvant dans la classe OutilsFichierTabules que j'ai déjà partagé :

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
 
package mathematiques.statistiques;
 
import fichiersdossiers.fichiersTabules.FichierTabule;
 
/**
 * <p>Description : Cette classe permet de centrer et reduire des donnees.</p>
 * <p>Packages necessaires : </p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * <p>Dernieres modifications :<br>
 * 5 Mars 2009 => Correction bug, precisions javadoc.<br>
 * 7 Aout 2008, V1.1 => Changement des noms des methodes, ajout des methodes pour les fichiers tabules.<br>
 * 30 Avril 2008 => Changement de nom de la classe, de son type et ajout des getters.<br>
 * 17 Avril 2008 => Creation : StandardizeData.</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.1
 */
 
public class StandardizeData
{
 
/** Tableau qui contient les moyennes des colonnes.*/
private double[] Moyennes = null ;
 
/** Tableau qui contient les ecarts types des colonnes.*/
private double[] EcartsTypes = null ;
 
 
 
/** Un constructeur vide.*/
public StandardizeData()
	{
 
	}
 
 
 
/** Methode qui centre (moyenne nulle) et reduit (ecart type egal a 1) les donnees. Le calcul est le suivant : pour chaque colonne C,
 * 	elle calcule la moyenne "m" et l'ecart type "ec", puis sur chaque element E de la colonne C, calcule E = (E-m)/ec ;
 * @param Data Le tableau contenant les donnees : les individus sont ranges en lignes.*/
public void Compute(double[][] Data)
	{
	int i, j ;
	int Largeur = Data[0].length ;
	int Hauteur = Data.length ;
 
	Moyennes = null ;
	EcartsTypes = null ;
	Moyennes = new double[Largeur] ;
	EcartsTypes = new double[Largeur] ;
 
	for (i=0 ; i < Largeur ; i++)
		{
		Moyennes[i] = EcartsTypes[i] = 0.0 ;
		for (j=0 ; j < Hauteur ; j++)
			Moyennes[i] += Data[j][i] ;
		Moyennes[i] /= (double)Hauteur ;
 
		for (j=0 ; j < Hauteur ; j++)
			EcartsTypes[i] += Math.pow(Data[j][i] - Moyennes[i], 2.0) ;
		EcartsTypes[i] = Math.sqrt(EcartsTypes[i]/(double)Hauteur) ;
 
		for (j=0 ; j < Hauteur ; j++)
			Data[j][i] = (Data[j][i] - Moyennes[i]) / EcartsTypes[i] ;
		}
	}
 
 
 
 
/** Methode qui centre (moyenne nulle) et reduit (ecart type egal a 1) les donnees du fichier. Donc elle ne peut operer que sur les colonnes de type DOUBLE.
 *  Elle fait le calcul suivant : pour chaque colonne, elle calcule la moyenne "m" et l'ecart type "ec",
 *  puis sur chaque element E de la colonne, calcule E = (E-m)/ec ;<br>
 * ATTENTION : methode qui opere sur TOUTES les colonnes de type DOUBLE, meme celles marquees "excluded".
 * @param fichier Le fichier tabule dont on souhaite normaliser les donnees.*/
public void Compute(FichierTabule fichier)
	{
	int i, j ;
	int Largeur = fichier.getLargeur() ;
	int Hauteur = fichier.getHauteur() ;
	double[] Tab = null ;
	double Moyenne, EcartType ;
 
	for (i=0 ; i < Largeur ; i++)
		if ( fichier.getTypeColonne(i) == FichierTabule.DOUBLE )
			{
			Tab = null ;
			Tab = fichier.getColumnDouble(i) ;
 
			Moyenne = EcartType = 0.0 ;
			for (j=0 ; j < Hauteur ; j++)
				Moyenne += Tab[j] ;
			Moyenne /= (double)Hauteur ;
 
			for (j=0 ; j < Hauteur ; j++)
				EcartType += Math.pow(Tab[j] - Moyenne, 2.0) ;
			EcartType = Math.sqrt(EcartType/(double)Hauteur) ;
 
			for (j=0 ; j < Hauteur ; j++)
				Tab[j] = (Tab[j] - Moyenne) / EcartType ;
			}
	Tab = null ;
	}
 
 
 
/** Methode qui centre (moyenne nulle) et reduit (ecart type egal a 1) les donnees du fichier. Donc elle ne peut operer que sur les colonnes de type DOUBLE.
 *  Elle fait le calcul suivant : pour chaque colonne, elle calcule la moyenne "m" et l'ecart type "ec",
 *  puis sur chaque element E de la colonne, calcule E = (E-m)/ec ;<br>
 * ATTENTION : methode qui opere sur TOUTES les colonnes de type DOUBLE, meme celles marquees "excluded".
 * @param fichier Le fichier tabule dont on souhaite normaliser les donnees.*/
public FichierTabule ComputeNew(FichierTabule fichier)
	{
	int x, y ;
	int Largeur = fichier.getLargeur() ;
	int Hauteur = fichier.getHauteur() ;
	FichierTabule res = null ;
	int[] TypeColonnes = new int[Largeur] ;
 
	for (x=0 ; x < Largeur ; x++) // On modifie le type des colonnes INTEGER en double afin de pouvoir les standardiser.
		if ( fichier.getTypeColonne(x) == FichierTabule.INTEGER ) TypeColonnes[x] = FichierTabule.DOUBLE ;
		else TypeColonnes[x] = fichier.getTypeColonne(x) ;
	res = new FichierTabule(Hauteur, TypeColonnes) ;
 
	for (x=0 ; x < Largeur ; x++)
		switch ( fichier.getTypeColonne(x) )
			{
			case FichierTabule.DOUBLE :
				for (y=0 ; y < Hauteur ; y++)
					res.setValue(y, x, fichier.getValueDouble(y, x)) ;
				break ;
			case FichierTabule.INTEGER :
				for (y=0 ; y < Hauteur ; y++)
					res.setValue(y, x, (double)fichier.getValueInt(y, x)) ;
				break ;
			case FichierTabule.STRING :
				for (y=0 ; y < Hauteur ; y++)
					res.setValue(y, x, fichier.getValueString(y, x)) ;
				break ;
			default :
			}
 
	TypeColonnes = null ; // On libère la mémoire.
	Compute(res) ; // On stadardize les données.
	return res ;
	}
 
 
/** Methode qui retourne le tableau contenant les moyennes calculees pour chaque colonne lors de l'utilisation de la methode Compute(double[][] Data).
 * @return Le tableau des moyennes.*/
public double[] getMoyennes()
	{
	return Moyennes ;
	}
 
/** Methode qui retourne le tableau contenant les ecarts types calcules pour chaque colonne lors de l'utilisation de la methode Compute(double[][] Data).
 * @return Le tableau des moyennes.*/
public double[] getEcartsTypes()
	{
	return EcartsTypes ;
	}
}

[ToTo13]

Et pour finir mes interfaces qui gèrent des points. Il y a des choses à améliorer dans ces classes, mais je n'ai pas trop le temps pour le moment

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
 
package mathematiques.primitives.pointstiti;
 
/**
 * <p>Description : Interface qui permet de definir un point dans un espace de dimension N.</p>
 * <p>Packages necessaires :</p>
 * <p>Dernieres modifications :<br>
 * 11 Janvier 2009 => Creation.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 */
 
public interface Point
{
 
/** Retourne la composante d'indice 0 du point.
 * @return La composante d'indice 0.*/
public double getX() ;
 
/** Retourne la composante d'indice 1 du point.
 * @return La composante d'indice 1.*/
public double getY() ;
 
/** Retourne la composante d'indice 2 du point.
 * @return La composante d'indice 2.*/
public double getZ() ;
 
/** Retourne tout le point (le tableau).
 * @return Le tableau representant le point.*/
public double[] get() ;
 
/** Retourne la Xieme composante du point.
 * @param x L'indice de la composante a retourner.
 * @return La valeur de la composante demandee.*/
public double get(int x) ;
 
/** Methode qui permet d'affecter tout le point par un tableau.
 * @param composantes Le tableau a copier dans le point.*/
public void set(double[] composantes) ;
 
/** Affecte les Xieme composante du point.
 * @param x L'indice de la composante a affecter.
 * @param composantes La valeur a affecter.*/
public void set(int x, double composantes) ;
 
/** Affecte la valeur passee en argument a la premiere coordonnee du point.
 * @param X La valeur a affecter.*/
public void setX(double X) ;
 
/** Affecte la valeur passee en argument a la deuxieme coordonnee du point.
 * @param Y La valeur a affecter.*/
public void setY(double Y) ;
 
/** Affecte la valeur passee en argument a la troisieme coordonnee du point.
 * @param Z La valeur a affecter.*/
public void setZ(double Z) ;
 
/** Affecte les composante en X et Y au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.*/
public void setXY(double X, double Y) ;
 
/** Affecte les composante en X, Y et Z au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.
 * @param Z Valeur a affecter a la composante en Z du point.*/
public void setXYZ(double X, double Y, double Z) ;
 
/** Methode qui retourne la taille (dimension) du point.
 * @return La dimension.*/
public int Size() ;
 
/** Retourne la dimension du point.
 * @return Dimension du point.*/
public int Dimension() ;
 
/** Methode qui determine si le point passe en argument est egal au point de cette classe.
 * @param p Le point qui doit etre compare au point de la classe.
 * @param Epsilon L'ecart maximum qu'il doit y avoir entre deux variables pour considerer qu'elles sont identiques. 
 * @return true si les deux point sont identiques, false sinon.*/
public boolean Equal(Point p, double Epsilon) ;
 
}

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
package mathematiques.primitives.pointstiti;
 
/**
 * <p>Description : Interface qui permet de definir un point en coordonnees entiere dans un espace de dimension N.</p>
 * <p>Packages necessaires :</p>
 * <p>Dernieres modifications :<br>
 * 11 Janvier 2009 => Creation.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 */
 
public interface PointI
{
 
/** Retourne la composante d'indice 0 du point.
 * @return La composante d'indice 0.*/
public int getX() ;
 
/** Retourne la composante d'indice 1 du point.
 * @return La composante d'indice 1.*/
public int getY() ;
 
/** Retourne la composante d'indice 2 du point.
 * @return La composante d'indice 2.*/
public int getZ() ;
 
/** Retourne tout le point (le tableau).
 * @return Le tableau representant le point.*/
public int[] get() ;
 
/** Retourne la Xieme composante du point.
 * @param x L'indice de la composante a retourner.
 * @return La valeur de la composante demandee.*/
public int get(int x) ;
 
/** Methode qui permet d'affecter tout le point par un tableau.
 * @param composantes Le tableau a copier dans le point.*/
public void set(int[] composantes) ;
 
/** Affecte les Xieme composante du point.
 * @param x L'indice de la composante a affecter.
 * @param composantes La valeur a affecter.*/
public void set(int x, int composantes) ;
 
/** Affecte la valeur passee en argument a la premiere coordonnee du point.
 * @param X La valeur a affecter.*/
public void setX(int X) ;
 
/** Affecte la valeur passee en argument a la deuxieme coordonnee du point.
 * @param Y La valeur a affecter.*/
public void setY(int Y) ;
 
/** Affecte la valeur passee en argument a la troisieme coordonnee du point.
 * @param Z La valeur a affecter.*/
public void setZ(int Z) ;
 
/** Affecte les composante en X et Y au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.*/
public void setXY(int X, int Y) ;
 
/** Affecte les composante en X, Y et Z au point.
 * @param X Valeur a affecter a la composante en X du point.
 * @param Y Valeur a affecter a la composante en Y du point.
 * @param Z Valeur a affecter a la composante en Z du point.*/
public void setXYZ(int X, int Y, int Z) ;
 
/** Methode qui retourne la taille (dimension) du point.
 * @return La dimension.*/
public int Size() ;
 
/** Retourne la dimension du point.
 * @return Dimension du point.*/
public int Dimension() ;
 
/** Methode qui determine si le point passe en argument est egal au point de cette classe.
 * @param p Le point qui doit etre compare au point de la classe.
 * @return true si les deux point sont identiques, false sinon.*/
public boolean Equal(PointI p) ;
}

[fusion_sadam]

Salut,
pourrais tu m'expliquer ce qu'est une forme forte, et à quoi ça sert ?
merci.

edit :
je viens de voir un de tes anciens post, en faite les formes fortes te permettent d'initialiser les centres des kmeans ?

je t'apprend peux être rien, mais il existe une très bonne méthode pour cela.
Procéder d'abord à une CAH classique sur un échantillon pas trop grand (<1000)
puis initialiser les kmean avec les centre de la CAH.
Ainsi sur un très grand nombre d'individu on obtient presque les mêmes résultats qu'une CAH avec la rapidité des kmeans

[ToTo13]

Bonjour,

il y a quelques algorithmes qui permettent d'initialiser plus ou moins correctement les K-Means ; SAS/JMP en utilise en d'entre eux.

L'avantage des formes fortes c'est de pouvoir regrouper les individus les plus souvent ensembles, donc on sait que des classes gravites autour de ces groupes d'individus. Prendre le barycentre de ces groupes d'individus comme initialisation est une méthode robuste.

[azazazs]

Bonjour Toto13,

J'ai lu vos posts concernant votre implémentation de K-means.

J'ai moi-même réalisé un petit programme sous Java dont voici les objectifs:

-Lecture de fichiers XML, provenant de fils RSS en anglais
-Analyse des mots constituants les titres et les descriptions (avec filtrage grâce à tree-tagger) afin de consituer un vocabulaire.
-Vectorisation de chaque item (chaque news des fils RSS)
- Application de K-means

Problème 1:
J'ai essayé d'imaginer un critère d'arrêt de l'algo (pour l'instant le nombre d'itérations est fixé à l'avance) en calculant la distance qui sépare le barycentre (de chaque cluster) à sa position dans l'itération précédente mais ce critère est trop limité (l'algo ne tourne qu'une seule fois!!).

Problème 2:
L'initialisation des clusters joue-t-elle un rôle dans la convergence de l'algo ? autrement dit, arrivera-t-on à un résultat différent si on initialise les clusters différemment ?

Problème 3:
L'algo ne donne pas toujours le même résultat quand je n'initialise pas aléatoirement les clusters.
En effet pendant le développement de l'application, j'obtenais des clusters relativement cohérent (avec des 10 itérations). Mais lorsque j'ai augmenté le nombre d'éléments à classer, tous les items se retrouvent dans le même cluster !

Bref mon application a beaucoup de petits soucis. J'espère que vous, ou quelqu'un d'autre pourra me guider.
PS:Je n'attends pas forcément de lignes de codes ni même de corrections de mon code j'ai juste besoin d'inspiration...

Bonnes fêtes.

[ToTo13]

Bonjour,

Envoyé par azazazs

Problème 1:
J'ai essayé d'imaginer un critère d'arrêt de l'algo (pour l'instant le nombre d'itérations est fixé à l'avance) en calculant la distance qui sépare le barycentre (de chaque cluster) à sa position dans l'itération précédente mais ce critère est trop limité (l'algo ne tourne qu'une seule fois!!).

Il est possible qu'un KMeans converge en une seule itération
L'avantage du déplacement des barycentres, c'est que tu peux changer le degrès de déplacement qui servira d'arrêt. Dans mon exemple j'ai utilisé un epsilon égal à 1.0, mais en pratique j'utilise souvent 0.001 voire moins lorsque je veux quelque chose de plus stable.
Tu peux également utiliser comme critère d'arrêt : aucun mouvement d'individu entre les clusters !!! Donc que d'une itération sur l'autre, tous les éléments restent dans le même cluster.

Envoyé par azazazs

Problème 2:
L'initialisation des clusters joue-t-elle un rôle dans la convergence de l'algo ? autrement dit, arrivera-t-on à un résultat différent si on initialise les clusters différemment ?

Oui, c'est la un des inconvénients des KMeans. En fait tu initialises aléatoirement les barycentres des clusters. Donc si tu changes les barycentres, tu changes les conditions d'initialisation et donc le résultat et la vitesse de convergence. Prend comme exemple le cas où tu initialiserais les barycentres directement sur une solution stable => Une seule itération.
J'ai lu que le logiciel SAS/JMP utilise un algorithme "intelligent", "malin" d'initialisation.

Envoyé par azazazs

Problème 3:
L'algo ne donne pas toujours le même résultat quand je n'initialise pas aléatoirement les clusters.

Ben... désolé... mais dans ce cas cela veut dire que tu t'es trompé dans ton algo ou dans l'implémentation .
Hormis l'initialisation qui est souvent aléatoire, le reste est tout ce qu'il y a de plus déterministe. Pour deux initialisation identiques, le résultat doit être le même.


Bonne continuation...

[ToTo13]

Et la classe permettant le calcul des formes fortes :

Code Java :

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
 
package rdf.clustering;
 
import java.util.Iterator;
import java.util.List;
import java.util.Vector;
 
import fichiersdossiers.fichiersTabules.FichierTabule;
import mathematiques.metriques.Metric;
import utils.chronometre.Chronometre;
import utils.sorts.QuickSort;
 
/**
 * <p>Description : Cette classe permet de calculer plusieurs KMeans afin de calculer les formes fortes. Les barycentres des formes fortes serviront
 *  a initialiser un dernier KMeans qui sera le resultat que l'on souhaite.</p>
 * <p>Packages necessaires : fichiersdossiers, mathematiques, utils.</p>
 * <p>Copyright : Copyright (c) 2007.</p>
 * <p>Laboratoire : LSIS.</p>
 * <p>Equipe : Image et Modele, I&M (ex LXAO).</p>
 * <p>Dernieres modifications :<br>
 * 30 Avril 2008 => Creation.</p>
 * 
 * @author Guillaume THIBAULT
 * @version 1.0
 */
 
public class KMeansFormesFortes
{
 
/** Le KMeans qui servira aux calculs.*/
private KMeans kmeans = null ;
 
/** Tableau contenant les clusters resultat de chaque individu.*/
private int[][] ClusterResultat = null ;
 
/** Tableau qui contiendra les resultats des composantes fortes.*/
private int[] FormesFortes = null ;
 
/** Tableau contenant les barycentres des formes fortes.*/
private double[][] Barycentres = null ;
 
/** Tableau qui contiendra tous les parametres.*/
private double[][] Tableau = null ;
 
 
 
 
/** Un simple constructeur qui va instancier le Kmeans qui sera utilise, a l'aide de la metrique passee en argument.
 * @param metrique La metrique a utiliser pendant les calculs.*/
public KMeansFormesFortes(Metric metrique)
	{
	if ( metrique == null ) throw new Error("Métrique = null") ;
	kmeans = new KMeans(metrique) ;
	}
 
 
/** Un simple constructeur auquel on passe directement le tableau de double.
 * @param Tableau Le tableau sur lequel on va travailler, contient les donnees.
 * @param nbKMeans Le nombre de KMeans que l'on doit calculer pour trouver les formes fortes.
 * @param nbClusters Le nombre de classes (clusters) du KMeans.
 * @param Epsilon La valeur de convergence du KMeans.
 * @param UnIndividuParClusterMinimum Est ce que l'on doit utiliser l'heuristique afin de n'avoir aucun cluster vide.
 * @param CentrerReduire Est ce que l'on doit centrer/reduire les donnees ?
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(double[][] Tableau, int nbKMeans, int nbClusters, double Epsilon,
						boolean UnIndividuParClusterMinimum, boolean CentrerReduire, Chronometre Chrono)
	{
	if ( nbKMeans <= 1 ) throw new Error("Nombre de KMeans incorrect : " + nbKMeans + ", attendu [2..N].") ;
 
	if ( Tableau == null ) throw new Error("Tabeau = null") ;
	this.Tableau = Tableau ;
 
	CalculerFormesFortes(nbKMeans, nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Chrono) ;
	}
 
 
/** Un simple constructeur auquel on passe un fichier tabule qui sera converti en tableau de double.
 * @param fichier Le fichier tabule sur lequel on va travailler, contient les donnees.
 * @param nbKMeans Le nombre de KMeans que l'on doit calculer pour trouver les formes fortes.
 * @param nbClusters Le nombre de classes (clusters) du KMeans.
 * @param Epsilon La valeur de convergence du KMeans.
 * @param UnIndividuParClusterMinimum Est ce que l'on doit utiliser l'heuristique afin de n'avoir aucun cluster vide.
 * @param CentrerReduire Est ce que l'on doit centrer/reduire les donnees ?
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
public void Calculer(FichierTabule fichier, int nbKMeans, int nbClusters, double Epsilon,
						boolean UnIndividuParClusterMinimum, boolean CentrerReduire,	Chronometre Chrono)
	{
	if ( nbKMeans <= 1 ) throw new Error("Nombre de KMeans incorrect : " + nbKMeans + ", attendu [2..N].") ;
	if ( fichier == null ) throw new Error("fichier = null.") ;
 
	int i, hauteur, largeur ;
	int Largeur = fichier.getLargeur() ;
	int Hauteur = fichier.getHauteur() ;
	int num, ligne, colonne = 0 ; // On remplit le tableau.
	int[] colonneint = null ;
	double[] colonnedouble = null ;
 
	List<Integer> NumColonnes = new Vector<Integer>() ; // On regarde quelles sont les colonnes exploitables : Valide, non nominale et de type int ou double.
	for (i=0 ; i < Largeur ; i++)
		if ( !fichier.isExcludedColumn(i) && !fichier.isNominal(i) &&
			(fichier.getTypeColonne(i) == FichierTabule.INTEGER || fichier.getTypeColonne(i) == FichierTabule.DOUBLE) )
			NumColonnes.add(i) ;
	largeur = NumColonnes.size() ;
	if ( largeur == 0 ) throw new Error("Aucune caracteristique exploitable dans ce fichier.") ;
 
	hauteur = 0 ; // On compte le nombre d'instances (lignes) valides.
	boolean[] Exclude = fichier.getExcluded() ;
	for (i=0 ; i < Exclude.length ; i++)
		if ( !Exclude[i] )
			hauteur++ ;
 
	Tableau = null ;
	Tableau = new double[hauteur][largeur] ;
 
	Iterator<Integer> iter = NumColonnes.iterator() ;
	while ( iter.hasNext() ) // On parcours les colonnes
		{
		num = iter.next() ;
		ligne = 0 ;
		switch ( fichier.getTypeColonne(num) ) // On ajoute les colonnes au tableau.
			{
			case FichierTabule.INTEGER :
				colonneint = fichier.getColumnInt(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonneint[i] ;
				break ;
			case FichierTabule.DOUBLE :
				colonnedouble = fichier.getColumnDouble(num) ;
				for (i=0 ; i < Hauteur ; i++)
					if ( !Exclude[i] )
						Tableau[ligne++][colonne] = colonnedouble[i] ;
				break ;
			default : throw new Error("Type de colonne incorrect.") ;
			}
		colonne++ ;
		}
 
	CalculerFormesFortes(nbKMeans, nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Chrono) ;
	}
 
 
 
/** Methode qui va effectuer le calcul des formes fortes.
 * @param nbKMeans Le nombre de KMeans que l'on doit calculer pour trouver les formes fortes.
 * @param nbClusters Le nombre de classes (clusters) du KMeans.
 * @param Epsilon La valeur de convergence du KMeans.
 * @param UnIndividuParClusterMinimum Est ce que l'on doit utiliser l'heuristique afin de n'avoir aucun cluster vide.
 * @param CentrerReduire Est ce que l'on doit centrer/reduire les donnees ?
 * @param Chrono Le chronometre pour mesurer le temps d'execution.*/
private void CalculerFormesFortes(int nbKMeans, int nbClusters, double Epsilon, boolean UnIndividuParClusterMinimum, boolean CentrerReduire, Chronometre Chrono)
	{
	int compteur, nb, nb2, Taille, i, j, k ;
	int nbDimensions = Tableau[0].length ;
	int nbIndividus = Tableau.length ;
	double taille = Math.pow(nbClusters, nbKMeans) ;
	int[] clusters = null ;
	boolean ok ;
	QuickSort qs = new QuickSort() ;
 
	if ( Double.isInfinite(taille) ) throw new Error("Nombre de composantes fortes trop grand : Math.pow(nbClusters, nbKMeans).") ;
	if ( taille > Integer.MAX_VALUE -1 ) throw new Error("Taille supérieure au MAX_INT.") ;
 
	if ( Chrono != null )
		{
		System.out.println("Calcul des formes fortes par les k-means : ") ;
		Chrono.setMarqueur() ;
		}
 
	ClusterResultat = null ;
	ClusterResultat = new int[nbKMeans][] ;
 
	for (i=0 ; i < nbKMeans ; i++)
		{
		if ( Chrono != null ) System.out.print("\t") ;
		kmeans.Calculer(Tableau, nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, null, Chrono) ;
		ClusterResultat[i] = kmeans.getClusterResultat() ;
		}
 
	Taille = (int)taille ;
	FormesFortes = null ;
	FormesFortes = new int[Taille] ; // On alloue le tableau des formes fortes, code dans la base nbClusters.
	for (i=0 ; i < Taille ; i++) FormesFortes[i] = 0 ;
 
	for (i=0 ; i < nbIndividus ; i++) // On remplit le tableau des composantes fortes.
		{
		nb = 0 ;
		for (k=0 ; k <  nbKMeans ; k++)
			nb = nb * nbClusters + ClusterResultat[k][i] ;
		FormesFortes[nb]++ ;
		}
 
	nb = 0 ;
	for (i=0 ; i < Taille ; i++) // On compte le nombre de cases non vides.
		if ( FormesFortes[i] != 0 ) nb++ ;
 
	if ( nb < nbClusters ) throw new Error("Nombre de formes fortes inférieur au nombre de clusters.") ;
 
	int[] FF = new int[nb] ; // Tableau contenant les nombre d'individus dans les formes fortes.
	int[] Indices = new int[nb] ; // Tableau contenant les indices des formes fortes qui ne sont pas vides.
 
	nb = 0 ;
	for (i=0 ; i < Taille ; i++) // On sauvegarde les cases et indices du tableau des composantes fortes qui ne sont pas nul.
		if ( FormesFortes[i] != 0 )
			{
			FF[nb] = FormesFortes[i] ;
			Indices[nb++] = i ;
			}
 
	qs.Sort(FF, Indices, 0, nb-1) ; // On tri afin de connaître les plus grand.
 
	boolean[] trouve = new boolean[nbIndividus] ; // Tableau permettant de savoir si cet individu a deja servie dans le calcul d'un barycentre.
	for (i=0 ; i < nbIndividus ; i++) trouve[i] = false ;
	Barycentres = null ;
	Barycentres = new double[nbClusters][nbDimensions] ; // Le tableau qui contiendra les barycentres résultats.
 
	compteur = 0 ; // On compte les barycentres calculés.
	for (k=nb-1 ; k >= nb-nbClusters ; k--) // On travaille sur les plus grand pour trouver les barycentres. 
		{
		clusters = Decomposer(Indices[k], nbKMeans, nbClusters) ; // On décompose les nombre pour savoir quels sont les clusters qui les ont généré.
 
		nb2 = 0 ;
		for (i=0 ; nb2 < FF[k] && i < nbIndividus ; i++) // On parcours tous les individus pour trouver ceux qui sont dans cette forme forte.
			if ( !trouve[i] ) // S'il n'a pas déjà été utilisé.
				{
				ok = true ;
				for (j=0 ; ok && j < nbKMeans ; j++) // On regarde s'il correspond.
					if ( ClusterResultat[j][i] != clusters[j] ) ok = false ;
				if ( ok ) // Il correspond...
					{
					for (j=0 ; j < nbDimensions ; j++) // On ajoute ses coordonnées au barycentre de la forme forte.
						Barycentres[compteur][j] += Tableau[i][j] ;
					trouve[i] = true ; // On ne travaillera plus sur lui...
					nb2++ ; // Un individu de moins à trouvé.
					}
				}
 
		if ( nb2 != FF[k] ) throw new Error("nb2 != CF[k]") ; // On a pas trouvé tous les individu => bug.
 
		for (j=0 ; j < nbDimensions ; j++) // On calcule le barycentre.
			Barycentres[compteur][j] /= (double)nb2 ;
 
		compteur++ ; // Une forme forte de traitée, à la suivante...
		}
 
	if ( Chrono != null ) System.out.print("\tFormes fortes, ") ;
	// On calcule le kmeans avec les barycentres des formes fortes.
	kmeans.Calculer(Tableau, nbClusters, Epsilon, UnIndividuParClusterMinimum, CentrerReduire, Barycentres, Chrono) ;
	if ( Chrono != null ) System.out.println("Terminé.") ;
	}
 
 
 
 
/** Methode qui decompose un nombre afin de retrouver les numeros de clusters qui l'on produit.
 * @param num Le numero a decomposer.
 * @param nbKMeans Le nombre de KMeans qui a ete effectue, c'est aussi le nombre de "nombre" a trouver, donc la taille du tableau resultat.
 * @param nbClusters Le nombre de clusters, utile pour connaitre la base qui a servi a generer le nombre.
 * @return Un tableau contenant les numeros de clusters qui ont genere le nombre.*/
private int[] Decomposer(int num, int nbKMeans, int nbClusters)
	{
	int[] res = new int[nbKMeans] ;
 
	for (int nb=nbKMeans-1 ; nb >= 0 ; nb--)
		{
		res[nb] = num % nbClusters ;
		num = (num - res[nb]) / nbClusters ;
		}
 
	return res ;
	}
 
 
 
/** Methode qui retourne le kmeans resultat, celui qui a ete calcule avec les donnees, mais initialise avec les barycentres des formes fortes.
 * @return Le kmeans resultat.*/
public KMeans getKMeansResultat()
	{
	return kmeans ;
	}
}

[azazazs]

Bonjour,

J'ai rendu ce projet à mon responsable, il y a déjà quelques mois (et il était plutôt satisfait).

Si cela intéresse encore quelqu'un, j'ai résolu tous mes problèmes et trouvé un moyen d'initialiser les clusters.

Voici le principe que j'ai implémenté:

Supposons que l'on veuille initialiser k clusters. Alors on commence d'abord par trouver les k vecteurs les plus "éloignés" des autres "en moyenne" (au sens de la distance euclidienne).
En gros, on calcule pour chaque vecteur un nombre "dm" qui est en fait la moyenne des distances par rapport aux autres vecteurs.
On choisit ensuite les k vecteurs dont les "dm" sont supérieurs aux autres et on se sert de leur coordonnées pour initialiser les barycentres des clusters.

L'idée c'est de choisir comme point de départ les vecteurs qui ont le moins de choses en commun avec les autres barycentres...

J'espère que c'est suffisamment clair...et j'ignore le degré de validité théorique de ce principe... en tous cas je serai heureux de répondre aux questions.

[neshavre]

Bonjour à tous,

J'ai un fichier .txt en entrée qui possède les données à classer. J'ai vu le code au dessus (sur un fichier tabulaire) mais quelle est la modification que je peut apporter pour le modifié pour un fichier texte et est ce que je peux faire des trucs comme ça?
Je voudrai appliquer l'algorithme des k-moyenne à ces données
S'il vous plait, j'ai besoin de vos aides, je suis coincée et je suis débutant en programmation java (eclipse).

Merci énormément.

[ToTo13]

C'est simple :
- nom des colonnes sur la première ligne, entre guillemets si nécessaires et espacé d'un espace.
- valeurs numérique séparées d'un espace
- valeurs nominales entre guillemet si nécessaire.

C'est également le format qu'acceptent weka et JMP.

[syki.mail]

Bonjour
Dans mon travail j'applique l'algorithme k-means 8 fois avec des objets prises aléatoirement. J'obtiens alors N vocabulaire.
comment je peux évalué ces 8 vocabulaires pour selectionner le meileur d'entre eux.

j’espère que la discussion encore valide.

[ToTo13]

Envoyé par syki.mail

Dans mon travail j'applique l'algorithme k-means 8 fois avec des objets prises aléatoirement.

Tu veux dire que tu initialises les barycentre aléatoirement ?

Envoyé par syki.mail

J'obtiens alors N vocabulaire. comment je peux évalué ces 8 vocabulaires pour selectionner le meileur d'entre

Qu'appelles tu un "vocabulaire" ?


La version des formes fortes que j'ai posté est assez "maladroite" :s
Au lien de stocker toutes les combinaison, il vaudrait mieux faire un accumulateur de taille NxN (avec N le nombre d'individu) et l'incrémenter à chaque itération.