In diesem Blog wird die Lernerfahrung beschrieben aus dem Online-Kurs „Machine Learning A-Z™: Hands-On Python & R In Data Science”. Ich gehe in diesem Blog der Frage nach, inwieweit sich dieser Kurs für IT Projektleiter und Product Owner eignet, um ein besseres Verständnis für Maschinenlernen / Künstliche Intelligenz zu bekommen – und zwar ohne tiefere Vorkenntnisse. Denn: Maschinenlernen bzw. Künstliche Intelligenz wird in der Softwareentwicklung eine wachsende Bedeutung einnehmen; in absehbarer Zeit dürfte es nur noch wenige Softwareprojekte geben, die gänzlich ohne Maschinenlernen auskommen. In den Worten von Google-Chef Sundar Pichai: „Wir werden uns von einer Mobile-first-Welt in eine KI-first-Welt bewegen“, wo der Computer ein mit Künstlicher Intelligenz (KI) ausgestatteter Sprachassistent sein wird.

In dieser Artikelserie zum udemy Academy-Kurs vermittele ich einige ausgewählte, wesentliche Knowledge Nuggets, die ein gutes Verständnis von der inhaltlichen Ausrichtung des Online-Kurses und gleichzeitig einige wesentliche Lerninhalte vermitteln. Dieser Überblick ist ein Appetizer und soll den Online-Kurs selbstverständlich nicht ersetzen.

Hier geht’s zu den ersten drei Teilen der Serie:

• Maschinenlernen für Product Owner, IT Projektmanager (Teil 1) – Einführung und Datenaufbereitung
• Maschinenlernen für Product Owner, IT Projektmanager (Teil 2) – Regressionsverfahren
• Maschinenlernen für Product Owner, IT Projektmanager (Teil 3) –Klassifizierungsverfahren

Maschinenlernen / Künstliche Intelligenz – Clusteranalyse mit dem K-Means Algorithmus

Der vierte Teil des Online-Kurses zum Maschinenlernen widmet sich der Clusteranalyse bzw. Clusterbildung, also: Identifikation von Clustern bzw. Datensegmenten in einer beliebigen Menge an Datenpunkten. Es werden zwei Methoden aus dem Maschinenlernen vorgestellt, die erste ist der K-Means-Algorithmus.

Eine zentrale Frage für die Clusterbildung ist diejenige nach dem Kriterium für die Zuordnung eines Datenpunktes zu einem Cluster. Zunächst einmal kann man sich schnell darauf einigen, dass die geometrische Distanz hierfür ein gutes Kriterium ist. Typischerweise wird für die Bestimmung der Distanz zwischen zwei Punkten die Euklidische Distanz herangezogen, die bei Methoden des Maschinenlernens immer wieder eine Rolle spielt (vgl. vorangegangene Kursteile):

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Euklidische Distanz

Bei der Zuordnung eines Punktes zu zwei bestehenden Clustern stellt sich dann aber durchaus die Frage, wie die Nähe (bzw. Zugehörigkeit) dieses Punktes zu den Clustern bestimmt werden soll. Dies ist mathematisch nicht mehr eindeutig. Man könnte die Distanz des Datenpunktes zu dem nächstgelegenen Datenpunkt innerhalb der bestehenden Cluster heranziehen. Oder: Die Distanz zu den am weitesten entfernten Datenpunktes innerhalb der bestehenden Cluster. Man könnte die Distanzen zu allen Datenpunkten eines Clusters berechnen, daraus den Durchschnitt bilden. Oder (und diese Option wird auch für die weiteren Überlegungen zugrunde gelegt) man berechnet den Mittelpunkte des Clusters und bestimmt den Abstand eines Datenpunktes hierzu.

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Distanz zwischen Clustern

Damit sind die grundlegenden Fragen geklärt und wir können uns einmal die Anwendung des K-Means Algorithmus als Methode des Maschinenlernens ansehen. Vorweg sei gesagt: Der K-Means Algorithmus ermittelt Cluster für eine vorgegebene Anzahl von Clustern – die Entscheidung, welche Anzahl von Clustern richtig ist, wird auf Basis einer anderen Methode getroffen (diese wird weiter unten vorgestellt). Es geht also darum, für eine vorgegebene Anzahl von Clustern, ebendiese Clusterbildung für eine gegebene Anzahl von Datenpunkten vorzunehmen. Wir legen also eine Anzahl von Clustern fest. Nämlich: 2

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Auswahl der Anzahl von Clustern

