Agrégation spectrale - Spectral clustering

Dans les statistiques multivariées , les techniques de regroupement spectral utilisent le spectre ( valeurs propres ) de la matrice de similarité des données pour effectuer une réduction de la dimensionnalité avant le regroupement en moins de dimensions. La matrice de similarité est fournie en entrée et consiste en une évaluation quantitative de la similarité relative de chaque paire de points dans l'ensemble de données.

En application à la segmentation d'images, le regroupement spectral est connu sous le nom de catégorisation d'objets basée sur la segmentation .

Définitions

Étant donné un ensemble énuméré de points de données, la matrice de similarité peut être définie comme une matrice symétrique , où représente une mesure de la similarité entre les points de données avec les indices et . L'approche générale de la classification spectrale consiste à utiliser une méthode de classification standard (il existe de nombreuses méthodes de ce type, k -means est discuté ci - dessous ) sur les vecteurs propres pertinents d'une matrice laplacienne de . Il existe de nombreuses façons différentes de définir un Laplacien qui ont des interprétations mathématiques différentes, et donc le regroupement aura également des interprétations différentes. Les vecteurs propres qui sont pertinents sont ceux qui correspondent aux plus petites valeurs propres du Laplacien, à l'exception de la plus petite valeur propre qui aura une valeur de 0. Pour l'efficacité du calcul, ces vecteurs propres sont souvent calculés comme les vecteurs propres correspondant aux plus grandes valeurs propres d'un fonction du Laplacien. ${\style d'affichage A}$${\displaystyle A_{ij}\geq 0}$${\style d'affichage i}$${\style d'affichage j}$${\style d'affichage A}$

Le regroupement spectral est bien connu pour se rapporter à la partition d'un système masse-ressort, où chaque masse est associée à un point de données et chaque raideur de ressort correspond à un poids d'un bord décrivant une similitude des deux points de données liés. Plus précisément, la référence classique explique que le problème aux valeurs propres décrivant les modes de vibration transversaux d'un système masse-ressort est exactement le même que le problème aux valeurs propres pour la matrice laplacienne du graphe définie comme

${\style d'affichage L:=DA}$,

où est la matrice diagonale ${\style d'affichage D}$

${\displaystyle D_{ii}=\sum _{j}A_{ij}.}$

Les masses qui sont étroitement reliées par les ressorts dans le système masse-ressort se déplacent évidemment ensemble à partir de la position d'équilibre dans les modes de vibration à basse fréquence, de sorte que les composantes des vecteurs propres correspondant aux plus petites valeurs propres du graphique Laplacien peuvent être utilisées pour regroupement des masses.

Une technique de regroupement spectrale connexe populaire est l' algorithme de coupe normalisée ou l' algorithme Shi-Malik introduit par Jianbo Shi et Jitendra Malik, couramment utilisé pour la segmentation d'images . Il divise les points en deux ensembles en fonction du vecteur propre correspondant à la deuxième plus petite valeur propre du Laplacien normalisé symétrique défini comme ${\style d'affichage (B_{1},B_{2})}$ ${\style d'affichage v}$

${\displaystyle L^{\text{norm}} :=ID^{-1/2}AD^{-1/2}.}$

Un algorithme mathématiquement équivalent prend le vecteur propre correspondant à la plus grande valeur propre de la matrice d' adjacence normalisée de la marche aléatoire . ${\style d'affichage P=D^{-1}A}$

Connaissant les vecteurs propres, le partitionnement peut être effectué de différentes manières, par exemple en calculant la médiane des composantes du deuxième plus petit vecteur propre , et en plaçant tous les points dont la composante dans est plus grande que dans , et le reste dans . L'algorithme peut être utilisé pour le regroupement hiérarchique en partitionnant à plusieurs reprises les sous-ensembles de cette manière. ${\style d'affichage m}$${\style d'affichage v}$${\style d'affichage v}$${\style d'affichage m}$${\style d'affichage B_{1}}$${\style d'affichage B_{2}}$

Algorithmes

Algorithme de base

1. Calculer le Laplacien (ou le Laplacien normalisé)${\style d'affichage L}$
2. Calculer les premiers vecteurs propres (les vecteurs propres correspondant aux plus petites valeurs propres de )${\style d'affichage k}$${\style d'affichage k}$${\style d'affichage L}$
3. Considérons la matrice formée par les premiers vecteurs propres ; la -ième ligne définit les caractéristiques du nœud du graphe${\style d'affichage k}$${\style d'affichage l}$${\style d'affichage l}$
4. Regroupez les nœuds du graphique en fonction de ces caractéristiques (par exemple, en utilisant le clustering k-means )

Si la matrice de similarité n'a pas déjà été explicitement construite, l'efficacité du clustering spectral peut être améliorée si la solution du problème de valeurs propres correspondant est effectuée sans matrice (sans manipuler explicitement ni même calculer la matrice de similarité), comme dans le Algorithme de Lanczos . ${\style d'affichage A}$

Pour les graphes de grande taille, la deuxième valeur propre de la matrice laplacienne du graphe (normalisé) est souvent mal conditionnée , ce qui conduit à une convergence lente des solveurs itératifs de valeurs propres. Le préconditionnement est une technologie clé qui accélère la convergence, par exemple dans la méthode LOBPCG sans matrice . Le clustering spectral a été appliqué avec succès sur de grands graphes en identifiant d'abord leur structure de communauté , puis en regroupant les communautés.

Le regroupement spectral est étroitement lié à la réduction de dimensionnalité non linéaire , et des techniques de réduction de dimension telles que l'intégration localement linéaire peuvent être utilisées pour réduire les erreurs dues au bruit ou aux valeurs aberrantes.

Logiciel

Le logiciel libre mise en œuvre de la classification spectrale est disponible dans les grands projets open source comme scikit-learn en utilisant LOBPCG avec multigrille préconditionnement ou ARPACK , MLlib pour pseudo-regroupement en utilisant l'vecteur propre itération de puissance méthode et R .

Relation avec d'autres méthodes de clustering

Les idées derrière le regroupement spectral peuvent ne pas être immédiatement évidentes. Il peut être utile de mettre en évidence les relations avec d'autres méthodes. En particulier, il peut être décrit dans le contexte des méthodes de clustering du noyau, ce qui révèle plusieurs similitudes avec d'autres approches.

Relation avec k- moyennes

Le problème k -means du noyau est une extension du problème k -means où les points de données d'entrée sont mappés de manière non linéaire dans un espace de caractéristiques de dimension supérieure via une fonction noyau . Le problème k- means du noyau pondéré étend encore ce problème en définissant un poids pour chaque cluster comme l'inverse du nombre d'éléments dans le cluster, ${\displaystyle k(x_{i},x_{j})=\varphi ^{T}(x_{i})\varphi (x_{j})}$${\style d'affichage w_{r}}$

${\displaystyle \max _{\{C_{s}\}}\sum _{r=1}^{k}w_{r}\sum _{x_{i},x_{j}\in C_{r }}k(x_{i},x_{j}).}$

Supposons une matrice des coefficients de normalisation pour chaque point pour chaque cluster si et zéro sinon. Supposons que est la matrice du noyau pour tous les points. Le noyau pondéré k -means problème avec n points et k clusters est donné comme, ${\style d'affichage F}$${\displaystyle F_{ij}=w_{r}}$${\displaystyle i,j\in C_{r}}$${\style d'affichage K}$

${\displaystyle \max _{F}\operatorname {trace} (KF)}$

tel que

${\displaystyle F=G_{n\fois k}G_{k\fois n}^{T}}$

${\displaystyle G^{T}G=I}$

tel que . De plus, il y a des contraintes d'identité sur donné par, ${\displaystyle \operatorname {rang} (G)=k}$${\style d'affichage F}$

${\displaystyle F\cdot \mathbb {I} =\mathbb {I} }$

${\displaystyle F^{T}\mathbb {I} =\mathbb {I} }$

où représente un vecteur de uns. Ce problème peut être reformulé comme ${\displaystyle \mathbb {I} }$

${\displaystyle \max _{G}\operatorname {trace} (G^{T}G).}$

Ce problème est équivalent au problème de clustering spectral lorsque les contraintes d'identité sur sont relâchées. En particulier, le problème des k- moyennes pondérées du noyau peut être reformulé comme un problème de clustering spectral (partitionnement de graphe) et vice versa. Les sorties des algorithmes sont des vecteurs propres qui ne satisfont pas aux exigences d'identité pour les variables indicatrices définies par . Par conséquent, le post-traitement des vecteurs propres est nécessaire pour l'équivalence entre les problèmes. Transformer le problème de clustering spectral en un problème de k- means à noyau pondéré réduit considérablement la charge de calcul. ${\style d'affichage F}$${\style d'affichage F}$

Relation avec DBSCAN

Le clustering spectral est également lié au clustering DBSCAN , qui trouve les composants connectés à la densité. Les composants connectés correspondent à des clusters spectraux optimaux (pas de bords coupés) ; et DBSCAN utilise un graphe voisin asymétrique avec des bords supprimés lorsque les points source ne sont pas denses. Ainsi, DBSCAN est un cas particulier de clustering spectral, mais qui permet des algorithmes plus efficaces (pire des cas , dans de nombreux cas pratiques beaucoup plus rapides avec des indices). ${\style d'affichage O(n^{2})}$

Mesures pour comparer les clusters

Ravi Kannan, Santosh Vempala et Adrian Vetta ont proposé une mesure bicritère pour définir la qualité d'un clustering donné. Ils ont dit qu'un clustering était un (α, ε)-clustering si la conductance de chaque cluster (dans le clustering) était d'au moins α et le poids des bords inter-clusters était d'au plus ε fraction du poids total de tous les arêtes dans le graphique. Ils examinent également deux algorithmes d'approximation dans le même article.

Solutions approximatives

Le clustering spectral est coûteux en calcul à moins que le graphique ne soit clairsemé et que la matrice de similarité puisse être construite efficacement. Si la matrice de similarité est une matrice de noyau RBF, le clustering spectral est coûteux. Il existe des algorithmes approximatifs pour rendre le clustering spectral plus efficace : méthode de puissance, méthode de Nystrom, etc. Cependant, des recherches récentes ont mis en évidence les problèmes du clustering spectral avec la méthode de Nystrom ; en particulier, la matrice de similarité avec l'approximation de Nystrom n'est pas positivement élémentaire, ce qui peut être problématique.

Histoire et littératures connexes

Le clustering spectral a une longue histoire. Le clustering spectral en tant que méthode d' apprentissage automatique a été popularisé par Shi & Malik et Ng, Jordan et Weiss.

Les idées et les mesures de réseau liées au clustering spectral jouent également un rôle important dans un certain nombre d'applications apparemment différentes des problèmes de clustering. Par exemple, les réseaux avec des partitions spectrales plus fortes mettent plus de temps à converger dans les modèles de mise à jour d'opinion utilisés en sociologie et en économie.

Voir également

• Propagation d'affinité
• Analyse en composantes principales du noyau
• L'analyse par grappes
• Théorie des graphes spectrales

Les références