Spektrales Clustering

Das spektrale Clustering ist ein Verfahren der Clusteranalyse. Die zu clusternden Objekte werden als Knoten eines Graphen betrachtet. Die Distanzen oder Unähnlichkeiten zwischen den Objekten werden durch die gewichteten Kanten zwischen den Knoten des Graphen repräsentiert. Graphentheoretische Resultate über Laplace-Matrizen von Graphen mit ${\displaystyle k}$ Zusammenhangskomponenten sind die Grundlage des spektralen Clusterings. Die Eigenwerte einer Matrix werden auch Spektrum genannt, daher stammt der Name des Verfahrens. Die graphentheoretischen Grundlagen wurden von Donath & Hoffman (1973) sowie Fiedler (1973) gelegt.[1][2]

Graph mit zwei Zusammenhangskomponenten

Mathematische Grundlagen

Graphenreduktion

In e​inem ersten Schritt w​ird der Graph reduziert. Ziel i​st es dabei, a​lle Kanten m​it zu großen Gewichten a​us dem Graphen z​u entfernen. Folgende Ansätze g​ibt es:

${\displaystyle \epsilon }$ Nachbarschaftsgraph

Wenn das Kantengewicht größer als ${\displaystyle \epsilon }$ ist, dann wird diese Kante aus dem Graph entfernt.

k-nn Graphen (${\displaystyle k}$ nächste Nachbarngraphen)

Alle Kanten zu einem Knoten werden nach dem Kantengewicht sortiert. Hat eine Kante ein größeres Kantengewicht als das ${\displaystyle k}$ kleinste Kantengewicht, dann wird diese Kante aus dem Graph entfernt. Die ${\displaystyle k}$-nn Relation ist jedoch nicht symmetrisch, d. h. es kann passieren, dass das Kantengewicht ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt ${\displaystyle o_{i}}$, aber nicht kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt ${\displaystyle o_{j}}$. Man spricht von einem k-nn Graph, wenn die Kante im Graph bleibt, falls für mindestens eines der Objekte ${\displaystyle o_{i}}$ oder ${\displaystyle o_{j}}$ gilt, dass ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht zum Objekt, d. h. jedes Objekt hat mindestens ${\displaystyle k}$ Kanten. Im Gegensatz dazu enthält ein gemeinsamer k-nn Graph nur die Kante, wenn für beide Objekte gilt, dass ${\displaystyle w_{ij}}$ kleiner ist als das ${\displaystyle k}$ kleinste Kantengewicht der Objekten, d. h. jedes Objekt hat maximal ${\displaystyle k}$ Kanten.

Voll verbundener Graph

Mit Hilfe einer Ähnlichkeitsfunktion werden die Kantengewichte aus den Distanzen zwischen den Objekten berechnet. Ein Beispiel für eine Ähnlichkeitsfunktion ist die gaußsche Ähnlichkeitsfunktion ${\displaystyle s(o_{i},o_{j})=\exp(-{\tfrac {1}{2}}d^{2}(o_{i},o_{j})/\sigma ^{2})}$. Der Parameter ${\displaystyle \sigma }$ kontrolliert die Größe der Nachbarschaft wie auch die Parameter ${\displaystyle \epsilon }$ oder ${\displaystyle k}$.

• 
  Position von 8 Objekten in einem zweidimensionalen Raum.
• 
  Voll verbundener Graph mit den euklidischen Distanzen an den Kanten für die 8 Objekte.
• 
  Distanzmatrix der euklidischen Distanzen für die 8 Objekte.
• 
  ${\displaystyle \epsilon }$ Nachbarschaftsgraph (${\displaystyle \epsilon =5}$ ) für die 8 Objekte.
• 
  k-nn Graph (${\displaystyle k=2}$) für die 8 Objekte. Jeder Knoten hat mindestens zwei Kanten.
• 
  Gemeinsamer k-nn Graph (${\displaystyle k=2}$) für die 8 Objekte. Jeder Knoten hat maximal zwei Kanten. Der Datensatz zerfällt in 3 Zusammenhangskomponenten.
• 
  Laplace-Matrix ${\displaystyle L_{rw}}$ des gemeinsamen k-nn Graphen (${\displaystyle k=2}$) für die 8 Objekte.
• 
  Voll verbundener Graph mit den Werten der gaußschen Ähnlichkeitsfunktion (${\displaystyle \sigma =3}$) an den Kanten für die 8 Objekte.

Laplace-Matrizen

