Was ist hierarchisches Clustering?

Clustering ist eine Technik des unbeaufsichtigten maschinellen Lernens, die in der Datenanalyse verwendet wird, um ähnliche Objekte zu erkennen und zu gruppieren. Hierarchische Clusteranalyse (HCA) oder hierarchisches Clustering gruppiert Objekte in einer Cluster-Hierarchie, ohne sie in eine lineare Reihenfolge zu setzen. Viele Disziplinen, wie z. B. Biologie, Bildanalyse und Sozialwissenschaften, verwenden hierarchische Clustering-Methoden, um Muster in Datensätzen zu erkunden und zu erkennen. Zu den Anwendungsfällen gehören die Kategorisierung von Populationen in der klinischen Forschung, Kundensegmentierung und die Erkennung von Gemeinschaften von Knotenpunkten 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.

Die hierarchische Clustering-Analyse ist mit hohen Rechenkosten verbunden. Die Verwendung eines Heapspeichers kann zwar die Rechenzeit reduzieren, erhöht aber gleichzeitig die Speicheranforderungen. Sowohl die spaltende als auch die agglomerative Art des Clusterings sind "„gierig“, was bedeutet, dass der Algorithmus entscheidet, welche Cluster zusammengeführt oder geteilt werden sollen, indem er in jeder Phase des Prozesses die lokal optimale Wahl trifft. Es ist auch möglich, ein Stopp-Kriterium anzuwenden, bei dem der Algorithmus die Agglomeration oder das Aufteilen von Clustern stoppt, wenn er eine vorgegebene Anzahl von Clustern erreicht.

Ein baumartiges Diagramm, das als Dendrogramm³ bezeichnet wird, wird häufig verwendet, um die Hierarchie der Cluster zu visualisieren. Es zeigt die Reihenfolge an, in der Cluster zusammengeführt oder geteilt wurden, und zeigt die Ähnlichkeit oder den Abstand zwischen Datenpunkten an. Dendrogramme können auch als verschachtelte Liste von Listen⁴ 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 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

Lassen Sie uns die gängigsten Methoden zur euklidischen Distanzverknüpfung erkunden. Beispiele für andere verwendbare Distanzmetriken sind 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 clusternden Daten, der Datendichte, der Clusterform ab sowie davon, ob der Datensatz Ausreißer 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 Ausreißer beeinträchtigt. Es gibt eine Einschränkung, die als Verkettungseffekt bekannt ist.⁶ Einige 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 die minimale Verknüpfung können wie folgt dargestellt werden:

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

Dabei sind A und B zwei Sätze 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 Ausreißern 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 Beobachtungssätze und *d* die Entfernung sind.

WPGMA wird durch die folgende Formel dargestellt

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

Dabei sind i und j die nächstgelegenen Cluster, die in jedem Schritt kombiniert werden, um einen neuen Cluster aus der Vereinigung von i und j zu bilden. Wir können dann die Entfernung zu einem anderen Cluster k berechnen, die das arithmetische Mittel der durchschnittlichen Abstände zwischen den 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 Summe der Quadrate (MISSQ)⁸ ein. Jeder Datenpunkt beginnt in seinem eigenen Cluster. Dieser Ansatz bedeutet, dass die Summe der Quadrate zwischen den Datenpunkten zunächst Null beträgt und dann beim Zusammenführen von Clustern zunimmt. Wards Methode minimiert die Summe der quadrierten Entfernungen der Punkte von den Clusterzentren beim Zusammenführen. Wards Methode ist eine gute Wahl für quantitative Variablen⁹ und wird weniger von Rauschen oder Ausreißern beeinflusst. Sie kann wie folgt dargestellt werden:

 ∣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 Cluster. Der Algorithmus verwendet ein ausgewähltes Linkage-Clustering-Kriterium, das auf einer Unähnlichkeitsmatrix basiert, um zu entscheiden, welches Cluster-Paar zusammengeführt werden soll. Der Algorithmus verschiebt sich in der Hierarchie nach oben und bildet solange Cluster-Paare, bis alles miteinander verknüpft ist. Dadurch entsteht eine hierarchische Reihe verschachtelter Cluster. Grob zusammengefasst sind die Schritte des agglomerativen Clustering¹⁰: 

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 Stoppkriterien erfüllt ist.

