Was ist hierarchisches Clustering?

Clustering ist eine unbeaufsichtigte Technik des maschinellen Lernens, die bei der Datenanalyse verwendet wird, um ähnliche Objekte zu erkennen und zu gruppieren. Die hierarchische Clusteranalyse (HCA) oder hierarchisches Clustering gruppiert Objekte in einer Clusterhierarchie, ohne eine lineare Reihenfolge zwischen ihnen zu erzwingen. Viele Disziplinen wie Biologie, Bildanalyse und Sozialwissenschaften verwenden hierarchische Clustering-Methoden, um Muster in Datensätzen zu ermitteln und zu erkennen. Zu den Anwendungsfällen gehören die Kategorisierung von Bevölkerungen in der klinischen Forschung, die Kundensegmentierung und die Erkennung von Knotengemeinschaften in Netzwerkmodellen.

Es gibt zwei Arten von hierarchischem Clustering:

- Agglomerativer oder Bottom-Up-Ansatz¹, bei dem Cluster immer wieder zu größeren zusammengeführt werden, bis ein einziger Cluster entsteht.

- Spaltender oder Top-Down-Ansatz, der² mit allen Daten in einem einzelnen Cluster beginnt und Cluster weiter aufteilt, bis alle Cluster Singletons sind.

Hierarchische Clusteranalysen haben hohe Rechenkosten. Die Verwendung eines Heaps kann zwar die Rechenzeit reduzieren, aber die Speicheranforderungen werden erhöht. Sowohl die spaltende als auch die agglomerative Art des Clusterings sind „greedy“, was bedeutet, dass der Algorithmus entscheidet, welche Cluster zusammenzuführen oder aufzuteilen sind, indem er in jeder Phase des Prozesses die lokal optimale Wahl trifft. Es ist auch möglich, Stoppkriterien anzuwenden, bei denen der Algorithmus die Agglomeration oder Aufteilung von Clustern stoppt, wenn eine vorgegebene Anzahl von Clustern erreicht wird.

Ein baumartiges Diagramm, auch Dendrogramm³ genannt, wird häufig verwendet, um die Hierarchie von Clustern zu visualisieren. Es zeigt die Reihenfolge an, in der Cluster zusammengeführt oder geteilt wurden, sowie die Ähnlichkeit oder Entfernung zwischen Datenpunkten. Dendrogramme können auch als verschachtelte Listenreihe⁴ mit Attributen verstanden werden.

Hierarchische Clustering-Algorithmen verwenden das Konzept einer Unähnlichkeitsmatrix, um zu entscheiden, welche Cluster zusammengeführt oder geteilt werden sollen. Die Unähnlichkeit ist der Abstand zwischen zwei Datenpunkten, der mit einer gewählten Verknüpfungsmethode (Linkage) gemessen wird. Die Werte in einer Unähnlichkeitsmatrix drücken Folgendes aus:

- Die Entfernung⁵, ein euklidischer Abstand als Beispiel, zwischen einzelnen Punkten in einer Menge

- Ein Kriterium für Linkage-Clustering, das die Unähnlichkeit als Funktion der paarweisen Abstände von Punkten über Datensätze hinweg angibt

Beschäftigen wir uns mit den gängigsten euklidischen Distanz-Linkage-Methoden. Beispiele für andere Metriken, die verwendet werden können, sind die Minkowski, Hamming, Mahalanobis, Hausdorf und Manhattan-Distanz. Beachten Sie, dass jede Verknüpfungsmethode unterschiedliche Cluster aus demselben Datensatz generiert. Die Auswahl der geeigneten Linkage-Clustering-Methode hängt von Faktoren wie der Art der zu geclusterten Daten, der Datendichte, der Cluster-Form und davon ab, ob der Datensatz Sonderfälle oder Rauschen enthält.

Die einzelne Verknüpfungsmethode analysiert paarweise Abstände zwischen Elementen in zwei Clustern und verwendet dann den Mindestabstand zwischen den Clustern. Die Min-Methode kann nicht-elliptische Clusterformen gut verarbeiten, wird aber durch Rauschen und Sonderfälle beeinträchtigt. Es gibt eine Einschränkung, die als Verkettungseffekt bekannt ist⁶. Ein paar Punkte, die eine Brücke zwischen einem Clusterpaar bilden, können dazu führen, dass die beiden Cluster zu einem einzigen Cluster verschmelzen. Die Kriterien für Min-Linkage können wie folgt dargestellt werden:

 mina∈A,b∈Bd(a,b)