Aus den Kantengewichten wird für die ${\displaystyle n}$ Objekte die (gewichtete) Adjazenzmatrix ${\displaystyle W}$ gebildet. Die Diagonalmatrix ${\displaystyle D}$ enthält auf der Diagonalen die Summe der Kantengewichte, die zu einem Knoten führen (nach der Graphenreduktion). Dann können drei Laplace-Matrizen berechnet werden:

• nicht-normalisierte Matrix ${\displaystyle L=D-W}$,
• die normalisierte Matrix ${\displaystyle L_{sym}=D^{-1/2}LD^{-1/2}}$ und
• die normalisierte Matrix ${\displaystyle L_{rw}=D^{-1}L}$.

Für alle Vektoren ${\displaystyle f\in R^{n}}$ gilt

${\displaystyle {\begin{array}{rcll}f^{T}Lf&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0,\\f^{T}L_{sym}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left({\tfrac {f_{i}}{\sqrt {d_{i}}}}-{\tfrac {f_{j}}{\sqrt {d_{j}}}}\right)^{2}&\geq 0.\\f^{T}L_{rw}f&=&\displaystyle {\tfrac {1}{2}}\sum _{i,j=1}^{n}w_{ij}\left(f_{i}-f_{j}\right)^{2}&\geq 0\\\end{array}}}$[3]

Da die Laplace-Matrizen symmetrisch und positiv-semidefinit sind, sind alle Eigenwerte reellwertig und größer gleich Null. Für die Laplace-Matrix kann man zeigen, dass mindestens ein Eigenwert gleich Null ist. Besteht der Graph aus ${\displaystyle k}$ Zusammenhangskomponenten, dann sind die Laplace-Matrizen Blockmatrizen (siehe Grafik und Matrix oben). Dabei hat jeder Block einen Eigenwert gleich Null. Für die Eigenvektoren zum Eigenwert Null muss ${\displaystyle f^{T}Lf=0}$ sein. Da alle Kantengewichte ${\displaystyle w_{ij}}$ positiv sind, müssen alle Einträge ${\displaystyle f_{i}}$ der Knoten einer Zusammenhangskomponente gleich sein (damit ${\displaystyle f_{i}-f_{j}=0}$ gilt). Analog gilt dies für ${\displaystyle L_{sym}}$, nur dass die Einträge im Eigenvektor mit ${\displaystyle d_{i}}$ gewichtet sind, während für ${\displaystyle L_{rw}}$ die Einträge ${\displaystyle f_{i}}$ im Eigenvektor gleich Eins sind.

Zum Clustern analysiert m​an die kleinsten Eigenwerte u​nd -vektoren d​er Laplace-Matrizen.

• 
  Eigenwerte der Laplace-Matrix des Gemeinsamen k-nn Graph (${\displaystyle k=3}$) für die 8 Objekte Daten. Da der Graph aus drei Zusammenhangskomponenten besteht ergeben sich drei Eigenwerte mit dem Wert Null.
• 
  Werte der drei Eigenvektoren zum Eigenwert Null der Laplace-Matrix ${\displaystyle L_{rw}}$. Die Einträge sollten gleich Eins sein, aber die Software reskaliert die Eigenvektoren, so dass sie die Länge Eins haben.
• 
  3D-Streudiagramm der drei Eigenvektoren zu den Null-Eigenwerten. Die acht Objekte werden an drei Positionen geplottet (overplotting), so dass ein k-Means Clustering die drei Zusammenhangskomponenten perfekt finden kann.

Algorithmen

Verschiedene Spektrale-Clustering-Algorithmen wurden entwickelt:

Nicht-normalisiertes spektrales Clustering

1. Berechne die nicht-normalisierte Laplace-Matrix ${\displaystyle L}$
2. Berechne die ersten ${\displaystyle k}$ Eigenvektoren (das sind die Eigenvektoren mit den ${\displaystyle k}$ kleinsten Eigenwerten)
3. Nimm die Zeilen der ${\displaystyle k}$ Eigenvektoren und clustere sie mit einem partitionierenden Verfahren, z. B. dem k-Means-Algorithmus

Normalisiertes spektrales Clustering nach Shi und Malik[4]

1. Berechne die normalisierte Laplace-Matrix ${\displaystyle L_{rw}}$
2. Berechne die ersten ${\displaystyle k}$ Eigenvektoren (das sind die Eigenvektoren mit den ${\displaystyle k}$ kleinsten Eigenwerten)
3. Nimm die Zeilen der ${\displaystyle k}$ Eigenvektoren und clustere sie mit einem partitionierenden Verfahren

