TP L2-Apprentissage

Posted on Wed 13 February 2019 in cours

Cette page regroules les informations sur la second partie du cours d'introduction à l'apprentissage automatique. Cette partie se concentre sur le partitionnement de données et l'apprentissage non-supervisé.

Cours

  • Cours du 15/10/19 : Fin Partie 1 (questions), début apprentissage non-supervisé
  • Cours du 5/11/19 : Partionnnement de données : k-moyennes, hierarchique et DBSCAN
  • Cours du 12/11/19 : Déplacé!
  • Cours du 19/11/19 : Mixture de Gaussienne 1D
  • Cours du 26/11/19 : Mixture de Gaussienne (suite)
Table of contents:

TP semaine du 11/11/2019 : Les k-moyennes

L'objectif de ce TP est de développer son propre code pour l'algorithme des k-moyennes ainsi que la génération de données synthétiques sur lesquelles on va travailler. Tout d'abord, créer un nouveau package partitionnement, et une nouvelle classe kmeans pour ce package.

L'algorithme des k-moyennnes

L'algorithme des k-moyennes fonctionnent en deux étapes

  • assigner chaque donnée à un cluster en particulier
  • mettre à jour la position des centres par rapport aux points qui leur ont été assignés

Il va donc falloir implémenter les méthodes suivantes.

  1. la méthode int[] Assigner, qui prendra en argument un tableau de données double[][] X représentant une liste de points dans un espace à D dimensions, et, les centres données par double[][] centres, représentant chaque centre (parmi les k centres) par une position dans l'espace à D dimensions. Ici il faudra pour chaque donnée, lui assigner le numéro du centre le plus proche. Vous ferez attention à rajouter une fonction spécifique pour le calcul de la distance.

  2. la méthode double Deplct, qui prendra comme arguments :

    • les centres
    • les données
    • l'assignement de chaque donnée et qui mettra à jour la position des centres. Attention, si un centre n'a été assigné à aucune donnée, il ne faut pas le déplacer ! Cette méthode renvoie la distance cumulée entre la position des nouveaux centres et des anciens.

Une fois implémentée ces deux fonctions, vous pouvez tester rapidement l'algorithme sur la code suivant:

 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
public static void main(String[] args) {
// creation d'un jeu de donnes simples pour tester l'algo

int D=2; // deux dimensions
int k=2; // deux centres
double[][] X = new double[6][D]; // 6 points en D dimensions
double[][] centres = new double[k][D];

    centres[0][0] = -1; centres[1][0] = 1;
    centres[0][1] = 0; centres[1][1] = 0;

    // position des donnees
    X[0][0] = -3;   X[0][1] = 1;
    X[1][0] = -2.5; X[1][1] = -0.5;
    X[2][0] = -4;   X[2][1] = 0;
    X[3][0] = 2;    X[3][1] = 2;
    X[4][0] = 2.5;  X[4][1] = -0.5;
    X[5][0] = 1.5;  X[5][1] = -1;

double eps=0.001;
double maj = 10;
int[] ass = new int[X.length];
while(maj>eps) {
    ass = Assigner(X,centres);
    maj = Deplct(X,centres,ass);
}

// verification
for(int i=0; i<X.length; i++) {
    System.out.println("Pt "+i+" assigné à "+ass[i]);
}
for(int i=0; i<centres.length; i++) {
    System.out.println("Pos centre "+i+": "+centres[i][0]+" "+centres[i][1]);
}
}

Si l'algorithme semble fonctionner, vous pouvez passer à la suite.

Génération de données synthétiques

Pour observer le comportement de l'algorithme des k-moyennes, on va mettre en place une classe permettant de générer des données synthétiques. Tout d'abord, créer la classe TasGaussien. Ensuite vous importerez la bibliothèque java.util.Random.

Commençons par tester cette bibliothèque. Dans la fonction main utiliser la fonction Random.nextDouble() pour générer des nombres aléatoires selon la distribution uniforme dans l'intervalle [0,1].

  • générer 100 nombres aléatoires uniformes et calculer la moyenne \(m\) de votre échantillon.
  • calculer également l'écart type donné par la formule suivante \(\sigma^2 = M^{-1} \sum_{i=1}^M (x^{(i)}-m)^2\) auquel il faudra prendre la racine carrée ensuite.

On va chercher à observer l'allure des variables aléatoires. Pour cela vous allez devoir implémenter une fonction histogramme:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
public static double[][] histogramme(double xmin, double xmax, int NbCases, double[] ech) {
    // On creer le tableau qui va contenir 
    //  0: les abcisses des cases de l'histogramme
    //  1: les valeurs pour chaque case
    double[][] Histo = new double[2][NbCases];
    // TODO: Calcule de la taille d'une case

// TODO: Calcule des abcisses Histo[0][...]

    for(int i=0; i<ech.length; i++) {
        // TODO: pour chaque valeur: trouver a quelle case elle appartient et incrementer de un l'histogramme

    }
    return Histo;
}

Faites maintenant les expériences suivantes:

  1. générer 1000 variables aléatoires uniformes, et calculer l'histogramme dans l'intervalle [0,1]. Visualiser l'histogramme en sauvant les valeurs de l'histogramme dans un fichier (écrire sur une ligne d'abord l'abcisse puis la valeur de l'histogramme séparée par une virgule) et utiliser ensuite le logiciel de votre choix (par exemple gnuplot).
  2. générer 1000 variables gaussiennes (Random.nextGaussian()) et générer l'histogramme de votre échantillon. Comment choisir ici les valeurs de \(x_{\rm min}\) et \(x_{\rm max}\) ?
  3. recommencer le 2. avec 10000 variables.
  4. générer 10000 variables aléatoires gaussiennes : les 5000 premières seront centrées en -3 et les 5000 secondes en 3. Reprendre 2. sur cette échantillon.

Dans chaque cas, vous visualiserez l'histogramme sur un graphe.

Avec deux gaussiennes

Ici on va commencer par générer un jeu de données synthétiques en 2 dimensions.

  1. à l'aide du générateur de variables aléatoires gaussiennes, générer une gaussienne centrée en (-2,2) et une autre en (5,0).
  2. Utiliser ces données avec l'algorithme des k-moyennes et regarder si l'algorithme fonctionne (vous pourrez visualiser les données en utilisant les informations ci-dessous)
  3. Essayer de generaliser l'approche en regardant avec plus de deux partitions.
Quelques tests
  • en générant des 4 clusters, regarder ce qu'il se passe si vous tenter d'inférer les données avec seulement 2 puis 3 centres.
  • en générant 4 clusters et en utilisant 4 centres, enregistrer à chaque étape de l'algorithme la répartition des différentes données et visualiser le résultat.
  • Que se passe-t-il si un centre est initialisé très loin des données ? (faites le test).
Visualisation des données
  1. Pour visualiser un histogramme, il faut dans un fichier enregistrer sur chaque ligne "x hist[x]", càd l'abcisse où on regarder et le nombre d'éléements correspondant dans l'histogramme. Ensuite il suffit sous gnuplot de faire plot "data.d".
  2. Pour viusaliser le nuage de points en deux dimensions il faut enregistrer dans un fichier sur chaque ligne les coordonnées x et y de chaque point. Ensuite il faut taper sous gnuplot plot "data.d". Si vous voulez afficher des couleurs différentes pour des groupes de points différents, vous pouvez espacer dans le fichier les différents groupes de points par deux retour à la ligne, et dans gnuplot il faudra ensuite préciser le numéro du bloc que vous voulez afficher, par exemple pour le bloc 2 : plot "data.d" i 2. Attention les blocs sont énumérés à partir de 0.

TP semaine du 25/11/2019 : La mixture de Gaussiennes

On va maintenant coder l'algorithme de mixture de Gaussiennes. Créer une nouvelle classe MixGauss dans laquelle on écrira l'algorithme. Vous reprendrez la structure décrite pour les k-moyennes (fonction Assigner et Deplct) mais cette fois-ci il faudra faire attention aux différences suivantes :

  • le tableau Assigner sera un double avec deux indices : un pour parcourir les données et un pour parcourir les centres. Vous pourrez vérifier que pour une données, la somme des probabilités d'appartenir à un centre doit être égale à un.
  • Dans la fonction Deplct, il peut-être utile de créer trois fonctions, chacune s'occupant de mettre à un jour un des paramètres.

Rappel des équations d'assignement en dimension \(D\) pour \(K\) gaussiennes :

$$ r_k^{(d)} = \frac{ \rho_k \prod_{i=1}^D \frac{1}{\sqrt{2\pi (\sigma_i^{(k)})^2}} \exp\left[-\frac{(x_i^{(d)} - m_i^{(k)})^2}{2 (\sigma_i^{(k)})^2}\right] }{\sum_{l=1}^{K} \rho_l \prod_{i=1}^D \frac{1}{\sqrt{2\pi (\sigma_i^{(l)})^2}} \exp\left[-\frac{(x_i^{(d)} - m_i^{(l)})^2}{2 (\sigma_i^{(l)})^2}\right] } $$

Rappel des équations de mise à jour (on notera \(R_k=\sum_{d=1}^M r_k^{(d)}\)) :

$$ m_i^{(k)} = \frac{\sum_{d=1}^M r_k^{(d)} x_i^{(d)} }{R_k} \\ (\sigma_i^{(k)})^2 = \frac{\sum_{d=1}^M r_k^{(d)} (x_i^{(d)} - m_i^{(k)})^2}{R_k} \\ \rho_k = \frac{R_k}{M} $$

Premier Test

  1. Reprener les données simples (cf le code java) des k-moyennes et vérifier que votre code converge sur cette exemple
  2. Générer un ensemble de données compososé de deux gaussiennes de 5000 points à une dimension : une centrée en \(x=-3\) et l'autre en \(x=2\), toutes les deux de variance 1. Vérifier que votre algorithme estime correctement les paramètres de la gaussienne. Afficher sur un graphe l'histogramme de vos données ainsi que la fonction représentant les deux gaussiennes.
  3. Refaites le même test mais cette fois en règlant la variance de la première à 0.5 et celle de la second à 2.
  4. Sur ce dernier test, sauvegarder à chaque itération de l'algorithme les paramètres des gaussiennes et tracer sur un même graphe la façon dont les gaussiennes se modifient lors des mise à jour.

cours machine learning