KI - Technik und Anwendungen

9 Unüberwachtes Lernen – Clustering

Nachdem wir mit der Regression und der Klassifikation die wichtigsten Formen des Überwachten Lernens kennengelernt haben, schauen wir uns nun an, wie Maschinen ohne Überwachung Muster in Daten aufspüren können. Dementsprechend werden solche Verfahren dem Unüberwachten Lernen zugeordnet. Unüberwachtes Lernen kann sehr nützlich sein, wenn große Datenmengen erst einmal vorgruppiert werden sollen, bevor ein Mensch eigene Überlegungen dazu anstellt. Das Aufteilen von Datenmengen in einzelne zusammengehörende Gruppen nennt man Clustering. Cluster sind Punktwolken aus ähnlichen Datenpunkten.pastedGraphic.png
Menschen fällt es leicht, Cluster zu bilden und damit die Zusammengehörigkeit von Datenpunkten zu erkennen. Bei den riesigen Datenmengen, die heute in Forschung und Wirtschaft anfallen, ist es oft erforderlich, diese Daten mit Maschinen zu clustern, um überhaupt einen Überblick zu erhalten. Dafür gibt es verschiedene Algorithmen. Wir schauen uns den verbreiteten k-Means-Algorithmus an.

Was ist das?
k-Means ist ein ML-Algorithmus des Unüberwachten Lernens, der es ermöglicht, eine beliebige Datenmenge in eine Anzahl k unterscheidbare Cluster zu organisieren (k steht für eine beliebige positive ganze Zahl). Man speist Daten und die Anzahl der erwarteten Cluster ein, und der Algorithmus weist jeden einzelnen Datenpunkt einem der k Cluster zu.

Beispiel: Eddy hört den ganzen Tag Hip-Hop und gilt unter seinen Freunden schon als ein kleiner Experte. Man spielt ihm einfach etwas vor, und er sagt dann oft so etwas wie: „Cooler East Coast Rap, Alter.“ Oder: „Oh Mann, das ist typisch West Coast Rap.“ Sein Bruder Elon ist noch nicht so der Kenner und fragt ständig nach, woran man das erkennen kann. Eddy will aber nicht den ganzen Tag erklären, was es mit den beiden Sorten von Hip-Hop auf sich hat. Er gibt seinem Bruder erst mal seine Playlist, auf der alle möglichen Songs von East und West Coast Hip-Hop gemischt sind. Elon soll sich mal selber da reinhören und dann im Internet nachgucken, was das für Hip-Hopper sind und zu welcher Richtung sie gehören.

Nun ist Elon mehr der Computer-Nerd und denkt sich: „Mann, das sind ja über 30 Alben! Bis ich die alle angehört und nachgeschlagen habe, das dauert ja Wochen. Das werde ich mal meinen Computer machen lassen.“ Elon hört kurz in einige Songs rein, und dabei fallen ihm zwei Merkmale besonders auf: Einige Tracks sind eher jazzig und andere eher funky. Außerdem sind einige der Songs sehr aggressiv vom Beat her, andere sind eher cool und relaxed. Eddy macht auf seinem Computer eine Tabelle auf und trägt die Alben dort ein. In Spalte 1 kommt der Name des Hip-Hoppers, in Spalte 2 ein Wert zwischen 1 und 10, je nachdem ob das Album er funky (1) oder jazzy (10) klingt. In Spalte 3 trägt Elon ein, ob das Stück eher cool (1) rüberkommt oder aggressiv (10) .

Album Funky – Jazzig Cool – Aggressiv
1 1 1
2 10 10
3 10 9
4 9 9
5 2 2
6 1 1
7 10 10
8 1 1
9 3 2
10 1 1
11 2 1
12 9 8
13 8 7
14 7 7
15 7 10

Danach lässt Elon sich ein Schaubild erzeugen, in dem die Wertekombinationen als Punkte angezeigt werden.

pastedGraphic_1.png

Aha, denkt Elon, da sieht man ja schon etwas Interessantes. Das Schaubild zeigt, dass sich die Tracks in zwei Gruppen, sogenannte Cluster, aufteilen lassen. Er sucht ein wenig im Internet herum, um mehr über Cluster zu erfahren, und findet bald schon ein paar interessante Videos, wie man diese Cluster mit KI automatisch errechnen kann. Die wichtigste Methode scheint der sogenannte k-Means-Algorithmus zu sein.

