Spectral Clustering : Guide complet — Principes, Exemples et Implémentation Python

Résumé

Le Spectral Clustering est une méthode de clustering non supervisé qui repose sur la théorie spectrale des graphes. Contrairement au K-Means classique qui suppose des clusters sphériques et convexes, le Spectral Clustering est capable de détecter des structures complexes, non convexes, comme des cercles concentriques ou des demi-lunes enchevêtrées. Le principe fondamental consiste à construire une matrice de similarité entre les points, à en extraire les vecteurs propres de la matrice laplacienne, puis à appliquer un K-Means dans cet espace spectral réduit. Ce guide complet explore les fondements mathématiques, l’intuition géométrique, et l’implémentation pratique du Spectral Clustering avec Python et scikit-learn.

Principe mathématique

Le Spectral Clustering s’articule autour de plusieurs étapes mathématiques rigoureuses qui transforment un problème de clustering difficile en un problème plus simple dans un espace spectral.

1. Construction de la matrice de similarité W

La première étape consiste à mesurer la similarité entre chaque paire de points de données. Pour un ensemble de n points {x₁, x₂, …, xₙ}, on construit une matrice de similarité W ∈ ℝⁿˣⁿ où chaque élément wᵢⱼ quantifie à quel point les points xᵢ et xⱼ sont similaires.

Le choix le plus courant est le noyau RBF (Radial Basis Function), aussi appelé noyau gaussien :

wᵢⱼ = exp(-‖xᵢ – xⱼ‖² / 2σ²)

où σ² est le paramètre de largeur du noyau. Plus deux points sont proches dans l’espace original, plus leur similarité est élevée (proche de 1). À l’inverse, deux points éloignés auront une similarité proche de zéro.

On peut également utiliser d’autres stratégies de construction :

• ε-voisinage : wᵢⱼ = 1 si ‖xᵢ – xⱼ‖ < ε, sinon 0
• k-plus proches voisins : chaque point est connecté à ses k plus proches voisins uniquement

En pratique, dans scikit-learn, le paramètre γ (gamma) contrôle la largeur du noyau RBF avec γ = 1/(2σ²), ce qui donne :

wᵢⱼ = exp(-γ × ‖xᵢ – xⱼ‖²)

2. Matrice des degrés D

À partir de la matrice de similarité W, on définit la matrice des degrés D, une matrice diagonale où chaque élément diagonal représente la somme des similarités d’un point avec tous les autres :

dᵢ = Σⱼ wᵢⱼ

D = diag(d₁, d₂, …, dₙ)

Le degré dᵢ peut être interprété comme l’« importance » ou la « connectivité » du point i dans le graphe de similarité. Un point bien connecté à beaucoup d’autres aura un degré élevé.

3. Matrice laplacienne L

La matrice laplacienne est l’objet central du Spectral Clustering. Elle capture la structure du graphe de similarité et ses propriétés spectrales révèlent les structures de clusters naturelles.

Laplacienne non normalisée :

L = D – W

Laplacienne normalisée symétrique (la plus utilisée en pratique) :

L_sym = D^(-1/2) × L × D^(-1/2) = I – D^(-1/2) × W × D^(-1/2)

Laplacienne normalisée asymétrique :

L_rw = D^(-1) × L = I – D^(-1) × W

La normalisation est importante car elle évite que des points à fort degré dominent la décomposition spectrale. La laplacienne possède des propriétés mathématiques remarquables : elle est symétrique, semi-définie positive, et sa multiplicité de la valeur propre zéro correspond exactement au nombre de composantes connexes du graphe.

4. Décomposition spectrale

On calcule les k plus petites valeurs propres et les k vecteurs propres correspondants de la matrice laplacienne L. Ces k vecteurs propres forment une matrice U ∈ ℝⁿˣᵏ où chaque ligne correspond à un point de données représenté dans l’espace spectral.

Pourquoi les plus petites valeurs propres ? Parce que la laplacienne encode la « tension » du graphe : les vecteurs propres associés aux petites valeurs propres correspondent aux directions dans lesquelles le graphe se sépare naturellement en clusters. C’est l’analogue spectral de la découpe minimale d’un graphe.

5. K-Means sur les vecteurs propres

Enfin, on applique l’algorithme K-Means sur les lignes de la matrice U. Chaque ligne de U est un point en dimension k, et le K-Means les regroupe en k clusters. L’affectation obtenue est transposée directement aux points de données originaux.

L’algorithme de Ng, Jordan et Weiss (2002) ajoute une étape de normalisation supplémentaire : avant d’appliquer K-Means, on normalise chaque ligne de U pour avoir une norme unitaire. Cette normalisation améliore significativement les résultats en projetant les points sur la sphère unité.

