AI-United » Allgemein » Die 5 Clusterbildung-Algorithmen, die jeder Datenwissenschaftler kennen muss

Die 5 Clusterbildung-Algorithmen, die jeder Datenwissenschaftler kennen muss

5 Clusterbildung-Algorithmen

Clusterbildung ist eine Machine Learning-Technik, bei der Datenpunkte gruppiert werden. Mit einer Reihe von Datenpunkten kann man einen Clusterbildung-Algorithmus verwenden, um jeden Datenpunkt in eine bestimmte Gruppe zu klassifizieren. Theoretisch sollten Datenpunkte, die sich in derselben Gruppe befinden, ähnliche Eigenschaften und / oder Merkmale aufweisen, während Datenpunkte in verschiedenen Gruppen sehr unterschiedliche Eigenschaften und / oder Merkmale aufweisen sollten. Clusterbildung ist eine Methode des unbeaufsichtigten Lernens und eine verbreitete Technik zur statistischen Datenanalyse, die in vielen Bereichen eingesetzt wird.

In der Datenwissenschaft kann man Clusterbildung-Analyse verwenden, um einige wertvolle Erkenntnisse aus unseren Daten zu gewinnen, indem man sieht, in welche Gruppen die Datenpunkte fallen, wenn wir einen Clusterbildung-Algorithmus anwenden. Heute werden wir uns fünf beliebte Clusterbildung-Algorithmen ansehen, die jeder Datenwissenschaftler kennen muss sowie ihre Vor- und Nachteile!

K-Means Clusterbildung

K-Means ist wahrscheinlich der bekannteste Clusterbildung-Algorithmus. Es wird in vielen einführenden Kursen in der Datawissenschaft und Maschinellem Lernen unterrichtet. Es ist leicht zu verstehen und in Code zu implementieren! Schauen Sie sich die untere Grafik an.

K-Means Clustering
  1. Zu Beginn wählt man zunächst eine Anzahl von Klassen / Gruppen aus, die verwendet werden soll, und initialisiert man zufällig ihre jeweiligen Mittelpunkte. Um die Anzahl der zu verwendenden Klassen herauszufinden, ist es ratsam, sich die Daten kurz anzusehen und zu versuchen, verschiedene Gruppen zu identifizieren. Die Mittelpunkte sind Vektoren mit der gleichen Länge wie jeder Datenpunktvektor und es sind die „X‘s“ in der obigen Grafik.
  2. Jeder Datenpunkt wird klassifiziert, indem der Abstand zwischen diesem Punkt und jedem Gruppenzentrum berechnet wird und der Punkt dann in der Gruppe klassifiziert wird, deren Mittelpunkt am nächsten liegt.
  3. Basierend auf diesen klassifizierten Punkten berechnet man das Gruppenzentrum neu, indem man den Mittelwert aller Vektoren in der Gruppe verwendet.
  4. Man wiederholt diese Schritte für eine bestimmte Anzahl von Iterationen oder bis die Gruppenzentren zwischen den Iterationen nicht viel geändert werden. Man kann die Gruppenzentren auch mehrmals zufällig initialisieren und dann den Lauf auswählen, der so aussieht, als würde er die besten Ergebnisse liefern.

K-Means hat den Vorteil, dass es ziemlich schnell ist, da man wirklich nur die Entfernungen zwischen Punkten und den Gruppenzentren berechnet; sehr wenige Berechnungen! Es hat somit eine lineare Komplexität O (n).

Auf der anderen Seite hat K-Means einige Nachteile. Zuerst muss man auswählen, wie viele Gruppen / Klassen vorhanden sind. Dies ist nicht immer trivial und im Idealfall eben mit einem Clusterbildung-Algorithmus, mit dem man herausfinden möchte, da es darauf ankommt, aus den Daten Insights zu gewinnen. K-Means beginnt auch mit einer zufälligen Auswahl von Clusterbildungszentren und kann daher zu unterschiedlichen Clusterbildung-Ergebnissen bei verschiedenen Läufen des Algorithmus führen. Daher sind die Ergebnisse möglicherweise nicht wiederholbar und weisen keine Konsistenz auf. Andere Clusterbildungsmethoden sind konsistenter.

