Was ist k-Means-Clustering?

Es handelt sich um eine der beliebtesten Clustering-Methoden, die beim maschinellen Lernen verwendet werden. Im Gegensatz zum überwachten Lernen sind die Trainingsdaten, die dieser Algorithmus verwendet, unbeschriftet, was bedeutet, dass Datenpunkte keine definierte Klassifikationsstruktur haben.

Es gibt verschiedene Arten von Clustering-Algorithmen, darunter exklusive, überlappende, hierarchische und probabilistische. Der k-Means-Clustering-Algorithmus ist ein Beispiel für eine exklusive oder „harte“ Clustering-Methode. Diese Form der Gruppierung sieht vor, dass ein Datenpunkt nur in einem Cluster vorhanden sein kann. Diese Art der Clusteranalyse wird in der Data Science häufig für die Marktsegmentierung, das Dokumenten-Clustering, die Bildsegmentierung und die Bildkomprimierung eingesetzt. Der k-Means-Algorithmus ist eine weit verbreitete Methode in der Clusteranalyse, da er effizient, effektiv und einfach ist.

k-Means ist ein iterativer, schwerpunktbasierter Clustering-Algorithmus, der einen Datensatz basierend auf dem Abstand zwischen den jeweiligen Schwerpunkten in ähnliche Gruppen unterteilt. Der Schwerpunkt oder das Clusterzentrum ist je nach den Eigenschaften der Daten entweder der Mittelwert oder der Median aller Punkte innerhalb des Clusters.

K-Means-Clustering ist ein iterativer Prozess zur Minimierung der Summe der Abstände zwischen den Datenpunkten und ihren Cluster-Mittelpunkten.

Der k-means-Clustering-Algorithmus kategorisiert Datenpunkte in Cluster, indem er ein mathematisches Distanzmaß, in der Regel das euklidische, vom Clusterzentrum verwendet. Das Ziel ist es, die Summe der Entfernungen zwischen Datenpunkten und den ihnen zugewiesenen Clustern zu minimieren. Datenpunkte, die einem Schwerpunkt am nächsten liegen, werden in derselben Kategorie zusammengefasst. Ein höherer k-Wert oder die Anzahl der Cluster bedeutet kleinere Cluster mit mehr Details, während ein niedrigerer k-Wert zu größeren Clustern mit weniger Details führt.

Der herkömmliche k-Means-Clustering-Algorithmus erfordert einige Schritte. Der erste Schritt besteht darin, k Schwerpunkte zu initialisieren, wobei k der Anzahl der für einen bestimmten Datensatz ausgewählten Cluster entspricht. Bei diesem Ansatz werden entweder Zufallsauswahl- oder anfängliche Schwerpunktstichprobenverfahren verwendet.

Der nächste Schritt umfasst einen zweistufigen iterativen Prozess, der auf dem Algorithmus für maschinelles Lernen zur Erwartungsmaximierung basiert.¹ Im Erwartungsschritt wird jeder Datenpunkt dem nächstgelegenen Schwerpunkt auf der Grundlage der Entfernung (in der Regel wieder euklidisch) zugeordnet. Der Schritt der Maximierung berechnet den Mittelwert aller Punkte für jeden Cluster und weist das Clustermittel oder den Schwerpunkt neu zu. Dieser Prozess wird wiederholt, bis die Schwerpunktpositionen konvergiert sind oder die maximale Anzahl von Iterationen erreicht wurde.

K-Means-Clustering ist einfach, reagiert aber empfindlich auf Anfangsbedingungen und Sonderfälle. Es ist wichtig, die Schwerpunktinitialisierung und die Anzahl der Cluster k zu optimieren, um die aussagekräftigsten Cluster zu erhalten. Es gibt mehrere Möglichkeiten, die Clustering-Komponenten des Algorithmus mithilfe von Bewertungsmetriken und anfänglichen Schwerpunktstichprobenverfahren zu bewerten und zu optimieren.

Qualitätscluster enthalten mindestens zwei Eigenschaften: 

1. Alle Datenpunkte innerhalb eines Clusters sollten ähnlich sein.
   
2. Cluster sollten sich voneinander unterscheiden.

