6.7 Übungsaufgabe Clustering

In dieser Übungsaufgabe zum Themengebiet Clustering können Sie anhand zwei unterschiedlichen Datenbeispiele die Cluster-Methoden anwenden und näher kennenlernen. Im ersten Beispiel versuchen Sie anhand von Messdaten von italienischen Weinen unterschiedliche Sorten festzustellen. Das zweite Beispiel behandelt die Daten der Fußball-Länderspiele zwischen 1871 und 2017, indem Gruppen ähnliche Teams gebildet werden sollen.

Ziel der Übung

In dieser Übung werden Sie die drei verschiedenen Clustering-Methoden k-Means, Hierarchisches Clustering und DBSCAN anwenden, hierbei sind eventuell Vorbereitungsschritte nötige. Bei den Verfahren selbst soll mit unterschiedlichen Parametern experimentiert werden. Schließlich werden die Ergebnisse verglichen und die Cluster sowohl intern als auch extern validiert.

Vorbereitetes Übungsmaterial:
Clustering

Weindaten

Da Clustering mit großen Daten und vielen Dimensionen viel Zeit in Anspruch nehmen kann, haben wir ein kleines Beispiel gewählt. Es enthält die Ergebnisse chemischer Analysen von 178 italienischen Weinen aus derselben Region, aber verschiedener Sorten – wie viele unterschiedliche Sorten es tatsächlich sind, sollen Sie versuchen mit Hilfe von Clustering zu ermitteln. Der Datensatz (wine_unlabeled.csv) ist dem Workspace bereitgelegt. Für die spätere externe Validierung liegt zudem die Datei wine_labels.csv bei. Die Daten stammen aus dem Machine Learning Repository der University of California, Irvine (UCI). Pro Beobachtung sind 13 verschiedene Analysewerte vorhanden, die in den Spaltenüberschriften beschrieben sind.

Vorbereitung

Die bereitgestellten Workflows enthalten bereits einige Knoten; ergänzen Sie die in den Teilaufgaben spezifizierten Knoten.

  • Im schon vorhandenen Normalizer-Knoten können Sie die Normalisierungsfunktion variieren, um deren mögliche Auswirkung auf das Clustering zu sehen.
  • Mit Hilfe der Statistik-Knoten können Sie die Daten auf mögliche Abhängigkeiten zwischen den Attributen untersuchen.

Aufgabe 1 — k-Means

Vervollständigen Sie den Workflow 01-k-means für das k-Means-Clustering. Spielen Sie etwas mit dem Wert von k und lassen Sie sich jeweils die Ergebnistabelle mit den Clusterzuordnungen anzeigen.

Um einen guten Wert für k zu finden, soll das Verfahren für k=2, 3, …, 20 durchgeführt und verglichen werden. Um das Ganze nicht 20x von Hand ausführen zu müssen, liegt dem Workspace der Workflow 00-loop-example, der beispielhaft die Funktionsweise einer Loop aufzeigt. In diesem werden die Werte für k aus einer vordefinierten Tabelle (mit nur einer Spalte) einzeln als Flow Variable erzeugt und “fließen” als Flow-Variable durch den gesamten Loop-Abschnitt des Workflows. Vor dem Ende der Loop-Iteration wird zu einer Tabelle jeweils eine Zeile hinzugefügt. Damit können Sie die Ergebnisse aus den Durchläufen sammeln.

Wenn Sie an der Stelle Do something… den k-Means-Knoten einfügen, können Sie die Flow-Variable vom Loop-Knoten an diesen übergeben (rote Line) und dort als Wert für die Anzahl der Cluster verwenden. Um die Clustering-Ergebnisse für die unterschiedlichen Werte von k zu vergleichen, nutzen Sie die folgenden Validierungsverfahren.

Interne Validierung

