Introduction à l'apprentissage automatique: TP2 - Exercice 1


Algorithmes de partitionnement et données synthétiques

Le but de ce premier exercice est d'explorer des algorithmes de partitionnement ( clustering ) sur des jeux de données synthétiques 2D. On comparera les classifications hiérarchiques de la bibliothèque scipy (de manière à pouvoir tracer les dendrogrammes plus simplement qu'avec les fonctions de scikit-learn), et l'algorithme $K$-means.

Vous pourrez lire les pages complément d'information (CI) plus tard si vous avez besoin de la documentation complète des fonctions utilisées.

Cet exercice est inspiré en partie de cette page de la documentation scikit-learn (CI)

Dans cet exercice (et seulement dans cet exercice), on utilisera les algorithmes de classification hiérarchique de la bibliothèque scipy plutôt que ceux de scikit-learn de manière à tracer facilement les dendrogrammes; ils sont décrits ici (CI)

L'algorithmes des $K$-moyennes ( $K$-means ) est décrit sur cette page (CI) et sur celle-ci (CI, rappel du cours).


TRAVAIL A FAIRE (il s'agit de l'objectif des questions suivantes): mettez en évidence les propriétés / limites des différents algorithmes en jouant sur les paramètres. Pour chaque jeu de données synthétiques défini ci-dessous:

  • pour les classifications hiérarchiques, faites le lien entre le dendrogramme et les valeurs de seuil permettant de trouver des clusters raisonnables dans chaque jeu de donnée
  • quel(s) jeu(x) de données pose(nt) le problème du chaînage pour la classification single linkage ? Dans ce cas, que donne le critère de Ward?
  • pour la méthode des $K$-moyennes, la méthode du coude permet-elle de fixer simplement la valeur de $K$?
  • discutez la pertinence des résultats de chaque méthode selon le jeu de données

Exécutez les cellules de ce carnet Jupyter les unes après les autres. Attention à bien exécuter les cellules dans l'ordre, sinon vous n'allez pas travailler avec les bonnes variables (en particulier, le dendrogramme dans la variable Z doit avoir été déterminé juste avant d'identifier les groupements par seuillage, sinon l'affichage sera incohérent).

En cas de problème d'exécution du code Python, vous pouvez redémarrer le noyau / kernel (onglet dans la barre du carnet Jupyter en haut).

On commence par charger les bibliothèques utiles

In [ ]:
# "magic function" Jupyter pour l'affichage des graphiques dans le carnet:
%matplotlib inline

# import des bibliothèques Python utiles:
import numpy as np
import matplotlib.pyplot as plt
from sklearn import cluster, datasets
from scipy.cluster.hierarchy import dendrogram, linkage, fcluster

# pour les "widgets" Jupyter permettant de régler les valeurs de variables 
import ipywidgets as widgets  
from ipywidgets import interact

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

In [ ]:
n_samples = 100

# blobs isotropes
blobs = datasets.make_blobs(n_samples=n_samples, random_state=8)

# "lunes"
moons = datasets.make_moons(n_samples=n_samples, noise=.05)

# blobs anisotropes
random_state = 170
X, y = datasets.make_blobs(n_samples=n_samples, random_state=random_state)
transformation = [[0.6, -0.6], [-0.4, 0.8]]
X_aniso = np.dot(X, transformation)
aniso = (X_aniso, y)

# blobs d'étalements variés
varied = datasets.make_blobs(n_samples=n_samples,
                             cluster_std=[1.0, 2.5, 0.5],
                             random_state=random_state)

Partitionnement des jeux de données avec différents algorithmes

Visualisation du jeu de données à partitionner

La première ligne de la cellule suivante permet de changer le jeu de données: commencez par blobs et exécutez le carnet jusque la fin, puis ré-exécuter le carnet depuis ici avec moons , aniso , varied .

In [ ]:
X,y = blobs  # changer le dataset ici (commencer par blobs, puis moons, aniso, varied)

plt.figure(figsize=[10,8])
plt.scatter(X[:, 0], X[:, 1], s=40)
plt.title('dataset'); # on met un ";" final sous Jupyter pour éviter des affichages intempestifs dans le carnet

Classification hiérarchique, critère single-linkage

On commence par afficher le dendrogramme

In [ ]:
Z = linkage(X,method="single")
maxdist=max(Z[:,2])  # hauteur du dendrogramme 
plt.figure(figsize=[10,8]);
dendrogram(Z) #,truncate_mode="level",p=10);  # le paramètre p permet éventuellement de ne pas afficher le "bas" du dendrogramme, utile pour un grand jeu de données
plt.title('Single linkage dendrogram with scipy');  

