Was ist Cluster-Analyse?

Die Cluster-Analyse ist eine Datenanalysetechnik, die die natürlich vorkommenden Gruppen innerhalb eines Datensatzes untersucht, der als Cluster bezeichnet wird. Bei der Cluster-Analyse müssen Datenpunkte nicht in vordefinierte Gruppen gruppiert werden, was bedeutet, dass es sich um eine unüberwachte Lernmethode handelt. Beim unüberwachten Lernen werden Erkenntnisse aus den Daten ohne vordefinierte Bezeichnungen oder Klassen abgeleitet. Ein guter Clustering-Algorithmus gewährleistet eine hohe Ähnlichkeit innerhalb des Clusters und geringe Ähnlichkeit zwischen Clustern.

Ein Beispiel für ein Datencluster-Problem

Die Gruppierung von Einzelhandelsgeschäften anhand ihres Umsatzes ist ein einfacher Anwendungsfall der Cluster-Analyse. Angenommen, ein Café hat acht Verkaufsstellen in der Stadt. Die folgende Tabelle zeigt die Verkäufe von Cappuccino und Eiskaffee pro Tag an.

Die folgende Grafik zeigt dieselben Daten, bei denen der Verkauf von Cappuccino und Eiskaffee für jede Verkaufsstelle auf der X- bzw. Y-Achse eingetragen ist. In diesem Beispiel war es einfach, die beiden natürlich vorkommenden Cluster von Café-Verkaufsstellen in einem Diagramm darzustellen und manuell zu visualisieren, da es nur begrenzte Datenpunkte gab.

Wenn es jedoch um Tausende Datenpunkte geht, müssen Cluster-Analyse-Algorithmen verwendet werden, um die Datenpunkte in verschiedene Cluster aufzuteilen.

Was sind die Anwendungen der Cluster-Analyse?

Die Cluster-Analyse wird häufig auf zwei Arten verwendet:

• Als eigenständiges Tool zur Lösung von Problemen im Zusammenhang mit der Datengruppierung.
• Als Vorverarbeitungsschritt für verschiedene Algorithmen für maschinelles Lernen.

Cluster-Analyse als eigenständiges Tool

• Marketing: Im Marketing kann die Cluster-Analyse verwendet werden, um Kunden basierend auf ihren Kaufmustern oder Interessen in verschiedene Bereiche aufzuteilen. Diese werden als Kundenpersönlichkeiten bezeichnet. Unternehmen verwenden dann unterschiedliche Marketingstrategien für verschiedene Kunden-Cluster.
• Risikoanalyse im Finanzwesen: Finanzorganisationen verwenden verschiedene Cluster-Analyse-Algorithmen, um ihre Kunden basierend auf ihrem Bankguthaben und ihren Schulden in verschiedene Risikokategorien zu unterteilen. Bei der Genehmigung von Krediten, Versicherungen oder Kreditkarten werden diese Cluster verwendet, um die Entscheidungsfindung zu unterstützen.
• Immobilien: Infrastrukturspezialisten nutzen Clustering, um Häuser nach Größe, Standort und Marktwert zu gruppieren. Diese Informationen werden verwendet, um das Immobilienpotenzial verschiedener Stadtteile zu bewerten.

Cluster-Analyse als Vorverarbeitungsschritt für maschinelles Lernen

Die Cluster-Analyse wird häufig als Vorverarbeitungsschritt für verschiedene Algorithmen für maschinelles Lernen verwendet.

Klassifizierungsalgorithmen führen Cluster-Analysen für einen umfangreichen Datensatz durch, um Daten herauszufiltern, die zu offensichtlichen Gruppen gehören. Erweiterte Datenklassifizierungstechniken können dann für die reduzierten, nicht offensichtlichen Datenpunkte verwendet werden. Da der Datensatz kleiner wird, wird die Rechenzeit stark reduziert. Dieselbe Methode kann in umgekehrter Weise verwendet werden, wobei ein Cluster-Analyse-Algorithmus verwendet wird, um sich auf das Wesentliche zu konzentrieren oder Ausreißerdaten zu identifizieren.

Bevor Sie einen Algorithmus für überwachtes Lernen ausführen, können Sie zunächst eine Cluster-Analyse der Eingabedaten durchführen, um die natürlichen Cluster in den Daten zu bestimmen.

Was sind die wichtigsten Cluster-Analyse-Algorithmen?

Algorithmen zur Cluster-Analyse gehören häufig zu den folgenden Kategorien:

• Partitionsbasierte Algorithmen
• Hierarchische Algorithmen
• Dichtebasierte Algorithmen
• Rasterbasierte Algorithmen
• Modellbasierte Algorithmen
• Einschränkungsbasiert Algorithmen
• Algorithmen zur Ausreißeranalyse