Intuition géométrique

L’idée centrale du Spectral Clustering est à la fois élégante et puissante : au lieu de clustériser directement les points dans leur espace d’origine, on les projette dans un espace spectral où les clusters deviennent naturellement séparables.

Imaginez un jeu de données formé de deux cercles concentriques. Dans l’espace bidimensionnel original, aucun hyperplan linéaire ne peut séparer le cercle intérieur du cercle extérieur. Le K-Means, qui cherche des partitions convexes, échouera systématiquement.

Le Spectral Clustering, lui, raisonne en termes de connectivité plutôt que de distance brute. Deux points sur le même cercle sont bien connectés (ils sont proches les uns des autres le long du cercle), tandis que deux points situés sur des cercles différents sont faiblement connectés (la distance radiale est grande). La matrice de similarité capture cette intuition, et la décomposition spectrale de la laplacienne révèle cette structure.

C’est comme éclairer les données sous un angle magique où les groupes deviennent évidents. L’espace spectral agit comme un prisme qui décompose la lumière des données en ses composantes fondamentales, révélant des structures cachées invisibles dans l’espace original.

Cette approche est profondément liée à la théorie des graphes : le Spectral Clustering revient à chercher la coupe minimale d’un graphe pondéré, c’est-à-dire la partition qui minimise les arêtes coupées entre les clusters tout en maximisant les arêtes à l’intérieur de chaque cluster.

Implémentation Python

Exemple de base avec scikit-learn

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import SpectralClustering, KMeans
from sklearn.datasets import make_circles, make_moons
from sklearn.metrics import adjusted_rand_score

# --- Données de démonstration : cercles concentriques ---
X_circles, y_circles = make_circles(
    n_samples=500, factor=0.5, noise=0.05, random_state=42
)

# Spectral Clustering
sc = SpectralClustering(
    n_clusters=2,
    affinity='rbf',
    gamma=10,
    assign_labels='kmeans',
    random_state=42
)
labels_sc = sc.fit_predict(X_circles)

# K-Means pour comparaison
km = KMeans(n_clusters=2, random_state=42)
labels_km = km.fit_predict(X_circles)

# Évaluation
ari_sc = adjusted_rand_score(y_circles, labels_sc)
ari_km = adjusted_rand_score(y_circles, labels_km)
print(f"Spectral Clustering — ARI : {ari_sc:.4f}")
print(f"K-Means — ARI : {ari_km:.4f}")

Données en forme de demi-lunes (moons)

# --- Données en demi-lunes ---
X_moons, y_moons = make_moons(
    n_samples=500, noise=0.08, random_state=42
)

sc_moons = SpectralClustering(
    n_clusters=2,
    affinity='rbf',
    gamma=15,
    random_state=42
)
labels_sc_moons = sc_moons.fit_predict(X_moons)

km_moons = KMeans(n_clusters=2, random_state=42)
labels_km_moons = km_moons.fit_predict(X_moons)

ari_sc_m = adjusted_rand_score(y_moons, labels_sc_moons)
ari_km_m = adjusted_rand_score(y_moons, labels_km_moons)
print(f"Spectral Clustering (moons) — ARI : {ari_sc_m:.4f}")
print(f"K-Means (moons) — ARI : {ari_km_m:.4f}")

Sur les données en demi-lunes, le Spectral Clustering atteint typiquement un ARI proche de 0,95 tandis que le K-Means plafonne autour de 0,45, confirmant son avantage décisif sur les structures non convexes.

Visualisation comparée

# Visualisation
fig, axes = plt.subplots(1, 3, figsize=(15, 4))

axes[0].scatter(X_circles[:, 0], X_circles[:, 1],
                c=y_circles, cmap='viridis', s=15)
axes[0].set_title('Véritables labels')
axes[0].set_axis_off()

axes[1].scatter(X_circles[:, 0], X_circles[:, 1],
                c=labels_sc, cmap='viridis', s=15)
axes[1].set_title(f'Spectral Clustering (ARI={ari_sc:.2f})')
axes[1].set_axis_off()

axes[2].scatter(X_circles[:, 0], X_circles[:, 1],
                c=labels_km, cmap='viridis', s=15)
axes[2].set_title(f'K-Means (ARI={ari_km:.2f})')
axes[2].set_axis_off()

plt.tight_layout()
plt.savefig('spectral_clustering_circles.png', dpi=150)
plt.show()

Impact de γ (gamma)

Le paramètre γ contrôle la granularité de la matrice de similarité :

gammas = [0.1, 1, 5, 10, 50, 200]
fig, axes = plt.subplots(2, 3, figsize=(15, 8))
axes = axes.flatten()

