Travaux pratiques - Classification spectrale

(correspond à 1 séance de TP)

Références externes utiles :

L’objectif de cette séance de TP est de présenter l’utilisation des fonctionnalités de scikit-learn concernant la classification spectrale, ainsi que de contribuer à une meilleure compréhension de cette méthode et de l’impact de la distribution des données sur les résultats. Des questions visent les différences dans les résultats obtenus par rapport à k-means. Pour cela, sont d’abord examinées des données générées de façon contrôlée et ensuite des données réelles vues en cours, sans ou avec un pré-traitement permettant de renforcer la séparation entre groupes.

La classification spectrale dans scikit-learn

La description de l’implémentation de la classification spectrale est dans SpectralClustering.

Pour définir la classification spectrale on appelle SpectralClustering(n_clusters=8, eigen_solver=None, random_state=None, n_init=10, gamma=1.0, affinity='rbf', n_neighbors=10, eigen_tol=0.0, assign_labels='kmeans', degree=3, coef0=1, kernel_params=None, n_jobs=1). Les paramètres d’appel sont (pour des explications complémentaires voir le lien ci-dessus) :

  • n_clusters : nombre de groupes demandé.

  • eigen_solver : solveur employé pour obtenir les valeurs propres de la matrice \(\mathbf{L}_{rw}\), peut être None, 'arpack', 'lobpcg', ou 'amg' ; pour “amg” (efficace sur de très grandes matrices creuses, mais aussi source d’instabilités) il est nécessaire d’avoir installé pyamg.

  • random_state : initialisation du générateur de nombres aléatoires pour eigen_solver = 'amg' et pour l’étape K-means finale.

  • n_init : nombre de relances (10 par défaut) de K-means pour obtenir les étiquettes de groupe ; la meilleure solution obtenue suite à ces relances este retenue.

  • gamma : facteur d’échelle employé pour le calcul de la similarité à travers des fonctions-noyaux ; sa valeur est l’inverse de la variance du noyau.

  • affinity : moyen employé pour obtenir la matrice de similarité (affinity) ; peut être une chaîne de caractères comme 'nearest_neighbors' (obtenue à partir des k plus proches voisins), 'rbf' (obtenue à travers le noyau gaussien), autres noyaux (qui doivent produire seulement des valeurs positives), 'precomputed' (la matrice de données transmise pour .fit() est en fait une matrice de similarités), une fonction de calcul, etc.

  • n_neighbors : valeur du nombre de voisins considérés pour la construction du graphe lorsque affinity = 'nearest_neighbors'.

  • eigen_tol : critère d’arrêt pour l’extraction des valeurs propres avec eigen_solver = 'arpack'.

  • assign_labels : méthode employée au final pour produire les étiquettes, peut être 'kmeans' ou 'discretize'.

  • degree : degré du polynôme si noyau polynomial.

  • coef0 : coefficient 0 pour noyau polynomial ou sigmoïde.

  • kernel_params : paramètres (sous forme de dictionnaire python) de certains noyaux.

  • n_jobs : nombre de tâches à lancer en parallèle (avec -1, autant detâche que de coeurs de CPU disponibles).

Les attributs accessibles sont les suivants :

  • affinity_matrix_ : matrice de similarités employée ; disponible après l’appel de .fit().

  • labels_ : étiquettes de groupe issues de la classification automatique.

Les méthodes qui peuvent être employées :

  • fit(X[, y]) : calcul de la matrice de similarité (si non fournie), puis classification des données à partir de X ; si la matrice de similarités est fournie (affinity = 'precomputed'), alors X est la matrice de similarités !

  • fit_predict(X, y) : classification et retourne dans y les étiquettes de groupe.

  • get_params([deep]) : lire les valeurs des paramètres de l’estimateur employé.

  • set_params(**params) : donner des valeurs aux paramètres de l’estimateur employé.

Nous nous servirons, ici encore, de l’indice de Rand ajusté pour évaluer la cohérence entre des classifications différentes d’un même ensemble de données.

