K-Means-ClusteringEs handelt sich um ein Vektorquantisierungsverfahren, das früher in der Signalverarbeitung eingesetzt wurde. Derzeit wird es hauptsächlich als Clusteranalysemethode im Bereich Data Mining verwendet.

Der Zweck der K-Means-Clusterbildung besteht darin, n Punkte in k Cluster aufzuteilen, sodass jeder Punkt zu dem Cluster gehört, der dem nächsten Mittelwert entspricht, und diesen als Clusterkriterium zu verwenden. Diese Art von Problem kann als das Problem der Aufteilung eines Datenraums in Voronoi-Zellen verstanden werden, das hauptsächlich zum Clustern zweidimensionaler Datenpunkte verwendet wird.

Hauptschritte

1. Wählen Sie k Punkte als anfängliche Massenpunkte aus.

2. Wiederholen Sie die Schritte:

• Ordnen Sie jedem Punkt den nächstgelegenen Schwerpunkt zu, um k Cluster zu bilden.
• Berechnen Sie den Schwerpunkt jedes Clusters neu.

3. Bis sich der Cluster nicht mehr ändert oder die maximale Anzahl an Iterationen erreicht ist.

Distanzmetriken und Zielfunktionen

Betrachten Sie die euklidische Distanzfunktion und verwenden Sie die Summe der quadrierten Fehler als Zielfunktion der Clusterbildung.

Für und Wider

Vorteile: Der K-Means-Algorithmus ist ein klassischer Algorithmus für Clustering-Probleme. Der Algorithmus ist einfach und schnell und weist bei großen Datenmengen eine relativ hohe Algorithmuseffizienz auf. Seine hohe Skalierbarkeit wird normalerweise als lokaler optimaler Endalgorithmus verwendet. Der Clustereffekt ist besser, wenn die Cluster dicht, rund und verklumpt sind und die Unterschiede zwischen den Clustern deutlich sind.

Nachteile: Der Benutzer muss die Anzahl k der zu generierenden Cluster im Voraus angeben; Der Algorithmus reagiert empfindlich auf den Anfangswert, und unterschiedliche Anfangswerte führen zu unterschiedlichen Clusterergebnissen. Es reagiert empfindlich auf Rauschdaten und isolierte Punktdaten und eine kleine Datenmenge hat einen enormen Einfluss auf den Durchschnittswert.

Verweise

【1】k-Means-Algorithmus – Wikipedia

【2】http://hometown.group/wp-content/uploads/2018/07/%E8%81%9A%E7%B1%BB.pdf