Spektrale Clusteranalyse
- Eingeführt von
- Ng, A. Y.; Jordan, M. I.; Weiss, Y.
- Jahr
- 2002
- Typ
- Graph-based clustering (spectral method)
Dieser Text ist eine maschinelle Übersetzung und wurde noch nicht geprüft. Original auf Englisch lesen
Was leistet sie?
Die Spektrale Clusteranalyse ist ein graphenbasierter unüberwachter Lernalgorithmus, der 2002 von Ng, Jordan und Weiss formalisiert wurde.
Er bildet Datenpunkte in einen niedrigdimensionalen Eigenraum ab, der aus dem Laplace-Operator des Ähnlichkeitsgraphen abgeleitet wird, bevor k-means angewendet wird. Diese spektrale Einbettung ermöglicht es, Cluster beliebiger Form – Ringe, Halbmonde, verschachtelte Spiralen – zu erkennen, die euklidische distanzbasierte Methoden konsequent nicht trennen können.
Die Intuition hinter der Methode
Standard-k-means partitioniert den Raum nach geradliniger Distanz und kann daher nur konvexe, annähernd kugelförmige "Blobs" finden. Die Spektrale Clusteranalyse umgeht dies, indem sie die Daten zunächst als Netzwerk betrachtet: Jeder Punkt ist ein Knoten, und Kanten zwischen Knoten tragen ein Gewicht, das die Ähnlichkeit der beiden Punkte widerspiegelt. Cluster entsprechen Regionen des Netzwerks, die intern dicht verbunden, aber mit dem Rest lose verbunden sind. Die Graph-Laplace-Matrix kodiert diese Konnektivitätsstruktur, und ihre kleinsten Eigenvektoren wirken wie ein glattes Koordinatensystem, das die Daten so streckt, dass gut getrennte Cluster weit auseinander liegen, selbst wenn sie im ursprünglichen Raum miteinander verwickelt waren. Ein einfacher k-means-Schritt in diesem neuen Koordinatensystem trennt sie dann sauber.
Geschichte
Die theoretischen Grundlagen der Spektralen Clusteranalyse gehen auf Fiedlers Arbeit von 1973 über Graphenkonnektivität und den algebraischen Konnektivitäts-Eigenwert zurück. Shi und Malik (2000) brachten den Ansatz durch ihr Normalized-Cuts-Kriterium für die Bildsegmentierung in die Computer Vision ein. Ng, Jordan und Weiss (2002) präsentierten auf der NIPS einen sauberen, allgemeingültigen Algorithmus – den heute am häufigsten zitierten – zusammen mit einer störungstheoretischen Analyse, die erklärt, wann und warum die Methode funktioniert. Von Luxburgs Tutorial von 2007 in Statistics and Computing vereinte die konkurrierenden Formulierungen, klärte die Rolle der Laplace-Normalisierung und wurde zur Standardreferenz für Praktiker. Die Spektrale Clusteranalyse nimmt heute einen zentralen Platz im Machine-Learning-Lehrplan ein und bleibt ein aktives Forschungsgebiet, mit laufenden Arbeiten zu skalierbaren Approximationen, robusten Kernels und Erweiterungen auf Graphen und Mannigfaltigkeiten.
Wann wird sie eingesetzt?
Die Spektrale Clusteranalyse eignet sich gut, wenn die Cluster in den Daten nicht-konvex, nicht-linear trennbar oder durch dünne Brücken verbunden sind, die euklidische Partitionierungsmethoden nicht erkennen können – häufige Beispiele sind ringförmige Cluster, verschachtelte Spiralen und Bildsegmente. Sie ist geeignet, wenn die paarweise Ähnlichkeit zwischen Punkten sinnvoll berechnet werden kann (entweder aus einem Kernel auf Rohmerkmalen oder aus einer vorab bereitgestellten Affinitätsmatrix) und wenn die Anzahl der Cluster k bekannt ist oder mittels der Eigengap-Heuristik geschätzt werden kann. Die Methode erfordert keine Verteilungsannahmen über die Clusterformen. Praktische Einschränkungen umfassen einen quadratischen Speicherbedarf in der Anzahl der Punkte (für die vollständige Affinitätsmatrix) und eine kubische Zeit für die Eigenzerlegung, was die Standardformulierung jenseits von etwa 10.000 Punkten teuer macht. Approximative Methoden (Nystrom, dünne Graphen, randomisierte SVD) erweitern ihre Reichweite auf größere Datensätze.
Grenzen und Hinweise
- Die Konstruktion der vollständigen n-mal-n-Affinitätsmatrix erfordert O(n^2) Speicher und O(n^3) Zeit für die Eigenzerlegung, was den naiven Algorithmus für große Datensätze unpraktikabel macht.
- Die Ergebnisse sind empfindlich gegenüber der Wahl der Kernel-Bandbreite sigma und der Strategie zur Graphenkonstruktion; schlechte Entscheidungen können Cluster zusammenführen oder fragmentieren.
- Die k-means-Initialisierung in der spektralen Einbettung führt zu Zufälligkeit; verschiedene Läufe können unterschiedliche Partitionen ergeben.
- Skaliert nicht gut auf sehr hochdimensionale Merkmalsräume ohne sorgfältige Kernelauswahl.
- Liefert nur Cluster-Labels; sie bietet kein generatives Modell und keine natürliche Out-of-Sample-Erweiterung für neue Punkte.
Die Bedingungen der Quelle ersetzen weder eine unabhängige wissenschaftliche Prüfung noch die Validierung durch eine Analyse-Engine.
Stärken
- Erkennt Cluster beliebiger Form, einschließlich nicht-konvexer und nicht-linear trennbarer Konfigurationen, die k-means und Gaußsche Mischmodelle überwinden.
- Kann auf jede paarweise Ähnlichkeitsmatrix angewendet werden, nicht nur auf euklidische Distanzen, wodurch sie auf Graphen, Zeichenketten und andere strukturierte Daten anwendbar ist.
- Die Eigengap-Heuristik bietet eine prinzipielle datengesteuerte Anleitung zur Wahl der Clusteranzahl k.
- Basiert auf einer reichen spektralen Graphentheorie, die eine formale Analyse von Konvergenz und Clusterqualität ermöglicht.
- Konzeptionell einfach und leicht implementierbar mit Standard-Linear-Algebra-Bibliotheken.
Anwendungen
- Bildsegmentierung: Partitionierung von Pixeln oder Superpixeln in wahrnehmungsmäßig kohärente Regionen unter Verwendung von Pixel-Level-Merkmalsähnlichkeit.
- Community Detection in sozialen und biologischen Netzwerken, wo paarweise Konnektivität und nicht Merkmalsvektoren die Struktur definieren.
- Bioinformatik: Gruppierung von Genen oder Proteinen nach Ähnlichkeit des Expressionsprofils, wobei Expressionscluster im Genraum selten konvex sind.
- Natürliche Sprachverarbeitung: Dokumenten- oder Satz-Clustering unter Verwendung von semantischen Ähnlichkeits-Kernels.
- Computer Vision: Bewegungserkennung und Punktwolkenpartitionierung, wo Clustergrenzen unregelmäßig sind.
- Explorative Datenanalyse: Aufdeckung nicht-offensichtlicher Clusterstrukturen vor der Anwendung konfirmatorischer Methoden.
So funktioniert es
So funktioniert es
Aus den Daten wird eine paarweise Ähnlichkeitsmatrix (Affinitätsmatrix) W konstruiert. Die häufigste Wahl ist der Gaußsche (RBF) Kernel, der benachbarten Paaren ein hohes Gewicht und entfernten Paaren ein Gewicht nahe Null zuweist. Der Bandbreitenparameter sigma steuert, wie schnell die Ähnlichkeit mit der Distanz abnimmt; seine gute Wahl ist entscheidend. Alternativ kann ein k-nächste-Nachbarn-Graph für dünnbesetzte Darstellungen auf großen Datensätzen verwendet werden.
Formel
W_{ij} = \exp\!\left(-\frac{\|x_i - x_j\|^2}{2\sigma^2}\right)Die Gradmatrix D ist die Diagonalmatrix, deren i-ter Eintrag die Summe der i-ten Zeile von W ist. Aus W und D wird der normalisierte (symmetrische) Graph-Laplace-Operator L_sym gebildet. Diese Matrix erfasst die vollständige Konnektivitätsstruktur des Ähnlichkeitsgraphen; ihr Eigenwertspektrum zeigt, wie viele natürliche Cluster die Daten enthalten und wie sauber sie getrennt sind.
Formel
L_{\mathrm{sym}} = D^{-1/2}(D - W)D^{-1/2} = I - D^{-1/2}W D^{-1/2}Die k Eigenvektoren, die den k kleinsten Eigenwerten von L_sym entsprechen, werden berechnet. Diese Eigenvektoren bilden die Spalten der Einbettungsmatrix U, die eine Zeile pro Datenpunkt hat. In diesem k-dimensionalen Spektralraum werden Punkte, die zum selben Cluster gehören, eng zusammengezogen, selbst wenn sie im ursprünglichen Merkmalsraum verschachtelt waren.
Formel
L_{\mathrm{sym}}\, u = \lambda u \quad \Rightarrow \quad U = [u_1,\, u_2,\, \ldots,\, u_k]Jede Zeile von U wird durch ihre euklidische Norm geteilt, um die eingebetteten Punkte auf die Einheits-Hypersphäre zu projizieren. Diese Normalisierung, eingeführt von Ng, Jordan und Weiss, entfernt störende Skalenunterschiede zwischen Eigenvektoren und stellt sicher, dass der nachfolgende k-means-Schritt sich auf die Winkelstruktur der Einbettung und nicht auf die Größe konzentriert.
Formel
T_{ij} = U_{ij} \Big/ \left(\sum_{j'} U_{ij'}^2\right)^{1/2}Das Standard-k-means-Clustering wird auf die Zeilen der normalisierten Einbettungsmatrix T angewendet. Da die spektrale Einbettung die Clustergeometrie bereits entwirrt hat, findet k-means auch für nicht-konvexe Clusterformen aussagekräftige Partitionen. Die Cluster-Labels werden dann auf die ursprünglichen Datenpunkte zurückabgebildet.
Häufige Fallstricke
- Wahl von sigma ohne prinzipielle Kreuzvalidierung oder Selbstabstimmung; eine zu kleine Bandbreite erzeugt einen getrennten Graphen, während eine zu große Bandbreite unterschiedliche Cluster zusammenführt.
- Vernachlässigung der Normalisierung der Affinitätsmatrixzeilen vor k-means (der Zeilen-Normalisierungsschritt von Ng et al. ist für die Stabilität unerlässlich).
- Ignorieren des Eigengaps: Die Verwendung eines festen k ohne Inspektion des Eigenwertspektrums führt oft zu Unter- oder Übersegmentierung.
- Anwendung des vollständigen Algorithmus auf Datensätze mit Zehntausenden von Punkten, ohne auf eine approximative oder dünnbesetzte Variante umzusteigen.
- Verwechslung von unnormalisierten (L = D - W) und normalisierten (L_sym, L_rw) Laplace-Operatoren, was die Clusterzuweisungen erheblich verändern kann.
Häufig gestellte Fragen
Wie wähle ich die Anzahl der Cluster k?
Die Eigengap-Heuristik ist die Standardanleitung: Berechnen Sie die Eigenwerte des normalisierten Laplace-Operators in aufsteigender Reihenfolge und suchen Sie nach der größten Lücke zwischen aufeinanderfolgenden Eigenwerten. Der Index, an dem diese Lücke auftritt, deutet auf die natürliche Anzahl der Cluster hin. Wenn der Eigengap mehrdeutig ist, können stabilitätsbasierte Ansätze – die Ausführung des Algorithmus für mehrere k-Werte und der Vergleich von Clusterzuweisungen über Störungen hinweg – helfen.
Wie soll ich die Gaußsche Kernel-Bandbreite sigma einstellen?
Eine gängige Heuristik ist der Median der paarweisen Distanzen im Datensatz oder ein k-nächste-Nachbarn-Selbstabstimmungsverfahren (Zelnik-Manor & Perona, 2004), das jedem Punkt eine lokale Bandbreite zuweist. In der Praxis sollte sigma durch Inspektion der Konnektivität des resultierenden Affinitätsgraphen validiert werden: Jeder Punkt sollte mindestens einige hochgewichtete Nachbarn haben, und der Graph sollte nicht in isolierte Komponenten fragmentieren.
Warum ist der Zeilen-Normalisierungsschritt notwendig?
Die Eigenvektoren des Laplace-Operators können sich in ihrer Skala erheblich unterscheiden. Ohne die Normalisierung jeder Zeile der Einbettungsmatrix auf Einheitslänge könnte der k-means-Schritt von Eigenvektoren mit großen Beträgen dominiert werden und informative, aber kleinere Betragskomponenten ignorieren. Die von Ng, Jordan und Weiss eingeführte Zeilen-Normalisierung bildet alle Punkte auf die Einheitskugel ab, sodass k-means auf die Winkelgeometrie der Einbettung reagiert.
Kann die Spektrale Clusteranalyse sehr große Datensätze verarbeiten?
Nicht in ihrer naiven Form, die O(n^2) Speicher und O(n^3) Eigenzerlegungszeit erfordert. Für große n umfassen Standardlösungen: die Erstellung eines dünnbesetzten k-nächste-Nachbarn-Graphen anstelle einer vollständigen Affinitätsmatrix; die Verwendung der Nystrom-Approximation zur Schätzung von Eigenvektoren aus einer Stichprobe; oder die Anwendung von randomisierter SVD. Diese approximativen Methoden stellen den größten Teil der Genauigkeit zu einem Bruchteil der Kosten wieder her.
Verwandte Methoden
Quellen
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.
Publikationsreferenz öffnenKopiert.von Luxburg, U. (2007). A Tutorial on Spectral Clustering. Statistics and Computing, 17, 395–416.
DOI-Referenz öffnenKopiert.Shi, J., & Malik, J. (2000). Normalized Cuts and Image Segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 22(8), 888–905.
DOI-Referenz öffnenKopiert.