Dabei sind A und B zwei Gruppen von Beobachtungen und d ist eine Entfernungsfunktion.

Cluster-Entfernungen können auch basierend auf den Punkten berechnet werden, die am weitesten voneinander entfernt sind. Die max-Methode ist weniger empfindlich gegenüber Rauschen und Sonderfällen als die min-Methode, aber die Verwendung dieser Methode kann die Ergebnisse verzerren, wenn kugelförmige oder große Cluster vorhanden sind. Die max-Verknüpfung erzeugt oft mehr kugelförmige Cluster als die min-Verknüpfung. Die max-Verknüpfung kann in der folgenden Formel dargestellt werden:

 maxa∈A,b∈Bd(a,b)

Dabei sind A und B zwei Gruppen von Beobachtungen und d ist die Entfernung.

Diese von Sokal und Michener eingeführten Methoden⁷  definieren den Abstand zwischen Clustern als den durchschnittlichen Abstand zwischen Paaren über alle Punktpaare in den Clustern hinweg. Der Algorithmus kann entweder die ungewichtete Paargruppenmethode mit arithmetischem Mittelwert (UPGMA) oder die gewichtete Paargruppenmethode mit arithmetischem Mittelwert (WPGMA) sein. Der Begriff „ungewichtet“ bedeutet hier, dass alle Entfernungen gleichermaßen zu jedem Durchschnitt beitragen.

UPGMA wird durch die folgende Formel dargestellt:

 1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

wobei *A* und *B* zwei Beobachtungsgruppen und *d* die Entfernung sind.

WPGMA wird durch die folgende Formel dargestellt:

 d(i∪j,k)=d(i,k)+d(j,k)2

wobei i und j die nächstgelegenen Cluster sind, die in jedem Schritt zu einem neuen Cluster der Allianz von i und j kombiniert werden. Wir können dann die Entfernung zu einem anderen Cluster k berechnen, der das arithmetische Mittel der durchschnittlichen Entfernungen zwischen Datenpunkten in k und i sowie k und j ist.

Hier verwenden wir den Abstand zwischen Clusterzentren oder Schwerpunkten. Der Abstand zwischen den Schwerpunkten wird mit Hilfe einer Abstandsfunktion berechnet:

∥μA-μB∥2

Dabei ist μ_A der Schwerpunkt von A und μ_B der Schwerpunkt von B.

Joe H. Ward führte in den 1960er Jahren die Methode der minimalen Zunahme der Quadrate (MISSQ) ein ⁸. Jeder Datenpunkt beginnt in seinem eigenen Cluster. Dieser Ansatz bedeutet, dass die Summe der Quadrate zwischen den Datenpunkten zunächst bei Null liegt und dann zunimmt, wenn wir Cluster zusammenführen. Wards Methode minimiert die Summe der quadratischen Abstände der Punkte von den Clusterzentren, wenn diese zusammengeführt werden. Die Methode von Ward ist eine gute Wahl für quantitative Variablen⁹ und wird weniger durch Rauschen oder Sonderfälle beeinträchtigt. Dies lässt sich wie folgt darstellen:

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

Dabei sind der Mittelwert von A und der Mittelwert von B die Schwerpunkte von A bzw. B und x ist ein Datenpunkt, der zur Vereinigung von A und B gehört

Die Methode der minimalen Varianz nach Ward kann mit einem Lance-Williams-Algorithmus verfeinert werden. Diese Algorithmen verwenden eine rekursive Formel, um Cluster-Abstände zu aktualisieren und das optimale Cluster-Paar zu finden, das sich am nächsten befindet und zu verschmelzen ist.

Beim agglomerativen hierarchischen Clustering, auch bekannt als agglomeratives Nesting (AGNES), beginnt jeder Datenpunkt als ein Cluster. Der Algorithmus verwendet ein ausgewähltes Linkage-Clustering-Kriterium, das auf einer Unähnlichkeitsmatrix basiert, um zu entscheiden, welches Clusterpaar zu verbinden ist. Der Algorithmus verschiebt sich in der Hierarchie nach oben und bildet so lange Cluster-Paare, bis alles miteinander verknüpft ist. Dadurch entsteht eine hierarchische Reihe verschachtelter Cluster. Grob zusammengefasst sind die Schritte des agglomerativen Clusters¹⁰:

1. Berechnung der Unähnlichkeitsmatrix unter Verwendung einer bestimmten Abstandsmetrik.

2. Ordnen Sie jeden Datenpunkt einem Cluster zu.

3. Führen Sie die Cluster basierend auf einem Verknüpfungskriterium für die Ähnlichkeit von Clustern zusammen.

4. Aktualisieren Sie die Entfernungsmatrix.

5. Wiederholen Sie die Schritte 3 und 4, bis ein einzelner Cluster übrig bleibt oder ein Stoppkriterium erfüllt ist.

Die Prinzipien hinter dem spaltenden hierarchischen Clustering wurden 1964 von Macnaughton-Smith und anderen¹¹ entwickelt und 1990 von Kaufman und Ruseeuw mit ihrem DIANA-Algorithmus (Divisive ANAlysis Clustering) ¹² weiter erforscht. Divisive Cluster verwenden den umgekehrten Ansatz von agglomerativen Clustern. Alle Datenpunkte beginnen in einem einzigen Cluster, der wiederholt in weitere Cluster aufgeteilt wird. Die Aufteilung erfolgt so lange, bis entweder alle verbleibenden Cluster Singletons sind oder Stoppkriterien wie eine vordefinierte Anzahl von Clustern erfüllt wurden. Divisive Methoden sind besser in der Lage, große Cluster zu identifizieren¹³ und können genauer sein als agglomerative Methoden, da der Algorithmus die gesamte Datensatzverteilung von Beginn des Prozesses an berücksichtigt.

Zur Verbesserung der Effizienz verwenden spaltende Methoden flache Clustering-Algorithmen wie k-means , um den Datensatz in Cluster aufzuteilen. Die Anzahl der Cluster muss im Voraus angegeben werden. Der k-Means-Algorithmus teilt Cluster auf, indem er die Summe der Quadrate innerhalb des Clusters zwischen den Schwerpunktpunkten minimiert. Dies wird als Trägheitskriterium¹⁴ bezeichnet. Die Schritte des spaltenden Clusterings¹⁵ sind:

1. Beginnen Sie mit allen Datenpunkten für eine Datensatzgröße N (d1, d2, d3 ... dN) in einem Cluster.

2. Teilen Sie den Cluster in zwei unterschiedliche oder heterogene Cluster durch Anwendung einer flachen Clustering-Methode wie dem k-Means-Algorithmus auf.

3. Wiederholung von Schritt 2, wobei der beste Cluster zum Teilen ausgewählt wird und die Sonderfälle des am geringsten zusammenhängenden Clusters nach jeder Iteration entfernt werden.

4. Beenden Sie den Vorgang, wenn sich jedes Beispiel in einem eigenen Cluster befindet, andernfalls wiederholen Sie Schritt 3.

Cluster-Ergebnisse werden in der Regel in einem Dendrogramm (binäre Baumstruktur) dargestellt. Die x-Achse im Dendrogramm stellt die Datenpunkte dar und die y-Achse oder die Höhe der Linien zeigt, wie weit die Cluster bei der Zusammenführung voneinander entfernt waren.

Sie können ein Dendrogramm verwenden, um zu entscheiden, wie viele Cluster¹⁶ es in Ihrem endgültigen Clustering-Modell geben wird. Eine Strategie besteht darin, den natürlichen Schnittpunkt im Baum zu identifizieren, an dem die Zweige schwinden und länger werden. Alternativ ist die Anzahl der Cluster durch die Anzahl der vertikalen Linien gegeben, die gekreuzt werden, wenn eine horizontale Linie das Dendrogramm schneidet.

In dem hier gezeigten Beispielbild schneidet die horizontale Linie H1 zwei vertikale Linien. Dies zeigt, dass es zu diesem Zeitpunkt im Prozess zwei Cluster gibt – einen Cluster mit den Punkten 5, 8 und 2 und einen Cluster mit den verbleibenden Punkten. Je weiter sich die horizontale Linie nach oben oder unten verschieben kann, ohne andere horizontale Linien im Dendrogramm zu schneiden, desto besser ist die Auswahl dieser Anzahl von Clustern für Ihr Clustering-Modell. Im folgenden Beispiel wählt die horizontale Linie H2 vier Cluster aus. H2 ist nicht in der Lage, sich so weit zu H1 zu verschieben, bevor es andere horizontale Linien schneidet. Dieses Szenario zeigt, dass die Wahl der zwei Cluster (H1) für Ihr Clustering-Modell wahrscheinlich besser geeignet ist.