Dann platzieren wir im Zweiten Schritt zwei Punkte, welche die Mittelpunkte der Cluster bilden, absolut beliebig bzw. zufällig (!). Für jeden der Datenpunkte ermitteln wir nun die Distanz zu allen (zufällig gesetzten) Cluster-Mittelpunkten. Wenn die Zuordnung aller Datenpunkt abgeschlossen ist, ermitteln wir für diese Datenpunkt-Wolken jedes (vorläufigen) Clusters den NEUEN Cluster-Mittelpunkt.

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Neuberechnung des Clustermittelpunktes

Da sich der Cluster-Mittelpunkt verschiebt, ergibt sich auch eine neue Zuordnung der Datenpunkte, da sich mit der Verschiebung der Cluster-Mittelpunkte auch die Distanz zu ebendiesen Mittelpunkten verändert. Es ergeben sich neue „Cluster-Punktwolken“. Diese Neuberechnung der Cluster-Mittelpunkte und Neu-Zuordnung der Datenpunkte wird so lange vorgenommen, bis der K-Means Algorithmus konvergiert, das heißt: Es gibt keine Verschiebungen mehr. Die Cluster-Bildung ist abgeschlossen.

Was an diesem K-Means Algorithmus überrascht, ist die zufällige Platzierung der ersten vorläufigen Cluster-Mittelpunkte. Es stellt sich die Frage, ob man von allen zufällig gewählten Startpunkten immer zum gleichen Ergebnis kommt. Betrachten wir etwa das intuitive Ergebnis für drei (3) Cluster bei gegebenen Datenpunkten:

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Random Initialization Trap

Tatsächlich ist es so, dass der K-Means Algorithmus bei anderer Wahl der Startpunkt auch zu einem anderen Ergebnis kommen kann, vergleiche nachfolgende Abbildung:

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Random Initialization Trap

Dies nennt man die Random Initialization Trap im Zusammenhang mit dem K-Means Algorithmus. Glücklicherweise bieten die Bibliotheken, die in Python und R zur Verfügung stehen, Parameter an, um dieses Problem zu neutralisieren. In Python nutzt man hier eine Weiterentwicklung des Algorithmus, die kmeans++ genannt wird.

Betrachten wir abschließend die wichtige Frage, wie der Data Scientist / Datenwissenschaftler entscheidet, welche Anzahl von Cluster für eine gegebene Menge an Datenpunkten Sinn machen. Als Ausgangspunkt wird hierfür ein Maß für die Homogenität von Datenclustern herangezogen, die analog der Kleinste Quadratemethode bei Regressionsverfahren funktioniert. Dieses Maß heißt Within-Cluster-Sum-of-Squares (WCSS) und ermittelt den Abstand eines jeden Punktes eines Clusters zum Cluster-Mittelpunkt; dieser Abstand wird quadriert. Je kleiner WCSS, desto homogener die Cluster.

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Within-Cluster-Sum-of-Squares (WCSS)

Im extremsten Fall bildet jeder Datenpunkt ein eigenes Cluster. In diesem Fall gilt: Der Abstand zwischen einem Datenpunkt zum Mittelpunkt des zugehörigen Clusters (der Punkt selbst) ist also NULL. Die Metrik WCSS ist für diesen Fall also Null. Die Optimierung kann also nicht darin bestehen, WCSS zu minimieren, denn damit würde die Lösung immer darauf hinauslaufen, für jeden Datenpunkt ein eigenes Cluster zu bestimmen.

Der Datenwissenschaftler hingegen trägt die Anzahl der Cluster und den errechneten Wert für WCSS in einem zweidimensionalen Koordinationsystem ab, man erhält folgendes Bild:

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Die Elbow-Methode

Man erkennt hier, dass die Erhöhung der Anzahl von Clustern zunächst eine starke Verbesserung des Homogenitätsmaßes WCSS bedeutet, doch bereits die Erhöhung von 3 auf 4 Cluster bringt nur noch eine minimale Verbesserung. Der Datenwissenschaftler nennt dies die Elbow Method, man ermittelt jenen Punkt, in dem die Kurve mit zunehmender Anzahl von Clustern abflacht. Der Name der Methode rührt daher, dass der Wendepunkt im Verlauf dieser Kurve an einen Ellenbogen erinnert.

Im praktischen Teil dieses Kurses (ich habe das in Python umgesetzt) starten wir mit einem Datenset, das wie folgt aussieht:

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Umsetzung in Python – Beispieldatensatz

Für die Nutzer eines Online-Shops liegt unter anderem die Information über das (geschätzte) Jahreseinkommen vor, das Kaufverhalten wird im sogenannten Spending Score auf einer Skala von 1 bis 100 bewertet. Nach der Clusteranalyse ergibt sich folgendes Bild:

Abbildung: Clusteranalyse mithilfe des K-Means-Algorithmus. Umsetzung in Python – Visualisierung des Ergebnisses

Maschinenlernen / Künstliche Intelligenz – Clusteranalyse mithilfe des Hierarchical Clustering

