Spectral Clustering via Graph Laplacian Eigenvectors (Ng–Jordan–Weiss Algorithm)

Le k-moyennes standard partitionne l'espace par distance en ligne droite, il ne peut donc trouver que des blobs 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 clusters 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 clusters 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.