Ein robustes Clustering-Modell¹⁷ erzeugt Cluster mit hoher Ähnlichkeit innerhalb der Klassen und geringer Ähnlichkeit zwischen den Klassen. Es kann jedoch schwierig sein, die Clusterqualität zu definieren, und Ihre Auswahl des Verknüpfungskriteriums und der Clusterzahlen kann einen erheblichen Einfluss auf Ihre Ergebnisse haben. Probieren Sie daher bei der Erstellung eines Cluster-Modells verschiedene Optionen aus und wählen Sie diejenigen aus, die Ihnen am besten helfen, Cluster im Datensatz zu erkunden und für die zukünftige Betrachtung aufzudecken. Zu den zu berücksichtigenden Faktoren¹⁸ gehören:

- Die Anzahl der Cluster, die für den Datensatz praktisch oder logisch sind (bei gegebener Datensatzgröße, Clusterformen, Rauschen usw.)

- Statistiken, wie etwa Mittel-, Maximal- und Minimalwerte für jeden Cluster

- Die beste anzuwendende Unähnlichkeitsmetrik oder das beste anzuwendende Verknüpfungskriterium

- Die Auswirkungen von Sonderfällen oder Ergebnisvariablen

- Beliebige spezifische Domain- oder Datensatzkenntnisse

Zu den weiteren Methoden zur Ermittlung der optimalen Clusteranzahl¹⁹ gehören:

- Die Elbow-Methode, bei der Sie die Summe der Quadrate innerhalb von Clustern gegen die Anzahl der Cluster darstellen und den „Ellbogen“ (den Punkt, an dem die Darstellung abflacht) bestimmen.

- Die Lückenstatistik, bei der Sie die tatsächliche Summe der Quadrate innerhalb des Clusters mit der erwarteten Summe der Quadrate innerhalb des Clusters für eine Nullreferenzverteilung vergleichen und die größte Lücke ermitteln.

Mit Hilfe des hierarchischen Clustering gewinnen Data Scientists Erkenntnisse zur Struktur und zu den Beziehungen innerhalb von Datensätzen. Es kann in verschiedenen Anwendungsfallen eingesetzt werden.

Durch hierarchisches Clustering können Trends analysiert und Kundendaten segmentiert werden, zum Beispiel durch Gruppierung nach Produktauswahl, demografischen Merkmalen, Kaufverhalten, Risikoprofil oder Interaktion mit sozialen Medien.

Patientenkohorten für die klinische Forschung können in die Tausende gehen. Hierarchische Cluster-Bildung hilft bei der Kategorisierung gemischter Bevölkerungsgruppen in homogenere Gruppen²⁰ , indem z. B. diagnostische Kriterien, physische Reaktionen oder DNA-Mutationen herangezogen werden. Sie kann auch auf die Gruppierung von Arten nach biologischen Funktionen angewendet werden, um die evolutionäre Entwicklung zu verstehen.

Hierarchisches Clustering wird in bildbasierten Texterkennungsanwendungen verwendet, um handgeschriebene Zeichen nach ihrer Form zu gruppieren. Es wird auch zum Speichern und Abrufen von Informationen anhand bestimmter Kriterien oder zum Kategorisieren von Ergebnissen genutzt.

Sowohl Python als auch die Programmiersprache R sind in der Data Science weit verbreitet. Python ist flexibel und kann ein breites Spektrum an Aufgaben bewältigen. R wurde speziell für statistische Berechnungen entwickelt und bietet umfangreiche Optionen zur Visualisierung Ihrer hierarchischen Clustering-Analyse.

Python bietet die Agglomerative Cluster-Funktion²¹ (siehe auch Beispiele für Agglomerative-Clustering²² auf sklearn), und SciPy bietet eine Funktion zur Darstellung von Dendrogrammen²³. Pakete wie dendextend²⁴ erweitern die Dendrogramm-Funktionalität von R, verbessern die Sensitivitätsanalyse und ermöglichen es Ihnen, verschiedene Dendrogramme zu vergleichen und zu manipulieren. Für eine praktische Erfahrung finden Sie in unseren Tutorials: wie man hierarchisches Clustering in Python implementiert und wie man hierarchisches Clustering in R implementiert.