Für eine interne Validierung der Cluster-Qualität (d.h. ohne zusätzliche Informationen wie Labels) kann man die Summe der Quadrate der Abstände zum jeweiligen Clusterzentrum heranziehen. Da es hierfür keinen einzelnen KNIME-Knoten gibt, ist im Workflow ein Weg skizziert, den Sie noch vervollständigen sollen. Dabei werden für jeden Datenpunkt (Zeile) der Tabelle zunächst die Mittelwerte aller Attribute im jeweiligen Cluster hinzugefügt (Joiner). Diese Mittelwerte findet man in der zweiten Output-Tabelle des k-Means-Knotens. Danach werden zur einfacheren Weiterberechnung alle Spalten entfernt, die nicht Original-Attribute oder deren Mittelwerte enthalten (Column Filter). Ein Java Snippet-Knoten berechnet dann für jeden Punkt das Quadrat der Distanz zu seinem Clusterzentrum und schreibt diese in eine neue Spalte. Alle anderen Spalten werden nun weggefiltert (Column Filter). Schließlich wird die Summe aller Zeilen gebildet, um das Schlussergebnis zu berechnen (GroupBy).

Vergleichen Sie die Ergebnisse für die unterschiedlichen k. Was fällt Ihnen auf? Warum lässt sich ein “bester” Wert für k nicht direkt ablesen? Überlegen bzw. prüfen Sie, welches Ergebnis man für k=178 erhält (178 ist die Gesamtzahl der Datenreihen, also die maximal mögliche Zahl von nicht-leeren Clustern).

Um einen "guten“ Wert für k zu finden, sollte man daher auf den Grad der Änderung des Summenwerts bei steigendem k schauen und größere Sprünge entdecken(man nennt dies auch die Elbow-Methode). Fügen Sie hierzu einen geeigneten Visualisierungsknoten im Workflow ein.

Externe Validierung

Für eine externe Validierung steht eine Datei mit Labels zur Verfügung (wine-labels.csv). Mit dem Entropy Scorer-Knoten können Sie die Cluster mit den tatsächlichen Weinsorten (Labels) in Beziehung setzen und jeweils einen Quality-Wert ermitteln; eine geringere Entropie bedeutet höhere Qualität.

Vergleichen Sie auch hier die Werte für die unterschiedlichen Werte für k. Bekommen Sie ein ähnliches Ergebnis wie bei der internen Validierung?

Aufgabe 2 — Hierarchisches Clustering

Führen Sie das Hierarchische Clustering auf denselben Daten durch. Im entsprechenden KNIME-Knoten muss wie bei k-Means eine Anzahl von Clustern vorgegeben werden. Diese hat aber keine Auswirkung auf das Clustering selbst, sondern dient lediglich dazu, aus dem erzeugten Dendrogramm den Clustering-Level, also die “Granularität” der gewünschten Cluster zu wählen. Wechseln Sie zwischen verschiedenen Distanzmaßen (Euclidean, Manhatten) sowie Linkage-Typen (Single, Complete, Average), um potenzielle Unterschiede im Clustering zu sehen. Nehmen Sie hier eine externe Validierung vor, um unterschiedliche Clusterungen zu vergleichen.

Aufgabe 3 — Dichtebasiertes Clustering mit DBSCAN

Nutzen Sie den bereitgestellten Workflow 03-dbscan, um DBSCAN für die Weindaten zu implementieren. Für den DBSCAN-Knoten müssen als Input die Distanzen zwischen den Datenpunkten berechnet werden, was mit Hilfe des Distance-Matrix-Knotens möglich ist

In DBSCAN muss ein Wert für Epsilon (Radius) und Minimum points (Mindestanzahl von Nachbarn im Radius) vorgegeben werden. Um passende Werte für Epsilon zu finden, bietet es sich an, die im Buch erläuterte Methode der kNN-Distanz zu nutzen. Hierfür ist im Workflow ein möglicher Weg aufgezeigt, bei dem mit Hilfe des Similarity-Search-Knotens aus der Distanzmatrix für jeden Punkt die k nächsten Nachbarn und deren Distanz ermittelt werden. Die Distanz zum k-nächsten Nachbarn können Sie dann weiter verwenden, um mit Hilfe eines Liniendiagramms (Line Plots) in der Verteilung einen “Knick” (falls vorhanden) zu ermitteln. Der y-Wert (Distanz) am “Knickpunkt” der Kurve bildet eine Obergrenze für Epsilon (ein guter Wert für Epsilon liegt in der Regel unterhalb dieses Werts).

