Projet clustering à grande échelle avec k-means

L'objectif de ce projet est d'implémenter un algorithme générique permettant de découper un ensemble en sous-ensembles disjoints (partition). L'algorithme à implémenter est l'algorithme appelé k-means. Cet algorithme est un algorithme itératif qui fonctionne de la manière suivante :

  1. On choisit k éléments (appelés centroïdes) dans l'ensemble de départ. Dans notre implémentation on prendra obligatoirement les k premiers éléments valides et distincts de l’ensemble de départ.
  2. On regroupe les éléments en k sous-ensembles de tel sorte qu’un élément appartient au sous-ensemble du centroïde dont il est le plus proche.
  3. Pour chaque sous-ensemble on calcul un nouveau centroïde qui correspond à la valeur moyenne des éléments de l’ensemble.
  4. Si les k nouveaux centroïdes sont suffisament différents des k centroïdes précédents on retourne à l’étape 2.
  5. On attribue à chacun des éléments de départ le numéro du sous-ensemble auquel il appartient.

Partie 1 :

Dans cette première partie, on souhaite implémenter l’algorithme k-means pour des valeurs réelles en une dimension.

  • Implémentez un programme qui prend en entrée deux le chemin de fichiers de fichier csv (fichier d'entrée et de sortie) et deux entiers.
  • Le premier fichier correspond au fichier d'entrée
  • Le deuxième fichier correspond à l'unique fichier de sortie
  • Le premier entier au nombre de cluster que l’on désire (k)
  • Le deuxième au numéro de la colonne que l’on veut utiliser dans le fichier csv pour faire le clustering.

Le fichier de sortie devra être le même que le fichier de départ avec une colonne supplémentaire qui indique dans quel cluster la valeur de la colonne i a été placée avec l’algorithme k-means.

Exemple d'appel, cette ligne calcul 3 clusters à partir de la colonne 5 du fichier meteo.csv et stocke le résultat dans le fichier result.csv.

yarn jar kmeans1D.jar /data/meteo.csv /kmeans/result.csv 3 5

k-means nD :

Modifiez votre programme pour permettre de calculer le clustering sur un nombre arbitraire de dimensions. Votre programme prendra en paramètre le nombre de cluster puis les n colonnes du fichier que l’on veut utiliser comme dimensions.

Exemple d'appel, cette ligne calcul 3 clusters à partir des colonnes 5 et 6 (deux dimensions) du fichier worldcitiespop.csv et stocke le résultat dans le fichier result.csv.

yarn jar kmeansnD.jar /data/worldcitiespop.csv /kmeans/result.csv 3 5 6

k-means hiérarchique

L’objectif de cette deuxième partie est d’appliquer récursivement l’algorithme kmeans pour créer un arbre de partitionnement. Ajoutez à votre programme précédent un paramètre qui donne le nombre de niveau N de la hiérarchie que l’on désire. Votre programme ajoutera N colonnes au fichier de départ, la colonne N_i indiquera le cluster auquel appartient un élément au niveau i.

Etiquetage

L’objectif de cette partie est d’attribuer un label à chaque cluster de chaque niveau obtenu dans les étapes précédentes. Pour cela écrivez un programme qui prend en entrée un fichier csv, un numéro de colonne d’étiquettes, un numéro de colonne de mesures et N numéros de colonnes de classification. En sortie il génère N fichiers correspondant aux étiquettes attribuées aux clusters d’un niveau. Pour déterminer l’étiquette d’un cluster on prendra le label de l’élément du cluster qui a la plus grande valeur sur la colonne de mesure.

Exemple :

Fichier source

Etiquette Mesure
Paris 10000
Bordeaux 200
Brest 50
Auxerre 100

yarn jar kmeansNdHierar.jar input.csv output.csv 2 3 1

Fichier sortie clustering hiérarchique

Etiquette Mesure N₀ N₁ N₂
Paris 10000 0 0 0
Bordeaux 200 0 1 0
Brest 50 0 1 1
Auxerre 100 1 0 0

yarn jar labelize.jar classif.csv sortie

sortie.2.csv

N0 N1 N2 Label
0 0 0 Paris
0 1 0 Bordeaux
0 1 1 Brest
1 0 0 Auxerre

sortie.1.csv

N0 N1 Label Mesure
0 0 Paris 10000
0 1 Bordeaux 200
1 0 Auxerre 100

Sortie.0.csv

N0 Label Mesure
0 Paris 10000
1 Auxerre 100