Une méthode qui transforme les données en graphe : chaque point est relié à ceux qui lui ressemblent. Elle cherche ensuite comment couper ce graphe en groupes reliés entre eux, mais peu reliés au reste. Elle retrouve des groupes de formes allongées ou enroulées que K-means, qui raisonne en distance au centre, découpe mal.
Un réseau social : on ne regarde pas où habitent les gens, mais qui est ami avec qui. Les communautés sont des cercles très connectés entre eux, peu connectés au reste.
Chaque point est relié à ses plus proches voisins, ou à tous avec un poids qui décroît avec la distance. Deux points proches dans une même chaîne restent connectés, même si la chaîne est enroulée.
À partir du graphe, on calcule les vecteurs propres d'une matrice appelée laplacien. Dans ce nouvel espace, les points bien connectés entre eux se retrouvent regroupés.
Un K-means, ou une autre méthode simple, découpe les points dans cette représentation. Les groupes obtenus sont renvoyés aux données d'origine.
Chaque image est décrite par ses 64 pixels (8 × 8). On veut regrouper les images semblables avant tout étiquetage, pour trier des documents numérisés ou préparer une vérification humaine.
Relié par un graphe des 10 plus proches voisins, le clustering spectral retrouve mieux les chiffres que K-means sur les mêmes pixels. Certains groupes sont presque purs (0, 4, 6) ; d'autres mélangent des chiffres proches, comme le 3 et le 9.
Les vraies étiquettes servent seulement au contrôle. L'indice de Rand ajusté vaut 0,753 pour le spectral et 0,667 pour K-means (1 = accord parfait, 0 = hasard). En production, sans étiquettes, on contrôle la pureté sur un petit échantillon vérifié à la main.
Noms donnés pour R (kernlab::specc) et Python (scikit-learn).
Le nombre de groupes, à fournir. L'écart entre valeurs propres successives (eigengap) donne une indication, à confirmer par le sens métier.
La construction du graphe, réglage décisif. En Python, affinity="nearest_neighbors" relie chaque point à ses n_neighbors voisins ; le noyau gaussien (défaut) dépend de gamma. En R, kpar="local" adapte la largeur du noyau à chaque point.
La méthode de découpage dans le nouvel espace : "kmeans" (défaut), "discretize" ou "cluster_qr", plus déterministe et sans départ aléatoire.
# Regrouper des chiffres manuscrits sans étiquette : clustering spectral en R
library(kernlab)
chiffres <- read.csv("chiffres_manuscrits.csv")
X <- as.matrix(chiffres[, 1:64]) # la vraie étiquette ne sert qu'au contrôle final
# Noyau gaussien à échelle locale : chaque image adapte la largeur à son voisinage
set.seed(42)
modele <- specc(X, centers = 10, kpar = "local")
groupes <- modele@.Data
# Comparaison avec K-means sur les mêmes pixels
km <- kmeans(X, centers = 10, nstart = 10)
purete <- function(g) sum(apply(table(g, chiffres$chiffre), 1, max)) / nrow(X)
cat("Pureté spectral :", round(purete(groupes), 3), "\n")
cat("Pureté K-means :", round(purete(km$cluster), 3), "\n")
# Chiffres présents dans chaque groupe
print(table(groupe = groupes, chiffre = chiffres$chiffre))# Regrouper des chiffres manuscrits sans étiquette : clustering spectral en Python
import pandas as pd
from sklearn.cluster import SpectralClustering, KMeans
from sklearn.metrics import adjusted_rand_score
chiffres = pd.read_csv("chiffres_manuscrits.csv")
X = chiffres.drop(columns="chiffre") # la vraie étiquette ne sert qu'au contrôle final
# Graphe des 10 plus proches voisins, puis découpage en 10 groupes
modele = SpectralClustering(n_clusters=10, affinity="nearest_neighbors", n_neighbors=10,
assign_labels="cluster_qr", random_state=42)
groupes = modele.fit_predict(X)
# Comparaison avec K-means sur les mêmes pixels
groupes_km = KMeans(n_clusters=10, n_init=10, random_state=42).fit_predict(X)
print("Accord avec les vrais chiffres (ARI) spectral :", round(adjusted_rand_score(chiffres["chiffre"], groupes), 3))
print("Accord avec les vrais chiffres (ARI) K-means :", round(adjusted_rand_score(chiffres["chiffre"], groupes_km), 3))
# Chiffre majoritaire et pureté de chaque groupe
tableau = pd.crosstab(pd.Series(groupes, name="groupe"), chiffres["chiffre"])
print(pd.DataFrame({"chiffre": tableau.idxmax(axis=1), "taille": tableau.sum(axis=1),
"purete": (tableau.max(axis=1) / tableau.sum(axis=1)).round(2)}).to_string())Quand les groupes ne sont pas des boules : chaînes, anneaux, formes imbriquées, ou données où seule la proximité locale a un sens. K-means découpe l'espace en zones autour de centres et coupe ces formes en morceaux. Le spectral suit les connexions de proche en proche.
Il calcule une matrice de similarité entre tous les points, puis des vecteurs propres de cette matrice. Le coût grimpe vite avec le nombre de points. Un graphe des plus proches voisins, creux, aide beaucoup ; au-delà de quelques dizaines de milliers de points, d'autres méthodes sont préférables.
Le spectre d'une matrice est l'ensemble de ses valeurs propres. La méthode utilise les vecteurs propres du laplacien du graphe de similarité pour représenter les points, d'où son nom.
Utilisé dans le nouvel espace du spectral. Seul, sur les données brutes, il suppose des groupes ronds.
Voir la fiche → formes libres, avec bruitTrouve aussi des groupes de formes libres, sans fixer leur nombre, et isole les points isolés.
Voir la fiche → même idée de grapheConstruit aussi un graphe de voisins, pour projeter les données en 2D. Souvent combiné à un clustering par densité.
Voir la fiche →Dataistudio forme les équipes au machine learning et à l'IA, sur des cas concrets.
Nous utilisons des cookies de mesure d'audience et de suivi publicitaire pour comprendre la fréquentation du site et l'efficacité de nos annonces. Rien n'est déposé sans votre accord. En savoir plus