Die Prinzipien hinter dem spaltenden hierarchischen Clustering wurden 1964 von Macnaughton-Smith und anderen¹¹ entwickelt und 1990 von Kaufman und Rousseeuw mit ihrem DIANA-Algorithmus (Divisive ANAlysis Clustering)¹² weiter untersucht. Beim spaltenden Clustering wird der dem agglomerativen Clustering entgegengesetzte Ansatz verwendet. Alle Datenpunkte beginnen in einem einzelnen Cluster, der wiederholt in mehrere Cluster aufgeteilt wird. Die Aufteilung erfolgt, bis entweder alle verbleibenden Cluster Singletons sind oder ein Stoppkriterium wie eine vordefinierte Anzahl von Clustern erfüllt ist. Spaltende Methoden sind besser in der Lage, große Cluster zu identifizieren¹³, und können genauer sein als agglomerative Methoden, da der Algorithmus die gesamte Verteilung des Datensatzes von Beginn des Prozesses an berücksichtigt.

Um die Effizienz zu verbessern, nutzen 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 spaltenden Clustering-Schritte¹⁵ sind:

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

2. Aufteilung des Clusters in zwei unterschiedliche oder heterogene Cluster durch Anwendung einer flachen Clustering-Methode wie den k-Means-Algorithmus.

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

4. Anhalten, wenn sich jedes Beispiel in einem eigenen Cluster befindet, andernfalls Wiederholung von 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.

Mithilfe eines Dendrogramms können Sie entscheiden, wie viele Cluster¹⁶ Ihr endgültiges Clustermodell enthalten soll. Eine Strategie besteht darin, den natürlichen Abbruchpunkt im Baum zu ermitteln, an dem die Zweige sich lichten und länger werden. Alternativ ergibt sich die Anzahl der Cluster aus der Anzahl der vertikalen Linien, 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 an diesem Punkt des Prozesses zwei Cluster vorhanden sind: ein Cluster mit den Punkten 5, 8 und 2 und ein Cluster mit den verbleibenden Punkten. Je weiter sich die horizontale Linie nach oben oder unten verschieben kann, ohne dass andere horizontale Linien im Dendrogramm geschnitten werden, desto besser ist die Auswahl dieser Anzahl von Clustern für Ihr Cluster-Modell. Im folgenden Beispiel wählt die horizontale Linie H2 vier Cluster aus. H2 ist kann nicht bis zu H1 auf und ab verschoben werden, ohne andere horizontale Linien zu schneiden. Dieses Szenario zeigt, dass die Option mit zwei Clustern (H1) wahrscheinlich besser für Ihr Clusteringmodell 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 die Auswahl des Verknüpfungskriteriums und der Clusternummern kann sich erheblich auf Ihre Ergebnisse auswirken. Probieren Sie daher beim Erstellen eines Clustering-Modells verschiedene Optionen aus und wählen Sie diejenigen aus, die Ihnen am besten helfen, Muster im Datensatz für zukünftige Überlegungen zu erkunden und 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 Ausreißern oder Ergebnisvariablen

- Irgendwelche spezifischen Domänen- oder Datensatzkenntnisse

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

- Die Ellbogenmethode, 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.

- 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. Hierarchisches Clustering hilft dabei, gemischte Populationen in homogenere Gruppen zu kategorisieren²⁰, z. B. anhand von diagnostischen Kriterien, physiologischen Reaktionen oder DNA-Mutationen. Es kann auch dazu verwendet werden, Arten nach biologischen Merkmalen zu gruppieren, 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 verwendet.

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 Funktion „AgglomerativeCluster²¹“ (siehe auch Beispiele für agglomeratives 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 verarbeiten. Wenn Sie praktische Erfahrungen sammeln möchten, sehen Sie sich unsere Schritt-für-Schritt-Tutorials dazu an wie man hierarchisches Clustering in Python implementiert und wie man hierarchisches Clustering in R implementiert.