for idx, gamma in enumerate(gammas):
    sc_test = SpectralClustering(
        n_clusters=2, affinity='rbf', gamma=gamma, random_state=42
    )
    labels = sc_test.fit_predict(X_circles)
    ari = adjusted_rand_score(y_circles, labels)

    axes[idx].scatter(X_circles[:, 0], X_circles[:, 1],
                      c=labels, cmap='viridis', s=15)
    axes[idx].set_title(f'gamma={gamma} — ARI={ari:.2f}')
    axes[idx].set_axis_off()

plt.tight_layout()
plt.savefig('spectral_gamma_sensitivity.png', dpi=150)
plt.show()

γ trop faible : la matrice de similarité devient presque uniforme, tous les points semblent connectés → le clustering perd en précision.

γ trop élevé : la matrice devient trop locale, chaque point n’est connecté qu’à ses voisins immédiats → fragmentation excessive et instabilité.

γ optimal : il crée une transition nette entre les points du même cluster (forte similarité) et les points de clusters différents (faible similarité).

Impact de n_clusters

# Recherche du nombre optimal de clusters via le coefficient de silhouette
from sklearn.metrics import silhouette_score

scores = []
cluster_range = range(2, 8)

for k in cluster_range:
    sc_test = SpectralClustering(
        n_clusters=k, affinity='rbf', gamma=10, random_state=42
    )
    labels = sc_test.fit_predict(X_circles)
    score = silhouette_score(X_circles, labels)
    scores.append(score)
    print(f"k={k} — Silhouette : {score:.4f}")

plt.plot(cluster_range, scores, marker='o')
plt.xlabel('Nombre de clusters (k)')
plt.ylabel('Score de silhouette')
plt.title('Évolution du score de silhouette en fonction de k')
plt.grid(True)
plt.savefig('spectral_n_clusters.png', dpi=150)
plt.show()

Hyperparamètres du Spectral Clustering

n_clusters

Le nombre de clusters à identifier. C’est l’hyperparamètre le plus critique, commun à toutes les méthodes de partitionnement. Comme pour le K-Means, il doit être spécifié a priori et peut être estimé via des méthodes telles que le coude (elbow), le score de silhouette, ou la gap statistic.

affinity

La fonction de similarité utilisée pour construire la matrice de similarité. Les options principales dans scikit-learn sont :

• ‘rbf’ (défaut) : noyau gaussien exp(-γ‖xᵢ – xⱼ‖²). Le plus polyvalent et recommandé dans la plupart des cas.
• ‘nearest_neighbors’ : utilise le graphe des k-plus proches voisins. Utile pour les données de haute dimension.
• ‘precomputed’ : la matrice de similarité est fournie directement par l’utilisateur.
• ‘poly’ : noyau polynomial (degree × xᵢᵀxⱼ + coef0)^(degree).
• ‘sigmoid’ : noyau sigmoïde tanh(γ × xᵢᵀxⱼ + coef0).

gamma

Le coefficient du noyau RBF, poly et sigmoid. Pour le noyau RBF, gamma = 1/(2σ²). Les valeurs usuelles se situent entre 0,1 et 100, selon l’échelle des données. Un bon point de départ est gamma = 1/n_features.

n_components

Le nombre de vecteurs propres utilisés pour la projection spectrale. Par défaut, il est égal à n_clusters. Il peut être augmenté pour capturer plus de structure, au prix d’un temps de calcul supplémentaire.

assign_labels

La méthode utilisée pour affecter les labels après la décomposition spectrale :

• ‘kmeans’ (défaut) : applique le K-Means classique sur les vecteurs propres.
• ‘discretize’ : utilise une stratégie de discrétisation (méthode de Jordan & Weiss), souvent plus stable mais parfois moins précise.

degree

Le degré du noyau polynomial. Utilisé uniquement lorsque affinity=’poly’. La valeur par défaut est 3.

coef0

Terme indépendant pour les noyaux poly et sigmoid. La valeur par défaut est 1,0.

n_init

Nombre d’exécutions indépendantes du K-Means interne. La meilleure solution (celle minimisant l’inertie) est conservée. La valeur par défaut est 10. Augmenter cette valeur améliore la stabilité au prix d’un temps de calcul accru.

Avantages et limites

Avantages

