Return to site

K-Means

Wie man mittels unüberwachtem Lernen Gruppen in Daten finden kann

· ML Algorithmen

Der K-means-Algorithmus ist ein Clustering Verfahren und somit ein unüberwachtes Lernverfahren. Das heißt, er versucht, aus einer Menge an Datenpunkten eine geeignete Gruppierung zu finden.

Beispiel Wohnungsmieten

Im Diagram sind Daten über Mietpreise in Wohnungen zu sehen. Ein Mensch erkennt sofort, dass der Mietpreis meist proportional zur Wohnungsgröße steigt, daneben gibt es noch ein paar Wohnungen, die überteuert sind (zu klein bei zu großem Preis) und ein paar Wohnungen, die unter Wert verkauft werden (zu groß bei zu kleinem Preis). Der K-means-Algorithmus soll die Daten für uns in die drei Gruppen einteilen.

K-Means allgemein

Der Algorithmus startet mit der Festlegung der Startpunkte. Diese repräsentieren den Mittelpunkt eines Clusters. Wir müssen dem Algorithmus am Anfang mitteilen, wie viele Cluster wir suchen, in diesem Falle sind es k = 3. Der Parameter k gibt dem Algorithmus seinen Namen. Wie im unten gezeigten Bild sind nun an drei zufälligen Stellen die Startpunkte.

Jeder Punkt im Diagram wird nun dem Cluster zugeordnet, dessen Mittelpunkt ihm am nächsten liegt. Sind alle Punkte zugeordnet, wird ein neuer Clustermittelpunkt berechnet und das Verfahren wiederholt. Der Mittelpunkt verschiebt sich dadurch in seine optimale Position. Wenn sich der Mittelpunkt nicht mehr verschiebt, dann ist das Clustering beendet.

Die Lage der Startpunkte ist essentiell für den Erfolg des K-means-Algorithmus. Ohne die menschliche Intuition ist es jedoch an dieser Stelle schwierig, zu bestimmen, wo die Startpunkte liegen müssen. Anstatt dessen wird das Clustering mehrmals wiederholt, dabei enstehen durch die verschiedenen Startpunkte eventuell verschiedene Cluster. 
Für jeden Durchlauf werden die Varianzen der Cluster addiert. Dadurch lässt sich vergleichen, wie die Qualität eines Clusters ist. Ist die Gesamtvarianz eines Durchlaufs hoch, heißt das, dass alle Cluster weit verstreut sind. Innerhalb der Cluster sollten die Punkte jedoch so nah wie möglich beieinander liegen. Der optimale Durchlauf ist also der, bei dem die Gesamtvarianz am niedrigsten ist.

Anzahl der Cluster

Bis jetzt muss der Mensch vorab festlegen, wie viele Cluster zu suchen sind. Da wir das Clustering jedoch automatisch ausführen möchten, muss ein Verfahren gefunden werden, das die Anzahl der Cluster automatisch bestimmt. Hier greift das Verfahren wieder auf die Bestimmung der Gesamtvarianz zurück. Eine niedrige Gesamtvarianz zeigt uns, wie nah sich die Punkte innerhalb eines Clusters sind. Wählen wir k = 1, liegen alle Punkte natürlich in einem Cluster und die Gesamtvarianz hat ihren höchsten Wert. Je kleiner k wird, desto kleiner wird auch die Gesamtvarianz. Am kleinsten ist sie, wenn k genauso groß ist wie die Anzahl der Datenpunkte. Dann ist die Varianz 0, da alle Punkte gleichzeitig die Mittelpunkte ihres eigenen Clusters sind, zu dem sie den Abstand 0 haben.

Das folgende Bild zeigt ein Diagram der Gesamtvarianz, das uns jedoch etwas anderes zeigt. Das Diagram wird auch Ellenbogen-Diagram genannt. Der "Ellenbogen" beschreibt die Stelle in dem Diagram, in dem der Graph einen starken Knick hat während davor und danach wenig Veränderung im Graph zu sehen ist. Davor steigt der Graph stark an, was bedeutet, dass eine Erhöhung von k stark zu einem besseren Clustering beiträgt. Ab dem "Ellenbogen" steigt der Graph nur noch schwach an, k zu erhöhen ist ab diesem Punkt nicht mehr sinnvoll, da das Ziel des Clusterings ist, möglichst wenige und allgemein gültige Gruppierungen in den Daten zu finden. Diesen "Ellenbogen"-Punkt zu bestimmen, ist ein eigenes Problem und soll nicht Teil dieses Artikels sein.

K-Means in hochdimensionalen Räumen

K-means funktioniert in beliebig vielen Dimensionen. Wichtig hierbei ist die Bestimmung der Distanz der einzelnen Punkte und die Bestimmung des Mittelpunkts eines Clusters. Meistens wird dabei die Euklidsche Distanz berechnet, im zweidimensionalen Raum auch als Pythagoras-Satz bekannt. Dass der Algorithmus auf ziemlich einfachen mathematischen Funktionen basiert, macht ihn zu einem extrem schnellen Algorithmus. Leider kann er auf Grund dieser Funktionen jedoch keine kategorischen und diskreten Daten clustern (z.B. ganzzahlige Werte oder Namen).

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OKSubscriptions powered by Strikingly