Die Methode des Hierarchical Clustering lässt sich in zwei Varianten umsetzen: Zum einen die agglomerierende Methode (diese wird im Folgenden vorgestellt), zum anderen die Teilende Methode. Bei der agglomerierenden Methode wird in der Ausgangssituation jeder Datenpunkt als Cluster betrachtet. Im ersten Schritt werden aus einer Menge von Datenpunkten (Datenpunkt = Cluster in der Ausgangssituation) jene beiden Punkte zu einem Cluster verbunden, die am nächsten beeinander liegen (anders ausgedrückt: niedrigste Euklidische Distanz). Für neu gebildete Cluster wird der Cluster-Mittelpunkte gebildet. Dann werden diejenigen Punkte/Cluster miteinander verbunden, die nun die geringste Distanz zueinander aufweisen. Dieses Verfahren wird iterativ so lange durchgeführt, bis alle Datenpunkte in einem Cluster zusammengeführt sind. So weit, so einfach.

Die Methode des Hierarchical Clustering generiert ein sogenanntes Dendrogramm, das wie folgt aussieht:

Abbildung: Clusteranalyse mithilfe des Hierarchical Clustering. Das Dendrogramm

Hier werden auf der X-Achse alle (!) Datenpunkte abgetragen. Auf der Y-Achse findet sich die Euklidische Distanz. Nehmen wir (vgl. obige Abbildung) die Punkte „P2“ und „P3“. Wenn diese zu einem Cluster verbunden werden, dann wird die Euklidische Distanz zwischen diesen beiden Punkten ermittelt (Y-Achse!), dann werden diese beiden Punkte im Dendrogramm miteinander verbunden in der angezeigten Weise. Wird das Cluster der beiden Punkte „P2, P3“ um den Punkte „P1“ erweitert, dann wird die Euklidische Distanz zwischen „P1“ und „P2, P3“ ermittelt, die neue Verbindung wird in der angezeigten Schreibweise im Dendrogramm abgetragen.
Im Ergebnis erhält man für die einfache Ausgangssituation von 6 Datenpunkten folgendes Dendrogramm:

Abbildung: Clusteranalyse mithilfe des Hierarchical Clustering. Das Dendrogramm

Das Dendrogramm erlaubt nun diverse Aussagen und Methoden zur Clusterbildung. Man kann hier etwa visuell erkennen, wie hoch die (maximale) Euklidische Distanz innerhalb verschiedener Zweige im Dendrogramm ist. Wenn man etwa als Kriterium für die Cluster-Bildung formuliert, dass die Cluster so gebildet werden, dass die Euklidische Distanz zwischen den Punkten maximal 1,75 betragen soll, dann setzt man eine Horizontale auf Höhe von 1,75 (Y-Achse) in das Dendrogramm. Im Fall unseres einfachen Beispiels kreuzt eine solche Horizontale (vgl. Abbildung) das Dendrogramm an zwei vertikalen Linien. Das heißt: Mit diesem Kriterium ergeben sich zwei Cluster.

Es gibt für das Dendrogramm auch eine Methode zur Bestimmung der optimalen Anzahl von Clustern, die analog zur Elbow Methode im Zusammenhang mit dem K-Means Algorithmus funktioniert:

Man verlängert alle (!) horizontalen Linien im Dendrogramm über die gesamte Breite des Koordinatensystems und ermittelt dann jene vertikale Linie, die am größten ist und nicht von einer horizontalen Linie gekreuzt/geschnitten wird. Durch eben diese vertikale Linie legt man dann eine Horizontale und kann die optimale Anzahl der Cluster abzählen:

Abbildung: Clusteranalyse mithilfe des Hierarchical Clustering. Bestimmung der optimalen Anzahl von Clustern im Dendrogramm

Die Umsetzung dieser Methode in Python ist insofern verblüffend, als die zur Verfügung stehende Bibliothek die Umsetzung in nur wenigen Codezeilen ermöglicht:

Abbildung: Clusteranalyse mithilfe des Hierarchical Clustering. Code in Python zur Generierung des Dendrogramms

Das Ergebnis, ein Dendrogramm mit Hundert Datenpunkten:

Abbildung: Clusteranalyse mithilfe des Hierarchical Clustering. Code in Python. Das Dendrogramm

Mit Abschluss von Teil 4 sind ca. 50% des Kurses absolviert!

Hier geht’s zum Kursteil 5. Dieser Kurs behandelt mathematische Verfahren, mit deren Hilfe etwa Produktempfehlungen in Online-Shops vorgenommen werden können („Kunden, die dieses Produkt gekauft haben, haben sich auch für … interessiert“), mathematisch ausgedrückt: Association Rule Learning.