1. Clusters non convexes : capacité unique à détecter des structures complexes que le K-Means ne peut pas identifier (cercles, lunes, spirales, structures en ruban).
2. Fondement théorique solide : basé sur la théorie spectrale des graphes avec des garanties mathématiques rigoureuses. Lié au problème de la coupe minimale normalisée (normalized cut).
3. Pas d’hypothèse de forme : ne suppose pas que les clusters sont sphériques, convexes ou de taille égale.
4. Polyvalence des similarités : peut utiliser n’importe quelle mesure de similarité, pas seulement la distance euclidienne. Cela permet de clustériser des données non vectorielles (graphes, séquences, images).
5. Convergence garantie : contrairement au K-Means qui peut converger vers des minima locaux très variables, la décomposition spectrale fournit une solution déterministe (une fois le K-Means final stabilisé).

Limites

1. Complexité computationnelle élevée : la construction de la matrice de similarité est en O(n²) et la décomposition spectrale en O(n³). Sur de grands jeux de données (n > 10 000), le Spectral Clustering devient prohibitif en temps et en mémoire.
2. Sensibilité aux hyperparamètres : le choix de γ est crucial et difficile à automatiser. Un mauvais γ peut conduire à des résultats complètement erronés.
3. Mémoire : la matrice de similarité W stocke n² éléments. Pour n = 50 000, cela représente déjà 10 Go en précision double.
4. Pas de fonction de prédiction : le Spectral Clustering est un algorithme transductif. Il ne peut pas affecter un label à un nouveau point sans recalculer toute la décomposition spectrale.
5. Sensibilité au bruit et aux outliers : les points isolés peuvent perturber significativement la matrice laplacienne et fausser la décomposition spectrale.

4 cas d’usage concrets

1. Segmentation d’images

Le Spectral Clustering est particulièrement efficace pour la segmentation d’images. Chaque pixel est traité comme un point dans un espace de caractéristiques (couleur, position, texture), et la matrice de similarité capture la continuité spatiale et chromatique. L’algorithme de Normalized Cuts (Shi & Malik, 2000), l’ancêtre du Spectral Clustering, a révolutionné le domaine de la vision par ordinateur.

from sklearn.cluster import SpectralClustering
from skimage import data, segmentation

image = data.astronaut()
pixels = image.reshape(-1, image.shape[-1])

sc_img = SpectralClustering(
    n_clusters=8, affinity='rbf', gamma=0.01, random_state=42
)
segments = sc_img.fit_predict(pixels)
segmented = segments.reshape(image.shape[:2])

plt.imshow(segmentation.mark_boundaries(image, segmented))
plt.axis('off')
plt.savefig('image_segmentation.png', dpi=150)
plt.show()

2. Détection de communautés dans les réseaux sociaux

Dans un réseau social représenté comme un graphe (nœuds = utilisateurs, arêtes = interactions), le Spectral Clustering identifie naturellement des communautés d’utilisateurs fortement interconnectés entre eux mais faiblement connectés au reste du réseau. La matrice de similarité est ici directement la matrice d’adjacence du graphe.

Cette application est massivement utilisée pour la détection de groupes d’intérêt, l’analyse de propagation d’information, et la modération de communautés en ligne.

3. Analyse de documents et regroupement thématique

Pour regrouper des documents par similarité sémantique, on peut utiliser le Spectral Clustering sur une matrice de similarité cosinus calculée entre les embeddings TF-IDF ou les représentations issues de modèles de langage. Contrairement au K-Means qui suppose des clusters sphériques dans l’espace vectoriel, le Spectral Clustering capture les nuances de similarité thématique, même lorsque les thèmes se chevauchent partiellement.

4. Bioinformatique et clustering de séquences génétiques

En bioinformatique, le Spectral Clustering est utilisé pour regrouper des séquences d’ADN ou des profils d’expression génique. La matrice de similarité peut être construite à partir de distances spécifiques aux séquences biologiques (distance de Hamming, score d’alignement BLAST). La capacité à détecter des clusters de forme arbitraire est cruciale lorsque les groupes biologiques ne suivent pas une distribution gaussienne.

Conclusion

Le Spectral Clustering est l’une des méthodes de clustering les plus élégantes du machine learning. En combinant la théorie des graphes, l’algèbre linéaire et l’optimisation, il offre une alternative puissante aux méthodes classiques là où celles-ci échouent. Son point fort — la capacité à identifier des clusters non convexes — est aussi sa faiblesse computationnelle, ce qui en fait un outil à réserver aux jeux de données de taille modérée.

Pour le praticien, la leçon principale est simple : utilisez le Spectral Clustering lorsque vous soupçonnez que vos clusters ont des formes complexes, et assurez-vous de maîtriser le réglage du paramètre γ. Pour les très grands jeux de données, considérez des approximations comme le Nyström Spectral Clustering ou le Spectral Clustering par échantillonnage pour réduire la complexité.

Voir aussi

• Comment utiliser les exceptions en Python ?
• Maîtrisez le Mahjong avec Python : Guide Complet pour Développeurs et Enthousiastes