Le clustering spectral expliqué : comment les vecteurs propres révèlent des structures de cluster complexes

et les vecteurs propres sont des concepts clés de l’algèbre linéaire qui jouent également un rôle important dans la science des données et l’apprentissage automatique. Auparavant, nous avons discuté de la façon dont la réduction de dimensionnalité peut être effectuée avec les valeurs propres et les vecteurs propres de la matrice de covariance.

Aujourd’hui, nous allons aborder une autre application intéressante : comment les valeurs propres et les vecteurs propres peuvent être utilisés pour effectuer un clustering spectral, qui fonctionne bien avec des structures de cluster complexes.

Dans cet article, nous explorerons comment les valeurs propres et les vecteurs propres rendent possible le regroupement spectral et pourquoi cette méthode peut surpasser les K-moyennes traditionnelles.

Nous commencerons par une visualisation simple qui vous montrera l’importance du regroupement spectral et vous motivera à continuer à apprendre comment le regroupement spectral peut être effectué avec des valeurs propres et des vecteurs propres.

Motivation pour le clustering spectral

Un excellent moyen d’apprendre le clustering spectral est de le comparer avec un algorithme de clustering traditionnel comme K-means sur un ensemble de données où K-means a du mal à fonctionner correctement.

Ici, nous utilisons un ensemble de données à deux lunes généré artificiellement où les clusters sont courbés. Le Scikit-learn make_moons l’algorithme génère deux lunes dans un espace à 2 dimensions. Ensuite, nous utilisons Scikit-learn KMoyennes et Clustering spectral algorithmes pour effectuer des K-moyennes et un clustering spectral. Enfin, nous comparons les visualisations de cluster.

Créer des données lunaires

# Make moon data
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

X, y = make_moons(n_samples=400, noise=0.05,
                  random_state=0)

plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], s=20)
plt.title("Original Moon Data")
plt.savefig("Moon data.png")

L’ensemble de données d’origine comporte deux structures de cluster courbes appelées lunes. C’est pourquoi nous l’appelons données lunaires.

Application des K-means aux données lunaires

# Apply K-means
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=2, random_state=0)

# Predict cluster index for each data point
labels_kmeans = kmeans.fit_predict(X)

# Visualize Clusters
plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], c=labels_kmeans, s=20)
plt.title("K-Means Clustering")
plt.savefig("K-means.png")

K-means regroupe souvent les données lunaires de manière incorrecte (il mélange incorrectement les points de données).

Application du regroupement spectral aux données lunaires

# Apply spectral clustering
from sklearn.cluster import SpectralClustering

spectral = SpectralClustering(n_clusters=2,
                              affinity='nearest_neighbors',
                              random_state=0)

# Predict cluster index for each data point
labels_spectral = spectral.fit_predict(X)