Jeder Algorithmus ist an sich komplex und kann für einige Analysen geeignet sein und nicht für andere.

Partitionsbasierte Algorithmen für die Cluster-Analyse

Bei dieser Methode beginnt ein Algorithmus mit mehreren Anfangsclustern. Dann verlagert er die Datenpunkte iterativ auf verschiedene Cluster, bis eine optimale Partition erreicht ist. Der K-Means-Clustering-Algorithmus ist einer der beliebtesten Clustering-Algorithmen.

Ein nachfolgendes Beispiel für K-Means-Clustering zeigt, wie das funktioniert.

Schritt 1: Entscheiden Sie sich für Cluster

Entscheiden Sie sich für die Anzahl der Cluster, „K“ für den Algorithmus, z. B. K = 3. Der Algorithmus partitioniert die obigen zwölf Datenpunkte in 3 Cluster. Die Zahl K kann einen beliebigen Wert haben. Abhängig davon kann die Richtigkeit des Clusterings variieren. Es gibt auch algorithmische Methoden, mit denen der optimale Wert für K bestimmt werden kann.

Schritt 2: Wählen Sie Datenpunkte aus

Da K = 3 ist, nehmen Sie drei beliebige Datenpunkte, um anzufangen. In diesem Beispiel werden die Punkte C, D und E zum Anfang ausgewählt. Beachten Sie, dass der K-Means-Algorithmus jeden Punkt als anfänglichen Mittelwert verwenden kann.

Schritt 3: Berechnen Sie die Entfernungen

Berechnen Sie die Entfernung von jedem Punkt im Datensatz zu jedem anfänglichen Cluster-Mittelwert. Drei Cluster-Mittelwerte C, D und E wurden zufällig ausgewählt. Berechnen Sie für jeden Datenpunkt in der Stichprobe die Entfernung von diesen drei Mittelwerten. Der euklidische Abstand zwischen zwei Punkten (X1, Y1) und (X2, Y2) wird wie folgt verwendet:

Nach Schritt 3 würde eine Tabelle den Abstand jedes Datenpunkts von den Anfangsmitteln C, D und E anzeigen.

Ein Datenpunkt wird einem Cluster basierend auf seiner Mindestentfernung hinzugefügt. Beispielsweise hat Punkt A einen Mindestabstand von einem anfänglichen Mittelwert C. Das bedeutet, dass A im Cluster mit dem Mittelwert C enthalten ist. Nach dem ersten Schritt werden die Cluster erhalten.

Schritt 4: Wiederholung — Berechnung neuer Mittelwerte

Jetzt sind die ersten Cluster leicht zu erkennen. Der nächste Schritt besteht darin, drei neue Cluster-Mittelwerte zu berechnen. Dazu wird jeder Datenpunkt in einem bestimmten Cluster genommen und ein Mittelwert berechnet.

Neuer Cluster-Mittelwert für den Cluster „C“ = (5+2+6+1+4+3+6/7, 21+11+22+10+23+14+12/7) = (3,85, 16,14). Nennen wir diesen Punkt X.

Neuer Cluster-Mittelwert für den Cluster „D“ = (1+2+5/3, 6+8+4/3) = (2,66, 6). Nennen wir diesen Punkt Y.

Neuer Cluster-Mittelwert für den Cluster „E“ = (4+5/2, 10+11/2) = (4,5, 10,5). Nennen wir diesen Punkt Z.

Schritt 5: Wiederholung — Berechnet den Abstand jedes Datenpunkts von den neuen Mittelwerten

Wiederholen Sie Schritt 3, um den Abstand aller Datenpunkte von den neu berechneten Cluster-Mittelwerten X, Y und Z zu ermitteln. In dieser neuen Iteration ist leicht zu erkennen, dass sich der Mindestabstand der Datenpunkte C, D, I und L geändert hat. Sie gehören jetzt zu einem neuen Cluster, wie nachfolgend angezeigt wird.

Dann muss die K-Means-Iteration fortgesetzt werden, da einige der Datenpunkte ihre Cluster geändert haben.

Schritt 6: Wiederholung — Berechnung neuer Mittelwerte und neuer Cluster

Da die Datenpunkte C, D, I, L ihre Cluster geändert haben, müssen neue Cluster-Mittelwerte wie in Schritt 4 berechnet werden. Dazu wird jeder Datenpunkt in einem bestimmten Cluster verwendet und ein Durchschnitt berechnet. Dann wird wie in Schritt 5 die Entfernung von jedem Datenpunkt zum neuen Cluster-Mittelwert berechnet. Basierend auf der Entfernung werden die Datenpunkte einem Cluster zugewiesen, zu dem eine Mindestentfernung besteht.