K-Medians ist ein weiterer Clusterbildung-Algorithmus, der sich auf K-Means bezieht, mit der Ausnahme, dass die Gruppenmittelpunkte nicht mit dem Mittelwert neu berechnet werden, sondern mit dem Medianvektor der Gruppe. Diese Methode ist weniger anfällig für Ausreißer (wegen der Verwendung des Median), ist jedoch bei größeren Datensätzen viel langsamer, da bei der Berechnung des Median-Vektors bei jeder Iteration eine Sortierung erforderlich ist.

Mean-Shift Clusterbildung

Mean-Shift Clusterbildung ist ein Sliding-Window-based Algorithmus, der versucht, dichte Bereiche von Datenpunkten zu finden. Es ist ein auf Zentroid basierender Algorithmus, das bedeutet, dass das Ziel darin besteht, die Mittelpunkte jeder Gruppe / Klasse zu ermitteln. Dabei werden die Kandidaten für die Mittelpunkte so aktualisiert, dass sie den Mittelwert der Punkte innerhalb des sliding-window darstellen. Dabei werden die Kandidaten für Mittelpunkt auf den Mittelwert der Punkte in Sliding-Window aktualisiert. Diese Kandidaten Windows werden dann in einer Nachverarbeitungsphase gefiltert, um nahezu doppelte Einträge zu eliminieren, und bilden den endgültigen Satz von Mittelpunkten und ihren entsprechenden Gruppen. Auf der unteren Grafik zu sehen.

Mean-Shift Clustering for a single sliding window
  1. Um die Mean-Shift zu erklären, betrachtet man eine Reihe von Punkten im zweidimensionalen Raum wie in der obigen Abbildung. Man beginnt mit einem kreisförmigen sliding-window, das an einem Punkt C (zufällig ausgewählt) zentriert ist und den Radius r als Kern hat. Die Mean-Shift ist ein Hügelkletteralgorithmus, bei dem dieser Kern bei jedem Schritt bis zur Konvergenz iterativ in einen Bereich mit höherer Dichte verschoben wird.
  2. Bei jeder Iteration wird Sliding-Window in Richtung höherer Dichte durch das Verschieben des Mittelpunkts zum Mittelwert der Punkte innerhalb des Windows (daher der Name) verschoben. Die Dichte innerhalb des Sliding-Window ist proportional zur Anzahl der Punkte darin. Durch Verschieben zum Mittelwert der Punkte im Window wird es natürlich allmählich zu Bereichen höherer Punktdichte verschoben. Schauen Sie sich die oberen Grafik an. Man bewegt den Kreis weiter, bis die Dichte nicht mehr erhöht wird (d. h. die Anzahl der Punkte in Window).
  3. Man setzt das Verschieben des Sliding-Window gemäß dem Mittelwert, fort, bis es keine Richtung gibt, in der, die Verschiebung mehr Punkte innerhalb des Kerns aufnehmen kann.
  4. Man setzt das Verschieben des Sliding-Window gemäß dem Mittelwert, fort, bis es keine Richtung gibt, in der, die Verschiebung mehr Punkte innerhalb des Kerns aufnehmen kann.

Nachfolgend ist eine Illustration des gesamten Prozesses von Anfang bis zum Ende mit allen gleitenden Fenstern dargestellt. Jeder schwarze Punkt stellt den Schwerpunkt eines gleitenden Fensters dar und jeder graue Punkt ist ein Datenpunkt.

The entire process of Mean-Shift Clustering

Im Gegensatz zum K-Means-Clustering muss die Anzahl der Cluster nicht ausgewählt werden, da die Mittelwertverschiebung dies automatisch erkennt. Das ist ein enormer Vorteil. Die Tatsache, dass sich die Cluster-Zentren in Richtung der Punkte maximaler Dichte konvergieren, ist ebenfalls wünschenswert, da sie intuitiv zu verstehen ist und im natürlich datengetriebenen Sinne gut passt. Der Nachteil ist, dass die Auswahl der Fenstergröße / des Radius „r“ nicht trivial sein kann.

Dichte-basierte räumliche Clusterbildung von Anwendungen mit Rauschen (DBSCAN)

DBSCAN ist ein auf Dichte basierter Clusterbildung-Algorithmus, der der Mean-Shift ähnlich ist, jedoch mit einigen bemerkenswerten Vorteilen. Schauen Sie sich die untenstehende Grafik an und lassen Sie uns starten!

DBSCAN Smiley Face Clustering
  1. DBSCAN beginnt mit einem beliebigen Startdatenpunkt, der nicht untersucht wurde. Die Nachbarschaft dieses Punktes wird unter Verwendung einer Entfernung epsilon ε; extrahiert (alle Punkte, die innerhalb der ε  im Abstand liegen, sind Nachbarschaftspunkte).
  2. Wenn es eine ausreichende Anzahl von Punkten (gemäß minPoints) innerhalb dieser Nachbarschaft gibt, dann beginnt der Clusterbildung-Prozess, und der aktuelle Datenpunkt wird der erste Punkt in dem neuen Cluster. Andernfalls wird der Punkt als Rauschen bezeichnet (dieser rauschende Punkt kann später Teil des Clusters werden). In beiden Fällen wird dieser Punkt als „untersucht“ markiert.
  3. Für diesen ersten Punkt des neuen Clusters werden auch die Punkte in seiner ε-Abstandsnachbarschaft Teil des gleichen Clusters. Diese Prozedur, bei der alle Punkte in der ε-Nachbarschaft zu demselben Cluster gehören, wird dann für alle neuen Punkte wiederholt, die der Clustergruppe gerade hinzugefügt wurden.
  4. Dieser Prozess, der Schritte 2 und 3 wird wiederholt, bis alle Punkte im Cluster festgelegt sind. D. h. alle Punkte innerhalb der ε Nachbarschaft des Clusters untersucht und etikettiert wurden.
  5. Wenn wir mit dem aktuellen Cluster fertig sind, wird ein neuer, nicht untersuchter Punkt aufgerufen und verarbeitet, wodurch ein weiteres Cluster oder Rauschen entdeckt wird. Dieser Vorgang wird wiederholt, bis alle Punkte als untersucht markiert sind. Da am Ende alle Punkte untersucht wurden, wurde jeder Punkt als entweder zu einem Cluster gehörend oder als Rauschen gekennzeichnet.

DBSCAN bietet einige große Vorteile gegenüber anderen Clusterbildung-Algorithmen. Erstens erfordert es überhaupt keine bestimmte Anzahl von Clustern. Sie identifiziert Ausreißer auch als Rauschen, anders als Mean-Shift, das sie einfach in einen Cluster wirft, selbst wenn der Datenpunkt sehr unterschiedlich ist. Außerdem kann es beliebig große und beliebig geformte Cluster gut finden.

Der Hauptnachteil von DBSCAN ist, dass es nicht so gut funktioniert wie andere, wenn die Cluster von unterschiedlicher Dichte sind. Dies liegt daran, dass die Einstellung der Entfernungsschwelle ε und der minPoints zum Identifizieren der Nachbarschaftspunkte von Cluster zu Cluster variiert, wenn die Dichte variiert. Dieser Nachteil tritt auch bei sehr hochdimensionalen Daten auf, da die Entfernungsschwelle wiederum schwierig zu schätzen ist.

Erwartungs-Maximierungs- (EM) -Clusterbildung unter Verwendung von Gaußsche Mischungsmodelle (GMM)

Einer der Hauptnachteile von K-Means ist die naive Verwendung des Mittelwerts für das Clusterzentrum. Man kann sehen, warum dies nicht die beste Vorgehensweise ist, wenn man das Bild unten betrachtet. Auf der linken Seite scheint es für das menschliche Auge ziemlich offensichtlich zu sein, dass es zwei kreisförmige Cluster mit unterschiedlichen Radien gibt, die im gleichen Mittelwert zentriert sind. K-Means kann damit nicht umgehen, da die Mittelwerte der Cluster sehr nahe beieinanderliegen. K-Means schlägt auch in Fällen fehl, in denen die Cluster nicht kreisförmig sind, auch wenn der Mittelwert als Clusterzentrum verwendet wird.

Two failure cases for K-Means

Gaußsche Mischungsmodelle (GMMs) gibt uns mehr Flexibilität als K-Means. Bei GMMs gehen wir davon aus, dass die Datenpunkte Gaußisch verteilt sind. Dies ist eine weniger einschränkende Annahme als die Angabe, dass sie kreisförmig sind, indem der Mittelwert verwendet wird. Auf diese Weise haben wir zwei Parameter, um die Form der Cluster zu beschreiben: den Mittelwert und die Standardabweichung! In einem zweidimensionalen Beispiel bedeutet dies, dass die Cluster jede beliebige elliptische Form annehmen können (da man sowohl in x- als auch in y-Richtung eine Standardabweichung hat). Somit ist jede Gaußsche Verteilung einem einzelnen Cluster zugeordnet.

Um die Parameter des Gaussian für jeden Cluster (z. B. den Mittelwert und die Standardabweichung) zu finden, verwenden wir einen Optimierungsalgorithmus namens Erwartungs-Maximierung (EM). Werfen Sie einen Blick auf der untenstehenden Grafik, die als Illustration der Gaußkurven zu den Clustern angebracht ist. Dann kann man mit dem Vorgang des Erwartungs-Maximierungs-Clusters mit GMMs fortfahren.

EM Clustering using GMMs
  1. Man beginnt mit der Auswahl der Anzahl von Clustern (wie bei K-Means) und dann wird der Gaußsche Verteilungsparameter jedem Cluster zufällig initialisiert. Man kann versuchen, einen guten Schätzwert für die Anfangsparameter zu geben, indem man auch die Daten kurz betrachtet. Beachten Sie, dass dies, wie auf der oberen Grafik gezeigt ist, nicht zu 100% notwendig ist, da die   Gaußschen Verteilungsparameter, zwar als sehr dürftig beginnen, werden aber schnell optimiert.
  2. In Anbetracht dieser Gaußschen Verteilungen für jeden Cluster, berechnet man die Wahrscheinlichkeit, dass jeder Datenpunkt zu einem bestimmten Cluster gehört. Je näher ein Punkt an der Mitte des Gaußschen Zentrums liegt, desto wahrscheinlicher gehört er zu diesem Cluster. Dies sollte intuitiv sinnvoll sein, da man bei einer Gaußschen Verteilung davon ausgeht, dass die meisten Daten näher am Zentrum des Clusters liegen.
  3. Basierend auf diesen Wahrscheinlichkeiten berechnet man einen neuen Parametersatz für die Gaußschen Verteilungen, sodass man die Wahrscheinlichkeiten von Datenpunkten innerhalb der Cluster maximiert. Man berechnet diese neuen Parameter mit einer gewichteten Summe der Datenpunktpositionen, wobei die Gewichte die Wahrscheinlichkeiten des Datenpunkts sind, der zu diesem bestimmten Cluster gehört. Um dies visuell zu erläutern, kann man einen Blick auf die obige Grafik werfen, insbesondere auf den gelben Cluster. Die Verteilung beginnt zufällig bei der ersten Iteration, aber man kann sehen, dass die meisten gelben Punkte rechts von dieser Verteilung liegen. Wenn man eine mit den Wahrscheinlichkeiten gewichtete Summe berechnet, obwohl sich einige Punkte in der Nähe des Zentrums befinden, befinden sich die meisten auf der rechten Seite.
  4. Die Schritte 2 und 3 werden bis zur Konvergenz iterativ wiederholt, wobei sich die Verteilungen von Iteration zu Iteration nicht viel ändern.

Die Verwendung von GMMs hat zwei entscheidende Vorteile. Erstens sind GMMs hinsichtlich der Cluster-Kovarianz viel flexibler als K-Means; Aufgrund des Standardabweichungsparameters können die Cluster jede Ellipsenform annehmen, anstatt auf Kreise beschränkt zu sein. K-Means ist eigentlich ein Sonderfall von GMM, bei dem die Kovarianz jedes Clusters entlang aller Dimensionen gegen 0 geht. Zweitens können GMMs, da sie Wahrscheinlichkeiten verwenden, mehrere Cluster pro Datenpunkt haben. Wenn sich also ein Datenpunkt in der Mitte von zwei überlappenden Clustern befindet, kann man einfach seine Klasse definieren, indem man sagt, dass dieser X-Prozent zu Klasse 1 und Y-Prozent zu Klasse 2 gehört. D. h. GMMs unterstützen gemischte Mitgliedschaft.

Agglomerative hierarchische Clusterbildung

Hierarchische Clusterbildung-Algorithmen teilt man in zwei Kategorien ein: von oben nach unten oder von unten nach oben. Bottom-up Algorithmen behandeln jeden Datenpunkt zu Beginn als einen einzigen Cluster und führen dann nacheinander Cluster-Paare zusammen (oder bilden sie zusammen), bis alle Cluster zu einem einzigen Cluster zusammengefügt wurden, das alle Datenpunkte enthält. Bottom-Up-hierarchische Clusterbildung wird daher hierarchische agglomerative Clusterbildung oder HAC genannt. Diese Clusterhierarchie wird als Baum (oder Dendrogramm) dargestellt. Die Wurzel des Baums ist der eindeutige Cluster, der alle Proben sammelt. Die Blätter sind die Cluster mit nur einer Probe. In der unteren Grafik sehen Sie sich bitte die Illustration an, bevor wir mit den Algorithmusschritten fortfahren.

Agglomerative hierarchische Clusterbildung
  1. Beginnt man damit, jeden Datenpunkt als einen einzigen Cluster zu behandeln, d. h. wenn sich in unserem Datensatz X Datenpunkte befinden, gibt es X Cluster. Dann wählt man eine Entfernungsmetrik aus, die die Entfernung zwischen zwei Clustern misst. Als Beispiel verwendet man eine durchschnittliche Verbindung, die den Abstand zwischen zwei Clustern als den durchschnittlichen Abstand zwischen Datenpunkten im ersten Cluster und Datenpunkten im zweiten Cluster definiert.
  2. Bei jeder Iteration kombiniert man zwei Cluster zu einem. Um 2 Clusters zu kombinieren, wird man  diejenigen mit der kleinsten durchschnittlichen Verbindung ausgewählt. Gemäß unserer gewählten Entfernungsmetrik haben diese beiden Cluster den geringsten Abstand voneinander und sind daher am ähnlichsten und sollten kombiniert werden.
  3. Schritt 2 wird wiederholt, bis die Wurzel des Baums erreicht wird. D. h. man hat nur einen Cluster, der alle Datenpunkte enthält. Auf diese Weise kann man auswählen, wie viele Cluster am Ende gewünscht sind, indem man einfach festlegt, wann die Cluster nicht mehr kombiniert werden sollen.

Beim hierarchischen Clusterbildung muss man nicht die Anzahl der Cluster angeben. Man kann sogar auswählen, welche Anzahl der Cluster am besten passt, da man einen Baum erstellt. Darüber hinaus reagiert der Algorithmus nicht auf die Wahl der Entfernungsmetrik. Alle arbeiten in der Regel gleich gut, während bei anderen Clusterbildung-Algorithmen die Wahl der Entfernungsmetrik kritisch ist. Ein besonders guter Anwendungsfall für hierarchische Clusterbildung-Methoden ist, wenn die zugrunde liegenden Daten eine hierarchische Struktur haben und Sie die Hierarchie wiederherstellen möchten. Bei anderen Clusterbildung-Algorithmen ist es unmöglich zu tun. Diese Vorteile der hierarchischen Clusterbildung gehen mit einer geringeren Effizienz einher, da sie im Gegensatz zu der linearen Komplexität von K-Means und GMM eine zeitliche Komplexität von O (n³) aufweist.

Fazit

Dies sind die Top 5 Clustering-Algorithmen, die ein Datenwissenschaftler wissen sollte! Zum Abschluss erhält man eine großartige Visualisierung der Leistungsfähigkeit dieser Algorithmen und einiger anderer, mit freundlicher Genehmigung von Scikit Learn.

Welche Clustering-Algorithmen sind in Ihrem Bereich im Einsatz?

Welche Clustering Systeme sind Ihrer Meinung nach die besten?

Auf diese und weitere Fragen wird das AI United Team gern antworten per Email oder in dem Q&A Bereich.

Quellen: https://towardsdatascience.com/the-5-clustering-algorithms-data-scientists-need-to-know-a36d136ef68

AI-United-Redaktion

One Reply to “Die 5 Clusterbildung-Algorithmen, die jeder Datenwissenschaftler kennen muss”

Kommentar hinzufügen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.