Skip to content
Retour aux résultats

Partitionnement spectral (Spectral Clustering)

Introduite par
Ng, A. Y.; Jordan, M. I.; Weiss, Y.
Année
2002
Type
Graph-based clustering (spectral method)

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Le partitionnement spectral est un algorithme d'apprentissage non supervisé basé sur les graphes, formalisé par Ng, Jordan et Weiss en 2002, qui projette les points de données dans un espace propre de faible dimension dérivé du laplacien du graphe de similarité avant d'appliquer k-moyennes.

Ce plongement spectral permet de retrouver des groupes de forme arbitraire — anneaux, croissants, spirales entrelacées — que les méthodes fondées sur la distance euclidienne échouent systématiquement à séparer.

L’intuition derrière la méthode

Le k-moyennes standard partitionne l'espace par distance en ligne droite, il ne peut donc trouver que des amas convexes, à peu près sphériques. Le partitionnement spectral contourne cela en considérant d'abord les données comme un réseau : chaque point est un nœud, et les arêtes entre les nœuds portent un poids qui reflète la similarité entre les deux points. Les groupes correspondent à des régions du réseau qui sont densément connectées en interne mais faiblement connectées au reste. La matrice laplacienne du graphe encode cette structure de connectivité, et ses plus petits vecteurs propres agissent comme un système de coordonnées lisse qui étire les données de sorte que des groupes bien séparés se retrouvent éloignés même lorsqu'ils étaient emmêlés dans l'espace d'origine. Une simple étape de k-moyennes dans ce nouveau système de coordonnées les sépare alors proprement.

Histoire

Les fondements théoriques du partitionnement spectral remontent aux travaux de Fiedler en 1973 sur la connectivité des graphes et la valeur propre de connectivité algébrique. Shi et Malik (2000) ont introduit l'approche en vision par ordinateur à travers leur critère normalized-cuts pour la segmentation d'images. Ng, Jordan et Weiss (2002) ont présenté un algorithme propre et généraliste à la conférence NIPS — celui le plus couramment cité aujourd'hui — ainsi qu'une analyse par théorie des perturbations expliquant quand et pourquoi la méthode fonctionne. Le tutoriel de Von Luxburg en 2007 dans Statistics and Computing a unifié les formulations concurrentes, clarifié le rôle de la normalisation laplacienne, et est devenu la référence standard pour les praticiens. Le partitionnement spectral occupe désormais une place centrale dans le cursus de l'apprentissage automatique et reste un sujet de recherche actif, avec des travaux en cours sur les approximations passant à l'échelle, les noyaux robustes et les extensions aux graphes et aux variétés.

Quand l’utiliser

Le partitionnement spectral est bien adapté lorsque les groupes dans les données sont non convexes, non linéairement séparables, ou connectés par des ponts minces que les méthodes de partitionnement euclidien ne peuvent pas détecter — des exemples courants incluent les groupes en forme d'anneau, les spirales entrelacées et les segments d'image. Il est approprié lorsque la similarité par paires entre les points peut être calculée de manière significative (soit à partir d'un noyau sur les caractéristiques brutes, soit à partir d'une matrice d'affinité pré-fournie), et lorsque le nombre de groupes k est connu ou peut être estimé à partir de l'heuristique de l'écart spectral (eigengap). La méthode ne fait aucune hypothèse distributionnelle sur les formes des groupes. Les limitations pratiques incluent une mémoire quadratique par rapport au nombre de points (pour la matrice d'affinité complète) et un temps cubique pour la décomposition en valeurs propres, rendant la formulation standard coûteuse au-delà d'environ 10 000 points. Des méthodes approximatives (Nystrom, graphes creux, SVD randomisée) étendent sa portée à des jeux de données plus grands.

