La classe ALGO_K_MEANS
La classe ALGO_K_MEANS
Embedded Files
La classe AlgoKMeans possède
Le tableau de données (tableau de tableaux de double),
Une liste de Data,
Une liste de clusters.
A partir des données du tableau, il faut créer des données de type Data, récupérer les coordonnées maximales, et demander la normalisation des données.
Il faut ensuite définir les clusters.
1. /**initialise de Data list, normalize them, and create the clusters
2. * @param _nbClusters nb of clusters
3. * @param _dim size of a data */
4. private static void initialize(int _nbClusters, int _dim) {
5. //samples is an double array : in rows, the users; in columns, skills
6. double[]maxs = new double[_dim];
7. Arrays.fill(maxs, Double.NEGATIVE_INFINITY);
8. for(double[] data:samples) {
9. dataSet.add(new Data(data));
10. Arrays.setAll(maxs, i->(maxs[i]>data[i]?maxs[i]:data[i]));
11. }
12. dataSet.forEach(d->d.normalize(maxs));
13.
14. createClusters(_nbClusters);
15. }
La création des premiers clusters a une influence importante dans la performance de l’algorithme.
La méthode K++ propose de prendre les données les plus éloignés les uns des autres :
Une donnée est sélectionnée aléatoirement pour être le centroïde du premier cluster
La seconde est la donnée plus éloignée de la première, elle constitue le centroïde du deuxième cluster
Puis, il suffit de prendre par la suite la donnée dont la distance minimale aux centroïdes présent est maximale.
Exemple, si un centroïde c1 est en (1,0) et un autre c2 est en (10,0) ;
Le point (0,0) est à une distance de 1 de c1 et de 10 de c2, distance minimale = 1
Le point (4,0) est à une distance de 4 de c1 et de 5 de c2, distance minimale = 4
C’est donc le point (4,0) qui est préféré pour être le 3e centroïde...
1. private static void createClusters(int _nbClusters) {
2. Data centroid = dataSet.get((int)(dataSet.size()*Math.random()));
3. Cluster firstCluster = new Cluster(centroid);
4. clusters.add(firstCluster);
5. int nbClusters = _nbClusters;
6. for(int c = 1; c<nbClusters; c++) {
7. Data farData = null;
8. double maxDist = Double.NEGATIVE_INFINITY;
9. for(Data data:dataSet) {
10. double minDist = Double.POSITIVE_INFINITY;
11. for(Cluster cluster:clusters) {
12. double dist = data.distNorm(cluster.getCentroid());
13. if(minDist>dist) minDist = dist;
14. }
15. if (maxDist<minDist) {
16. maxDist = minDist;
17. farData = data;
18. }
19. }
20. Cluster cluster = new Cluster(farData.clone());
21. clusters.add(cluster);
22. }
23. System.out.println("Initially, centroids are:");
24. System.out.println(" java php .Net Python SQL");
25. clusters.forEach(c->System.out.println(c.centroid.toString()));
26. }
L’aglo consiste à trouver pour chaque donnée le cluster le plus adapté, celui dont le centroïde est le plus proche :
1. /**search the best cluster for a data
2. * @param data the data to place in a cluster
3. * @return the cluster whose the centroid is the closest from the data*/
4. private static Cluster searchCluster(Data data) {
5. Cluster bestCluster = null;
6. double minimum = Double.POSITIVE_INFINITY;
7. double distance=0;
8. for(Cluster cluster:clusters) {
9. distance = data.distNorm(cluster.getCentroid());
10. if(distance < minimum){ minimum = distance; bestCluster = cluster; }
11. }
12. return bestCluster;
13. }
Puis à recalculer le centre de chaque cluster ; pour ensuite réarranger les données dans les clusters, recalculer le centre de chaque cluster, ... tant que cela est nécessaire...
1. /**algorithm of Kmeans :
2. * set each data in the best cluster and do a loop:
3. * -compute the new clusters centers; -moving of data in best clusters if necessary */
4. private static void kMeanCluster() {
5. dataSet.forEach(data -> searchCluster(data).add(data));
6. boolean moving = true;
7. while(moving) {
8. moving = false;
9. clusters.forEach(c -> c.centralize());
10. for(Data data:dataSet) {
11. Cluster bestCluster = searchCluster(data);
12. if(data.getCluster() != bestCluster){
13. moving = true;
14. data.getCluster().remove(data);
15. bestCluster.add(data);
16. }
17. }}}
L’ensemble est complet, avec une fonction qui crée des valeurs, il reste à tester :
1. /**create some randomize data
2. * @param _nb nb of data to generate
3. * @param _dim dimension of the data */
4. private static void createSamples(int _nb, int _dim) {
5. samples =new double[_nb][_dim];
6. for(int i=0; i<_nb; i++)
7. Arrays.setAll(samples[i], j-> Math.random()*100); /**skills range 0..100*/
8.
9. }
10.
11. /**main program*/
12. public static void main(String[] args) {
13. int dim=5; /** 5 skills */
14. int nbSamples = 10000; /**10 000 Users */
15. createSamples(nbSamples, dim);
16. int nbClusters = 15;
17. System.out.println("classification of " +nbSamples+ " samples of dimension " + dim + " into " + nbClusters + " clusters.");
18. long start = System.currentTimeMillis();
19. initialize(nbClusters, dim);
20. kMeanCluster();
21. long end = System.currentTimeMillis();
22. System.out.println("after " + (end-start) + " ms ");
23. clusters.forEach(c->c.computeStats());
24. // Print out clustering results.
25. double error = 0;
26. int nb=0;
27. for(Cluster cluster:clusters) {
28. if (cluster.dataSet.size()>0) {
29. System.out.println(cluster);
30. nb++;
31. error += cluster.moyDist;
32. }
33. }
34. error = error/(nb*dim);
35. System.out.println("gobal error= " + String.format(Locale.ENGLISH, "%.2f", (error*100)) + " % ");
36. }
Page updated
Google Sites
Report abuse