Voir le flux RSS

Open source et architecture logicielle

Implémentation de l’algorithme K-Means en java (partie 3)

Noter ce billet
par , 30/04/2020 à 09h20 (303 Affichages)
Pour ce dernier volet voici la classe DataSet qui porte la structure et les méthodes à invoquer pour réaliser l’algorithme K-Means.
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
 
public class DataSet {
	private List<Point> population;
	private List<Centroide> centroides;
	private  double EPSILON = 0.1;
 
	public DataSet() {
		this.population = new ArrayList<Point>();
		this.centroides = new ArrayList<Centroide>();
	}
	public void addData(Point p) {
		this.population.add(p);
	}
	public void addCentroide(Centroide e) {
		this.centroides.add(e);
	}
	public List<Point> getPopulation() {
		return population;
	}
	public List<Centroide> getCentroides() {
		return centroides;
	}
	public void assignation() {
		this.getCentroides().forEach(element -> element.empty());
		for (Point point : this.getPopulation()) {
			List<Double> distances = new ArrayList<Double>();
			for (Centroide cent : this.getCentroides()) {
				distances.add(point.getDistance(cent.getCenter()));
			}
			Double minimum = distances.stream().mapToDouble(v->v).min().orElseThrow(NoSuchElementException::new);
			this.getCentroides().get(distances.indexOf(minimum)).add(point);
		}
	}
	public boolean variation() {
		boolean flag = false;
		for (Centroide cent : this.getCentroides()) {
			Point newCenter = cent.getBarycenter();
			if(cent.getCenter().getDistance(newCenter) > EPSILON) {
				flag = true;
				cent.setCenter(newCenter);
			}
		}
		return flag;
	}
	@Override
	public String toString() {
		return "DataSet [population=" + population + ", centroides=" + centroides + "]";
	}
	public void kMeans() {
		do {
			this.assignation();
		} while(this.variation());
	}
}
Et voici quelques explications de ce code simple :

1/ Les propriétés de l’objet
On trouve 2 collections :
- population (le dataset des indidividus cible)
- centroïdes (les centroïdes choisi pour le traitement)
J’ai choisi de prendre des ArrayList pour sa convivialité pour des raisons de performances puisqu’ils seront toujours accédés de façon linéaire.
On y trouve aussi une variable numérique EPSILON que j’ai fixé arbitrairement à 0.1
Epsilon et la variation des positions requises des centroïde en dessous de laquelle l’itération s’arrête. En toute rigueur j’aurai également du ajouter comme critère de convergence pour l’arrêt de l’itération le nombre de boucles.

2/ Les méthodes de l’objet
1.1/ La méthode assignation
Cette méthode permet de d’attribuer un centroïde à chaque individu du cluster. A chaque exécution de cette fonction, les clusters de tout les centroïdes sont vidés, puis remplis avec les individus recalculés. J’avoue avoir eu recours une dernière fois aux lambdas pour trouver la distance minimum en une ligne plutôt qu’en 10, pour montrer la puissance du côté fonctionnel du code (pour les jeunes jedi non encore convertis).

2.2/ La méthode variation
Cette méthode calcule le barycentre de chaque cluster et le compare à la valeur du centroïde. Si cette valeur est supérieure à EPSILON alors elle repositionne le centroïde et donne le feu vert pour la prochaine itération. Sinon elle signale que l’algorithme a convergé.

2.3/ La méthode kMeans
Il s’agit de la boucle qui modélise la doctrine macroscopique de l’algorithme K-Means.
Peut être que j’aurais simplement dû la placer dans le main() mais mon cerveau doit être trop tordu et j’ai souhaité que ma classe DataSet soit totalement autoporteuse de l’algorithme. De plus j’ai appliqué le principe du couplage lâche partout ou des atomes étaient remplaçables (Point notamment), et mettre cette méthode dans la classe DataSet ne me semblait pas être antagoniste de cette doctrine.

Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Viadeo Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Twitter Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Google Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Facebook Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Digg Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Delicious Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog MySpace Envoyer le billet « Implémentation de l’algorithme K-Means en java (partie 3) » dans le blog Yahoo

Tags: algorithme, java
Catégories
Java

Commentaires

  1. Avatar de gerard093
    • |
    • permalink
    Pour les gens intéressés par les algorithmes de data sciences, je recommande d'aller faire un tour sur le site de weka.

    En effet, les applications de data sciences sont accompagnées d'un générateur de code qui permet de mettre en oeuvre des applications java à moindre coût. Et c'est open source ...

    https://www.cs.waikato.ac.nz/ml/weka/
  2. Avatar de autran
    • |
    • permalink
    Je confirme l'intérêt de ce site.
    Mais il impose de n'utiliser que les (excellents) objets de l'API WEKA