Wann ist der K-Means-Algorithmus fertig?

K-Means ist ein iterativer Partitionsalgorithmus:

• Entscheiden Sie zunächst für die Anzahl der Cluster (K). Im obigen Beispiel ist K = 3.
• Weisen Sie zufällig die Anzahl K von Datenpunkten als anfänglichen Cluster-Mittelwert zu.
• Wiederholen Sie die folgenden Schritte, bis kein Datenpunkt seinen Cluster ändert.
• Berechnet die mittlere Entfernung vom Datenpunkt zum Cluster-Mittelwert.
• Weisen Sie dem Cluster mit der niedrigsten Entfernung einen Datenpunkt zu.
• Überprüfen Sie, ob ein Datenpunkt seinen Cluster geändert hat.

Wenn in einer neuen Iteration jeder Datenpunkt in seinem vorherigen Cluster verbleibt, wird der K-Means-Algorithmus beendet. Das bedeutet, dass sich eine lokal optimale Lösung ergeben hat.

Partitionsbasierter K-Medoids Clustering-Algorithmus

Der K-Medoids-Algorithmus ist ein weiterer partitionsbasierter Clustering-Algorithmus. Die K-Medoid-Algorithmen wählen Medoide als repräsentatives Objekt eines Clusters. Der K-Medoids-Algorithmus versucht, solche Datenpunkte zu finden, die eine minimale Unähnlichkeit zu jedem anderen Datenpunkt in einem bestimmten Cluster aufweisen. Bis die Unähnlichkeit minimiert ist, partitioniert der K-Medoid-Algorithmus den Datensatz iterativ. Der K-Means-Algorithmus verwendet häufig die quadrierte Fehlerentfernung (euklidische Entfernung), und K-Medoid-Algorithmen verwenden häufig die Absolutwert-Entfernung wie die Manhattan-Entfernung, um die Unähnlichkeit zwischen zwei Datenpunkten zu messen.

Eine Standardimplementierung des K-Medoid-Algorithmus ist der Partition Around Medoids (PAM)-Algorithmus. Hier sind die grundlegenden Schritte des PAM-Algorithmus.

1. Wählen Sie einen Wert für K, wobei K die Anzahl der Cluster ist, in die die Datenpunkte aufgeteilt werden.
2. Wählen Sie K-Anzahl der Datenpunkte zufällig als Medoide.
3. Messen Sie für jeden Datenpunkt (Xi, Yi) im Datensatz die Unähnlichkeit zwischen dem Punkt und den oben ausgewählten Medoiden. Ein häufig verwendetes Maß für Unähnlichkeit ist die Manhattan-Distanz:
   • | Xi — Ci| + | Yi - Cj|, wobei (Ci, Cj) für ein Medoid steht.
4. Jeder Datenpunkt (Xi, Yi) wird einem Cluster zugewiesen, in dem die Unähnlichkeit minimal ist.
5. Berechnen Sie für jeden der oben genannten Cluster die Gesamtkosten — die Summe der Unähnlichkeiten der einzelnen Datenpunkte in diesem Cluster.
6. Wählen Sie nun nach dem Zufallsprinzip einen Nicht-Medoid-Punkt als neuen Medoid aus und wiederholen Sie die Schritte 3 bis 5.
7. Beenden Sie den Vorgang, wenn es keine Änderungen in den Clustern gibt.

Vergleich von K-Means- und K-Medoid-Algorithmen

Obwohl der K-Means-Algorithmus einfach ist, liefert er keine guten Ergebnisse, wenn die Daten viel Rauschen und Ausreißer aufweisen. Die K-Medoid-Methode ist in solchen Fällen robuster. Die K-Medoid-Algorithmen wie PAM sind jedoch nur nützlich, wenn der Datensatz klein ist. Wenn die Datensatzgröße zunimmt, erhöht sich die Rechenzeit für den K-Medoid-Algorithmus exponentiell.

Divisiver Algorithmen

Wie der Name schon sagt, weisen divisive Algorithmen am Anfang alle Datenpunkte einem einzigen Cluster zu. Anschließend wird der Cluster in Cluster unterteilt, die sich am wenigsten ähneln. Der Algorithmus teilt diese Cluster dann rekursiv auf, bis eine optimale Lösung erreicht ist. Divisive Algorithmen werden auch als Top-Down-Clustering-Verfahren bezeichnet.

Agglomerative Algorithmen