Classification spectrale de données générées

Commencez par une classification spectrale des données générées suivant 5 lois normales dans le TP sur K-means. Les données sont générées par :

import numpy as np    # si pas encore fait

from sklearn.utils import shuffle

data1 = np.random.randn(100,3) + [3,3,3]
data2 = np.random.randn(100,3) + [-3,-3,-3]
data3 = np.random.randn(100,3) + [-3,3,3]
data4 = np.random.randn(100,3) + [-3,-3,3]
data5 = np.random.randn(100,3) + [3,3,-3]

ones = np.ones(100)
c1, c2, c3, c4, c5 = ones, 2 * ones, 3 * ones, 4 * ones, 5 * ones
data = np.concatenate((data1,data2,data3,data4,data5))
labels = np.concatenate((c1, c2, c3, c4, c5))
print(data.shape)   # vérification
# (500, 4)
print(labels.shape)
# (500,)
data, labels = shuffle(data, labels)

import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(data[:,0], data[:,1], data[:,2])
plt.title("Données d'apprentissage")
plt.show()

Appliquez la classification spectrale avec une construction du graphe sur la base des k plus proches voisins (affinity='nearest_neighbors' ; la valeur par défaut du nombre de voisins n_neighbors est 10) :

from sklearn.cluster import SpectralClustering
spectral = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='nearest_neighbors').fit(data)

Visualisez les résultats de cette classification :

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')
ax.scatter(data[:,0], data[:,1], data[:,2], c=spectral.labels_)
plt.title("Classification spectrale")
plt.show()

L’indice de Rand ajusté permet d’évaluer la cohérence entre les groupes de départ et le partitionnement trouvé par classification automatique :

from sklearn import metrics
metrics.adjusted_rand_score(spectral.labels_, labels)

L’appel à metrics.adjusted_rand_score() compare le partitionnement obtenu par la classification automatique (ici, étiquettes de groupe de spectral.labels_) avec le partitionnement correspondant aux groupes définis au départ (étiquettes de la dernière colonne de data).

Question :

Répétez plusieurs fois la classification avec des valeurs différentes (mais \(\geq 1\)) pour le paramètre n_neighbors (dont la valeur par défaut est 10). Que constatez-vous ? Expliquez.

Correction :

Il faut préciser la valeur de n_neighbors dans la liste des paramètres :

spectral = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='nearest_neighbors', n_neighbors=7).fit(data)

On observe une forte stabilité (indiquée par des valeurs de 1 ou très proches de 1 pour l’indice de Rand ajusté) pour n_neighbors \(\geq 7\). Pour des valeurs inférieures, en revanche, beaucoup d’observations sont des sommets isolés dans le graphe, les résultats de classification sont médiocres (car il y a trop de composantes connexes) et la stabilité est faible (valeurs diverses et faibles de l’indice de Rand ajusté).

Question :

Changez le mode de calcul de la matrice de similarités avec affinity = 'rbf', faites varier le paramètre correspondant gamma et visualisez les résultats. Attention, gamma n’est pas l’écart-type \(\sigma\) du noyau gaussien ('rbf') utilisé mais plutôt \(1/\sigma^2\).

Correction :

Il faut préciser la valeur de gamma dans la liste des paramètres :

spectral = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='rbf', gamma=1.0).fit(data)

On observe une forte stabilité (indiquée par des valeurs de 1 ou très proches de 1 pour l’indice de Rand ajusté) pour gamma \(\leq 8\). Pour des valeurs supérieures, en revanche, beaucoup d’observations sont des sommets isolés dans le graphe, les résultats de classification sont médiocres (car il y a trop de composantes connexes) et la stabilité est faible (valeurs diverses et faibles de l’indice de Rand ajusté).

Question :

