Header
   TUM Logo Clusteranalyse Polytop
Header_Inhalt

Header Bild

K-Means

K-means ist ein Prototyp-basiertes Clustererfahren, das heißt die Cluster werden durch Prototypen (z.B. Zentrum) repräsentiert. Dabei betrachtet man normalerweise Daten aus dem n-dimensionalen kontinuierlichen Raum. Wir werden uns hier aus Anschauungsgründen auf den 2-dimensionalen Euklidischen Raum beschränken.

Idee

Die Aufgabe ist es unseren Datensatz in K Cluster zu unterteilen. Dabei gehen wir wie folgt vor: Wir wählen uns K verschiedene Punkte als Anfangszentren. Dann ordnen wir jeden Datenpunkt den ihm nähesten Zentrum zu. Dann berechnen aus den jetzigen Clustern die Zentren neu. Dann ordnen wir wieder jeden Datenpunkt den ihm nähesten Cluster zu, usw. Das wird so lange wiederholt, bis sich die Zentren nicht mehr oder nur wenig verschieben.

Algorithmus

  1. Wähle K Punkte als Anfangszentren
  2. wiederhole
  3. Ordne jeden Punkte dem Cluster zu, zu dessen Zentrum er am nähesten liegt
  4. Berechne Clusterzentren neu
  5. bis sich die Zentren nicht mehr ändern

Die größten Änderungen der Zentren erfolgen in den ersten Schleifendurchläufen. Das kann benutzt werden um schwächere Abbruchkriterien zu definieren.

Hier ein Beispiel für den K-Means-Algorithmus. Die ungefüllten Symbole stellen die Zentren dar, es sind die ersten 4 Schritte abgebildet.

PIC     PIC

PIC     PIC

Zuordnung von Punkten zu Clustern

Wir defnieren die Nähe eines Punktes zu einem Cluster (also dessen Zentrum) über den euklidischen Abstand. Man kann auch andere Abstandsmaße oder Ähnlichkeitsmaße wählen und erhält dann im Allgemeinen andere Cluster. Für einige Kombinationen von Abstandsmaßen und Typen von Zentren konvergiert K-means immer.

Neuberechnung der Zentren

Das Ziel eines Clusterverfahrens wird durch die Zielfunktion ausgedrückt. Im euklidischen Raum ist eine mögliche Zielfunktion die Summe der quadratischen Abstände zum Zentrum SSE:

 K
∑ ∑ 2
SSE = dist(ci,x)
i=1 x∈Ci

wobei Ci das i-te Cluster, ci das Zentrum des i-ten Clusters sowie dist der euklidische Abstand ist.
Wir wollen wollen unsere Zentren so wählen, dass der SSE möglichst klein wird. Das erreichen wir, indem wir unsere Zentren als arithmetisches Mittel der Clusterpunkte wählen.
Wählt man den Manhattan-Abstand als Abstandsmaß und die Summe der Abstände der Clusterpunkte zu den Zentren als Zielfunktion, so ergibt sich der Median als Minimalstelle der Zielfunktion und somit als neues Zentrum.

Wahl der Anfangszentren

Die Wahl der Anfangszentren ist der Schlüsselschritt des Algorithmus, da man hier durch eine gute Wahl viel Aufwand sparen kann. Dafür gibt es einige Strategien:

  • Führe den Algorithmus mehrmals mit verschiedenen zufälligen Anfangszentren durch und wähle dann das Ergebnis mit dem niedrigstem SSE.
  • Wende hierarchisches Clustern auf einen Teil der Daten an, extrahiere K Cluster und wähle Zentren dieser Cluster alsAnfangszentren.
  • Starte mit dem Zentrum aller Punkte. Wähle sukzessive den Punkt, der am weitesten von allen bisherigen Zentren entfernt ist als Zentrum für das nächste Cluster.
kmeans_schlechte_anfangszentren
Schlecht gewählte Anfangszentren (linkes Bild): natürliche Cluster werden nicht erkannt (mittleres Bild), bei anderer Wahl der Anfangszentren erkennt K-Means die natürlichen Cluster (rechtes Bild)

Laufzeit und Speicherbedarf

Der Speicherbedarf ist gering, da nur die Datenpunkte und die Zentren gespeichert werden: O((m + K) x n), wobei m die Anzahl der Datenpunkte und n ihre Dimension ist. Die Laufzeit ist linear in der Anzahl der Datenpunkte: O(I x K x M x N), wobei I die Anzahl der Schleifendurchläufe ist. Dabei ist I oft klein und kann normalerweise gut abgeschätzt werden.

zusätzliche Gesichtspunkte

  • Behandlung leerer Cluster: ersetze Zentrum des leeren Clusters
  • Ausreißer: haben übermäßigen Einfluss auf SSE erkenne und behandle Ausreißer vor Anwendung des Algorithmus
  • Reduzierung des SSE durch Nachbearbeitung:
    • erhöhe Clusteranzahl: teile Cluster auf oder bilde neues Cluster
    • vermindere Clusteranzahl: löse Cluster auf oder verschmelze Cluster
  • Inkrementelle Neuberechnung der Zentren: nach jeder Zuordnung eines Punktes zu einem Cluster werden Zentren neu berechnet (0 oder 2 Neuberechnungen nötig)
    • Vorteil: Keine leeren Cluster möglich
    • Probleme: Gewichtung der Datenpunkte, Abhängigkeit von der Reihenfolge der Datenpunkte
 

Vor- und Nachteile von K-means

Vorteile: K-means ist einfach, effizient und kommt mit vielen verschiedenen Datentypen zurecht.
Beispiel_K-Means

Beispiel einer optimalen Clusterung eines Datensatzes, welcher natürliche Cluster unterschiedlicher Dichten beinhaltet.
 

Nachteile: K-means hat Probleme, "natürliche" Cluster zu erkennen, die keine kugelförmige Struktur haben (mit Zulassung von Subclustern lösbar) oder die große Abweichungen in Dichte und Größe aufweisen. Desweiteren haben Ausreißer großen Einfluss auf das Ergebnis.

Beispiel

Oben: Datensatz mit natürlichen Clustern besonderer Form: K-Means erkennt diese, wenn man Subcluster und diese zusammenfasst.

Unterhalb sehen Sie eine Clusterung von K-Means eines verrauschten Datensatzes. Hier erzielt etwa DBSCAN deutlich bessere Ergebnisse.

Beispiel

Copyright 2009 - Team Clusteranalyse
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _