Robustes Clustering mittels k-Means • Aggregata

Die Texte in diesem Artikel wurden teilweise mit Hilfe künstlicher Intelligenz erarbeitet und von uns korrigiert und überarbeitet. Für die Generierung wurden folgende Dienste verwendet:

Bing DeepL Write

Einordnung

Clustering ist für viele Unternehmen relevant, da es eine wichtige Disziplin des Data Mining ist und zur Analyse von Datensätzen verwendet wird. Ziel der Clusteranalyse ist es, neue Gruppen in Daten zu identifizieren - im Gegensatz zur Klassifikation, bei der die Daten bestehenden Klassen zugeordnet werden und entsprechende Label vorhanden sind.

Der k-Means-Algorithmus ist ein Vektorquantisierungsverfahren, das auch in der Clusteranalyse verwendet wird. Im Folgenden wird dieser Algorithmus vorgestellt.

Grundlagen vom k-Means-Algorithmus

Ursprünglich aus dem Gebiet der Signalverarbeitung zielt $k$ -Means darauf ab, $n \in \mathbb{N}$ (unterschiedliche) Beobachtungen in jeweils $k \in \mathbb{N}$ Partitionen zu unterteilen, welche möglichst homogen und kompakt sein sollen. Hierbei werden sogenannte Zentroide oder Clusterschwerpunkte für die Einteilung verwendet, die den (gewichteten) Mittelpunkt einer Partition darstellen.

Im Rahmen des Unsupervised Learning werden die hier entstehenden Partitionen als Cluster bezeichnet.

Sich ergebende Partitionierungsbereiche können auch visualisiert werden, z.B. mit Hilfe eines Veronoi-Diagramms.

Die hier entstehenden neuen Gruppen in den jeweiligen Clustern können schließlich z.B. zur automatischen Klassifikation, zur Mustererkennung in der Bildverarbeitung oder zur Marktsegmentierung (oder in beliebigen anderen Verfahren, die auf derartiges Vorwissen angewiesen sind) genutzt werden. ¹ ²

Mathematisches Problem hinter k-Means

Bei der Zuordnung von $n$ Beobachtungen zu $k$ Clustern wollen wir zwei verschiedene Kriterien möglichst gut erfüllen:

Die Ähnlichkeit der Datenpunkte innerhalb der einzelnen Clustern soll möglichst hoch sein.
Die Ähnlichkeit der Datenpunkte zwischen den einzelnen Clustern soll möglichst gering sein.

Diese beiden Kriterien optimieren so, dass die Datenpunkte tatsächlich verschiedenen Partitionen zugeordnet werden. Die Grundidee hinter k-Means besteht darin, eine beliebige Beobachtung $x_i \in \mathbb{R}^d$ mit der Dimension des Datensatzes $d \in \mathbb{N}$ unter Verwendung von Zentrioden mit den Koordinaten $m_j \in \mathbb{R}^d, j \in \{ 1, \dots, k\}$ einem Cluster zuzuordnen. Um eine Zuweisung zu den Clustern zu erreichen, verwenden wir die Koordinaten der Zentroide $m_1, \dots, m_k$ und berechnen für jeden Datenpunkt $x_i$ den Zentroid mit dem minimalen Abstand:

$\min_{l \in \{ 1, \dots, k \}} {\Vert x_i - m_l \Vert}_2.$

Dabei ist ${\Vert \cdot \Vert}_2$ der euklidische Distanz.

Prinzipiell sind auch andere Abstandsmaße für die Berechnung des Abstandes zwischen den Punkten möglich, die euklidische Distanz wird jedoch am häufigsten verwendet.

Diese Schritte sind auf alle Punkte anzuwenden. Damit ergibt sich insgesamt folgendes Minimierungsproblem:

$J = \sum_{i=1}^{k} \sum_{j = 1}^{n} {\Vert x_j - m_i \Vert}_2^2.$

Dabei ist $J$ der Gesamtwert der zu minimierenden Kostenfunktion. Diese Kostenfunktion basiert auf der Methode der kleinsten Quadrate. Um diese Kostenfunktion algorithmisch möglichst einfach zu minimieren, verwenden wir folgende Schritte des k-Means-Algorithmus:

Weise jeder Observation $x_i, i \in \{ 1, \dots, n \}$ zufällig einem Cluster zu.
Für jeden der Cluster, berechne den Zentroid $m_j, j \in \{ 1, \dots, k\}$ .
Weise jede Observation dem Cluster zu, zu deren Zentroiden es am nächsten ist. Wiederhole hierbei die Schritte 2 und 3, sollten sich Änderungen in dem aktuellen Durchlauf von Schritt 3 ergeben haben.

Auf diese Weise erhält man iterativ eine Lösung, die sich mit zunehmender Anzahl der Iterationen einer besseren Lösung annähert. Sobald das Abbruchkriterium erfüllt ist, erhalten wir eine Lösung, die auf dem aktuell verwendeten Parameter $k$ basiert. Es ist zu beachten, dass es sich hierbei auch um ein lokales Optimum anstelle eines globalen Optimums handeln kann - dementsprechend sollte der Algorithmus mehrmals mit dem gleichen Wert von $k$ durchgeführt werden. Von diesen Lösungen sollte schließlich diejenige verwendet werden, die den niedrigsten Wert der Kostenfunktion erreicht. ¹ ³

Anwendungsbeispiel

Um eine einfache Clusteranalyse mit dem k-Means-Algorithmus durchführen zu können, habe ich eine Reihe von zufälligen Datenpunkten erzeugt. Um jeden dieser Datenpunkte wurden nun insgesamt 300 Datenpunkte mit geringem Abstand zufällig generiert. Das Ergebnis sieht wie folgt aus

In dieser Visualisierung sind die verschiedenen Cluster, die sich aus der Modellierung der zufällig generierten Daten ergeben, gut zu erkennen. Durch Anwendung der Clusteranalyse mit $k=3$ kann man sehr gut erkennen, dass sich die Cluster so bilden, dass jeweils eine Gruppe von Datenpunkten um die Startpunkte herum ein Cluster bildet.

Zusätzlich können wir auch die Wahl unseres $k$ ‘s ändern, z.B. auf $k=4$ . Hier wäre es z.B. möglich, dass sich in der Mitte der Ebene ein Zentroid bildet, der eventuell einige Punkte aus allen Clustern in den Cluster aufnimmt, oder eine Reihe anderer Möglichkeiten.

Die Visualisierung zeigt, dass das vorherige Cluster $3$ in jeweils zwei Gruppen aufgeteilt wurde. Es ist nicht ganz klar, warum dies der Fall ist, was ein gutes Beispiel dafür ist, dass die Lösungen des Unsupervised Learning nicht immer offensichtlich oder nachvollziehbar sein müssen. Dementsprechend sollte bei der Anwendung des k-Means-Algorithmus Hintergrundwissen in die Wahl des Parameters $k$ einfließen, um Lösungen mit geringem Realitätsbezug bereits im Vorfeld auszuschließen.

Vor- und Nachteile von k-Means

Vorteile

Der große Vorteil von k-Means in diesem Zusammenhang ist die Einfachheit des Algorithmus. Sowohl die einzelnen Schritte als auch der gesamte Algorithmus sind sowohl in der Konzeption als auch in der Implementierung nicht sehr komplex, was die Popularität des Algorithmus erklärt. Außerdem ist der Algorithmus aufgrund seiner einfachen Konzeption gut auf viele Probleme des unüberwachten Lernens anwendbar. ² ³

Nachteile

Der k-Means-Algorithmus hat eine Reihe von Nachteilen, die berücksichtigt werden müssen: ¹ ³

Es ist notwendig, die Anzahl der Cluster $k$ im Voraus zu bestimmen, um ein Clustering durchführen zu können, obwohl die optimale Anzahl der Cluster im Voraus nicht unbedingt bekannt ist.

Um experimentell eine gute Anzahl von Clustern zu finden, wird oft auf die Elbow-Methode verwiesen. Dabei handelt es sich um ein Verfahren, welches darauf basiert, dass die globale Kostenfunktion ab einer bestimmten Anzahl von Clustern einen geringeren Abfall in der Kostenfunktion aufweist als bei einer höheren Anzahl von Clustern. Da ich selbst nie mit dieser Methode gearbeitet habe, verweise ich hier auf einen guten Artikel, der dieses Thema weiter behandelt: stackabuse.com.

Manchmal ist eine Vorverarbeitung der Daten notwendig, um aussagekräftige Ergebnisse in den Daten zu finden. Es ist jedoch nicht immer im Voraus klar, ob dies notwendig ist und wie es durchgeführt werden soll.
k-Means in seiner Grundform ordnet den einzelnen Datenpunkten im Startschritt die anfänglichen Cluster zufällig zu. Dies ist oft ineffizient und führt zu einer höheren Anzahl von Iterationen, bis das Abbruchkriterium erreicht ist.

Eine Erweiterung von k-Means, die speziell diese Situation verbessert, ist k-Means-++. Diese ist in den meisten Standardimplementierungen (wie z.B. Scikit-Learn) enthalten. ⁴

Die Ergebnisse insbesondere des Unsupervised Learning entsprechen nicht immer den Erwartungen. Dies erschwert die Interpretation der Ergebnisse von Unsupervised-Learning-Algorithmen.

Anwendungsgebiete

Es gibt eine Reihe guter Beispiele, auf welche der Algorithmus angewendet werden kann: ² ⁵ ³

Kundensegmentierung: Hier unterteilen wir die Kundendaten nach Merkmalen, die sie von anderen Gruppen unterscheiden. Dies ermöglicht z.B. den gezielten Einsatz von zielgerichteter Werbung und steigert sowohl die Kosten als auch die Effizienz der Maßnahme.
Optimierung von Geodaten: Der Algorithmus kann in Kombination mit Ant Colony Optimization verwendet werden, um die optimale Anzahl von Startpunkten für Geschäfte zu finden.
Turnieranalyse: Um Turniere in beliebigen Sportarten oder eSport zu analysieren, können die entsprechenden Daten in Cluster eingeteilt und so einzeln besser analysiert werden.

Diese Beispiele sind Einzelbeispiele, in der Realität (und in den Quellen) finden sich weitere Anwendungsbeispiele.