Sur les 500 données générées comme au TP précédent (sur K-means) suivant une distribution uniforme dans \([0, 1)^3\), appliquez la classification spectrale avec toujours n_clusters=5 et visualisez les résultats. Examinez la stabilité (en utilisant l’indice de Rand) des partitionnements obtenus. Observez-vous des différences significatives par rapport aux résultats obtenus lors du TP sur K-means ? Expliquez.

Correction :

 udata = np.random.rand(500,3)
 spectral = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='nearest_neighbors').fit(udata)

 fig = plt.figure()
 ax = fig.add_subplot(111, projection='3d')
 ax.scatter(udata[:,0], udata[:,1], udata[:,2], c=spectral.labels_)
 plt.show()

 spectral2 = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='nearest_neighbors').fit(udata)
 metrics.adjusted_rand_score(spectral2.labels_, spectral.labels_)
 spectral2 = SpectralClustering(n_clusters=5, eigen_solver='arpack', affinity='nearest_neighbors').fit(udata)
 metrics.adjusted_rand_score(spectral2.labels_, spectral.labels_)

Les résultats sont bien plus stables que lors de l'application directe de *K-means*. Cela s'explique par la meilleure qualité de la représentation des données obtenue dans l'étape de *embedding* spectral, qui a comme conséquence une plus faible dépendance des résultats de l'intialisation aléatoire utilisée pour le calcul des étiquettes (par application de *K-means* sur les lignes de la matrice :math:`\mathbf{U}_k`).
Pour retrouver l'instabilité des résultats, indiquant l'absence de structure dans les données, il est nécessaire de faire varier d'autres paramètres, comme ``n_neighbors`` (si ``affinity = 'nearest_neighbors'``) ou ``gamma`` (``affinity = 'rbf'``).

Classification spectrale des données « textures »

Pour rappel, ces données correspondent à 5500 observations décrites par 40 variables. Chaque observation appartient à une des 11 classes de textures ; chaque classe est représentée par 500 observations. Les données sont issues de https://www.elen.ucl.ac.be/neural-nets/Research/Projects/ELENA/databases/REAL/texture/. Nous appliquerons la classification spectrale à ces données, avec n_clusters = 11, et examinerons dans quelle mesure les groupes issus de la classification automatique se rapprochent des classes présentes.

Si les données ne sont pas dans le répertoire de travail il est nécessaire de les chercher d’abord. En ligne de commande :

%%bash
wget -nc http://cedric.cnam.fr/~crucianm/src/texture.dat

Mélangez les observations et appliquez la classification spectrale à ces données (attention, la dernière colonne contient les étiquettes de classe) :

textures = np.loadtxt('texture.dat')
np.random.shuffle(textures)
spectral = SpectralClustering(n_clusters=11, eigen_solver='arpack',
               affinity='nearest_neighbors').fit(textures[:,:40])
metrics.adjusted_rand_score(spectral.labels_, textures[:,40])
# 0.58187284077679202

On constate que les groupes issus de la classification spectrale se rapprochent un peu plus des classes présentes dans ces données que les groupes issus de l’application directe de K-means.

Question :

Après une analyse discriminante de ces données, appliquez la classification spectrale avec n_clusters = 11 aux données projetées dans l’espace discriminant. Que constatez-vous ? Expliquez. Visualisez les résultats.

Correction :

from sklearn.discriminant_analysis import LinearDiscriminantAnalysis
lda = LinearDiscriminantAnalysis()
lda.fit(textures[:,:40],textures[:,40])

texturest = lda.transform(textures[:,:40])
spectral = SpectralClustering(n_clusters=11, eigen_solver='arpack',
               affinity='nearest_neighbors').fit(texturest)
metrics.adjusted_rand_score(spectral.labels_, textures[:,40])
# 0.88065883985307725

La classification spectrale arrive à retrouver un peu mieux les classes de données, mais les résultats sont moins bons que ceux obtenus par l’application directe de K-means (voir TP précédent). Cela est la conséquence de la présence de « chemins » (données intermédiaires) entre les « blobs » qui constituent les différentes classes. Ces « chemins » ont plus d’impact sur la classification spectrale que sur K-means.