Spektrales Clustering

Graph mit zwei Zusammenhangskomponenten

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 $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.

Mathematische Grundlagen

Graphenreduktion

In einem ersten Schritt wird der Graph reduziert. Ziel ist es dabei, alle Kanten mit zu großen Gewichten aus dem Graphen zu entfernen. Folgende Ansätze gibt es:

$\epsilon$ Nachbarschaftsgraph

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

k-nn Graphen ($k$ nächste Nachbarngraphen)

Alle Kanten zu einem Knoten werden nach dem Kantengewicht sortiert. Hat eine Kante ein größeres Kantengewicht als das $k$ kleinste Kantengewicht, dann wird diese Kante aus dem Graph entfernt. Die $k$-nn Relation ist jedoch nicht symmetrisch, d. h. es kann passieren, dass das Kantengewicht $w_{ij}$ kleiner ist als das $k$ kleinste Kantengewicht zum Objekt $o_{i}$, aber nicht kleiner ist als das $k$ kleinste Kantengewicht zum Objekt $o_{j}$. Man spricht von einem k-nn Graph, wenn die Kante im Graph bleibt, falls für mindestens eines der Objekte $o_{i}$ oder $o_{j}$ gilt, dass $w_{ij}$ kleiner ist als das $k$ kleinste Kantengewicht zum Objekt, d. h. jedes Objekt hat mindestens $k$ Kanten. Im Gegensatz dazu enthält ein gemeinsamer k-nn Graph nur die Kante, wenn für beide Objekte gilt, dass $w_{ij}$ kleiner ist als das $k$ kleinste Kantengewicht der Objekten, d. h. jedes Objekt hat maximal $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 $s(o_{i},o_{j})=\exp(-{\tfrac {1}{2}}d^{2}(o_{i},o_{j})/\sigma ^{2})$. Der Parameter $\sigma$ kontrolliert die Größe der Nachbarschaft wie auch die Parameter $\epsilon$ oder $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.
• 
  $\epsilon$ Nachbarschaftsgraph ($\epsilon =5$ ) für die 8 Objekte.
• 
  k-nn Graph ($k=2$) für die 8 Objekte. Jeder Knoten hat mindestens zwei Kanten.
• 
  Gemeinsamer k-nn Graph ($k=2$) für die 8 Objekte. Jeder Knoten hat maximal zwei Kanten. Der Datensatz zerfällt in 3 Zusammenhangskomponenten.
• 
  Laplace-Matrix $L_{rw}$ des gemeinsamen k-nn Graphen ($k=2$) für die 8 Objekte.
• 
  Voll verbundener Graph mit den Werten der gaußschen Ähnlichkeitsfunktion ($\sigma =3$) an den Kanten für die 8 Objekte.

Laplace-Matrizen

Aus den Kantengewichten wird für die $n$ Objekte die (gewichtete) Adjazenzmatrix $W$ gebildet. Die Diagonalmatrix $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 $L=D-W$,
• die normalisierte Matrix $L_{sym}=D^{-1/2}LD^{-1/2}$ und
• die normalisierte Matrix $L_{rw}=D^{-1}L$.

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

${\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}}$

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 $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 $f^{T}Lf=0$ sein. Da alle Kantengewichte $w_{ij}$ positiv sind, müssen alle Einträge $f_{i}$ der Knoten einer Zusammenhangskomponente gleich sein (damit $f_{i}-f_{j}=0$ gilt). Analog gilt dies für $L_{sym}$, nur dass die Einträge im Eigenvektor mit $d_{i}$ gewichtet sind, während für $L_{rw}$ die Einträge $f_{i}$ im Eigenvektor gleich Eins sind.

Zum Clustern analysiert man die kleinsten Eigenwerte und -vektoren der Laplace-Matrizen.

• 
  Eigenwerte der Laplace-Matrix des Gemeinsamen k-nn Graph ($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 $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 $L$
2. Berechne die ersten $k$ Eigenvektoren (das sind die Eigenvektoren mit den $k$ kleinsten Eigenwerten)
3. Nimm die Zeilen der $k$ Eigenvektoren und clustere sie mit einem partitionierenden Verfahren, z. B. dem k-Means-Algorithmus

Normalisiertes spektrales Clustering nach Shi und Malik

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

Normalisiertes spektrales Clustering nach Ng, Jordan und Weiss

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

Bezüglich der Wahl der Verfahrensparameter bzw. -algorithmen empfiehlt das Tutorial von Ulrike von Luxburg:

• 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 $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 $k$ so gewählt werden, dass der Graph nicht weniger Zusammenhangskomponenten hat als man Cluster erwartet.
  • Für den gemeinsamen k-nn Graph sollte $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 $k$ ist nicht bekannt.
  • Für den $\epsilon$ Nachbarschaftsgraph sollte man $\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 $\sigma$ so gewählt werden, dass der resultierende Graph dem k-nn Graph oder dem $\epsilon$ Nachbarschaftsgraph entspricht. Daumenregel sind auch: $\sigma$ gleich der längsten Kante im minimalen Spannbaum oder $\sigma$ als die mittlere Distanz zum $k$ nächsten Nachbarn mit $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 $L_{rw}$, kann z. B. der k-Means-Algorithmus gut clustern.

Beispiel

Der Iris Datensatz wurde von Sir Ronald Fisher (1936) als Beispiel für eine Diskriminanzanalyse benutzt. Manchmal wird er auch ‚Anderson's Iris Datensatz‘ genannt, weil Edgar Anderson die Daten erhoben hat um die morphologische Variation in Schwertlilien zu quantifizieren. Der Datensatz besteht aus jeweils 50 Exemplaren von drei Arten: der Borsten-Schwertlilie (Iris setosa), der Schillernde Schwertlilie (Iris versicolor) und der Virginische Schwertlilie (Iris virginica). An einem Kelchblatt (engl. sepal) und an einem Kronblatt (engl. petal) wurden jeweils die Länge und Breite gemessen. Der Datensatz enthält also 150 Beobachtungen und 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 man in der linken (ersten) Grafik in der Streudiagrammmatrix sieht, unterscheidet sich eine der drei Arten (rot in der Grafik) deutlich von den anderen Arten. Die beiden anderen Arten können nur schwer voneinander getrennt werden. Die mittlere (zweite) Grafik zeigt die euklidischen Distanzen zwischen den Objekten in einer Heatmap mit Graustufen. Je dunkler das Grau ist, desto näher sind sich die Objekte. Dabei sind die Objekte bereits so umgeordnet worden, dass Objekte mit ähnlichen Distanzen zu anderen Objekten nahe beieinander sind. Die verwendete Software nutzt ein hierarchisches Clusterverfahren dazu und zeigt auch die Dendrogramme. Die rechte (dritte) Grafik zeigt das Ergebnis des spektralen Clusterings. Man sieht, dass die gefundenen Cluster einigermaßen mit den drei Arten übereinstimmen.

• 
  Schwarz: Kanten zwischen Objekten, die bei einem k-nn Graph ($k=50$) erhalten bleiben. Weiß: Kanten, die gelöscht wurden.
• 
  Schwarz: Kanten zwischen Objekten, die bei einem gemeinsamen k-nn Graph ($k=50$) erhalten bleiben. Weiß: Kanten, die gelöscht wurden.
• 
  Streudiagramm der Eigenwerte der Laplace-Matrix $L_{rw}$ für den k-nn Graph ($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 $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 $k=50$ gewählt. Danach wurde die Laplace-Matrix $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 $14/150\approx 9{,}4\,\%$.