Nehmen Sie auch hier eine externe Validierung vor.(Die o.g. interne Validierung wäre hier wenig aussagekräftig. Warum? Denken Sie an die Art, wie Cluster gebildet werden.)

Zusammenfassung und Vergleich

Mit welchem Verfahren und welchen Parametern haben Sie die besten Clustering-Ergebnisse bekommen?

Fußballdaten

Dieses Datenbeispiel enthält die Ergebnisse aller Fußball-Länderspiele (der Herren) zwischen 1871 und 2017 (knapp 40.000 Datenpunkte). Aufgabe ist es, die Nationalmannschaften in Cluster einzuteilen. Eine Anwendung könnte sein, Gruppen „ähnlicher“ Teams für neue Turnierformen zu bestimmen.

In der nachfolgenden Tabelle sind die Attribute der Datei international-football-results-from-1872-to-2017.csv erläutert:

Attributename Bedeutung / ggfs. Ausprägungen
date Datum des Spiels
home_team Name der Heimmannschaft
away_team Name der Gastmannschaft
home_score Erzielte Tore der Heimmannschaft
away_score Erzielte Tore der Gastmannschaft
tournament Name des Turniers bzw. “friendly” für Freundschaftsspiel
city Name der Stadt, in der das Spiel ausgetragen wurde
country Name des Landes, in dem das Spiel ausgetragen wurde
neutral TRUE/FALSE Spalte, die angibt, ob das Spiel auf für beide Mannschaften neutralem Boden stattgefunden hat

Vorbereitung

Um Ihnen Zeit zu sparen, enthält der bereitgestellte Workflow 04-football-clustering bereits umfangreiche Möglichkeiten für die Datenaufbereitung; dabei werden aus den Spielergebnissen Mannschaftsstatistiken gebildet. Diese können Sie noch erweitern oder abändern. Auch könnte es noch sinnvoll sein, nicht alle Spiele einzubeziehen, sondern manche Matches (z.B. sehr alte) auszufiltern (überlegen Sie, warum). Dies können Sie mit dem Row Filter Knoten direkt nach dem Einlesen machen. Der untere Teil der Datenaufbereitung „normalisiert“ die Kennzahlen Anzahl Siege/Niederlagen/Unentschieden mittels Division durch die Gesamtanzahl der Spiele, die die betreffende Mannschaft gespielt hat (da sich diese zwischen den Teams teilweise erheblich unterscheiden). Sie können diese zusätzliche „Normalisierung“ einbinden, indem Sie deren Output (statt dem der oberen Reihe) als Input für das Clustering verwenden. Im Normalizer-Knoten am Ende der Vorverarbeitung können Sie die Normalisierungsfunktion variieren, um deren mögliche Auswirkung auf das Clustering zu sehen

Clustering-Verfahren

Wenden Sie nun nacheinander die kennengelernten Knoten auf die Fußballdaten an und interpretieren Sie diese Ergebnisse.

Aufgabe 1 — k-Means

