Clustering-Algorithmen: Von den Anfängen bis zum Stand der Technik

Es ist keine schlechte Zeit, um Datenwissenschaftler zu sein. Seriöse Leute werden sich für Sie interessieren, wenn Sie das Gespräch auf „Big Data“ lenken, und der Rest der Partygesellschaft wird fasziniert sein, wenn Sie „Künstliche Intelligenz“ und „Maschinelles Lernen“ erwähnen. Sogar Google glaubt, dass Sie nicht schlecht sind und dass Sie sogar noch besser werden. Es gibt eine Menge „intelligenter“ Algorithmen, die Datenwissenschaftlern bei ihrer Arbeit helfen. Es mag alles kompliziert erscheinen, aber wenn wir die Algorithmen ein wenig verstehen und organisieren, ist es gar nicht so schwer, den richtigen zu finden und anzuwenden.

Kurse über Data Mining oder maschinelles Lernen beginnen in der Regel mit Clustering, weil es sowohl einfach als auch nützlich ist. Es ist ein wichtiger Teil eines etwas größeren Bereichs des unüberwachten Lernens, bei dem die Daten, die wir beschreiben wollen, nicht beschriftet sind. In den meisten Fällen ist dies der Fall, wenn der Benutzer uns nicht viele Informationen über die erwartete Ausgabe gegeben hat. Der Algorithmus hat nur die Daten und sollte sein Bestes geben. In unserem Fall sollte er ein Clustering durchführen, d. h. die Daten in Gruppen (Cluster) einteilen, die ähnliche Datenpunkte enthalten, während die Unähnlichkeit zwischen den Gruppen so groß wie möglich ist. Die Datenpunkte können alles Mögliche darstellen, z. B. unsere Kunden. Clustering kann nützlich sein, wenn wir z. B. ähnliche Nutzer gruppieren und dann für jedes Cluster unterschiedliche Marketingkampagnen durchführen wollen.

K-Means Clustering

Nach der notwendigen Einführung geht es in Data-Mining-Kursen immer mit K-Means weiter, einem effektiven, weit verbreiteten und vielseitigen Clustering-Algorithmus. Bevor er ausgeführt wird, muss eine Abstandsfunktion zwischen Datenpunkten definiert werden (z. B. der euklidische Abstand, wenn Punkte im Raum geclustert werden sollen), und es muss die Anzahl der gewünschten Cluster (k) festgelegt werden.

Der Algorithmus beginnt mit der Auswahl von k Punkten als Startzentren („Zentren“ von Clustern). Wir können einfach k beliebige Punkte auswählen oder einen anderen Ansatz verwenden, aber die Auswahl von Zufallspunkten ist ein guter Anfang. Dann wiederholen wir iterativ zwei Schritte:

1. Zuweisungsschritt: Jeder der m Punkte aus unserem Datensatz wird einem Cluster zugewiesen, das durch den nächstgelegenen der k Zentroide repräsentiert wird. Für jeden Punkt werden die Entfernungen zu jedem Schwerpunkt berechnet, und es wird einfach der am wenigsten entfernte ausgewählt.

2. Aktualisierungsschritt: Für jeden Cluster wird ein neuer Schwerpunkt als Mittelwert aller Punkte im Cluster berechnet. Nach dem vorherigen Schritt haben wir eine Reihe von Punkten, die einem Cluster zugeordnet sind. Nun wird für jeden solchen Satz ein Mittelwert berechnet, den wir zum neuen Schwerpunkt des Clusters erklären.

Nach jeder Iteration verschieben sich die Schwerpunkte langsam, und der Gesamtabstand von jedem Punkt zu seinem zugeordneten Schwerpunkt wird immer geringer. Die beiden Schritte wechseln sich ab, bis Konvergenz erreicht ist, d. h. bis sich die Clusterzuordnung nicht mehr ändert. Nach einer bestimmten Anzahl von Iterationen wird jedem Schwerpunkt dieselbe Menge von Punkten zugewiesen, was wiederum zu denselben Schwerpunkten führt. K-Means konvergiert garantiert zu einem lokalen Optimum. Dies muss jedoch nicht unbedingt die beste Gesamtlösung (globales Optimum) sein.

Das endgültige Clustering-Ergebnis kann von der Auswahl der anfänglichen Zentroide abhängen, weshalb man sich viele Gedanken über dieses Problem gemacht hat. Eine einfache Lösung besteht darin, K-Means ein paar Mal mit zufälligen Anfangszuweisungen auszuführen. Wir können dann das beste Ergebnis auswählen, indem wir dasjenige mit der minimalen Summe der Abstände von jedem Punkt zu seinem Cluster nehmen – der Fehlerwert, den wir in erster Linie zu minimieren versuchen.