Diese Algorithmen beginnen damit, dass jeder Datenpunkt einem anderen Cluster zugewiesen wird. Dann verbindet der Algorithmus rekursiv die ähnlichsten Cluster, bis eine optimale Lösung erreicht ist. Agglomerative Algorithmen werden auch als Bottom-up-Clustering-Verfahren bezeichnet.

Beispiel für einen agglomerativen Clustering-Algorithmus

Nachfolgend finden Sie eine Entfernungsmatrix für fünf Datenpunkte. Die Entfernung zwischen den Punkten kann basierend auf der euklidischen Entfernung oder der Manhattan-Entfernung oder einer anderen Entfernungsformel berechnet werden. Die Abstandsmatrix ist immer eine symmetrische Matrix, da der Abstand zwischen den Punkten X und Y der gleiche ist wie der zwischen Y und X. Basierend auf dieser Abstandsmatrix, ein Beispiel für einen agglomerativen (Bottom-up-) Clustering-Algorithmus.

Schritt 1: Suchen Sie in der Entfernungsmatrix die beiden Punkte, deren Entfernung am kleinsten ist. Im obigen Beispiel sind es die Punkte 3 und 5. Der Abstand zwischen ihnen beträgt 2. Ordnen Sie sie in einen einzigen Cluster ein.

Schritt 2: Entfernen Sie die Punkte 3 und 5 und ersetzen Sie sie durch einen Cluster „35“ und erstellen Sie eine neue Entfernungsmatrix. Dazu muss der Abstand zwischen allen Datenpunkten und dem Cluster „35“ berechnet werden. Es gibt verschiedene Möglichkeiten, diese Entfernung zu bestimmen.

In diesem Beispiel wurde die folgende Methode verwendet, um die Entfernung zu messen:

Abstand von Punkt X vom Cluster „35“ = Minimum (Abstand (X, 3), Entfernung (X, 5)). Die aktualisierte Entfernungsmatrix, die auf dieser Methode basiert, lautet:

Schritt 3: Wiederholen Sie Schritt 2, bis alle Datenpunkte zu einem Cluster zusammengefasst wurden. Im aktuellen Beispiel sind sechs Iterationen erforderlich. Das folgende Diagramm zeigt die Bildung von Clustern an. Diese Art der Darstellung wird als Dendrogramm bezeichnet. In dieser Darstellung stellt die Y-Achse den Abstand zwischen zwei Datenpunkten dar. Der Abstand zwischen den Punkten 3 und 5 beträgt beispielsweise 2.

Schritt 4: Sobald alle Datenpunkte wie oben gezeigt einen Cluster bilden, sind, entscheiden Sie, wie viele Cluster beibehalten werden müssen. Es ist eine schwierige Entscheidung, da jeder hierarchische Clustering-Algorithmus letztendlich einen einzigen Cluster ergibt. Es stehen verschiedene Methoden zur Verfügung, um die optimale Anzahl von Clustern zu bestimmen, nachdem ein hierarchischer Clustering-Algorithmus die Daten partitioniert hat.

Dichtebasierte Clustering-Algorithmen

Diese Algorithmen beruhen auf dem Gedanken, dass Cluster immer dichter sind als ihr umgebender Datenraum. Dichtebasierte Algorithmen beginnen mit einem einzelnen Datenpunkt und untersuchen die Datenpunkte in seiner Nachbarschaft. Die Punkte in der Nachbarschaft des Anfangspunkts sind in einem einzigen Cluster enthalten. Die Definition von Nachbarschaft hängt von der Implementierung des Algorithmus ab. Dichtebasiertes räumliches Clustering von Anwendungen mit Rauschen (DBSCAN) ist ein beliebter Clustering-Algorithmus in dieser Kategorie.

Rasterbasierte Clustering-Algorithmen

Rasterbasierte Clustering-Algorithmen ähneln den dichtebasierten. Der Datenraum ist in mehrere kleinere Bereiche unterteilt, die als Raster bezeichnet werden. Jeder Datenpunkt ist einer bestimmten Rasterzelle zugewiesen. Der Algorithmus berechnet dann die Dichte jedes Rasters. Die Raster, deren Dichte unter einem Schwellenwert liegt, werden beseitigt. Anschließend bildet der Algorithmus Cluster aus benachbarten Gruppen dichter Raster. Statistisches Informationsgitter (STING) und Clustering in Quest (CLIQUE) sind zwei beliebte Raster-basierte Algorithmen.

Neben den oben diskutierten Algorithmen umfasst die Cluster-Analyse eine Gruppe von modellbasierten Clustering-, Einschränkungsbasierten Clustering- und Ausreißer-analyse-Algorithmen.

Vor- und Nachteile von Clustering-Analyse-Algorithmen