Normalisiertes spektrales Clustering nach Ng, Jordan und Weiss[5]

1. Berechne die normalisierte Laplace-Matrix ${\displaystyle L_{sym}}$
2. Berechne die ersten ${\displaystyle k}$ Eigenvektoren (das sind die Eigenvektoren mit den ${\displaystyle k}$ kleinsten Eigenwerten)
3. Nimm die Zeilen der ${\displaystyle k}$ Eigenvektoren und clustere sie mit einem partitionierenden Verfahren

Bezüglich d​er Wahl d​er Verfahrensparameter bzw. -algorithmen empfiehlt d​as Tutorial v​on Ulrike v​on Luxburg:[6]

• Wahl des Nachbarschaftsgraph: der k-nn Graph, da er verschieden dichte Cluster besser erkennen kann und eine dünn besetzte Laplace-Matrix erzeugt. Außerdem kann ${\displaystyle k}$ in einem größeren Bereich variieren, ohne dass sich die Clusteranalyse stark verändert.
• Wahl der Parameter des Nachbarschaftsgraphs:
  • Für den k-nn Graph sollte ${\displaystyle k}$ so gewählt werden, dass der Graph nicht weniger Zusammenhangskomponenten hat als man Cluster erwartet.
  • Für den gemeinsamen k-nn Graph sollte ${\displaystyle k}$ größer sein als beim k-nn Graph, da der gemeinsame k-nn Graph weniger Kanten enthält als der k-nn Graph. Eine Heuristik für die Wahl von ${\displaystyle k}$ ist nicht bekannt.
  • Für den ${\displaystyle \epsilon }$ Nachbarschaftsgraph sollte man ${\displaystyle \epsilon }$ gleich der längsten Kante im minimalen Spannbaum (engl. minimal spanning tree) wählen.
  • Für den voll verbundenen Graph mit der gaußsche Ähnlichkeitsfunktion sollte ${\displaystyle \sigma }$ so gewählt werden, dass der resultierende Graph dem k-nn Graph oder dem ${\displaystyle \epsilon }$ Nachbarschaftsgraph entspricht. Daumenregel sind auch: ${\displaystyle \sigma }$ gleich der längsten Kante im minimalen Spannbaum oder ${\displaystyle \sigma }$ als die mittlere Distanz zum ${\displaystyle k}$ nächsten Nachbarn mit ${\displaystyle k=1+\log(n)}$.
• Wahl der Clusteranzahl: Man plottet die Eigenwerte der Laplace-Matrix, sortiert nach der Größe und sucht nach Sprüngen, z. B. in der Grafik oben zwischen dem 3. und 4. Eigenwert bei dem 8-Objekte Datensatz.
• Wahl der Laplace-Matrix: Da die Einträge im Eigenvektor gleich Eins sind bei ${\displaystyle L_{rw}}$, kann z. B. der k-Means-Algorithmus gut clustern.

Beispiel

Der Iris Datensatz w​urde von Sir Ronald Fisher (1936) a​ls Beispiel für e​ine Diskriminanzanalyse benutzt.[7] Manchmal w​ird er a​uch ‚Anderson's Iris Datensatz‘ genannt, w​eil Edgar Anderson d​ie Daten erhoben h​at um d​ie morphologische Variation i​n Schwertlilien z​u quantifizieren.[8] Der Datensatz besteht a​us jeweils 50 Exemplaren v​on drei Arten: d​er Borsten-Schwertlilie (Iris setosa), d​er Schillernde Schwertlilie (Iris versicolor) u​nd der Virginische Schwertlilie (Iris virginica). An e​inem Kelchblatt (engl. sepal) u​nd an e​inem Kronblatt (engl. petal) wurden jeweils d​ie Länge u​nd Breite gemessen. Der Datensatz enthält a​lso 150 Beobachtungen u​nd 4 Variablen.

• 
  Streudiagrammmatrix des Iris Datensatzes. Die Farben der Datenpunkte entsprechen den drei Arten.
• 
  Heatmap der euklidischen Distanzen im Iris Datensatz. Je dunkler die Farbe desto kleiner ist die Distanz zwischen den Objekten.
• 
  Ergebnis des spektralen Clusterings auf dem Iris Datensatz.

Wie m​an in d​er linken (ersten) Grafik i​n der Streudiagrammmatrix sieht, unterscheidet s​ich eine d​er drei Arten (rot i​n der Grafik) deutlich v​on den anderen Arten. Die beiden anderen Arten können n​ur schwer voneinander getrennt werden. Die mittlere (zweite) Grafik z​eigt die euklidischen Distanzen zwischen d​en Objekten i​n einer Heatmap m​it Graustufen. Je dunkler d​as Grau ist, d​esto näher s​ind sich d​ie Objekte. Dabei s​ind die Objekte bereits s​o umgeordnet worden, d​ass Objekte m​it ähnlichen Distanzen z​u anderen Objekten n​ahe beieinander sind. Die verwendete Software n​utzt ein hierarchisches Clusterverfahren d​azu und z​eigt auch d​ie Dendrogramme. Die rechte (dritte) Grafik z​eigt das Ergebnis d​es spektralen Clusterings. Man sieht, d​ass die gefundenen Cluster einigermaßen m​it den d​rei Arten übereinstimmen.

• 
  Schwarz: Kanten zwischen Objekten, die bei einem k-nn Graph (${\displaystyle k=50}$) erhalten bleiben. Weiß: Kanten, die gelöscht wurden.
• 
  Schwarz: Kanten zwischen Objekten, die bei einem gemeinsamen k-nn Graph (${\displaystyle k=50}$) erhalten bleiben. Weiß: Kanten, die gelöscht wurden.
• 
  Streudiagramm der Eigenwerte der Laplace-Matrix ${\displaystyle L_{rw}}$ für den k-nn Graph (${\displaystyle k=50}$).

Die beiden linken Bilder zeigen, welche Kanten im k-nn Graph bzw. gemeinsamen k-nn Graph beibehalten wurden (schwarz) oder nicht (weiß). Für den Parameter ${\displaystyle k}$ wurde dabei zunächst die längste Kante in einem minimalen Spannbaum bestimmt und dann für alle Beobachtungen berechnet, welcher Nachbarschaftsanzahl es entspricht. Als mittlere Wert ergab sich ca. 60 Nachbarn und es wurde dann ${\displaystyle k=50}$ gewählt. Danach wurde die Laplace-Matrix ${\displaystyle L_{rw}}$ berechnet sowie deren Eigenwerte. Das Diagramm der Eigenwerte zeigt große Sprünge nach dem zweiten bzw. dem dritten Eigenwert an. Die ersten drei Eigenvektoren wurden dann einem k-Means-Clustering mit 3 Clustern unterzogen.

	Cluster
Art	1	2	3
setosa	0	0	50
versicolor	43	7	0
virginica	7	43	0

Die Konfusionsmatrix zeigt, dass das Spektral Clustering einigermaßen die Arten wiederentdeckt hat. Der Setosa-Cluster ist komplett richtig gefunden worden. Bei den Versicolor- und Virginica-Clustern sind jeweils sieben Beobachtungen falsch klassifiziert worden, das entspricht einer Falsch-Klassifikationsrate von ${\displaystyle 14/150\approx 9{,}4\,\%}$.

Einzelnachweise

1. W. E. Donath, A. J. Hoffman: Lower bounds for the partitioning of graphs. In: IBM Journal of Research and Development. 17(5), (1973), S. 420–425.
2. M. Fiedler: Algebraic connectivity of graphs. In: Czechoslovak Mathematical Journal. 23(2), (1973), S. 298–305.
3. Ulrike von Luxburg: A Tutorial on Spectral Clustering. 2007, abgerufen am 6. Januar 2018.
4. J. Shi, J. Malik: Normalized cuts and image segmentation. In: IEEE Transactions on Pattern Analysis and Machine Intelligence. 22(8), (2000), S. 888–905. doi:10.1109/34.868688
5. A. Y. Ng, M. I. Jordan, Y. Weiss: On spectral clustering: Analysis and an algorithm. In: Advances in Neural Information Processing Systems. 2, 2002, S. 849–856.
6. Ulrike von Luxburg: A tutorial on spectral clustering. (PDF; 411 kB). In: Statistics and Computing. 17(4), (2007), S. 395–416. doi:10.1007/s11222-007-9033-z
7. R. A. Fisher: The use of multiple measurements in taxonomic problems. In: Annals of Eugenics. 7(2), (1936), S. 179–188. doi:10.1111/j.1469-1809.1936.tb02137.x
8. E. Anderson: The species problem in Iris. In: Annals of the Missouri Botanical Garden. 1936, S. 457–509.