IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

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


Sujet :

Contribuez

  1. #1
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut [java] Centres mobiles / K-means / Formes fortes
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 ;
    	}
    }
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  2. #2
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut Centres mobiles
    La classe permettant le calcul des centres mobiles :
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 ;
    	}
    }
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  3. #3
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Voilà l'interface pour les métriques, à vous d'utiliser celle que vous préférez :
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 ;
    	}
    }
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  4. #4
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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) ;
    }
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  5. #5
    Membre à l'essai
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    26
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 26
    Points : 15
    Points
    15
    Par défaut
    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

  6. #6
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  7. #7
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2008
    Messages : 11
    Points : 10
    Points
    10
    Par défaut
    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.

  8. #8
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Bonjour,

    Citation Envoyé par azazazs Voir le message
    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.



    Citation Envoyé par azazazs Voir le message
    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.




    Citation Envoyé par azazazs Voir le message
    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...
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  9. #9
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut Calcul des formes fortes par k-moyennes
    Et la classe permettant le calcul des formes fortes :
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    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 ;
    	}
    }
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  10. #10
    Membre à l'essai
    Profil pro
    Inscrit en
    Décembre 2008
    Messages
    11
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Décembre 2008
    Messages : 11
    Points : 10
    Points
    10
    Par défaut Fini !
    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.

  11. #11
    Candidat au Club
    Femme Profil pro
    Chercheur en informatique
    Inscrit en
    Mai 2011
    Messages
    3
    Détails du profil
    Informations personnelles :
    Sexe : Femme
    Localisation : France, Seine Maritime (Haute Normandie)

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Enseignement

    Informations forums :
    Inscription : Mai 2011
    Messages : 3
    Points : 4
    Points
    4
    Par défaut implémenter l'algorithme k-moyenne à partir d'un fichier texte
    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.

  12. #12
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  13. #13
    Membre régulier
    Enseignant Chercheur
    Inscrit en
    Décembre 2011
    Messages
    172
    Détails du profil
    Informations professionnelles :
    Activité : Enseignant Chercheur

    Informations forums :
    Inscription : Décembre 2011
    Messages : 172
    Points : 73
    Points
    73
    Par défaut
    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.

  14. #14
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Citation Envoyé par syki.mail Voir le message
    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 ?


    Citation Envoyé par syki.mail Voir le message
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  15. #15
    Candidat au Club
    Profil pro
    Inscrit en
    Novembre 2010
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2010
    Messages : 3
    Points : 4
    Points
    4
    Par défaut algo Kmeans appliqué sur un fichier .txt
    Bonjour,

    @toto13 : ci joint le fichier base1.txt qui est en fait une base de données IRIS
    J'ai essayé de copier /coller le code du kmeans sur un fichier tabulé et j'ai tiens en compte vos remarques mais je n'arrive pas à des résultats.
    Donc l'idée est de parcourir le fichier ligne par ligne et de séparer dans chaque ligne les attributs par "," et les mettres dans un tableau à 2 dimenssion ou bien une liste !!!
    S'il vous plait de m'aider, quelles sont les lignes de code que je peux les modifiés par rapport à votre code puisque je trouve que le principe de kmeans reste le meme quoi!

    Merci d'avance
    Fichiers attachés Fichiers attachés

  16. #16
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Bonjour,

    enlevez les virgules et mettez des espaces à la place.
    Etant donné que l'on est dans de la classification (donc non supervisé), les classes sont inutiles.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  17. #17
    Nouveau Candidat au Club
    Femme Profil pro
    Inscrit en
    Juillet 2011
    Messages
    1
    Détails du profil
    Informations personnelles :
    Sexe : Femme

    Informations forums :
    Inscription : Juillet 2011
    Messages : 1
    Points : 1
    Points
    1
    Par défaut
    Bonjour,
    S'il vous plaît est ce que vous pouvez me décrire la classe PointNB, la classe chronometre et la classe QuickSort car ils ne sont pas mentionnées
    Merci

  18. #18
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    Les classes Point* sont des classes qui représentent des points. J'ai donné les interfaces, donc à toi de rapidement développer la tienne. Dans ce cas, il s'agit d'un point de dimension N.

    QuickSort fait le tri d'un tableau.
    Mais il y a une petite variante ici, c'est qu'elle prend deux tableaux en paramètres. Elle trie le premier et modifie les valeurs du second en conséquence : lorsqu'une modification est faite sur le premier tableau, elle l'est aussi sur le deuxième.

    Tout ce qui touche au Chronometre peut être supprimé, c'était à mes débuts lorsque je voulais mesurer des temps d'exécution.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

Discussions similaires

  1. Des jeux Java sur mobile phone
    Par ..::snake::.. dans le forum Développement Mobile en Java
    Réponses: 3
    Dernier message: 21/06/2007, 13h00
  2. Graphisme pour un jeux java sur mobile
    Par marocleverness dans le forum Java ME
    Réponses: 4
    Dernier message: 15/03/2007, 16h53
  3. import java.util.Date et plate-forme java
    Par Mathieu72 dans le forum Langage
    Réponses: 5
    Dernier message: 17/02/2007, 17h51
  4. Java pour mobile ?
    Par Michaël dans le forum Développement Mobile en Java
    Réponses: 3
    Dernier message: 25/01/2006, 20h22
  5. [Débutant] Applications Java pour Mobiles
    Par bakkula dans le forum Développement Mobile en Java
    Réponses: 4
    Dernier message: 13/09/2005, 01h09

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo