Clustering-Algorithmen: Vom Anfang bis zum Stand der Technik

Es ist keine schlechte Zeit, um Data Scientist zu sein. Ernsthafte Leute könnten Interesse an Ihnen finden, wenn Sie das Gespräch auf „Big Data“ lenken, und der Rest der Party-Crowd wird fasziniert sein, wenn Sie „Künstliche Intelligenz“ und „Maschinelles Lernen“ erwähnen. Sogar Google denkt, dass du nicht schlecht bist und dass du noch besser wirst. Es gibt viele „intelligente“ Algorithmen, die Datenwissenschaftlern bei ihrer Zauberei helfen. Es mag alles kompliziert erscheinen, aber wenn wir Algorithmen ein wenig verstehen und organisieren, ist es nicht einmal so schwer, den zu finden und anzuwenden, den wir brauchen.

Kurse zu Data Mining oder maschinellem Lernen beginnen normalerweise mit Clustering, da es sowohl einfach als auch nützlich ist. Es ist ein wichtiger Teil eines etwas breiteren Bereichs des unbeaufsichtigten Lernens, in dem die Daten, die wir beschreiben möchten, nicht gekennzeichnet sind. In den meisten Fällen hat uns der Benutzer hier nicht viele Informationen über die erwartete Ausgabe gegeben. Der Algorithmus hat nur die Daten und er sollte sein Bestes geben. In unserem Fall sollte es Clustering durchführen – das Trennen von Daten in Gruppen (Cluster), die ähnliche Datenpunkte enthalten, während die Unähnlichkeit zwischen den Gruppen so hoch wie möglich ist. Datenpunkte können alles darstellen, wie z. B. unsere Kunden. Clustering kann nützlich sein, wenn wir beispielsweise ähnliche Benutzer gruppieren und dann auf jedem Cluster unterschiedliche Marketingkampagnen durchführen möchten.

K-Means-Clustering

Nach der notwendigen Einführung werden Data-Mining-Kurse immer mit K-Means fortgesetzt; ein effektiver, weit verbreiteter Allround-Clustering-Algorithmus. Bevor wir es tatsächlich ausführen, müssen wir eine Distanzfunktion zwischen Datenpunkten definieren (z. B. die euklidische Distanz, wenn wir Punkte im Raum gruppieren möchten), und wir müssen die Anzahl der gewünschten Cluster (k) festlegen.

Der Algorithmus beginnt mit der Auswahl von k Punkten als Startschwerpunkte ('Zentren' von Clustern). Wir können einfach beliebige k zufällige Punkte auswählen oder einen anderen Ansatz verwenden, aber das Auswählen zufälliger Punkte ist ein guter Anfang. Dann wiederholen wir iterativ zwei Schritte:

1. Zuordnungsschritt: Jeder von m Punkten aus unserem Datensatz wird einem Cluster zugeordnet, das durch den nächsten der k Schwerpunkte repräsentiert wird. Für jeden Punkt berechnen wir Entfernungen zu jedem Schwerpunkt und wählen einfach den am wenigsten entfernten aus.

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

Nach jeder Iteration bewegen sich die Schwerpunkte langsam, und die Gesamtentfernung von jedem Punkt zu seinem zugewiesenen Schwerpunkt wird immer geringer. Die beiden Schritte wechseln sich ab bis zur Konvergenz, das heißt bis keine Änderungen mehr in der Clusterzuordnung erfolgen. Nach einer Reihe von Iterationen wird jedem Schwerpunkt dieselbe Menge von Punkten zugewiesen, was wiederum zu denselben Schwerpunkten führt. K-Means konvergiert garantiert gegen ein lokales Optimum. Das muss aber nicht zwingend die beste Gesamtlösung (globales Optimum) sein.

Das endgültige Clustering-Ergebnis kann von der Auswahl der Anfangsschwerpunkte abhängen, daher wurde diesem Problem viel Aufmerksamkeit geschenkt. 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 Entfernungen von jedem Punkt zu seinem Cluster nehmen – dem Fehlerwert, den wir in erster Linie zu minimieren versuchen.

Andere Ansätze zum Auswählen von Anfangspunkten können sich auf das Auswählen entfernter Punkte stützen. Dies kann zu besseren Ergebnissen führen, aber wir haben möglicherweise ein Problem mit Ausreißern, diesen seltenen Einzelpunkten, die einfach „aus“ sind und möglicherweise nur einige Fehler sind. Da sie weit von einem bedeutungsvollen Cluster entfernt sind, kann jeder dieser Punkte zu einem eigenen „Cluster“ werden. Ein guter Ausgleich ist die K-Means++-Variante [Arthur und Vassilvitskii, 2007], deren Initialisierung immer noch zufällige Punkte auswählt, aber mit einer Wahrscheinlichkeit, die proportional zum quadratischen Abstand von den zuvor zugewiesenen Schwerpunkten ist. Punkte, die weiter entfernt sind, werden mit größerer Wahrscheinlichkeit als Startschwerpunkte ausgewählt. Wenn es also eine Gruppe von Punkten gibt, wird die Wahrscheinlichkeit, dass ein Punkt aus der Gruppe ausgewählt wird, ebenfalls höher, wenn sich ihre Wahrscheinlichkeiten addieren, wodurch das von uns erwähnte Ausreißerproblem gelöst wird.

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

Java (Weka)

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

Python (Scikit-lernen)

 > >> 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[::10]) [1 1 1 1 1 0 0 0 0 0 2 2 2 2 2] > >> print(yiris[::10]) [0 0 0 0 0 1 1 1 1 1 2 2 2 2 2]

Im obigen Python-Beispiel haben wir einen standardmäßigen Beispieldatensatz „Iris“ verwendet, der Blütenblätter und Kelchblätter für drei verschiedene Arten von Iris enthält. Wir gruppierten diese in drei Cluster und verglichen die erhaltenen Cluster mit der tatsächlichen Art (Ziel), um zu sehen, dass sie perfekt zusammenpassen.

In diesem Fall wussten wir, dass es drei verschiedene Cluster (Arten) gibt, und K-Means hat richtig erkannt, welche zusammengehören. Aber wie wählen wir im Allgemeinen eine gute Anzahl von Clustern k aus? Diese Art von Fragen sind im maschinellen Lernen weit verbreitet. Wenn wir mehr Cluster anfordern, werden sie kleiner, und daher wird der Gesamtfehler (Summe der Entfernungen von Punkten zu ihren zugewiesenen Clustern) kleiner. Ist es also eine gute Idee, einfach ein größeres k zu setzen? Wir können damit enden, dass k = m ist, das heißt, jeder Punkt ist sein eigener Schwerpunkt, wobei jeder Cluster nur einen Punkt hat. Ja, der Gesamtfehler ist 0, aber wir haben weder eine einfachere Beschreibung unserer Daten erhalten, noch ist sie allgemein genug, um einige neue Punkte abzudecken, die auftreten können. Das nennt man Overfitting, und das wollen wir nicht.

Eine Möglichkeit, mit diesem Problem umzugehen, besteht darin, eine gewisse Strafe für eine größere Anzahl von Clustern einzubeziehen. Wir versuchen jetzt also, nicht nur den Fehler, sondern Fehler + Strafe zu minimieren. Der Fehler konvergiert einfach gegen Null, wenn wir die Anzahl der Cluster erhöhen, aber die Strafe wird größer. An manchen Stellen ist der Gewinn durch das Hinzufügen eines weiteren Clusters geringer als die eingeführte Strafe, und wir haben das optimale Ergebnis. Eine Lösung, die Bayes'sches Informationskriterium (BIC) für diesen Zweck verwendet, heißt X-Means [Pelleg und Moore, 2000].

Eine andere Sache, die wir richtig definieren müssen, ist die Abstandsfunktion. Manchmal ist das eine unkomplizierte Aufgabe, eine logische angesichts der Natur von Daten. Für Punkte im Raum ist die euklidische Distanz eine offensichtliche Lösung, aber sie kann für Merkmale unterschiedlicher „Einheiten“, für diskrete Variablen usw. schwierig sein. Dies kann viel Domänenwissen erfordern. Oder wir können maschinelles Lernen um Hilfe bitten. Wir können tatsächlich versuchen, die Abstandsfunktion zu lernen. Wenn wir einen Trainingssatz von Punkten haben, von denen wir wissen, wie sie gruppiert werden sollten (dh Punkte, die mit ihren Clustern gekennzeichnet sind), können wir überwachte Lerntechniken verwenden, um eine gute Funktion zu finden, und sie dann auf unseren Zielsatz anwenden, der noch nicht gruppiert ist .

Die in K-Means verwendete Methode ähnelt mit ihren zwei abwechselnden Schritten einer Expectation-Maximization (EM)-Methode. Eigentlich kann es als eine sehr einfache Version von EM angesehen werden. Es sollte jedoch nicht mit dem ausgefeilteren EM-Clustering-Algorithmus verwechselt werden, obwohl es einige der gleichen Prinzipien aufweist.

EM-Clustering

Beim K-Means-Clustering wird also jeder Punkt nur einem einzigen Cluster zugewiesen, und ein Cluster wird nur durch seinen Schwerpunkt beschrieben. Dies ist nicht zu flexibel, da wir möglicherweise Probleme mit Clustern haben, die sich überlappen oder nicht kreisförmig sind. Mit EM-Clustering können wir jetzt einen Schritt weiter gehen und jeden Cluster durch seinen Schwerpunkt (Mittelwert), Kovarianz (damit wir elliptische Cluster haben können) und 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 (multivariate - abhängig von mehreren Variablen) gegeben. Das bedeutet auch, dass wir die Wahrscheinlichkeit berechnen können, dass ein Punkt unter einer Gaußschen „Glocke“ liegt, dh die Wahrscheinlichkeit, dass ein Punkt zu einem Cluster gehört.

Wir starten nun die EM-Prozedur, indem wir für jeden Punkt die Wahrscheinlichkeiten dafür 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 eins. Zwei oder mehr Cluster können jedoch akzeptable Kandidaten sein, sodass der Punkt eine Wahrscheinlichkeitsverteilung über Cluster aufweist. Diese Eigenschaft des Algorithmus, nicht zu einem Cluster gehörende Punkte einzuschränken, wird als „Soft Clustering“ bezeichnet.

Der M-Schritt berechnet nun die Parameter jedes Clusters neu, wobei die Zuweisungen von Punkten zu dem vorherigen Satz von Clustern verwendet werden. Um den neuen Mittelwert, die Kovarianz und das Gewicht eines Clusters zu berechnen, werden alle Punktdaten mit ihrer Wahrscheinlichkeit gewichtet, zu dem Cluster zu gehören, wie im vorherigen Schritt berechnet.

Das Abwechseln dieser beiden Schritte erhöht die Gesamt-Log-Wahrscheinlichkeit, bis sie konvergiert. Auch hier kann das Maximum lokal sein, sodass wir den Algorithmus mehrmals ausführen können, um bessere Cluster zu erhalten.

Wenn wir nun für jeden Punkt einen einzigen Cluster bestimmen wollen, können wir einfach den wahrscheinlichsten auswählen. Mit einem Wahrscheinlichkeitsmodell können wir es auch verwenden, um ähnliche Daten zu generieren, dh mehr Punkte abzutasten, die den von uns beobachteten Daten ähnlich sind.

Affinitätsausbreitung

Affinity Propagation (AP) wurde 2007 von Frey und Dueck veröffentlicht und erfreut sich aufgrund seiner Einfachheit, allgemeinen Anwendbarkeit und Leistungsfähigkeit immer größerer Beliebtheit. Es ändert seinen Status vom Stand der Technik zum De-facto-Standard.

Die Hauptnachteile von K-Means und ähnlichen Algorithmen sind die Auswahl der Anzahl von Clustern und die Auswahl des anfänglichen Satzes von Punkten. Die Affinitätsausbreitung nimmt stattdessen als Eingabemaße der Ähnlichkeit zwischen Paaren von Datenpunkten und betrachtet gleichzeitig alle Datenpunkte als potenzielle Exemplare. Dabei werden reellwertige Nachrichten zwischen Datenpunkten ausgetauscht, bis nach und nach ein qualitativ hochwertiger Satz von Exemplaren und entsprechenden Clustern entsteht.

Als Eingabe erfordert der Algorithmus, dass wir zwei Datensätze bereitstellen:

1. Ähnlichkeiten zwischen Datenpunkten, die darstellen, wie gut ein Punkt als Beispiel für einen anderen geeignet ist. Wenn zwischen zwei Punkten keine Ähnlichkeit besteht, da sie nicht zum selben Cluster gehören können, kann diese Ähnlichkeit je nach Implementierung weggelassen oder auf -Infinity gesetzt werden.

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

Sowohl Ähnlichkeiten als auch Präferenzen werden oft durch eine einzige Matrix dargestellt, wobei die Werte auf der Hauptdiagonalen Präferenzen darstellen. Die Matrixdarstellung eignet sich gut für dichte Datensätze. Wo Verbindungen zwischen Punkten spärlich sind, ist es praktischer, nicht die gesamte nxn-Matrix im Speicher zu speichern, sondern stattdessen eine Liste von Ähnlichkeiten mit 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 Implementierung.

Der Algorithmus durchläuft dann eine Reihe von Iterationen, bis er konvergiert. Jede Iteration hat zwei Message-Passing-Schritte:

1. Berechnung der Verantwortlichkeiten: Die Verantwortlichkeit r(i, k) spiegelt die gesammelten Beweise dafür wider, wie gut Punkt k geeignet ist, um als Musterbeispiel für Punkt i zu dienen, unter Berücksichtigung anderer potenzieller Musterexemplare für Punkt i. Die Verantwortung wird vom Datenpunkt i zum Kandidatenbeispielpunkt k gesendet.

2. Berechnung der Verfügbarkeiten: Die Verfügbarkeit a(i, k) spiegelt die gesammelten Beweise dafür wider, wie angemessen es für Punkt i wäre, Punkt k als sein Exemplar zu wählen, wobei die Unterstützung von anderen Punkten berücksichtigt wird, dass Punkt k ein Exemplar sein sollte. Die Verfügbarkeit wird vom Kandidatenbeispielpunkt k zum Punkt i gesendet.

Um Verantwortlichkeiten zu berechnen, verwendet der Algorithmus ursprüngliche Ähnlichkeiten und Verfügbarkeiten, die in der vorherigen Iteration berechnet wurden (anfänglich werden alle Verfügbarkeiten auf Null gesetzt). Verantwortlichkeiten werden auf die Eingabeähnlichkeit zwischen Punkt i und Punkt k als seinem Exemplar abzüglich der größten Ähnlichkeits- und Verfügbarkeitssumme zwischen Punkt i und anderen Kandidatenexemplaren festgelegt. Die Logik hinter der Berechnung, wie geeignet ein Punkt für ein Exemplar ist, ist, dass er mehr bevorzugt wird, wenn die anfängliche a priori-Präferenz höher war, aber die Verantwortung wird geringer, wenn es einen ähnlichen Punkt gibt, der sich selbst als guten Kandidaten betrachtet, also gibt es ein ' Wettbewerb' zwischen den beiden, bis einer in einer Iteration entschieden wird.

Die Berechnung der Verfügbarkeiten verwendet dann berechnete Verantwortlichkeiten als Beweis dafür, ob jeder Kandidat ein gutes Beispiel abgeben würde. Die Verfügbarkeit a(i, k) wird auf die Eigenverantwortung r(k, k) plus die Summe der positiven Verantwortlichkeiten gesetzt, die das Kandidat-Exemplar k aus anderen Punkten erhält.