# Visualize Clusters
plt.figure(figsize=[4.2, 3])
plt.scatter(X[:,0], X[:,1], c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral.png")

Désormais, les points de données sont correctement attribués aux lunes, qui ressemblent aux données originales. Le clustering spectral fonctionne bien sur les structures de cluster complexes. En effet, les vecteurs propres de la matrice laplacienne lui permettent de détecter des structures de cluster complexes.

Jusqu’à présent, nous avons implémenté le clustering spectral en utilisant le module intégré Clustering spectral algorithme dans Scikit-learn. Ensuite, vous apprendrez comment implémenter le clustering spectral à partir de zéro. Cela vous aidera à comprendre comment les valeurs propres et les vecteurs propres fonctionnent dans les coulisses de l’algorithme.

Qu’est-ce que le clustering spectral ?

Le clustering spectral regroupe les points de données en fonction de leurs similitudes plutôt que de leurs distances. Cela lui permet de révéler des structures de cluster complexes et non linéaires sans suivre les hypothèses du clustering traditionnel à k-moyennes.

L’intuition derrière la réalisation du clustering spectral est la suivante :

Étapes pour effectuer un clustering spectral

1. Obtenir des données
2. Construire la similarité matrice
3. Construire la matrice des diplômes
4. Construire la matrice laplacienne (graphe Laplacien)
5. Trouvez les valeurs propres et les vecteurs propres de la matrice laplacienne. Les vecteurs propres révèlent la structure du cluster (comment les points de données se regroupent), agissant comme de nouvelles fonctionnalités, et les valeurs propres indiquent la force de la séparation des clusters.
6. Sélectionnez les vecteurs propres les plus importants pour intégrer les données dans une dimension inférieure (réduction de dimensionnalité)
7. Appliquer des K-means sur le nouvel espace de fonctionnalités (clustering)

Le clustering spectral combine la réduction de dimensionnalité et le clustering K-means. Nous intégrons les données dans un espace de dimension inférieure (où les clusters sont plus faciles à séparer), puis effectuons un clustering K-means sur le nouvel espace de fonctionnalités. En résumé, le clustering K-means fonctionne dans l’espace de fonctionnalités d’origine tandis que le clustering spectral fonctionne dans le nouvel espace de fonctionnalités réduit.

Implémentation du clustering spectral – étape par étape

Nous avons résumé les étapes de regroupement spectral avec les valeurs propres et les vecteurs propres de la matrice laplacienne. Implémentons ces étapes avec Python.

1. Obtenez des données

Nous utiliserons les mêmes données que celles utilisées précédemment.

from sklearn.datasets import make_moons

X, y = make_moons(n_samples=400, noise=0.05,
                  random_state=0)

2. Construire la matrice de similarité (affinité)

Le clustering spectral regroupe les points de données en fonction de leurs similitudes. Par conséquent, nous devons mesurer la similarité entre les points de données et inclure ces valeurs dans une matrice. Cette matrice est appelée la matrice de similarité (W). Ici, nous mesurons la similarité à l’aide d’un Noyau gaussien.

Si vous avez n nombre de points de données, la forme de W est (n,n). Chaque valeur représente la similarité entre deux points de données. Les valeurs plus élevées dans les points moyens de la matrice sont plus similaires.

from sklearn.metrics.pairwise import rbf_kernel

W = rbf_kernel(X, gamma=20)

3. Construire la matrice des diplômes

La matrice de degrés (D) contient la somme des similitudes pour chaque nœud. Il s’agit d’une matrice diagonale et chaque valeur diagonale montre la similitude totale de ce point avec tous les autres points. Tous les éléments hors diagonale sont nuls. La forme de la matrice des degrés est également (n,n).

import numpy as np

D = np.diag(np.sum(W, axis=1))

np.sum(W, axis=1)fait la somme de chaque ligne de la matrice de similarité.

4. Construire la matrice laplacienne

La matrice laplacienne (L) représente la structure du graphe de similarité, où les nœuds représentent chaque point de données et les arêtes relient des points similaires. Ainsi, cette matrice est aussi appelée la graphique Laplacien et est défini comme suit.

En Python, c’est

L = D - W

D-W pour L garantit mathématiquement que le regroupement spectral trouvera des groupes de points de données qui sont fortement connectés au sein du groupe mais faiblement connectés aux autres groupes.

La matrice laplacienne (L) est aussi un (n,n) matrice carrée. Cette propriété est importante pour L car la décomposition propre n’est définie que pour les matrices carrées.

5. Décomposition propre de la matrice laplacienne

Décomposition propre de la matrice laplacienne est le processus de décomposition (factorisation) de cette matrice en valeurs propres et vecteurs propres [ref: Eigendecomposition of a Covariance Matrix with NumPy]

Si la matrice laplacienne (L) a n vecteurs propres, nous pouvons le décomposer comme suit :

Où:

• X = matrice de vecteurs propres
• Λ = matrice diagonale de valeurs propres

Les matrices X et Λ peut être représenté comme suit :

Les vecteurs x1, x2 et x3 sont des vecteurs propres et λ1, λ2 et λ3 sont leurs valeurs propres correspondantes.

Les valeurs propres et les vecteurs propres viennent par paires. Une telle paire est connue sous le nom de paire propre. Donc matrice L peut avoir plusieurs paires propres [ref: Eigendecomposition of a Covariance Matrix with NumPy]

L’équation aux valeurs propres suivante montre la relation entre L et une de ses paires propres.

Où:

• L = Matrice laplacienne (devrait être une matrice carrée)
• x = vecteur propre
• λ = valeur propre (facteur d’échelle)

Calculons toutes les paires propres de la matrice laplacienne.

eigenvalues, eigenvectors = np.linalg.eigh(L)

6. Sélectionnez les vecteurs propres les plus importants

En clustering spectral, l’algorithme utilise les plus petits vecteurs propres de la matrice laplacienne. Nous devons donc sélectionner les plus petits dans le vecteurs propres matrice.

Les plus petites valeurs propres correspondent aux plus petits vecteurs propres. Le huit() La fonction renvoie les valeurs propres et les vecteurs propres par ordre croissant. Nous devons donc examiner les premières valeurs de valeurs propres vecteur.

print(eigenvalues)

Nous prêtons attention à la différence entre valeurs propres consécutives. Cette différence est connue sous le nom écart propre. Nous sélectionnons la valeur propre qui maximise l’écart propre. Il représente le nombre de clusters. Cette méthode est appelée la heuristique d’écart propre.

Selon l’heuristique eigengap, le nombre optimal de clusters k est sélectionné au point où le saut le plus grand se produit entre les valeurs propres successives.

S’il y a k de très petites valeurs propres, il y aura k groupes! Dans notre exemple, les deux premières petites valeurs propres suggèrent deux clusters, ce qui est exactement ce à quoi nous nous attendons. C’est le rôle des valeurs propres dans le regroupement spectral. Ils sont très utiles pour décider du nombre de clusters et des plus petits vecteurs propres !

On sélectionne les deux premiers vecteurs propres correspondant à ces petites valeurs propres.

k = 2
U = eigenvectors[:, :k]

Ces deux vecteurs propres dans la matrice U représentent un nouvel espace de fonctionnalités appelé intégration spectrale, où les clusters deviennent linéairement séparables. Voici la visualisation de l’intégration spectrale.

import matplotlib.pyplot as plt

plt.figure(figsize=[4.2, 3])
plt.scatter(U[:,0], U[:,1], s=20)
plt.title("Spectral Embedding")
plt.xlabel("Eigenvector 1")
plt.ylabel("Eigenvector 2")
plt.savefig("Spectral embedding.png")

Ce graphique montre comment les vecteurs propres transforment les données d’origine en un nouvel espace où les clusters deviennent linéairement séparables.

7. Appliquer des K-means sur l’intégration spectrale

Maintenant, nous pouvons simplement appliquer des K-moyennes dans l’intégration spectrale (nouvel espace vectoriel propre) pour obtenir des étiquettes de cluster, puis nous attribuons ces étiquettes aux données d’origine pour créer des clusters. K-means fonctionne bien ici car les clusters sont linéairement séparables dans le nouvel espace vectoriel propre.

import matplotlib.pyplot as plt
from sklearn.cluster import KMeans

kmeans = KMeans(n_clusters=k)
labels_spectral = kmeans.fit_predict(U)
# U represents spectral embedding

plt.figure(figsize=[4.2, 3])
# Assign cluster labels to original data
plt.scatter(X[:,0], X[:,1], c=labels_spectral, s=20)
plt.title("Spectral Clustering")
plt.savefig("Spectral Manual.png")

C’est la même chose que ce que nous avons obtenu de la version Scikit-learn !

Choisir la bonne valeur pour Gamma

Lors de la création de la matrice de similarité ou de la mesure de la similarité à l’aide d’un noyau gaussien, nous devons définir la bonne valeur pour le gamma hyperparamètre, qui contrôle la rapidité avec laquelle la similarité diminue avec la distance entre les points de données.

from sklearn.metrics.pairwise import rbf_kernel

W = rbf_kernel(X, gamma=?)

Pour les petites valeurs gamma, la similarité diminue lentement et de nombreux points semblent similaires. Par conséquent, cela entraîne des structures de cluster incorrectes.

Pour des valeurs gamma élevées, la similarité diminue très rapidement et seuls les points très proches sont connectés. Les clusters deviennent donc fortement séparés.

Pour les valeurs moyennes, vous obtiendrez des clusters équilibrés.

Il est préférable d’essayer plusieurs valeurs, telles que 0,1, 0,5, 1, 5, 10, 15, et de visualiser les résultats du clustering pour choisir la meilleure.

Pensées finales

Dans le clustering spectral, un ensemble de données est représenté sous forme de graphique au lieu d’une collection de points. Dans ce graphique, chaque point de données est un nœud et les lignes (bords) entre les nœuds définissent la façon dont les points similaires se connectent entre eux.

L’algorithme de regroupement spectral a besoin de cette représentation graphique sous une forme mathématique. C’est pourquoi nous avons construit une matrice de similarité (affinité) (W). Chaque valeur de cette matrice mesure la similarité entre les points de données. Les valeurs élevées dans la matrice signifient que deux points sont très similaires, tandis que les valeurs faibles signifient que deux points sont très différents.

Ensuite, nous avons construit la matrice des degrés (D), qui est une matrice diagonale dans laquelle chaque valeur diagonale montre la similarité totale de ce point avec tous les autres points.

En utilisant la matrice de degrés et la matrice de similarité, nous avons construit la matrice laplacienne du graphe, qui capture la structure du graphe et est essentielle pour le regroupement spectral.

Nous avons calculé les valeurs propres et les vecteurs propres du Matrice laplacienne. Les valeurs propres aident à choisir le meilleur nombre de clusters et les plus petits vecteurs propres. Ils indiquent également la force de la séparation des clusters. Les vecteurs propres révèlent la structure du cluster (limites du cluster ou comment les points de données se regroupent) et sont utilisés pour obtenir un nouvel espace de fonctionnalités dans lequel les points fortement connectés du graphique se rapprochent dans cet espace. Les clusters deviennent plus faciles à séparer et K-means fonctionne bien dans le nouvel espace.

Voici le flux de travail complet du clustering spectral.

Ensemble de données → Graphique de similarité → Graphique laplacien → Vecteurs propres → Clusters

---

C’est la fin de l’article d’aujourd’hui.

S’il vous plaît laissez-moi savoir si vous avez des questions ou des commentaires.

Rendez-vous dans le prochain article. Bon apprentissage à vous !

Conçu et rédigé par :
Rukshan Pramoditha

2025-03-08