www.wikidata.de-de.nina.az

Spektrales Clustering Das spektrale Clustering ist ein Verfahren der Clusteranalyse Die zu clusternden Objekte werden al

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

Graph mit zwei Zusammenhangskomponenten

Mathematische Grundlagen Bearbeiten

Graphenreduktion 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:

Laplace-Matrizen 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

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.

Algorithmen Bearbeiten

Verschiedene Spektrale-Clustering-Algorithmen wurden entwickelt:

  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
  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
  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:

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

Beispiel Bearbeiten

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.

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

  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: (Nicht mehr online verfügbar.) 2007, archiviert vom Original 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: (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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das spektrale Clustering ist ein Verfahren der Clusteranalyse Die zu clusternden Objekte werden als Knoten eines Graphen betrachtet Die Distanzen oder Unahnlichkeiten zwischen den Objekten werden durch die gewichteten Kanten zwischen den Knoten des Graphen reprasentiert Graphentheoretische Resultate uber Laplace Matrizen von Graphen mit k 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 amp Hoffman 1973 sowie Fiedler 1973 gelegt 1 2 Graph mit zwei Zusammenhangskomponenten Inhaltsverzeichnis 1 Mathematische Grundlagen 1 1 Graphenreduktion 1 2 Laplace Matrizen 2 Algorithmen 3 Beispiel 4 EinzelnachweiseMathematische Grundlagen BearbeitenGraphenreduktion Bearbeiten In einem ersten Schritt wird der Graph reduziert Ziel ist es dabei alle Kanten mit zu grossen Gewichten aus dem Graphen zu entfernen Folgende Ansatze gibt es ϵ displaystyle epsilon nbsp Nachbarschaftsgraph Wenn das Kantengewicht grosser als ϵ displaystyle epsilon nbsp ist dann wird diese Kante aus dem Graph entfernt k nn Graphen k displaystyle k nbsp nachste Nachbarngraphen Alle Kanten zu einem Knoten werden nach dem Kantengewicht sortiert Hat eine Kante ein grosseres Kantengewicht als das k displaystyle k nbsp kleinste Kantengewicht dann wird diese Kante aus dem Graph entfernt Die k displaystyle k nbsp nn Relation ist jedoch nicht symmetrisch d h es kann passieren dass das Kantengewicht w i j displaystyle w ij nbsp kleiner ist als das k displaystyle k nbsp kleinste Kantengewicht zum Objekt o i displaystyle o i nbsp aber nicht kleiner ist als das k displaystyle k nbsp kleinste Kantengewicht zum Objekt o j displaystyle o j nbsp Man spricht von einem k nn Graph wenn die Kante im Graph bleibt falls fur mindestens eines der Objekte o i displaystyle o i nbsp oder o j displaystyle o j nbsp gilt dass w i j displaystyle w ij nbsp kleiner ist als das k displaystyle k nbsp kleinste Kantengewicht zum Objekt d h jedes Objekt hat mindestens k displaystyle k nbsp Kanten Im Gegensatz dazu enthalt ein gemeinsamer k nn Graph nur die Kante wenn fur beide Objekte gilt dass w i j displaystyle w ij nbsp kleiner ist als das k displaystyle k nbsp kleinste Kantengewicht der Objekten d h jedes Objekt hat maximal k displaystyle k nbsp Kanten Voll verbundener Graph Mit Hilfe einer Ahnlichkeitsfunktion werden die Kantengewichte aus den Distanzen zwischen den Objekten berechnet Ein Beispiel fur eine Ahnlichkeitsfunktion ist die gausssche Ahnlichkeitsfunktion s o i o j exp 1 2 d 2 o i o j s 2 displaystyle s o i o j exp tfrac 1 2 d 2 o i o j sigma 2 nbsp Der Parameter s displaystyle sigma nbsp kontrolliert die Grosse der Nachbarschaft wie auch die Parameter ϵ displaystyle epsilon nbsp oder k displaystyle k nbsp nbsp Position von 8 Objekten in einem zweidimensionalen Raum nbsp Voll verbundener Graph mit den euklidischen Distanzen an den Kanten fur die 8 Objekte nbsp Distanzmatrix der euklidischen Distanzen fur die 8 Objekte nbsp ϵ displaystyle epsilon nbsp Nachbarschaftsgraph ϵ 5 displaystyle epsilon 5 nbsp fur die 8 Objekte nbsp k nn Graph k 2 displaystyle k 2 nbsp fur die 8 Objekte Jeder Knoten hat mindestens zwei Kanten nbsp Gemeinsamer k nn Graph k 2 displaystyle k 2 nbsp fur die 8 Objekte Jeder Knoten hat maximal zwei Kanten Der Datensatz zerfallt in 3 Zusammenhangskomponenten nbsp Laplace Matrix L r w displaystyle L rw nbsp des gemeinsamen k nn Graphen k 2 displaystyle k 2 nbsp fur die 8 Objekte nbsp Voll verbundener Graph mit den Werten der gaussschen Ahnlichkeitsfunktion s 3 displaystyle sigma 3 nbsp an den Kanten fur die 8 Objekte Laplace Matrizen Bearbeiten Aus den Kantengewichten wird fur die n displaystyle n nbsp Objekte die gewichtete Adjazenzmatrix W displaystyle W nbsp gebildet Die Diagonalmatrix D displaystyle D nbsp enthalt auf der Diagonalen die Summe der Kantengewichte die zu einem Knoten fuhren nach der Graphenreduktion Dann konnen drei Laplace Matrizen berechnet werden nicht normalisierte Matrix L D W displaystyle L D W nbsp die normalisierte Matrix L s y m D 1 2 L D 1 2 displaystyle L sym D 1 2 LD 1 2 nbsp und die normalisierte Matrix L r w D 1 L displaystyle L rw D 1 L nbsp Fur alle Vektoren f R n displaystyle f in R n nbsp gilt f T L f 1 2 i j 1 n w i j f i f j 2 0 f T L s y m f 1 2 i j 1 n w i j f i d i f j d j 2 0 f T L r w f 1 2 i j 1 n w i j f i f j 2 0 displaystyle begin array rcll f T Lf amp amp displaystyle tfrac 1 2 sum i j 1 n w ij left f i f j right 2 amp geq 0 f T L sym f amp amp 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 amp geq 0 f T L rw f amp amp displaystyle tfrac 1 2 sum i j 1 n w ij left f i f j right 2 amp geq 0 end array nbsp 3 Da die Laplace Matrizen symmetrisch und positiv semidefinit sind sind alle Eigenwerte reellwertig und grosser gleich Null Fur die Laplace Matrix kann man zeigen dass mindestens ein Eigenwert gleich Null ist Besteht der Graph aus k displaystyle k nbsp Zusammenhangskomponenten dann sind die Laplace Matrizen Blockmatrizen siehe Grafik und Matrix oben Dabei hat jeder Block einen Eigenwert gleich Null Fur die Eigenvektoren zum Eigenwert Null muss f T L f 0 displaystyle f T Lf 0 nbsp sein Da alle Kantengewichte w i j displaystyle w ij nbsp positiv sind mussen alle Eintrage f i displaystyle f i nbsp der Knoten einer Zusammenhangskomponente gleich sein damit f i f j 0 displaystyle f i f j 0 nbsp gilt Analog gilt dies fur L s y m displaystyle L sym nbsp nur dass die Eintrage im Eigenvektor mit d i displaystyle d i nbsp gewichtet sind wahrend fur L r w displaystyle L rw nbsp die Eintrage f i displaystyle f i nbsp im Eigenvektor gleich Eins sind Zum Clustern analysiert man die kleinsten Eigenwerte und vektoren der Laplace Matrizen nbsp Eigenwerte der Laplace Matrix des Gemeinsamen k nn Graph k 3 displaystyle k 3 nbsp fur die 8 Objekte Daten Da der Graph aus drei Zusammenhangskomponenten besteht ergeben sich drei Eigenwerte mit dem Wert Null nbsp Werte der drei Eigenvektoren zum Eigenwert Null der Laplace Matrix L r w displaystyle L rw nbsp Die Eintrage sollten gleich Eins sein aber die Software reskaliert die Eigenvektoren so dass sie die Lange Eins haben nbsp 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 BearbeitenVerschiedene Spektrale Clustering Algorithmen wurden entwickelt Nicht normalisiertes spektrales ClusteringBerechne die nicht normalisierte Laplace Matrix L displaystyle L nbsp Berechne die ersten k displaystyle k nbsp Eigenvektoren das sind die Eigenvektoren mit den k displaystyle k nbsp kleinsten Eigenwerten Nimm die Zeilen der k displaystyle k nbsp Eigenvektoren und clustere sie mit einem partitionierenden Verfahren z B dem k Means AlgorithmusNormalisiertes spektrales Clustering nach Shi und Malik 4 Berechne die normalisierte Laplace Matrix L r w displaystyle L rw nbsp Berechne die ersten k displaystyle k nbsp Eigenvektoren das sind die Eigenvektoren mit den k displaystyle k nbsp kleinsten Eigenwerten Nimm die Zeilen der k displaystyle k nbsp Eigenvektoren und clustere sie mit einem partitionierenden VerfahrenNormalisiertes spektrales Clustering nach Ng Jordan und Weiss 5 Berechne die normalisierte Laplace Matrix L s y m displaystyle L sym nbsp Berechne die ersten k displaystyle k nbsp Eigenvektoren das sind die Eigenvektoren mit den k displaystyle k nbsp kleinsten Eigenwerten Nimm die Zeilen der k displaystyle k nbsp Eigenvektoren und clustere sie mit einem partitionierenden VerfahrenBezuglich 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 dunn besetzte Laplace Matrix erzeugt Ausserdem kann k displaystyle k nbsp in einem grosseren Bereich variieren ohne dass sich die Clusteranalyse stark verandert Wahl der Parameter des Nachbarschaftsgraphs Fur den k nn Graph sollte k displaystyle k nbsp so gewahlt werden dass der Graph nicht weniger Zusammenhangskomponenten hat als man Cluster erwartet Fur den gemeinsamen k nn Graph sollte k displaystyle k nbsp grosser sein als beim k nn Graph da der gemeinsame k nn Graph weniger Kanten enthalt als der k nn Graph Eine Heuristik fur die Wahl von k displaystyle k nbsp ist nicht bekannt Fur den ϵ displaystyle epsilon nbsp Nachbarschaftsgraph sollte man ϵ displaystyle epsilon nbsp gleich der langsten Kante im minimalen Spannbaum engl minimal spanning tree wahlen Fur den voll verbundenen Graph mit der gausssche Ahnlichkeitsfunktion sollte s displaystyle sigma nbsp so gewahlt werden dass der resultierende Graph dem k nn Graph oder dem ϵ displaystyle epsilon nbsp Nachbarschaftsgraph entspricht Daumenregel sind auch s displaystyle sigma nbsp gleich der langsten Kante im minimalen Spannbaum oder s displaystyle sigma nbsp als die mittlere Distanz zum k displaystyle k nbsp nachsten Nachbarn mit k 1 log n displaystyle k 1 log n nbsp Wahl der Clusteranzahl Man plottet die Eigenwerte der Laplace Matrix sortiert nach der Grosse und sucht nach Sprungen z B in der Grafik oben zwischen dem 3 und 4 Eigenwert bei dem 8 Objekte Datensatz Wahl der Laplace Matrix Da die Eintrage im Eigenvektor gleich Eins sind bei L r w displaystyle L rw nbsp kann z B der k Means Algorithmus gut clustern Beispiel BearbeitenDer Iris Datensatz wurde von Sir Ronald Fisher 1936 als Beispiel fur 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 Lange und Breite gemessen Der Datensatz enthalt also 150 Beobachtungen und 4 Variablen nbsp Streudiagrammmatrix des Iris Datensatzes Die Farben der Datenpunkte entsprechen den drei Arten nbsp Heatmap der euklidischen Distanzen im Iris Datensatz Je dunkler die Farbe desto kleiner ist die Distanz zwischen den Objekten nbsp 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 konnen 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 naher sind sich die Objekte Dabei sind die Objekte bereits so umgeordnet worden dass Objekte mit ahnlichen 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 einigermassen mit den drei Arten ubereinstimmen nbsp Schwarz Kanten zwischen Objekten die bei einem k nn Graph k 50 displaystyle k 50 nbsp erhalten bleiben Weiss Kanten die geloscht wurden nbsp Schwarz Kanten zwischen Objekten die bei einem gemeinsamen k nn Graph k 50 displaystyle k 50 nbsp erhalten bleiben Weiss Kanten die geloscht wurden nbsp Streudiagramm der Eigenwerte der Laplace Matrix L r w displaystyle L rw nbsp fur den k nn Graph k 50 displaystyle k 50 nbsp Die beiden linken Bilder zeigen welche Kanten im k nn Graph bzw gemeinsamen k nn Graph beibehalten wurden schwarz oder nicht weiss Fur den Parameter k displaystyle k nbsp wurde dabei zunachst die langste Kante in einem minimalen Spannbaum bestimmt und dann fur alle Beobachtungen berechnet welcher Nachbarschaftsanzahl es entspricht Als mittlere Wert ergab sich ca 60 Nachbarn und es wurde dann k 50 displaystyle k 50 nbsp gewahlt Danach wurde die Laplace Matrix L r w displaystyle L rw nbsp berechnet sowie deren Eigenwerte Das Diagramm der Eigenwerte zeigt grosse Sprunge nach dem zweiten bzw dem dritten Eigenwert an Die ersten drei Eigenvektoren wurden dann einem k Means Clustering mit 3 Clustern unterzogen ClusterArt 1 2 3setosa 0 0 50versicolor 43 7 0virginica 7 43 0Die Konfusionsmatrix zeigt dass das Spektral Clustering einigermassen 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 9 4 displaystyle 14 150 approx 9 4 nbsp Einzelnachweise Bearbeiten 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 M Fiedler Algebraic connectivity of graphs In Czechoslovak Mathematical Journal 23 2 1973 S 298 305 Ulrike von Luxburg A Tutorial on Spectral Clustering Nicht mehr online verfugbar 2007 archiviert vom Original am 6 Februar 2011 abgerufen am 6 Januar 2018 nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot www kyb mpg de 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 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 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 R A Fisher The use of multiple measurements in taxonomic problems Memento des Originals vom 16 Mai 2017 imInternet Archive nbsp Info Der Archivlink wurde automatisch eingesetzt und noch nicht gepruft Bitte prufe Original und Archivlink gemass Anleitung und entferne dann diesen Hinweis 1 2 Vorlage Webachiv IABot rcs chemometrics ru In Annals of Eugenics 7 2 1936 S 179 188 doi 10 1111 j 1469 1809 1936 tb02137 x E Anderson The species problem in Iris In Annals of the Missouri Botanical Garden 1936 S 457 509 Abgerufen von https de wikipedia org w index php title Spektrales Clustering amp oldid 229780764