Spektrales Clustering

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen
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 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]

Mathematische Grundlagen

[Bearbeiten | Quelltext bearbeiten]

Graphenreduktion

[Bearbeiten | Quelltext bearbeiten]

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:

Nachbarschaftsgraph
Wenn das Kantengewicht größer als ist, dann wird diese Kante aus dem Graph entfernt.
k-nn Graphen ( nächste Nachbarngraphen)
Alle Kanten zu einem Knoten werden nach dem Kantengewicht sortiert. Hat eine Kante ein größeres Kantengewicht als das kleinste Kantengewicht, dann wird diese Kante aus dem Graph entfernt. Die -nn Relation ist jedoch nicht symmetrisch, d. h. es kann passieren, dass das Kantengewicht kleiner ist als das kleinste Kantengewicht zum Objekt , aber nicht kleiner ist als das kleinste Kantengewicht zum Objekt . Man spricht von einem k-nn Graph, wenn die Kante im Graph bleibt, falls für mindestens eines der Objekte oder gilt, dass kleiner ist als das kleinste Kantengewicht zum Objekt, d. h. jedes Objekt hat mindestens Kanten. Im Gegensatz dazu enthält ein gemeinsamer k-nn Graph nur die Kante, wenn für beide Objekte gilt, dass kleiner ist als das kleinste Kantengewicht der Objekten, d. h. jedes Objekt hat maximal 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 . Der Parameter kontrolliert die Größe der Nachbarschaft wie auch die Parameter oder .

Laplace-Matrizen

[Bearbeiten | Quelltext bearbeiten]

Aus den Kantengewichten wird für die Objekte die (gewichtete) Adjazenzmatrix gebildet. Die Diagonalmatrix 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 ,
  • die normalisierte Matrix und
  • die normalisierte Matrix .

Für alle Vektoren gilt

[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 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 sein. Da alle Kantengewichte positiv sind, müssen alle Einträge der Knoten einer Zusammenhangskomponente gleich sein (damit gilt). Analog gilt dies für , nur dass die Einträge im Eigenvektor mit gewichtet sind, während für die Einträge im Eigenvektor gleich Eins sind.

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

Verschiedene Spektrale-Clustering-Algorithmen wurden entwickelt:

Nicht-normalisiertes spektrales Clustering
  1. Berechne die nicht-normalisierte Laplace-Matrix
  2. Berechne die ersten Eigenvektoren (das sind die Eigenvektoren mit den kleinsten Eigenwerten)
  3. Nimm die Zeilen der 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
  2. Berechne die ersten Eigenvektoren (das sind die Eigenvektoren mit den kleinsten Eigenwerten)
  3. Nimm die Zeilen der Eigenvektoren und clustere sie mit einem partitionierenden Verfahren
Normalisiertes spektrales Clustering nach Ng, Jordan und Weiss[5]
  1. Berechne die normalisierte Laplace-Matrix
  2. Berechne die ersten Eigenvektoren (das sind die Eigenvektoren mit den kleinsten Eigenwerten)
  3. Nimm die Zeilen der Eigenvektoren und clustere sie mit einem partitionierenden Verfahren

Bezüglich der Wahl der Verfahrensparameter bzw. -algorithmen empfiehlt das Tutorial von Ulrike von 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 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 so gewählt werden, dass der Graph nicht weniger Zusammenhangskomponenten hat als man Cluster erwartet.
    • Für den gemeinsamen k-nn Graph sollte 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 ist nicht bekannt.
    • Für den Nachbarschaftsgraph sollte man 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 so gewählt werden, dass der resultierende Graph dem k-nn Graph oder dem Nachbarschaftsgraph entspricht. Daumenregel sind auch: gleich der längsten Kante im minimalen Spannbaum oder als die mittlere Distanz zum nächsten Nachbarn mit .
  • 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 , kann z. B. der k-Means-Algorithmus gut clustern.

Der Iris Datensatz wurde von Sir Ronald Fisher (1936) als Beispiel für eine Diskriminanzanalyse benutzt.[7] Manchmal wird er auch ‚Anderson's Iris Datensatz‘ genannt, weil Edgar Anderson die Daten erhoben hat um die morphologische Variation in Schwertlilien zu quantifizieren.[8] 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.

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.

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 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 gewählt. Danach wurde die Laplace-Matrix 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 .

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  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, archiviert vom Original (nicht mehr online verfügbar) am 6. Februar 2011; abgerufen am 6. Januar 2018.  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/www.kyb.mpg.de
  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 (Memento des Originals vom 16. Mai 2017 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis.@1@2Vorlage:Webachiv/IABot/rcs.chemometrics.ru. 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.