Limites et points d’attention

  • La construction de la matrice d'affinité complète n x n nécessite une mémoire O(n^2) et un temps O(n^3) pour la décomposition en valeurs propres, rendant l'algorithme naïf irréalisable pour les grands jeux de données.
  • Les résultats sont sensibles au choix de la largeur de bande du noyau sigma et à la stratégie de construction du graphe ; de mauvais choix peuvent fusionner ou fragmenter des groupes.
  • L'initialisation k-moyennes dans le plongement spectral introduit du hasard ; différentes exécutions peuvent produire des partitions différentes.
  • Passe mal à l'échelle dans les espaces de caractéristiques de très haute dimension sans une sélection soignée du noyau.
  • Fournit uniquement des étiquettes de groupe ; il n'offre pas de modèle génératif ni d'extension naturelle hors échantillon pour de nouveaux points.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Détecte des groupes de forme arbitraire, y compris des configurations non convexes et non linéairement séparables qui déjouent k-moyennes et les modèles de mélange gaussien.
  • Peut opérer sur toute matrice de similarité par paires, pas seulement les distances euclidiennes, ce qui le rend applicable aux graphes, chaînes de caractères et autres données structurées.
  • L'heuristique de l'eigengap fournit un guide rigoureux, fondé sur les données, pour choisir le nombre de groupes k.
  • Fondé sur une riche théorie spectrale des graphes, permettant une analyse formelle de la convergence et de la qualité des groupes.
  • Conceptuellement simple et facilement implémentable à l'aide de bibliothèques d'algèbre linéaire standard.

Applications

  • Segmentation d'images : partitionnement de pixels ou de superpixels en régions perceptuellement cohérentes en utilisant la similarité des caractéristiques au niveau des pixels.
  • Détection de communautés dans les réseaux sociaux et biologiques où la connectivité par paires plutôt que les vecteurs de caractéristiques définit la structure.
  • Bioinformatique : regroupement de gènes ou de protéines par similarité de profils d'expression, où les groupes d'expression sont rarement convexes dans l'espace des gènes.
  • Traitement du langage naturel : partitionnement de documents ou de phrases à l'aide de noyaux de similarité sémantique.
  • Vision par ordinateur : segmentation de mouvement et partitionnement de nuages de points où les frontières des groupes sont irrégulières.
  • Analyse exploratoire de données : révéler une structure de groupes non évidente avant d'appliquer des méthodes de confirmation.

Comment ça marche

Comment ça marche

1

Une matrice de similarité (affinité) par paires W est construite à partir des données. Le choix le plus courant est le noyau gaussien (RBF), qui attribue un poids élevé aux paires proches et un poids proche de zéro aux paires distantes. Le paramètre de largeur de bande sigma contrôle la rapidité avec laquelle la similarité décroît avec la distance ; bien le choisir est essentiel. Alternativement, un graphe des k plus proches voisins peut être utilisé pour des représentations plus creuses sur de grands jeux de données.

Formule
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)
2

La matrice de degrés D est la matrice diagonale dont la i-ème entrée est la somme de la i-ème ligne de W. À partir de W et D, le laplacien du graphe normalisé (symétrique) L_sym est formé. Cette matrice capture la structure complète de connectivité du graphe de similarité ; son spectre de valeurs propres révèle combien de groupes naturels les données contiennent et à quel point ils sont clairement séparés.

Formule
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}
3

Les k vecteurs propres correspondant aux k plus petites valeurs propres de L_sym sont calculés. Ces vecteurs propres forment les colonnes de la matrice de plongement U, qui a une ligne par point de données. Dans cet espace spectral k-dimensionnel, les points appartenant au même groupe sont rapprochés même s'ils étaient entrelacés dans l'espace de caractéristiques d'origine.

Formule
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]
4

Chaque ligne de U est divisée par sa norme euclidienne pour projeter les points plongés sur l'hypersphère unité. Cette normalisation, introduite par Ng, Jordan et Weiss, supprime les différences d'échelle parasites entre les vecteurs propres et garantit que l'étape de k-moyennes subséquente se concentre sur la structure angulaire du plongement plutôt que sur l'amplitude.

Formule
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}
5

Le partitionnement par k-moyennes standard est appliqué aux lignes de la matrice de plongement normalisée T. Parce que le plongement spectral a déjà démêlé la géométrie des groupes, k-moyennes trouve des partitions significatives même pour des formes de groupes non convexes. Les étiquettes de groupe sont ensuite réaffectées sur les points de données d'origine.

Pièges courants

  • Choix de sigma sans validation croisée rigoureuse ou auto-réglage ; une largeur de bande trop petite crée un graphe déconnecté, tandis qu'une largeur de bande trop grande fusionne des groupes distincts.
  • Négliger de normaliser les lignes de la matrice d'affinité avant k-moyennes (l'étape de normalisation des lignes de Ng et al. est essentielle pour la stabilité).
  • Ignorer l'eigengap : utiliser un k fixe sans inspecter le spectre des valeurs propres conduit souvent à une sous- ou sur-segmentation.
  • Appliquer l'algorithme complet à des jeux de données de dizaines de milliers de points sans passer à une variante approximative ou creuse.
  • Confondre les laplaciens non normalisés (L = D - W) et normalisés (L_sym, L_rw), ce qui peut modifier substantiellement les affectations de groupes.

Questions fréquentes

Comment choisir le nombre de groupes k ?

L'heuristique de l'eigengap est le guide standard : calculer les valeurs propres du laplacien normalisé par ordre croissant et rechercher le plus grand écart entre les valeurs propres consécutives. L'indice auquel cet écart se produit suggère le nombre naturel de groupes. Lorsque l'eigengap est ambigu, les approches basées sur la stabilité — exécuter l'algorithme pour plusieurs valeurs de k et comparer les affectations de groupes à travers les perturbations — peuvent aider.

Comment régler la largeur de bande du noyau gaussien sigma ?

Une heuristique courante est la médiane des distances par paires dans l'jeu de données, ou un schéma d'auto-réglage des voisins les plus proches (Zelnik-Manor & Perona, 2004) qui attribue une largeur de bande locale à chaque point. En pratique, sigma doit être validé en inspectant la connectivité du graphe d'affinité résultant : chaque point doit avoir au moins quelques voisins à poids élevé, et le graphe ne doit pas se fragmenter en composantes isolées.

Pourquoi l'étape de normalisation des lignes est-elle nécessaire ?

Les vecteurs propres du laplacien peuvent différer considérablement en échelle. Sans normaliser chaque ligne de la matrice de plongement à une longueur unitaire, l'étape k-moyennes peut être dominée par les vecteurs propres de grande amplitude et ignorer les composantes informatives mais de plus petite amplitude. La normalisation des lignes introduite par Ng, Jordan et Weiss projette tous les points sur la sphère unité de sorte que k-moyennes réponde à la géométrie angulaire du plongement.

Le partitionnement spectral peut-il gérer de très grands jeux de données ?

Pas sous sa forme naïve, qui nécessite une mémoire O(n^2) et un temps de décomposition en valeurs propres O(n^3). Pour un grand n, les remèdes standards incluent : la construction d'un graphe creux des k plus proches voisins au lieu d'une matrice d'affinité complète ; l'utilisation de l'approximation de Nystrom pour estimer les vecteurs propres à partir d'un sous-échantillon ; ou l'application de SVD randomisée. Ces méthodes approximatives récupèrent la plupart de la précision pour une fraction du coût.

Méthodes associées

Sources

  1. Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On Spectral Clustering: Analysis and an Algorithm. Advances in Neural Information Processing Systems, 14, 849–856.

    Ouvrir la référence de la publication
    Copié.
  2. von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.

    Ouvrir la référence DOI
    Copié.
  3. Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.

    Ouvrir la référence DOI
    Copié.