La cellule suivante permet de changer la valeur du seuil (variable seuil ) dans le dendrogramme de manière interactive (cela fixe donc le nombre de clusters) et affiche la classification non-supervisée correspondante:

In [ ]:
@interact(seuil=(0,maxdist,maxdist/100))   # "décorateur" Jupyter, permettant une interaction avec un argument de la fonction
def graphique_clustering_single(seuil):
    clusters=fcluster(Z, seuil, criterion='distance') 
    plt.figure(figsize=[10,8]);
    plt.scatter(X[:, 0], X[:, 1], s=40, c=clusters, cmap='jet');
    plt.title('Single linkage with scipy, seuil='+str(seuil)+', nombres de clusters: '+str(max(clusters)));
In [ ]:
# dans certains cas (en particulier sur MacOS) @interact ne fonctionne pas
# si vous êtes dans cette situation, faites varier la valeur de seuil entre 0 et maxdist et appelez la fonction d'affichage:
# vous ferez de même dans les cellules ci-dessous faisant appel à @interact
print(maxdist)
seuil= 0.5
print(seuil)
graphique_clustering_single(seuil)

Question 1. Jouez avec le seuil et faites le lien entre le dendogramme et le nombre de groupes. Selon le dataset, la classification obtenue vous semble-t-elle correspondre à ce qu'on aimerait obtenir?

Réciproquement, la cellule suivante permet de changer la valeur du nombre de clusters ($nc$) à trouver:

In [ ]:
@interact(nc=(1,10,1))
def graphique_clustering_single(nc):
    clusters=fcluster(Z, nc, criterion='maxclust') 
    plt.figure(figsize=[10,8]);
    plt.scatter(X[:, 0], X[:, 1], s=40, c=clusters, cmap='jet');
    plt.title('Single linkage with scipy, n_cluster='+str(nc));

Classification hiérarchique, critère de Ward

On commence par afficher le dendrogramme:

In [ ]:
Z = linkage(X,method="ward")
maxdist=max(Z[:,2])
plt.figure(figsize=[10,8]);
dendrogram(Z)#,truncate_mode="level",p=5)
plt.title('Ward criterion dendrogram with scipy');  # met quelques secondes à s'afficher

Question 2. Comparez l'aspect du dendrogramme avec celui obtenu avec le critère single-linkage, et les différences de comportement selon le dataset.

Changez la valeur du seuil (variable seuil ) dans le dendrogramme (qui fixe le nombre de clusters):

In [ ]:
@interact(seuil=(0,maxdist,maxdist/100))
def graphique_clustering_Ward(seuil):
    clusters=fcluster(Z, seuil, criterion='distance') 
    plt.figure(figsize=[10,8]);
    plt.scatter(X[:, 0], X[:, 1], s=40, c=clusters, cmap='jet');
    plt.title('Ward linkage with scipy, seuil='+str(seuil)+', nombres de clusters: '+str(max(clusters)));

On peut aussi changer la valeur du nombre de clusters (nc) à trouver:

In [ ]:
@interact(nc=(1,10,1))
def graphique_clustering_Ward(nc):
    clusters=fcluster(Z, nc, criterion='maxclust') 
    plt.figure(figsize=[10,8]);
    plt.scatter(X[:, 0], X[:, 1], s=40,c=clusters,cmap='jet');
    plt.title('Ward linkage with scipy, n_cluster='+str(nc));

$K$-means

Changez la valeur du nombre $K$ de clusters:

In [ ]:
@interact(K=(1,10,1))
def graphique_clustering_KMeans(K):
    clustering=cluster.KMeans(n_clusters=K)  
    clustering.fit(X)
    print("Inertie: %.2f" % clustering.inertia_)
    plt.figure(figsize=[10,8]);
    plt.scatter(X[:, 0], X[:, 1], s=40,c=clustering.labels_,cmap='jet');
    plt.title('Kmeans, n_cluster='+str(K));

Question 3. Pour quels datasets $K$-means vous semble-t-il adapté? Constatez que d'une exécution à l'autre, l'algorithme peut donner un résultat différent. Pour quelle raison?

On va tracer le graphique de l'inertie en fonction du nombre $K$ de clusters cherchés. La méthode du "coude" ( elbow ) fixe $K$ comme le premier point du graphique où l'inertie ne baisse plus vraiment et s'infléchit (présence d'un "coude").

In [ ]:
inertie=np.zeros((10))
for K in range(1,11):
    clustering=cluster.KMeans(n_clusters=K)
    clustering.fit(X)
    inertie[K-1]=clustering.inertia_
plt.figure(figsize=[10,8]);
plt.plot(np.arange(1,11),inertie);
plt.xlabel("K");
plt.ylabel("inertie");
plt.title("elbow plot");

Question 4. Dans quel cas la méthode du coude vous semble-t-elle adaptée?