9 Unsupervised Machine Learning: Clustering von Daten¶

In dieser Einheit Beschäftigen wir uns mit einer interessanten Methode, um Daten zu “ordnen”, dem Clustering. Damit tauchen wir ein Stück in das Gebiet des Machine Learnings ein, genauer gesagt, gehört dieser Ansatz zum sogenannten “unsupervised learning”. Das bedeutet, dass man über den Datensatz nicht allzuviel wissen muss, um ihn in Kategorien (bzw. Cluster) einteilen zu können oder ihn besser verstehen zu lernen.

Allerdings ist auch nicht von vornherein klar, dass es eine Struktur in den Daten gibt, die eine signifikante Bedeutung hat. Damit Sie das besser verstehen, sehen wir uns am besten gleich ein Beispiel an. Ich habe diemal wieder ein Stück aus einem Dataset von kaggle.com vorbereitet. Genauer gesagt, von der folgenden Quelle: https://www.kaggle.com/datasets/grisme/hourly-snapshots-of-lightning-network Nehmen Sie eine beliebige CSV Datei aus dem Unterordner “nodes” des Datensatzes (wir verwenden hier _2019_12_11_16_0537.csv) und benennen Sie diese entsprechend auf ‘lightning_strokes.csv’ um. Im Moodle finden Sie dieses Beispiel fertig zum Download, sodass Sie sich nicht das gesamte Dataset herunterladen müssen.

Hier aber zunächst noch die Imports für heute:

9.1 Was ist bzw. macht ein Clustering-Algorithmus eigentlich?¶

Bevor wir uns jetzt ans Clustering machen, möchte ich noch eine Runde erklären, was das eigentlich kann und tun soll. Dadurch wird sich auch die Frage beantworten, die ich gerade vorher im Kommentar gestellt habe, nämlich: Werden diese Daten sich fürs Clustern eignen?

Ein Clustering-Algorithmus teilt einen Datensatz in Gruppen ein. Das passiert auf der Basis der Eigenschaften der Daten untereinander, z.B. wie “benachbart” sie sind (was auch immer das dann im Detail heißen mag). Wenn wir Daten haben, die 2-dimensionalen Koordinaten entsprechen (so wie in unserem Beispiel), dann ist die Sache recht anschaulich. Das werden wir hier also auch so verwenden und uns ansehen. Das muss aber nicht so sein. Sie können Daten verwenden, für die eine Ähnlichkeit recht umständlich definiert ist, oder sogar erst definiert werden muss.

Für das Clustering selbst (also die Gruppeneinteilung von Daten) gibt es verschiedene Algorithmen, die verschiedene Parameter für das Gruppieren nutzen. Lassen Sie uns also zunächst einmal diese Parameter kurz durchsehen:

• Die Anzahl der gewünschten/vermuteten Cluster: Manche Algorithmen, wie z.B. K-Means (siehe weiter unten) verlangen die Festlegung auf eine bestimmte Anzahl von Clustern von vornherein. Das bedeutet, man legt z.B. 3 Cluster fest, clustert dann die Daten so und sieht (bzw. kann berechnen), wie gut diese Wahl gepasst hat.
• Ein bestimmter Abstand, den die Elemente maximal haben dürfen, um zum gleichen Cluster zu gehören, oder etwas Derartiges. Das kann ein einzelner Abstand oder ein gemittelter sein, je nachdem. So etwas setzt auch voraus, dass man zumindest irgendeine Ahnung von der ungefähren Dimension so eines Clusters hat.
• Die Art der Daten und zwar entweder absolute Koordinaten oder Distanzen: Manche Algorithmen brauchen gar keine absoluten Distanzen, um ein Clustering berechnen zu können, sondern nur die Distanzen zwischen allen Elementen der Daten. Das Agglomerative Clustering, das wir uns gleich ansehen werden, ist so ein Algorithmus. Diese Variante (nur Distanzen) kann ziemlich praktisch sein, vor allem dann, wenn man die Abstandsmessung, die man zur Verfügung hat, nicht so einfach in koordinaten umsetzen kann. Denken Sie z.B. an eine Sequenzähnlichkeit von Buchstabenketten oder DNA.
• Die Art, wie die Distanzen berechnet werden: Z.B. kann man immer die kleinste Distanz eines Elements zu einem bereits bestehenden Cluster nehmen, oder die gemittelten Distanzen des Elements zu allen Elementen eines bestehenden Clusters, oder dergleichen mehr.