Schließlich können wir verschiedene Stoppkriterien haben, um die Prozedur zu beenden, z. B. wenn Änderungen der Werte unter einen bestimmten Schwellenwert fallen oder die maximale Anzahl von Iterationen erreicht ist. An jedem Punkt des Affinity Propagation-Verfahrens liefert uns das Summieren der Responsibility (r)- und Availability (a)-Matrizen die Clustering-Informationen, die wir benötigen: Für Punkt i repräsentiert das k mit dem Maximum r(i, k) + a(i, k) den Punkt ich bin vorbildlich. Oder, wenn wir nur den Satz von Exemplaren brauchen, können wir die Hauptdiagonale scannen. Wenn r(i, i) + a(i, i) > 0 ist, ist Punkt i ein Exemplar.

Wir haben gesehen, dass es bei K-Means und ähnlichen Algorithmen schwierig sein kann, die Anzahl der Cluster zu bestimmen. Bei AP müssen wir es nicht explizit spezifizieren, aber es kann immer noch eine gewisse Abstimmung erforderlich sein, wenn wir entweder mehr oder weniger Cluster erhalten, als wir vielleicht für optimal halten. Glücklicherweise können wir die Anzahl der Cluster verringern oder erhöhen, indem wir einfach die Einstellungen anpassen. Das Festlegen von Präferenzen auf einen höheren Wert führt zu mehr Clustern, da jeder Punkt „sicherer“ in Bezug auf seine Eignung als Vorbild ist und daher schwerer zu „schlagen“ und unter die „Dominanz“ eines anderen Punkts einzuordnen ist. Umgekehrt führt das Festlegen niedrigerer Einstellungen zu weniger Clustern. als würden sie sagen „nein, nein, bitte, du bist ein besseres Vorbild, ich trete deinem Cluster bei“. Als allgemeine Regel können wir alle Präferenzen auf die mittlere Ähnlichkeit für eine mittlere bis große Anzahl von Clustern oder auf die niedrigste Ähnlichkeit für eine mittlere Anzahl von Clustern setzen. Es können jedoch einige Durchläufe mit Anpassung der Einstellungen erforderlich sein, um das Ergebnis zu erhalten, das genau unseren Anforderungen entspricht.

Erwähnenswert ist auch die hierarchische Affinitätsausbreitung als Variante des Algorithmus, der sich mit quadratischer Komplexität befasst, indem er den Datensatz in ein paar Teilmengen aufteilt, sie separat gruppiert und dann die zweite Stufe der Gruppierung durchführt.

Letzten Endes…

Es gibt eine ganze Reihe von Clustering-Algorithmen, jeder mit seinen Vor- und Nachteilen in Bezug auf die Art der Daten, mit denen sie arbeiten, die Zeitkomplexität, Schwächen und so weiter. Um weitere Algorithmen zu erwähnen, gibt es zum Beispiel Hierarchical Agglomerative Clustering (oder Linkage Clustering), gut geeignet, wenn wir nicht unbedingt kreisförmige (oder hypersphärische) Cluster haben und die Anzahl der Cluster nicht im Voraus kennen. Es beginnt damit, dass jeder Punkt ein separater Cluster ist, und funktioniert, indem in jedem Schritt zwei engste Cluster verbunden werden, bis sich alles in einem großen Cluster befindet.

Mit Hierarchical Agglomerative Clustering können wir die Anzahl der Cluster nachträglich leicht bestimmen, indem wir das Dendrogramm (Baumdiagramm) horizontal schneiden, wo wir es für geeignet halten. Es ist auch wiederholbar (gibt immer die gleiche Antwort für denselben Datensatz), ist aber auch von höherer Komplexität (quadratisch).

Dann ist auch DBSCAN (Density-Based Spatial Clustering of Applications with Noise) ein erwähnenswerter Algorithmus. Es gruppiert Punkte, die dicht beieinander liegen, und erweitert Cluster in jede Richtung, in der sich Punkte in der Nähe befinden, wodurch unterschiedliche Formen von Clustern behandelt werden.

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

Es braucht Erfahrung mit etwas Trial-and-Error, um zu wissen, wann man den einen oder anderen Algorithmus verwendet. Glücklicherweise haben wir eine Reihe von Implementierungen in verschiedenen Programmiersprachen, so dass das Ausprobieren nur ein wenig Spielfreude erfordert.