Führen Sie das k-Means-Clustering für verschiedene k (z.B. k = 3, 4, …, 30) durch. Dafür ist im Workflow ein Intervall Loop eingerichtet, die die Werte für k nacheinander durchgeht. Wenn Sie den k-Means-Knoten eingefügt haben, können Sie bei „Number of Clusters“ diesen Loop-Wert übergeben, somit wird dieser als Wert für die Anzahl der Cluster verwenden. Der Loop führt k-Means dann für alle k aus und nimmt anschließend eine interne Evaluation vor. Im Workflow ist dafür ein Verfahren (brauner Kasten) vorbereitet und schon im Loop integriert, der für jedes Clustering die Summe der quadratischen Distanzen aller Punkte zu ihren Clusterschwerpunkten berechnet. Diese Summe wird für jeden Durchlauf der Loop gesammelt und an eine Tabelle angehängt. Bitte beachten Sie: Es ist nicht sinnvoll, für verschiedene k diese Summenwerte direkt zu vergleichen, da die Summen mit wachsendem k immer kleiner werden (warum ist das so?). Stattdessen kann man den Verlauf der Veränderung der Summe abhängig von k betrachten und auffällige „Sprünge“ als Indikator für gute bzw. schlechte Werte von k verwenden. Für individuelle k können Sie dann k-Means nochmals gesondert ausführen, indem Sie im Knoten das k direkt eingeben. Die Cluster können Sie mit der View im grüner Kasten einsehen. Für eine externe Validierung können Sie Ihre individuelle Fußball-Expertise oder auch offizielle Statistiken wie FIFA-Ranglisten o.ä. verwenden.

Aufgabe 2 — Hierarchisches Clustering

Führen Sie das hierarchische Clustering auf denselben Daten durch. Sie können den Knoten an derselben Stelle „einhängen“ wie k-Means. Den Loop brauchen Sie aber prinzipiell nicht: Im KNIME-Knoten für Hierarchical Clustering muss zwar wie bei k-Means eine Anzahl von Clustern vorgegeben werden; diese hat aber keine Auswirkung auf das Clustering selbst, sondern lediglich auf die Output-Tabelle, die für jeden Datensatz den zugehörigen Cluster enthält (dazu muss KNIME wissen, wieviele gewünscht sind). Es wird also durch die Vorgabe aus dem erzeugten Dendrogramm der passende Clustering-Level, also die „Granularität“ der Cluster, ausgewählt. Sie können hier natürlich ebenfalls verschiedene Werte vergleichen.

Wechseln Sie auch zwischen verschiedenen Distanzmaßen (Euclidean, Manhatten) sowie LinkageTypen (Single, Complete, Average), um potenzielle Unterschiede im Clustering zu sehen.

Aufgabe 3 — Dichtebasiertes Clustering mit DBSCAN

Nutzen Sie den bereitgestellten Workflow, um DBSCAN zu implementieren. Für den DBSCAN-Knoten müssen als Input die Distanzen zwischen den Datenpunkten berechnet werden, was mit Hilfe des Distance-Matrix-Calculate-Knotens möglich ist. Hier können Sie die Wahl der Distanzfunktion variieren.

In DBSCAN muss ein Wert für Epsilon (Radius) und Minimum points (Mindestanzahl von Nachbarn im Radius) vorgegeben werden. Die Wahl dieser Werte hat großen Einfluss auf das Clustering, vor allem auf die Anzahl der Cluster und die Anzahl der Ausreißer (Noise), und es ist nicht einfach, gute Werte zu finden.

Um geeignete Werte für Epsilon zu finden (bzw. ungeeignete schnell auszuschließen), kann man die im Buch erläuterte Methode der kNN-Distanz nutzen. Hierfür ist im Workflow ein möglicher Weg aufgezeigt, bei dem mit Hilfe des Similarity-Search-Knotens für jeden Punkt die k nächsten Nachbarn und deren Distanzen ermittelt werden. Die Distanz zum k-nächsten Nachbarn können Sie dann weiterverwenden, um mit Hilfe eines Line Plots in der Verteilung einen „Knick“ (falls vorhanden) zu ermitteln. Der y-Wert (Distanz) am „Knickpunkt“ der Kurve bildet eine Obergrenze für Epsilon (geeignete Werte für Epsilon liegen in der Regel unterhalb dieses Werts).

Zusammenfassung und Vergleich

Mit welchem Verfahren und welchen Parametern haben Sie die „besten“ Ergebnisse bekommen? Welche(s) Verfahren sehen Sie für die vorliegende Anwendung bzw. Daten grundsätzlich als eher problematisch, und warum?