Diese Eigenschaften werden durch Minimierung des Intracluster-Abstands und Maximierung des Intercluster-Abstands aller Datenpunkte in einem Datensatz erreicht. Mit anderen Worten: Je kompakter und isolierter ein Cluster von anderen Clustern ist, desto besser. Das Ziel des k-Means-Clustering-Algorithmus besteht darin, die Summe der quadratischen Fehler (SSE) zu minimieren.² Die Berechnung der SSE des quadrierten euklidischen Abstands jedes Punktes zu seinem nächsten Schwerpunkt bewertet die Qualität der Clusterzuweisungen, indem die Gesamtvariation innerhalb jedes Clusters gemessen wird.

Cluster-Evaluierungsmetriken überprüfen die Qualität und bieten verschiedene Perspektiven zur Analyse der Clustering-Ergebnisse. Dies hilft bei der Auswahl der optimalen Anzahl von Clustern und der Schwerpunktinitialisierung. Die folgenden Auswertungsmetriken sind gängige Methoden zum Messen der Intra- und Intercluster-Entfernungen beim Clustering.

Der k-means-Clustering-Algorithmus zielt darauf ab, Zentren oder Clusterzentren auszuwählen, die die Trägheit minimieren, eine Bewertungsmetrik, die misst, wie gut ein Datensatz auf der Grundlage von Entfernungsmetriken geclustert wurde. Die Trägheit wird berechnet, indem der Abstand zwischen einem Datenpunkt und seinem Schwerpunkt gemessen, der Abstand quadriert und die Quadrate für jeden Datenpunkt im Cluster addiert werden. Die Summe oder der Trägheitswert ist der Intracluster-Abstand. Je niedriger die Summe, desto besser, denn das bedeutet, dass die Datenpunkte innerhalb des Clusters kompakt oder ähnlicher sind.³

Die zweite Eigenschaft wird mit dem Dunn-Index gemessen. Der Dunn-Index stellt die Beziehung zwischen der minimalen Cluster-Distanz und der maximalen Cluster-Distanz dar. Cluster mit einem hohen Abstand zwischen den Clustern weisen auf eine bessere Qualität hin, da dies bedeutet, dass die Cluster so unterschiedlich wie möglich sind.⁴

Die Optimierung ist bei der Verwendung von k-means wichtig, um die besten Clustering-Ergebnisse zu erzielen.

Der k-Means-Algorithmus ist aufgrund seines zufälligen Initialisierungsschritts nicht deterministisch. Diese Methode impliziert, dass sich die Clusterzuweisungen unterscheiden können, wenn der Algorithmus zweimal mit identischen Daten ausgeführt wird. Um optimale Clustering-Ergebnisse zu erzielen, verbessert die richtige Auswahl der anfänglichen Schwerpunkte und der optimalen Anzahl von Clustern die Genauigkeit und Geschwindigkeit des k-Means-Algorithmus.

Jeder Cluster wird durch einen Schwerpunkt – einen Zentroid – dargestellt, einen Datenpunkt, der das Clusterzentrum repräsentiert. K-Means gruppiert ähnliche Datenpunkte in Clustern, indem der Abstand zwischen Datenpunkten in einem Cluster mit ihrem Schwerpunkt oder k-Mittelwert minimiert wird. Das Hauptziel des k-Means-Algorithmus besteht darin, die Gesamtentfernungen zwischen den Punkten und dem ihnen zugewiesenen Cluster-Schwerpunkt zu minimieren. Der Algorithmus arbeitet iterativ, und die anfängliche Partitionsauswahl kann sich stark auf die resultierenden Cluster auswirken.

Eine zufällige Initialisierung kann zu uneinheitlichen Ergebnissen führen. Es gibt Zentroid-Initialisierungsmethoden, um diese Risiken zu mindern. Eine Studie von NUS Computing erklärt und vergleicht Methoden wie das beliebte k-means++ mit der zufälligen Initialisierung.⁵

k-means++ ist ein k-Means-Algorithmus, der die Auswahl des anfänglichen Clusterschwerpunkts oder der anfänglichen Clusterschwerpunkte optimiert. Das von den Forschern Arthur und Vassilvitskii entwickelte k-means++ verbessert die Qualität der endgültigen Clusterzuweisung.⁶

Der erste Schritt zur Initialisierung mithilfe der k-means++-Methode besteht darin, einen Schwerpunkt aus dem Datensatz auszuwählen. Berechnen Sie für jeden nachfolgenden Schwerpunkt die Entfernung jedes Datenpunkts von seinem nächstgelegenen Clusterzentrum. Der nachfolgende Schwerpunkt wird unter Berücksichtigung der Wahrscheinlichkeit ausgewählt, dass ein Punkt in einer proportionalen Entfernung vom zuvor ausgewählten nächstgelegenen Schwerpunkt liegt. Der Prozess führt Iterationen aus, bis die gewählte Anzahl von Clusterzentren initialisiert wurde.

Hier ist ein Tutorial von IBM Developer, das die Methode k-means++ für die Initialisierung verwendet.

Im Idealfall iteriert der k-Means-Algorithmus, bis die optimale Anzahl von Clustern erreicht ist. Die maximale Anzahl von Iterationen ist erreicht, sobald die Schwerpunkte die Konvergenz erreicht haben.

Eine Methode, um die optimale Anzahl von Clustern zu erreichen, ist die Elbow-Methode. Die Elbow-Methode ist eine grafische Methode zur Ermittlung der optimalen Anzahl von Clustern innerhalb eines k-Means-Clustering-Algorithmus. Sie misst den euklidischen Abstand zwischen jedem Datenpunkt und seinem Clusterzentrum und wählt die Anzahl der Cluster basierend darauf, wo die Änderung der „innerhalb des Clusters liegenden Quadratsumme“ (Within Cluster Sum of Squares, WCSS) abflacht. Dieser Wert stellt die Gesamtvarianz innerhalb jedes Clusters dar, die gegen die Anzahl der Cluster aufgetragen wird.⁷

Der erste Schritt der Elbow-Methode besteht darin, das WCSS für jeden Cluster (k) zu berechnen. Dann wird der WCSS-Wert entlang der y-Achse und die Anzahl der Cluster entlang der x-Achse aufgetragen. Mit zunehmender Anzahl der Cluster sollten die Punkte auf der Grafik ein konstantes Muster bilden. Aus diesem Muster ergibt sich ein Bereich für die optimale Anzahl an Clustern.⁸ Berücksichtigen Sie bei der Entscheidung über die Anzahl der Cluster die Rechenkosten. Je höher die Anzahl der Cluster, desto mehr Rechenleistung wird benötigt, insbesondere bei großen Datensätzen.

Diese Methode ist nicht unbedingt die beste, insbesondere bei Datensätzen mit hoher Dimensionalität oder unregelmäßiger Form. Eine weitere Methode zur Auswahl der optimalen Anzahl von Clustern ist die Silhouettenanalyse.⁹

Der k-Means-Clustering-Algorithmus wird in fast allen Bereichen und Branchen verwendet. Sie wird in der Regel auf Daten des maschinellen Lernens angewendet, die wenige Dimensionen haben, numerisch sind und leicht portioniert werden können.

Forscher haben das k-Means-Clustering mit Deep-Learning-Methoden wie CNNs und RNNs integriert, um die Leistung verschiedener maschineller Lernaufgaben wie Computer Vision, NLP und viele andere Bereiche zu verbessern. Hier finden Sie eine Liste der häufigsten k-Means-Clustering-Anwendungen:

Kundensegmentierung: Die Praxis, die Kunden eines Unternehmens auf der Grundlage gemeinsamer Merkmale, die Ähnlichkeit widerspiegeln, in Gruppen einzuteilen. Diese Strategie ermöglicht es Unternehmen, bestimmte Cluster oder Kundengruppen für spezifische Werbekampagnen anzusprechen.

Dokumentenklassifizierung: Ein Verfahren zur Zuweisung verschiedener Klassen oder Kategorien zu Dokumenten. Diese Methode wird von vielen Unternehmen zur Moderation von Inhalten verwendet. Sehen Sie sich diese Watson Discover-Dokumentation an, um einen Dokumentklassifikator zu erstellen.

Bildsegmentierung: Ein Verfahren der Computervision, das ein digitales Bild in verschiedene Pixelgruppen unterteilt. Diese Forschungsarbeit untersucht, wie k-Means-Modelle zur Identifizierung von Grenzen in medizinischen Bildern eingesetzt werden.¹⁰

Empfehlungsmaschinen: Anwendungen im gesamten Internet verwenden Empfehlungsmaschinen. Hauptkomponentenanalyse und k-Means-Clustering-Techniken werden verwendet, um Produktempfehlungen für E-Commerce-Unternehmen zu erstellen.¹¹

Wenn Sie praktische Erfahrungen sammeln möchten, sehen Sie sich das Tutorial an, in dem die Grundlagen der Durchführung von k-Means-Clustering in Python mithilfe von IBM Watson Studio auf watsonx.ai erklärt werden.

Dieses Tutorial verwendet ein Modul aus der scikit-learn (sklearn)-Bibliothek, das k-means-Clustering durchführt. Das Modul enthält integrierte Optimierungstechniken, die durch seine Klassenparameter manipuliert werden. Die Klasse für das Modul sieht folgendermaßen aus:

class sklearn.cluster.KMeans(n_clusters=8, *, init='k-means++', n_init='auto', max_iter=300, tol=0.0001, verbose=0, random_state=None, copy_x=True, algorithm='lloyd')12

Zu den Parametern gehören die Anzahl der zu bildenden Cluster und die Anzahl der zu generierenden Zentroide (n_clusters). Es stehen zwei Initialisierungsmethoden zur Verfügung: k-means++ und random. Es enthält auch Attribute zum Festlegen der maximalen Anzahl von Iterationen. Jede Iteration beginnt mit der Aufteilung des Datensatzes in den Wert des Parameters n_clusters.

Diese Bibliotheken werden verwendet, um einen Testdatensatz zu generieren und eine Clusteranalyse durchzuführen:

import pandas as pd 
import sklearn
import matplotlib.pyplot as plt
import seaborn as sns
import numpy

from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.decomposition import PCA
from sklearn.preprocessing import StandardScaler

Zu den allgemeinen Vorteilen von K-Means-Clustering in Anwendungen des maschinellen Lernens gehören:

Einfach: K-Means-Clustering ist einfach zu verstehen und in die Praxis umzusetzen. Es ist die beliebteste Technik des unbeaufsichtigten maschinellen Lernens.

Schnelligkeit: k-Means-Clustering ist mit einem rechnerisch einfachen iterativen Ansatz konzipiert. Der k-Means-Clustering-Algorithmus ist schneller als das hierarchische Clustering, bei dem eine baumartige Struktur von Clustern aufgebaut wird und der paarweise Abstand zwischen allen Datenpunkten berechnet werden muss.

Skalierbar: k-Means ist auch leicht auf große Datensätze skalierbar und lässt sich auf Cluster unterschiedlicher Formen und Größen verallgemeinern, was ideal für die Clusteranalyse ist. Da der Algorithmus so recheneffizient ist, ist er im Vergleich zu anderen Methoden besser skalierbar und für große Datensätze geeignet.

Zu den häufigsten Herausforderungen im Zusammenhang mit k-Means-Clustering gehören:

Abhängigkeit von Eingabeparametern: K-Means-Clustering hängt von richtig eingestellten Eingabeparametern ab. Die Festlegung des richtigen Schwerpunkts und der richtigen Anzahl von Clustern ist für aussagekräftige Clusterergebnisse unerlässlich. Eine schlechte Zentroid-Initialisierung kann zu einer längeren Laufzeit und Cluster-Zuweisungen von geringer Qualität führen. Es wurde viel Forschung in die Verbesserung des Schwerpunktinitialisierungsverfahrens für bessere Clustering-Ergebnisse und eine schnellere Konvergenzzeit gesteckt.

Mögliche Leistungsschwäche bei bestimmten Datensätzen: k-Means funktioniert effektiv, wenn der Datensatz Cluster ähnlicher Größe enthält und es keine nennenswerten Sonderfälle oder Dichtevariationen gibt. k-Means schneidet schlecht ab, wenn der Datensatz viele Variationen enthält oder hochdimensional ist. Daten, die nicht mit bestimmten Annahmen des Datensatzes übereinstimmen, können dazu führen, dass k-Means Cluster von geringer Qualität erzeugt.¹³ Zum Beispiel könnten ungleichmäßig große Cluster die Schwerpunkte in Richtung der größeren Cluster verzerren, was zu einer Verzerrung und Fehlklassifizierung bei den kleineren Clustern führt. Um dieses Problem zu lösen, kann k-Means mithilfe von Wahrscheinlichkeitsmodellen wie dem Gaußschen Mischknoten verallgemeinert werden.

Signifikante Auswirkungen von Sonderfällen: Sonderfälle haben einen erheblichen Einfluss auf die Ergebnisse des k-Means-Clustering. Verschiedene Cluster sollten weit voneinander entfernt sein, aber nicht so weit, dass die Datenpunkte verzerrt werden. Es ist wichtig, die Annahmen der Daten zu berücksichtigen, bevor k-Means angewendet wird. K-Means ist besonders empfindlich gegenüber Sonderfällen, da es darauf abzielt, Zentroide durch Mittelwertbildung von Werten mit einem Cluster zu bestimmen. Diese Empfindlichkeit macht es anfällig für eine Überanpassung, um diese Sonderfälle einzubeziehen.