V03 - Clusterverfahren Flashcards
Wie ist Accuracy definiert? (V03F07)
Gibt an, wie viele Einschätzungen von allen Einschätzungen richtig waren. Also richtig als positiv und negativ erkannt wurden
Wie ist Precision definiert? (V03F07)
Gibt an, wie viele der als positiv vorhergesagten tatsächlich positiv sind
Welche Erfolgsmaße gibt es und wie werden sie berechnet? (V03F08)
○ Accuracy: (TP+TN) / (TP+TN+FP+FN)
○ Precision: TP / (TP+FP)
○ Recall: TP / (FN+TP)
○ F-Measure: 2* (Precision*Recall) / (Precision + Recall)
Welche Distanzfunktionen (Distanzmaße) gibt es für numerische Merkmale? (V03F13)
○ Euklidische Distanz
○ Manhattan-Distanz
○ Maximus-Metrik
Welche Verfahren gibt es für Hierarchische Clusterverfahren? (V03F16)
Agglomerative und divisive Verfahren
Wie wird bei agglomerative Verfahren vorgegangen? (V03F16)
Bei agglomerativen Verfahren werden aus einzelnen kleinen Gruppen immer größere Gruppen gebildet. Zu Beginn wird jeder einzelne Datenpunkt als eigene Gruppe betrachtet.
Wie wird bei divisiven Verfahren vorgegangen? (V03F16)
Bei den divisiven Verfahren werden aus einer großen Gruppe immer kleinere Gruppen gebildet, bis theoretisch am Ende jeder Datenpunkt eine eigene Gruppe darstellt.
Wie wird beim agglomerativen Verfahren vorgegangen (Detaillierter, 5 Schritte)? (V03F17)
○ 1 Gestartet wird mit N Clustern, d.h. jeder Datenpunkt zählt als eigenes Cluster
○ 2 Berechnung der Ausgangsdistanzmatrix (Ähnlichkeitsmatrix)
○ 3 Ermittlung der beiden Cluster mit der geringsten Distanz (größten Ähnlichkeit)
○ 4 Vereinigung der beiden Cluster mit der geringsten Distanz
○ 5 Gibt es nur noch eine Gruppe? Wenn ja Ende, wenn nein Neuberechnung der Distanzmatrix und ab Schritt 3 wiederholen
Was zeigt ein Dendrogramm? (V03F21)
○ Koordinatensystem mit allen Datenpunkten auf der X-Achse und dem Heterogenitätsmaß auf der Y-Achse. Zeigt die Ergebnisse einer hierarchischen Klassifikation, durch das Zusammenfügen von Datenpunkten oder Aufsplitten von Clustern. Die Reihenfolge kann gut abgelesen werden.
○ Es werden zunächst sehr ähnliche Punkte/Cluster zusammengefügt, sodass ein langer vertikaler Strich eine hohe Heterogenität (Unähnlichkeit) zwischen den Punkten/Clustern anzeigt, die dadurch verbunden werden. Also sollte an solchen Stellen der Algorithmus gestoppt werden, sodass sehr unähnliche Punkte/Cluster nicht zusammengefügt werden
Was sind Eigenschaften des Single-Linkage Verfahrens? (V03F30)
○ Geeignet verzweigte, gekrümmte oder lang gestreckte Cluster zu “erkennen”, da es genügt, dass ein Objekt einer Klasse nahe bei einem Objekt einer anderen Klasse liegt
○ Gruppen werden zusammengefasst, die nur durch eine “Brücke” miteinander verbunden sind, ansonsten aber deutlich separiert voneinander im Raum liegen (kontrahierend) -> Verkettungseffekt (chaining effect), der zu außerordentlich heterogenen Clustern führen kann
○ Monotonieeigenschaft (Clusterdistanz nimmt von Stufe zu Stufe zu)
Was sind Struktogramme und wie kann die Anzahl der Cluster bestimmt werden? (V03F54)
○ Koordinatensystem mit allen Clustern auf der X-Achse und dem Streuungsmaß auf der Y-Achse. Wird bei agglomerativen Verfahren von rechts nach links gelesen: Gestartet wird mit N Clustern und einer Streuung von 0. Je mehr Cluster, desto höher die Streuung zwischen den einzelnen Clustern.
○ Ein starker Anstieg der Streuung zeigt eine hohe Heterogenität innerhalb der entstandenen Cluster. Das Clustering sollte vor einem solchen Anstieg gestoppt werden, um Homogenität zu gewährleisten.
○ Zur Bestimmung der Clusterzahl bietet sich daher die Lokalisation eines steilen “Knicks” vor einem flacheren Verlauf der Kurve in dem zugehörigen Struktogramm an.
Welche Schritte werden beim K-Means-Algorithmus durchgeführt? (V03F58)
○ 1 Wähle K Objekte als initiale Clusterzentroide
○ 2 Wähle das K+1te Objekt als aktuelles Objekt
○ 3 Ordne das aktuelle Objekt dem Cluster zu, zu dessen Centroid der geringste Abstand vom Objekt besteht
○ 4 Bestimme in diesem Cluster den aktuellen Centroid
○ 5 Wähle das nächste Objekt und gehe zu Schritt 3
Was ist das Problem bei K-Means-Algorithmus? (V03F58)
Problem ist die Abhängigkeit von der Auswahl der initialen Centroide und der Reihenfolge der Werte.
Was ist bei der Auswahl von Clusterverfahren zu beachten? (V03F69)
○ Cluster haben unterschiedliche Form, Größe und Dichte
○ Nicht jedes Verfahren kann die gleichen Formen und die gleichen Varianten an Clustern entdecken (z.B. K-Means erkennt nur konvexe Cluster)
○ Dichtebasierte Verfahren sind in der Lage, Cluster unterschiedlichster Formen zu entdecken
○ Cluster können hierarchisch angeordnet sein
Wie wird beim Single-Linkage Verfahren im zwei Variablen Fall vorgegangen? (V03F26)
○ Nearest-Neighbour-Methode, da die Distanz zweier Cluster über die Distanz von zwei Objekten der Cluster bestimmt wird, die sich am nächsten sind
○ Auf jeder Stufe werden die Clusterdistanzen bestimmt
○ Es werden immer die Cluster zusammengefasst, bei denen die Distanz minimal ist
○ Zur Bestimmung der Distanzen wird eine Matrix angelegt, durch die vorhandene Symmetrie ist die untere Dreiecksmatrix ausreichend
○ 1. Schritt:
§ Aus der Ausgangssituation wird der kleinste Wert der Matrix gewählt und die beiden entsprechenden Cluster der Punkte fusioniert
§ Anschließend werden die Distanzen neu berechnet (erklärt mit Bezug auf die Tabelle):
Die Werte aus der zu entfernenden Zeile/Spalte werden mit den Werten aus der Spalte/Zeile des anderen zusammengefassten Elements verglichen. Dabei wird immer ein Element, das nicht fusioniert, betrachtet. Bsp. Wenn A und D fusionieren und C und B noch übrig sind: (DB) = 2,887 wird mit (AB) = 4,438 verglichen. Der kleinere Wert wird als neuer Wert in die nächste Tabelle übernommen. Dies wird mit allen Elementen aus der verschwindenden Spalte/Zeile gemacht. (DC) = 4,339 und (AC) = 3,084 also wird (AC) übernommen.
Der Wert der zusammengeführten Cluster wird “einfach gelöscht” also im Beispiel der Wert (AD)
○ 2. Schritt: die Ergebnistabelle aus Schritt 1 ist die Grundlage für die nächste Fusion. Es wird wieder der kleinste Wert für die Fusion ausgewählt und das Vorgehen aus Schritt 1 wiederholt
○ Die Schritte werden wiederholt, bis es nur noch ein Cluster gibt, welches alle Objekte enthält