Wie funktioniert es?
Clusterbildung mit k-Means funktioniert folgendermaßen: Aus einer Reihe von Eingangsdaten wird automatisch eine Anzahl von Clustern errechnet, und zwar so, dass jeder Punkt der Eingangsdaten einem Cluster zugeordnet wird. Und das Schönste: Das geht ganz automatisch. Man muss nichts trainieren oder vorher zuweisen. Auch muss man nichts überwachen: Das Lernen funktioniert unüberwacht. Das Einzige, was man vorgeben muss, ist die Anzahl der Cluster, die man erwartet. Im Fall von Elon war es klar, dass es zwei Cluster gibt (East-Coast und West-Coast), in anderen Fällen ist es nicht immer klar, wie viele Cluster es am Ende gibt. Da hilft dann oft eine Visualisierung wie oben und dann ein Ausprobieren mit einer bestimmten Anzahl von Clustern. Und hier das Ganze noch einmal Schritt für Schritt, diesmal für k=3, also drei Cluster:

Quelle: Wikipedia, Lizenz CC-BY-SA (3.0) https://de.wikipedia.org/wiki/K-Means-Algorithmus#/media/Datei:K_Means_Example_Step_4.svg

Und noch mal als Video. Schau Dir hier die Erklärung des k-means Algorithmus bei YouTube an.

 

Vorteile/Nachteile

Vorteile: Einfacher Algorithmus, effizient auch für große Datenmengen.
Nachteile: Man muss die Anzahl der Cluster (k) vorgeben.

 Elon speist die Daten aus der Tabelle in den k-Means-Algorithmus ein und erhält folgende Ausgabe:

Die beiden roten Kreuze markieren die Mittelpunkte der beiden Cluster (im Englischen „centroids“ genannt). Der Algorithmus spuckt auch die genauen Koordinaten der Centroids aus. Es sind die Punkte (1.57, 1.28) und (8.75, 8.75).

Das Coole am k-Means-Algorithmus ist, dass man die Centroiden nutzen kann, um neue Datenpunkte zu klassifizieren, also zuzuordnen, welchem Cluster sie zugehören. Datenpunkte gehören zu dem Cluster, zu dessen Centroiden sie den geringsten Abstand haben. Der Centroid kennzeichnet den typischen Fall eines Clusters.

Elon ahnt jetzt schon, welcher Cluster East-Coast (rechts oben) ist und welcher West-Coast (links unten). Er schaut noch einmal bei Wikipedia für ein paar Alben nach und findet sich bestätigt. Seine Kriterien, die Songs zu kategorisieren, waren also gar nicht so schlecht. Als ihm sein Bruder wieder einen neuen Track vorspielt, merkt er gleich: sehr cool und funky. Er sagt dann ganz lässig: „Cool, und typisch West-Coast, Digga.“ Sein Bruder sagt: „Genau, jetzt hast du es gerafft, kaum einer ist cooler und mehr West-Coast als Snoop.“

Wirtschaft
Das Clustering von Daten ist ein wichtiges Instrument in der Forschung und der Wirtschaft. In der Forschung kommt es oft vor, dass man neue Ergebnisse finden will, die man noch nicht vorhersehen kann. k-Means bietet ein einfaches Verfahren, das in große, unübersichtliche Datenmengen eine vorläufige Struktur bringt. Auch in der Wirtschaft ist bei massenhaft anfallenden Kundendaten das Clustering sehr beliebt. Im Marketing werden z.B. Kunden anhand ihrer Nutzungsdaten gerne in Gruppen zusammengefasst, für die man jeweils bestimmte Marketingstrategien erarbeiten kann. So könnte z.B. ein Online-Händler versuchen, seine Kunden anhand von Häufigkeit der Bestellungen und Preis der gekauften Produkte zu clustern und herausfinden, welche typischen Kundengruppen er hat: Z.B. einige, die ganz häufig kleine Produkte kaufen, diejenigen, die ganz selten, dann aber ganz teure Produkte kaufen, und diejenigen, die regelmäßig mittelteure Produkte kaufen.

Gesellschaft und Individuum
Das Clustering von Kundengruppen ist in einer konsumorientierten Massengesellschaft ein wichtiges Instrument, um effiziente Dienstleistungen und Produkte anzubieten. Allerdings kann das auch Nachteile haben, wenn die Klassifikationen, die ein Algorithmus vornimmt, nicht mit dem Selbstverständnis der Menschen übereinstimmt. Personen könnten anhand bestimmter Verhaltensmuster in eine bestimmte „Ecke“ gestellt werden. So könnte ein Algorithmus einen Kunden beispielsweise als anfällig für Extremismus einstufen, weil er bestimmte Produkte kauft: Literatur über Extremismus und zugleich Baseballschläger. Dabei könnte das aber auch einfach ein Extremismusforscher sein, der gerne Baseball spielt. (Eventuell: Beispiel Rice cooker/bag pack)