- K-means
-
Der k-Means-Algorithmus ist ein Verfahren, das in einer Menge von Objekten ähnliche Objekte zu Gruppen zusammenfasst. Der Algorithmus ist eine Inkarnation des EM-Algorithmus und zeichnet sich durch seine Einfachheit aus und wurde intensiv erforscht.
Die Ähnlichkeit der Objekte wird durch eine Abstandsfunktion modelliert.
Algorithmus
Vor der Ausführung des k-Means-Algorithmus muss die Anzahl k der zu ermittelnden Gruppen festgelegt werden. Des Weiteren wird ein Hilfsalgorithmus benötigt, der zu mehreren Objekten ein Zentrum ermittelt. Der k-Means-Algorithmus selbst besteht aus fünf Schritten.
- Bestimmung von k Clusterzentren.
- Jedes Objekt wird demjenigen Cluster zugeordnet, dessen Zentrum ihm am nächsten liegt.
- Für jedes Cluster wird das Zentrum neu berechnet.
- Basierend auf den neu berechneten Zentren werden die Objekte wieder wie in Schritt 2 auf die Cluster verteilt.
- Wurde bei der Neuverteilung mindestens ein Objekt einem anderen Cluster zugeordnet, dann wiederhole den Algorithmus beginnend mit Schritt 3.
Beispiel
Die folgenden Bilder zeigen einen Durchlauf des k-Means-Algorithmus zur Bestimmung von drei Gruppen.
Drei Clusterzentren wurden zufällig gewählt. 
Die durch Rechtecke repräsentierten Objekte (Datenpunkte) werden jeweils dem Cluster mit dem nächsten Clusterzentrum zugeordnet. 
Die Zentren (jeweilige Schwerpunkte) der Cluster werden neu berechnet. 
Die Objekte werden neu verteilt und erneut dem Cluster zugewiesen, dessen Zentrum am nächsten ist. Siehe auch
- Global K-means-Algorithmus
- Fast Global K-Means-Algorithmus
- Clustering
Wikimedia Foundation.
