data > opinion

Tom Alby

02 k-Means

2020-08-20


Sie sind hier: start / lehrveranstaltungen / datenanalyse und machine learning mit excel / 02 k means /

Allgemeine Einführung in den Algorithmus

Die zuvor behandelte Lineare Regression ist ein Beispiel für überwachtes Lernen beziehungsweise Supervised Learning. Der Maschine werden Beispiele gezeigt, und daraus soll eine Art Regel entstehen. Bei k-Means handelt es sich um einen Algorithmus, der dem Unsupervised Learning zuzuordnen ist, d.h. es gibt hier keine Vorgaben bis auf die Daten selbst, aus denen der Algorithmus Muster erkennen soll. Er fällt in die Kategorie Exploratory Data Mining.

Dazu nehmen wir einen Datensatz über Weine als Untersuchungsobjekt. In der folgenden Tabelle sind drei verschiedene Weintypen enthalten (Spalte Type), die Weine unterscheiden sich aber auch so.

Type Alcohol Malic Ash Alcalinity Magnesium Phenols Flavanoids Nonflavanoids Proanthocyanins Color Hue Dilution Proline
1 14.23 1.71 2.43 15.6 127 2.80 3.06 0.28 2.29 5.64 1.04 3.92 1065
1 13.20 1.78 2.14 11.2 100 2.65 2.76 0.26 1.28 4.38 1.05 3.40 1050
1 13.16 2.36 2.67 18.6 101 2.80 3.24 0.30 2.81 5.68 1.03 3.17 1185
1 14.37 1.95 2.50 16.8 113 3.85 3.49 0.24 2.18 7.80 0.86 3.45 1480
1 13.24 2.59 2.87 21.0 118 2.80 2.69 0.39 1.82 4.32 1.04 2.93 735
1 14.20 1.76 2.45 15.2 112 3.27 3.39 0.34 1.97 6.75 1.05 2.85 1450

Die spannende Frage ist, ob ein Algorithmus die verschiedenen Typen identifizieren kann anhand ihrer unterschiedlichen Eigenschaften. Dies wird Clustering genannt. Bei k-Means muss zunächst definiert werden, wie viele Cluster es geben soll, genau dafür steht nämlich das k. Bei den Weinen wissen wir schon, wie viele Cluster wir haben, daher können wir dies dem Algorithmus einfach vorgeben und dann sehen, wie gut er die Weine tatsächlich gruppieren kann. Wir könnten ihm auch nur einen Teil der Weine zum Training geben und dann schauen, ob er bei einem Wein aus dem anderen Teil dann erkennen kann, zu welcher Gruppe er gehört. Allerdings stehen hier nur sehr wenige Daten zur Verfügung, so dass wir uns einfach nur anschauen, ob k-Means es von alleine schafft, die Weine richtig zu gruppieren.

Der Wein-Datensatz hat einen großen Vorteil, denn bis auf den Typ bestehen alle Daten aus Zahlen. So können wir sie auch plotten, hier als Beispiel Alkoholgehalt versus Säure:

In diesem Plot ist noch kein eindeutiges Muster zu erkennen, aber der zweidimensionale Raum ermöglicht die Veranschaulichung des Algorithmus. Wenn in diesen Raum drei Centroiden gesetzt werden, auf Deutsch vielleicht “Mittelpunkte” genannt, um die die einzelnen Datenpunkte gruppiert werden sollen, dann stellt sich die Frage, wo genau die Centroids gesetzt werden können, um die bestmögliche Abgrenzung zu ermöglichen.

Hier kommen wieder Abstände ins Spiel, veranschaulicht in der folgenden Animation an anderen Daten. Die Mittelpunkte werden zunächst zufällig gesetzt und dann geschaut, wie weit die einzelnen Mitglieder eines Clusters von dem jeweils nächsten Mittelpunkt entfernt sind. Um nun die tatsächlichen Mittelpunkte zu finden, versucht der Algorithmus die quadratischen Abweichungen der durchschnittlichen Entfernung jedes einzelnen Datenpunkts von dem Mittelpunkt zu optimieren. Durch Umsetzen des Mittelpunkts kann es dazu kommen, dass ein Punkt wieder einem anderen Mittelpunkt zugeordnet wird.

Die Cluster für den Wein sehen wie folgt aus:

Hat der Algorithmus die richtigen Cluster gefunden? Da k-Means die Centroiden zufällig auswählt, werden die Labels jedes Mal unterschiedlich verteilt sein, so dass andere Typen-Labels verwendet werden. Wir müssen also schauen, ob Elemente desselben Typs dasselbe Cluster bekommen haben, auch wenn die Bezeichnung eine andere ist. Dies kann visualisiert werden, in dem einfach die Paare gezählt werden und die Gruppenzuordnung (V1 ist der Original-Typ, V2 das von k-Means berechnete Cluster) mit der Anzahl der Paare geplottet wird. Die Anzahl ist durch die Größe des jeweiligen Punkts visualisiert:

Wie man schön sehen kann, hat k-Means die meisten Weine in dieselbe Gruppe geclustert wie sie auch zuvor eingeordnet waren.

Implementierung mit Excel

Die Implementierung in Excel erfordert leider ein wenig mehr Handarbeit. Zunächst müssen die Werte aus den Beispiel-Daten standardisiert werden. Dazu wird zunächst der Mittelwert gebildet jeder Spalte und dann die Standardabweichung berechnet. Zum Schluss werden alle Werte mit der Formel

=STANDARDISIERUNG(WERT;DURCHSCHNITT;STANDARDABWEICHUNG)

neu berechnet in neue Zellen überführt. Im nächsten Schritt werden dann Spalten für jedes Cluster eingeführt, die zunächst einmal leer bleiben. Dann werden die Entfernungen jedes Weines zu diesen Clustern berechnet, und zwar anhand der Euklidischen Distanz. Dies könnte für ein Cluster so aussehen:

=WURZEL(STABW((ZELLEN DER WEINWERTE- ZELLEN DES CLUSTERS)^2))

Da wir 3 Cluster haben, muss dies also drei Mal durchgeführt werden. Dann wird für jeden Abstand noch der Min-Wert und ein Vergleich-Wert hinzugefügt.

Zum Schluss müssen wir noch eine Zielzelle hinzufügen, anhand der optimiert werden kann; dies ist in unserem Beispiel die Summe aller minimalen Entfernungen. Nun kann der Solver angeworfen werden:

Wichtig: Der Solver kommt leider nicht mit sehr vielen Daten klar. Dann kann die folgende Fehlermeldung erscheinen:

Zu viele Variablen (Excel Solver)

Im Zweifel müssen Zeilen gelöscht werden, um das Beispiel durchrechnen zu können. Nun kann Excel dabei beobachtet werden, wie es die jeweiligen Cluster durchrechnet:

Weitere Punkte