Andere Ansätze zur Auswahl der Anfangspunkte können sich auf die Auswahl entfernter Punkte stützen. Dies kann zu besseren Ergebnissen führen, aber wir können ein Problem mit Ausreißern haben, jenen seltenen einzelnen Punkten, die einfach „daneben“ sind und vielleicht nur Fehler darstellen. Da sie weit von einem aussagekräftigen Cluster entfernt sind, kann jeder dieser Punkte am Ende ein eigener „Cluster“ sein. Ein guter Ausgleich ist die K-Means++-Variante, deren Initialisierung immer noch zufällige Punkte auswählt, aber mit einer Wahrscheinlichkeit, die proportional zum quadratischen Abstand zu den zuvor zugewiesenen Zentren ist. Punkte, die weiter entfernt sind, haben eine höhere Wahrscheinlichkeit, als Start-Zentren ausgewählt zu werden. Wenn es also eine Gruppe von Punkten gibt, wird die Wahrscheinlichkeit, dass ein Punkt aus der Gruppe ausgewählt wird, mit der Summe ihrer Wahrscheinlichkeiten ebenfalls höher, wodurch das erwähnte Ausreißerproblem gelöst wird.

K-Means++ ist auch die Standardinitialisierung für die K-Means-Implementierung von Scikit-learn in Python. Wenn Sie Python verwenden, könnte dies die Bibliothek Ihrer Wahl sein. Für Java ist die Weka-Bibliothek ein guter Anfang:

Java (Weka)

// Load some dataInstances data = DataSource.read("data.arff");// Create the modelSimpleKMeans kMeans = new SimpleKMeans();// We want three clusterskMeans.setNumClusters(3);// Run K-MeanskMeans.buildClusterer(data);// Print the centroidsInstances centroids = kMeans.getClusterCentroids();for (Instance centroid: centroids) { System.out.println(centroid);}// Print cluster membership for each instancefor (Instance point: data) { System.out.println(point + " is in cluster " + kMeans.clusterInstance(point));}

Python (Scikit-learn)

> >> from sklearn import cluster, datasets> >> iris = datasets.loadiris()> >> Xiris = iris.data> >> yiris = iris.target> >> kmeans = cluster.KMeans(nclusters=3)> >> kmeans.fit(Xiris)KMeans(copy_x=True, init='k-means++', ...> >> print(kmeans.labels)> >> print(yiris)

Im obigen Python-Beispiel haben wir einen Standard-Beispiel-Datensatz „Iris“ verwendet, der die Abmessungen der Blütenblätter und Kelchblätter von drei verschiedenen Iris-Arten enthält. Wir haben diese in drei Cluster eingeteilt und die erhaltenen Cluster mit den tatsächlichen Arten (Ziel) verglichen, um zu sehen, dass sie perfekt übereinstimmen.

In diesem Fall wussten wir, dass es drei verschiedene Cluster (Arten) gab, und K-Means erkannte korrekt, welche zusammengehören. Aber wie wählt man im Allgemeinen eine gute Anzahl von Clustern k? Diese Art von Fragen sind beim maschinellen Lernen recht häufig. Wenn wir mehr Cluster anfordern, werden diese kleiner sein, und daher wird der Gesamtfehler (Summe der Abstände zwischen den Punkten und den ihnen zugeordneten Clustern) kleiner sein. Ist es also eine gute Idee, einfach ein größeres k festzulegen? Am Ende könnte k = m stehen, d. h. jeder Punkt ist sein eigener Schwerpunkt, wobei jedes Cluster nur einen Punkt hat. Ja, der Gesamtfehler ist 0, aber wir haben keine einfachere Beschreibung unserer Daten erhalten, und sie ist auch nicht allgemein genug, um einige neue Punkte abzudecken, die möglicherweise auftreten. Das nennt man Overfitting, und das wollen wir nicht.

Eine Möglichkeit, mit diesem Problem umzugehen, besteht darin, eine Strafe für eine größere Anzahl von Clustern vorzusehen. Wir versuchen also, nicht nur den Fehler zu minimieren, sondern Fehler + Strafe. Der Fehler konvergiert einfach gegen Null, wenn wir die Anzahl der Cluster erhöhen, aber die Strafe wird größer. An einem bestimmten Punkt wird der Gewinn durch das Hinzufügen eines weiteren Clusters geringer sein als die eingeführte Strafe, und wir haben das optimale Ergebnis. Eine Lösung, die zu diesem Zweck das Bayes’sche Informationskriterium (BIC) verwendet, heißt X-Means.

Eine andere Sache, die wir richtig definieren müssen, ist die Distanzfunktion. Manchmal ist das eine einfache Aufgabe, eine logische Aufgabe angesichts der Natur der Daten. Für Punkte im Raum ist der euklidische Abstand eine offensichtliche Lösung, aber bei Merkmalen mit unterschiedlichen „Einheiten“, bei diskreten Variablen usw. kann es schwierig werden. Dies kann eine Menge an Fachwissen erfordern. Oder wir können das maschinelle Lernen um Hilfe bitten. Wir können versuchen, die Abstandsfunktion zu lernen. Wenn wir eine Trainingsmenge von Punkten haben, von denen wir wissen, wie sie gruppiert werden sollten (d. h. Punkte, die mit ihren Clustern beschriftet sind), können wir Techniken des überwachten Lernens verwenden, um eine gute Funktion zu finden, und diese dann auf unsere Zielmenge anwenden, die noch nicht geclustert ist.

Die in K-Means verwendete Methode mit ihren zwei abwechselnden Schritten ähnelt einer Erwartungsmaximierungsmethode (EM). Tatsächlich kann es als eine sehr einfache Version von EM betrachtet werden. Sie sollte jedoch nicht mit dem aufwändigeren EM-Clusteralgorithmus verwechselt werden, auch wenn sie einige der gleichen Prinzipien teilt.

EM-Clustering

Beim K-Means-Clustering wird also jeder Punkt nur einem einzigen Cluster zugeordnet, und ein Cluster wird nur durch seinen Schwerpunkt beschrieben. Dies ist nicht sehr flexibel, da wir Probleme mit Clustern haben können, die sich überschneiden oder nicht kreisförmig sind. Mit EM Clustering können wir nun einen Schritt weiter gehen und jeden Cluster durch seinen Schwerpunkt (Mittelwert), seine Kovarianz (so dass wir elliptische Cluster haben können) und sein Gewicht (die Größe des Clusters) beschreiben. Die Wahrscheinlichkeit, dass ein Punkt zu einem Cluster gehört, ist nun durch eine multivariate Gaußsche Wahrscheinlichkeitsverteilung gegeben (multivariat – abhängig von mehreren Variablen). Das bedeutet auch, dass wir die Wahrscheinlichkeit berechnen können, dass ein Punkt unter einer Gaußschen „Glocke“ liegt, d.h. die Wahrscheinlichkeit, dass ein Punkt zu einem Cluster gehört.

Wir beginnen nun das EM-Verfahren, indem wir für jeden Punkt die Wahrscheinlichkeiten berechnen, dass er zu jedem der aktuellen Cluster gehört (die wiederum zu Beginn zufällig erstellt werden können). Dies ist der E-Schritt. Wenn ein Cluster ein wirklich guter Kandidat für einen Punkt ist, hat er eine Wahrscheinlichkeit nahe bei eins. Allerdings können auch zwei oder mehr Cluster akzeptable Kandidaten sein, so dass der Punkt eine Verteilung der Wahrscheinlichkeiten über die Cluster hat. Diese Eigenschaft des Algorithmus, dass Punkte nicht nur zu einem Cluster gehören, wird als „soft clustering“ bezeichnet.

Im M-Schritt werden nun die Parameter jedes Clusters neu berechnet, wobei die Zuordnungen der Punkte zu den vorherigen Clustern verwendet werden. Um den neuen Mittelwert, die Kovarianz und die Gewichtung eines Clusters zu berechnen, wird jeder Punkt mit der im vorherigen Schritt berechneten Wahrscheinlichkeit der Zugehörigkeit zu dem Cluster gewichtet.

Die Abwechslung dieser beiden Schritte erhöht die gesamte log-likelihood, bis sie konvergiert. Auch hier kann das Maximum lokal sein, so dass wir den Algorithmus mehrmals ausführen können, um bessere Cluster zu erhalten.

Wenn wir nun für jeden Punkt einen einzelnen Cluster bestimmen wollen, können wir einfach den wahrscheinlichsten auswählen. Wenn wir ein Wahrscheinlichkeitsmodell haben, können wir es auch verwenden, um ähnliche Daten zu generieren, d.h. um mehr Punkte zu stichprobenartig zu erfassen, die den von uns beobachteten Daten ähnlich sind.

Affinity Propagation

Affinity Propagation (AP) wurde 2007 von Frey und Dueck veröffentlicht und wird aufgrund seiner Einfachheit, allgemeinen Anwendbarkeit und Leistungsfähigkeit immer beliebter. Sie entwickelt sich vom Stand der Technik zum De-facto-Standard.

Die Hauptnachteile von K-Means und ähnlichen Algorithmen sind die Auswahl der Anzahl der Cluster und die Auswahl der Anfangspunkte. Bei der Affinity Propagation werden stattdessen Ähnlichkeitsmaße zwischen Datenpunktpaaren verwendet und gleichzeitig alle Datenpunkte als potenzielle Exemplare betrachtet. Zwischen den Datenpunkten werden Nachrichten mit reellen Werten ausgetauscht, bis sich allmählich eine qualitativ hochwertige Gruppe von Beispielen und entsprechenden Clustern herausbildet.

Als Eingabe benötigt der Algorithmus zwei Datensätze:

1. Ähnlichkeitsmaße zwischen Datenpunkten, die angeben, wie gut ein Punkt geeignet ist, ein Beispiel für einen anderen zu sein. Gibt es keine Ähnlichkeit zwischen zwei Punkten, d. h. können sie nicht zum selben Cluster gehören, kann diese Ähnlichkeit je nach Implementierung weggelassen oder auf -Unendlich gesetzt werden.

2. Präferenzen, die die Eignung jedes Datenpunktes als Exemplar darstellen. Möglicherweise haben wir a priori Informationen darüber, welche Punkte für diese Rolle bevorzugt werden könnten, und können dies durch Präferenzen darstellen.

Beide, Ähnlichkeiten und Präferenzen, werden oft durch eine einzige Matrix dargestellt, wobei die Werte auf der Hauptdiagonale Präferenzen darstellen. Die Matrixdarstellung eignet sich gut für dichte Datensätze. Bei spärlichen Verbindungen zwischen Punkten ist es praktischer, nicht die gesamte n x n-Matrix im Speicher zu speichern, sondern eine Liste der Ähnlichkeiten zu verbundenen Punkten zu führen. Hinter den Kulissen ist der „Austausch von Nachrichten zwischen Punkten“ dasselbe wie die Manipulation von Matrizen, und es ist nur eine Frage der Perspektive und der Implementierung.

Der Algorithmus durchläuft dann eine Reihe von Iterationen, bis er konvergiert. Jede Iteration umfasst zwei Schritte der Nachrichtenübermittlung:

1. Berechnung der Verantwortlichkeiten: Die Zuständigkeit r(i, k) spiegelt die akkumulierte Evidenz dafür wider, wie gut Punkt k als Beispiel für Punkt i geeignet ist, unter Berücksichtigung anderer potenzieller Beispiele für Punkt i. Die Zuständigkeit wird von Datenpunkt i an den Beispielkandidaten Punkt k gesendet.

2. Berechnung der Verfügbarkeiten: Die Verfügbarkeit a(i, k) spiegelt die akkumulierte Evidenz dafür wider, wie angemessen es für Punkt i wäre, Punkt k als sein Exemplar zu wählen, unter Berücksichtigung der Unterstützung von anderen Punkten, dass Punkt k ein Exemplar sein sollte. Die Verfügbarkeit wird vom Beispielkandidaten Punkt k an Punkt i gesendet.

Um die Verantwortlichkeiten zu berechnen, verwendet der Algorithmus die ursprünglichen Ähnlichkeiten und Verfügbarkeiten, die in der vorherigen Iteration berechnet wurden (anfangs werden alle Verfügbarkeiten auf Null gesetzt). Die Zuständigkeiten werden auf die eingegebene Ähnlichkeit zwischen Punkt i und Punkt k als sein Exemplar gesetzt, abzüglich der größten Summe aus Ähnlichkeit und Verfügbarkeit zwischen Punkt i und anderen Kandidaten-Exemplaren. Die Logik hinter der Berechnung, wie geeignet ein Punkt für ein Exemplar ist, besteht darin, dass er mehr bevorzugt wird, wenn die anfängliche A-priori-Präferenz höher war, aber die Verantwortlichkeit sinkt, wenn es einen ähnlichen Punkt gibt, der sich selbst für einen guten Kandidaten hält, so dass es einen „Wettbewerb“ zwischen den beiden gibt, bis in einer Iteration eine Entscheidung getroffen wird.

Die Berechnung der Verfügbarkeiten verwendet also die berechneten Verantwortlichkeiten als Beweis dafür, ob jeder Kandidat ein gutes Exemplar wäre. Die Verfügbarkeit a(i, k) ist gleich der Eigenverantwortung r(k, k) plus der Summe der positiven Verantwortlichkeiten, die der Beispielkandidat k von anderen Punkten erhält.

Schließlich können wir verschiedene Abbruchkriterien festlegen, um das Verfahren zu beenden, z. B. wenn die Veränderungen der Werte unter einen bestimmten Schwellenwert fallen oder wenn die maximale Anzahl von Iterationen erreicht ist. An jedem beliebigen Punkt des Affinity Propagation-Verfahrens liefert die Summierung der Matrizen Responsibility (r) und Availability (a) die benötigten Clustering-Informationen: Für Punkt i stellt das k mit dem höchsten r(i, k) + a(i, k) das Exemplar von Punkt i dar. Wenn wir nur die Menge der Exemplare benötigen, können wir auch die Hauptdiagonale scannen. Wenn r(i, i) + a(i, i) > 0 ist, ist Punkt i ein Exemplar.

Wie wir gesehen haben, kann es bei K-Means und ähnlichen Algorithmen schwierig sein, die Anzahl der Cluster zu bestimmen. Bei AP müssen wir die Anzahl nicht explizit festlegen, aber es kann immer noch eine Anpassung erforderlich sein, wenn wir entweder mehr oder weniger Cluster erhalten, als wir für optimal halten. Glücklicherweise können wir die Anzahl der Cluster einfach durch Anpassung der Präferenzen verringern oder erhöhen. Ein höherer Wert für die Präferenzen führt zu mehr Clustern, da jeder Punkt „sicherer“ in seiner Eignung als Exemplar ist und es daher schwieriger ist, ihn zu „schlagen“ und unter die „Vorherrschaft“ eines anderen Punktes zu bringen. Umgekehrt führen niedrigere Präferenzen zu weniger Clustern, als ob sie sagen würden: „Nein, nein, bitte, du bist ein besseres Exemplar, ich werde deinem Cluster beitreten“. Als allgemeine Regel kann man alle Präferenzen auf den Median der Ähnlichkeit für eine mittlere bis große Anzahl von Clustern oder auf die niedrigste Ähnlichkeit für eine moderate Anzahl von Clustern setzen. Es kann jedoch sein, dass mehrere Durchläufe mit angepassten Einstellungen erforderlich sind, um ein Ergebnis zu erhalten, das genau unseren Bedürfnissen entspricht.

Hierarchical Affinity Propagation ist ebenfalls erwähnenswert, als eine Variante des Algorithmus, die mit quadratischer Komplexität zurechtkommt, indem sie den Datensatz in mehrere Teilmengen aufteilt, diese getrennt clustert und dann die zweite Ebene des Clusterns durchführt.

Am Ende…

Es gibt eine ganze Reihe von Clustering-Algorithmen, von denen jeder seine Vor- und Nachteile in Bezug auf die Art der Daten, die Zeitkomplexität, die Schwächen und so weiter hat. Um noch mehr Algorithmen zu nennen, gibt es zum Beispiel das Hierarchische Agglomerative Clustering (oder Linkage Clustering), das gut geeignet ist, wenn wir nicht unbedingt kreisförmige (oder hypersphärische) Cluster haben und die Anzahl der Cluster nicht im Voraus kennen. Zu Beginn ist jeder Punkt ein separater Cluster, und in jedem Schritt werden die beiden nächstgelegenen Cluster miteinander verbunden, bis sich alles in einem großen Cluster befindet.

Beim Hierarchischen Agglomerativen Clustering kann die Anzahl der Cluster leicht im Nachhinein festgelegt werden, indem das Dendrogramm (Baumdiagramm) an den geeigneten Stellen horizontal geschnitten wird. Es ist auch wiederholbar (gibt immer die gleiche Antwort für den gleichen Datensatz), ist aber auch von höherer Komplexität (quadratisch).

Dann ist DBSCAN (Density-Based Spatial Clustering of Applications with Noise) auch ein erwähnenswerter Algorithmus. Er gruppiert Punkte, die dicht beieinander liegen, und erweitert die Cluster in jede Richtung, in der es nahe gelegene Punkte gibt, so dass verschiedene Formen von Clustern behandelt werden können.

Diese Algorithmen verdienen einen eigenen Artikel, und wir können sie später in einem separaten Beitrag untersuchen.

Es erfordert Erfahrung und etwas Ausprobieren, um zu wissen, wann man den einen oder anderen Algorithmus verwenden sollte. Glücklicherweise gibt es eine Reihe von Implementierungen in verschiedenen Programmiersprachen, so dass das Ausprobieren nur ein wenig Bereitschaft zum Spielen erfordert.