Insgesamt läuft es darauf hinaus, dass man, je nach Algorithmus, die eine oder andere Vorgabe machen muss, damit der Algorithmus arbeiten kann. Andere Parameter kommen jeweils dann als Resultat heraus oder kommen nicht vor.

Wir sehen uns jetzt drei verschiedene Algorithmen nacheinander an, die etwas verschieden funktionieren. Mit jedem davon könnten wir viel mehr Zeit verbringen, die wir allerdings nicht haben. Daher erkläre ich jeweils nur kurz das Grundprinzip, zeige Ihnen den grundlegenden Aufruf aus der Package Scikit-Learn, und wir vergleichen den Output für jeweils einen zentralen Parameter.

Aber keine Sorge: In der Übungsaufgabe sind Sie dann wieder zum Experimentieren mit dem Clustering dieser Daten aufgerufen.

9.2 Der Algorithmus Agglomerative Clustering, kurz und einfach erklärt, mit Beispiel¶

Agglomeratives Clustering wird auch als “hierarchisches” Clustering bezeichnet. Warum, das ergibt sich aus der Funktionsweise. Die Schritte bei dieser Art des Clusterings ist wie folgt:

• Die Distanzen zwischen allen Datenpunkten werden berechnet (oder sie sind anstelle von absoluten Koordinaten bereits gegeben, siehe oben)
• Die beiden Datenpunkte mit der kürzesten Distanz werden zu einem Cluster kombiniert.
• Dieser Cluster wird entweder durch alle seine Mitglieder repräsentiert und deren Koordinaten bleiben für Vergleiche verfügbar, oder er bekommt eine zentrale Koordinate zugewiesen
• Für den neuen Cluster werden alle Distanzen zu den anderen Punkte im Datensatz berechnet
• Die beiden Datenpunkte (inklusive des neuen Clusters) mit der kürzesten Distanz werden wieder zu einem neuen Cluster kombiniert.
• Das kann so vor sich gehen, dass entweder der erste Cluster wächst oder ein separater neuer Cluster aus zwei einzelnen Datenpunkten entsteht und der erste Cluster unverändert bleibt.
• Dieser Vorgang wiederholt sich so oft, bis alle Punkte Clustern zugeordnet sind.
• Das führt letztendlich dazu, dass am Ende alle Daten in einem riesigen Cluster landen, dass allerdings gleichzeitig die Hierarchie innerhalb des Clusters über einen Baumgraphen klar ist
• Wenn man tatsächlich mehrere Cluster erhalten möchte, dann muss man mit dem Kombinieren aufhören, bevor alles in einem Cluster landet. Das geht entweder über eine Maximale Distanz, bei der aufgehört wird, oder über eine bestimmte Anzahl von Clustern, die man haben möchte, und bei der dann aufgehört wird.

Insgesamt ist diese Methode sehr mächtig. Wir sehen uns jetzt einmal konkret an, was Agglomeratives Clustering aus unseren Beispieldaten macht. Der Grundaufruf der Klassen aus Scikit-Learn ist immer der gleiche: Wir generieren eine Instanz der Klasse soundso und davon holen wir uns dann die sogenannten “Labels”, d.h. die Zahlen, die für jedes Element im Datensatz die Clusterzugehörigkeit anzeigen. So sieht das aus:

So stellt sich der Algorithmus also die Daten in 4 Clustern vor. Das kann man jetzt gut finden oder auch nicht, aber damit geben wir uns natürlich nicht zufrieden. Daher lassen wir einen Loop über verschiedene Anzahlen von Clustern laufen und sehen uns die Ergebnisse nebeneinander an. Dabei zeigt ein Colorbar an der Seite jeweils an, wie die Farben zu den Nummern der Cluster gehören.

9.3 Der Algorithmus DBSCAN, kurz und einfach erklärt, mit Beispiel¶

Als nächste Möglichkeit sehen wir uns einen Algorithmus an, der als DBSCAN bekannt ist. Diese Abkürzung steht für Density-Based Spatial Clustering of Applications with Noise, und das funktioniert wie folgt:

• Der Algorithmus durchsucht die Datenpunkte der Reihe nach, und klärt für jeden Datenpunkt, ob er ein core-sample ist
• Ein core-sample ist dadurch gekennzeichnet, dass es von einer bestimmten Anzahl anderer Samples höchstens einen bestimmten Abstand hat.
• Durch dieses Konzept der mindestens soundsoviele Punkte mit höchstens diesem Abstand voneinander wird eine Dichte beschrieben (daher density-based)
• Ein Cluster besteht dann in diesem Fall aus einer zusammenhängenden Menge von core-samples und allen Punkten, die von einem dieser core-samples höchstens den vorbestimmten Abstand haben (die selber aber keine core-samples sind, weil sie am Rand eines Clusters liegen, bzw. dort, wo er “weniger dicht” wird).
• Alle Punkte, die nicht innerhalb des vorgegebenen Abstands zu einem core-sample liegen, werden als Ausreißer bzw. Noise (Rauschen) gewertet und bekommen einen extra Label zugewiesen
• Kritische Parameter hier sind also:
  • Der Abstand, der die Dichte bestimmt, und
  • Die minimale Anzahl von Punkten, die es braucht, um core-samples zu finden

Schauen wir uns zunächst einmal von einem solchen Clustering den Output an:

Jetzt können wir natürlich auch hier einen Loop laufen lassen, der uns mehrere Darstellungen unseres Datensatzes mit verschiedenen Parametern zeigt. Am wichtigsten ist hier der voreingestellte Abstand, weshalb wir diesen über Werte in einer Liste variieren werden.

In den Figuren, die im Folgenden erzeugt werden, sehen Sie an der Seite wieder das Colorbar. Dort können Sie auch anhand der Skala sehen, wie viele Cluster jeweils erzeugt wurden.

Hier sieht man deutlich den Effekt der verschieden eingestellten Abstände. Bei kleinen Werten ergeben sich teils seltsame Muster. Erst bei mittelgroßen Werten erscheint das Clustering auch auf den ersten Blick sinnvoll. Bei zu großen Werten landen wieder alle Punkte in einem einzigen Cluster.

Was man ebenfalls anhand des Colorbars schön sehen kann, sind die jeweils als “Ausreißer” bzw. “Noise” eingestuften, ganz dunkelblauen Punkte.

9.4 Der Algorithmus K-Means, kurz und einfach erklärt, mit Beispiel¶

Als letzten Cluster-Algorithmus sehen wir uns noch einen sehr gebräuchlichen an, nämlich k-means. Dieser Algorithmus setzt ein Prinzip um, das uns vielleicht im Vergleich mit den beiden bisher erklärten noch etwas intuitiver erscheint, was nämlich die Bildung und Definition der Cluster betrifft. Hier sind die Eckpunkte von k-means:

• Die Anzahl $N$ der Cluster muss bei diesem Algorithmus vorgegeben werden und ändert sich auch während der Laufzeit des Algorithmus nicht.
• Der Datensatz wird in $N$ Cluster eingeteilt.
• k-means geht grundsätzlich von Daten auf der Basis von Koordinaten aus. Vorberechnete Differenzen nimmt er nur mit einigen Modifikationen an.
• Für jeden Cluster wird ein sogenanntes “Centroid” berechnet, also das Clusterzentrum. Zu beachten ist, dass das Clusterzentrum im Allgemeinen nicht einem der Datenpunkte im Datensatz entsprechen wird (also quasi ein extra-Punkt ist, der sich im Laufe der Zeit ändert).
• Diese Clusterzentren werden nun so optimiert, dass jeder Datenpunkt zu jenem Cluster gehört, dessen Centroid er am nächsten liegt.
• Das führt zu einer Optimierung der Varianz der Abstände der Datenpunkten zum Centroid in jedem Cluster
• Bei der Optimierung werden im wesentlichen zwei Schritte ausgeführt:
  • Zuordnung jedes Datenpunkts zum nächsten Centroid
  • Neuberechnung der Centroiden auf der Basis dieser Zuordnung
• Die wiederholte Ausführung dieser beiden Schritte wird bei Konvergenz der Centroiden-Positionen abgebrochen

Sehen wir uns das jetzt einmal in der Praxis an. Der Parameter, den wir hier variieren werden, ist wieder die Anzahl der Cluster.