Single-Linkage-Clustering - Single-linkage clustering

In der Statistik ist Single-Linkage-Clustering eine von mehreren Methoden für hierarchisches Clustering . Es basiert auf der Gruppierung von Clustern von unten nach oben (agglomeratives Clustering), wobei bei jedem Schritt zwei Cluster kombiniert werden, die das nächste Elementpaar enthalten, das noch nicht zu demselben Cluster gehört.

Ein Nachteil dieses Verfahrens besteht darin, dass es dazu neigt, lange dünne Cluster zu erzeugen, in denen benachbarte Elemente desselben Clusters kleine Abstände aufweisen, Elemente an entgegengesetzten Enden eines Clusters jedoch viel weiter voneinander entfernt sein können als zwei Elemente anderer Cluster. Dies kann zu Schwierigkeiten bei der Definition von Klassen führen, die die Daten sinnvoll unterteilen könnten.

Überblick über agglomerative Clustering-Methoden

Zu Beginn des agglomerativen Clustering-Prozesses befindet sich jedes Element in einem eigenen Cluster. Die Cluster werden dann nacheinander zu größeren Clustern zusammengefasst, bis sich alle Elemente im selben Cluster befinden. Bei jedem Schritt werden die beiden durch den kürzesten Abstand getrennten Cluster kombiniert. Die Funktion zur Bestimmung des Abstands zwischen zwei Clustern, die als Verknüpfungsfunktion bezeichnet wird , unterscheidet die agglomerativen Clustering-Methoden.

Beim Single-Linkage-Clustering wird der Abstand zwischen zwei Clustern durch ein einzelnes Elementpaar bestimmt: die beiden Elemente (eines in jedem Cluster), die einander am nächsten liegen. Der kürzeste dieser paarweisen Abstände, die bei einem Schritt verbleiben, führt dazu, dass die beiden Cluster, deren Elemente beteiligt sind, zusammengeführt werden. Das Verfahren wird auch als Clustering für den nächsten Nachbarn bezeichnet . Das Ergebnis der Clusterbildung kann als Dendrogramm dargestellt werden , das die Reihenfolge zeigt, in der Cluster zusammengeführt wurden, und die Entfernung, in der jede Zusammenführung stattgefunden hat.

Mathematisch wird die Verknüpfungsfunktion - der Abstand D ( X , Y ) zwischen den Clustern X und Y - durch den Ausdruck beschrieben

${\ Anzeigestil D (X, Y) = \ min _ {x \ in X, y \ in Y} d (x, y),}$

wobei X und Y zwei beliebige Sätze von Elementen sind, die als Cluster betrachtet werden, und d ( x , y ) den Abstand zwischen den beiden Elementen x und y bezeichnet .

Naiver Algorithmus

Der folgende Algorithmus ist ein agglomeratives Schema, das Zeilen und Spalten in einer Proximity-Matrix löscht, wenn alte Cluster zu neuen zusammengeführt werden. Die Näherungsmatrix enthält alle Entfernungen . Den Clustern werden Sequenznummern zugewiesen und es handelt sich um die Ebene des -ten Clusters. Ein Cluster mit der Sequenznummer m wird mit ( m ) und der Nähe zwischen Clustern bezeichnet und bezeichnet . ${\ displaystyle N \ times N}$${\ displaystyle D}$${\ displaystyle d (i, j)}$${\ displaystyle 0,1, \ ldots, n-1}$${\ displaystyle L (k)}$${\ displaystyle k}$${\ displaystyle (r)}$${\ displaystyle (s)}$${\ displaystyle d [(r), (s)]}$

Der Einzelverknüpfungsalgorithmus besteht aus den folgenden Schritten:

1. Beginnen Sie mit dem disjunkten Clustering mit Ebene und Sequenznummer . ${\ displaystyle L (0) = 0}$${\ displaystyle m = 0}$
2. Suchen Sie das ähnlichste Clusterpaar im aktuellen Clustering, z. B. Paar , je nachdem, wo das Minimum über allen Clusterpaaren im aktuellen Clustering liegt. ${\ displaystyle (r), (s)}$${\ displaystyle d [(r), (s)] = \ min d [(i), (j)]}$
3. Erhöhen Sie die Sequenznummer : . Merge - Cluster und in einem einzigen Cluster das nächste Clustering zu bilden . Stellen Sie die Ebene dieses Clusters auf ein ${\ displaystyle m = m + 1}$${\ displaystyle (r)}$${\ displaystyle (s)}$${\ displaystyle m}$${\ displaystyle L (m) = d [(r), (s)]}$
4. Aktualisieren der Distanzmatrix, durch Löschen der Zeilen und Spalten entsprechen , Clustern und und das Hinzufügen einer Zeile und Spalte entsprechend dem neu gebildeten Cluster. Die Nähe zwischen dem neuen Cluster, dem bezeichneten und dem alten Cluster ist definiert als . ${\ displaystyle D}$${\ displaystyle (r)}$${\ displaystyle (s)}$${\ displaystyle (r, s)}$${\ displaystyle (k)}$${\ Anzeigestil d [(r, s), (k)] = \ min \ {d [(k), (r)], d [(k), (s)] \}}$
5. Wenn sich alle Objekte in einem Cluster befinden, stoppen Sie. Andernfalls fahren Sie mit Schritt 2 fort.

Arbeitsbeispiel

Dieses Arbeitsbeispiel basiert auf einer genetischen JC69- Distanzmatrix, die aus dem 5S-ribosomalen RNA- Sequenz-Alignment von fünf Bakterien berechnet wurde : Bacillus subtilis ( ), Bacillus stearothermophilus ( ), Lactobacillus viridescens ( ), Acholeplasma modicum ( ) und Micrococcus luteus ( ). ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle e}$

Erster Schritt

• Erstes Clustering

Nehmen wir an, wir haben fünf Elemente und die folgende Matrix paarweiser Abstände zwischen ihnen: ${\ displaystyle (a, b, c, d, e)}$${\ displaystyle D_ {1}}$

	ein	b	c	d	e
ein	0	17	21	31	23
b	17	0	30	34	21
c	21	30	0	28	39
d	31	34	28	0	43
e	23	21	39	43	0

In diesem Beispiel ist der niedrigste Wert von , also gruppieren wir Elemente und . ${\ displaystyle D_ {1} (a, b) = 17}$${\ displaystyle D_ {1}}$${\ displaystyle a}$${\ displaystyle b}$

• Schätzung der ersten Verzweigungslänge

Lassen Sie bezeichnen den Knoten , mit dem und sind jetzt verbunden. Die Einstellung stellt sicher, dass Elemente und äquidistant von sind . Dies entspricht der Erwartung der Ultrametrizitätshypothese . Die Zweige verbinden und um dann Längen zu haben ( siehe die endgültige Dendrogramm ) ${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle \ delta (a, u) = \ delta (b, u) = D_ {1} (a, b) / 2}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle u}$${\ displaystyle \ delta (a, u) = \ delta (b, u) = 17/2 = 8,5}$

• Erstes Distanzmatrix-Update

Anschließend aktualisieren wir die anfängliche Proximity-Matrix in eine neue Proximity-Matrix (siehe unten), deren Größe aufgrund der Clusterbildung von with um eine Zeile und eine Spalte reduziert wurde . Fettgedruckte Werte entsprechen den neuen Abständen, berechnet unter Beibehaltung des Mindestabstands zwischen jedem Element des ersten Clusters und jedem der verbleibenden Elemente: ${\ displaystyle D_ {1}}$${\ displaystyle D_ {2}}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle D_ {2}}$${\ displaystyle (a, b)}$

${\ Anzeigestil D_ {2} ((a, b), c) = min (D_ {1} (a, c), D_ {1} (b, c)) = min (21,30) = 21}$

${\ Anzeigestil D_ {2} ((a, b), d) = min (D_ {1} (a, d), D_ {1} (b, d)) = min (31,34) = 31}$

${\ Anzeigestil D_ {2} ((a, b), e) = min (D_ {1} (a, e), D_ {1} (b, e)) = min (23,21) = 21}$

Kursiv gedruckte Werte in werden von der Matrixaktualisierung nicht beeinflusst, da sie Abständen zwischen Elementen entsprechen, die nicht am ersten Cluster beteiligt sind. ${\ displaystyle D_ {2}}$

Zweiter Schritt

• Zweites Clustering

Wir wiederholen nun die drei vorherigen Aktionen, beginnend mit der neuen Distanzmatrix  : ${\ displaystyle D_ {2}}$

	(a, b)	c	d	e
(a, b)	0	21	31	21
c	21	0	28	39
d	31	28	0	43
e	21	39	43	0

Hier und sind die niedrigsten Werte von , also verbinden wir Cluster mit Element und mit Element . ${\ displaystyle D_ {2} ((a, b), c) = 21}$${\ displaystyle D_ {2} ((a, b), e) = 21}$${\ displaystyle D_ {2}}$${\ displaystyle (a, b)}$${\ displaystyle c}$${\ displaystyle e}$

• Schätzung der zweiten Verzweigungslänge

Lassen Sie bezeichnen den Knoten , zu dem , und sind jetzt verbunden. Aufgrund der Ultrametrizitätsbeschränkung sind die Zweige, die sich zu oder zu und zu und auch zu verbinden, gleich und haben die folgende Gesamtlänge: ${\ displaystyle v}$${\ displaystyle (a, b)}$${\ displaystyle c}$${\ displaystyle e}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle v}$${\ displaystyle c}$${\ displaystyle v}$${\ displaystyle e}$${\ displaystyle v}$${\ displaystyle \ delta (a, v) = \ delta (b, v) = \ delta (c, v) = \ delta (e, v) = 21/2 = 10,5}$

Wir leiten die fehlende Astlänge ab: ( siehe das letzte Dendrogramm ) ${\ displaystyle \ delta (u, v) = \ delta (c, v) - \ delta (a, u) = \ delta (c, v) - \ delta (b, u) = 10,5-8,5 = 2}$

• Aktualisierung der zweiten Distanzmatrix

Anschließend aktualisieren wir die Matrix in eine neue Distanzmatrix (siehe unten), deren Größe aufgrund der Clusterbildung von mit und mit um zwei Zeilen und zwei Spalten reduziert wurde  : ${\ displaystyle D_ {2}}$${\ displaystyle D_ {3}}$${\ displaystyle (a, b)}$${\ displaystyle c}$${\ displaystyle e}$

${\ Anzeigestil D_ {3} (((a, b), c, e), d) = min (D_ {2} ((a, b), d), D_ {2} (c, d), D_ {2} (e, d)) = min (31,28,43) = 28}$

Letzter Schritt

Die endgültige Matrix lautet: ${\ displaystyle D_ {3}}$

	((a, b), c, e)	d
((a, b), c, e)	0	28
d	28	0

Also schließen wir uns Clustern an und . ${\ displaystyle ((a, b), c, e)}$${\ displaystyle d}$

Lassen Sie bezeichnen die (root) an dem Knoten und sind jetzt verbunden. Die Zweige verbinden und um dann Längen haben: ${\ displaystyle r}$${\ displaystyle ((a, b), c, e)}$${\ displaystyle d}$${\ displaystyle ((a, b), c, e)}$${\ displaystyle d}$${\ displaystyle r}$

${\ displaystyle \ delta (((a, b), c, e), r) = \ delta (d, r) = 28/2 = 14}$

Wir leiten die verbleibende Astlänge ab:

${\ displaystyle \ delta (v, r) = \ delta (a, r) ​​- \ delta (a, v) = \ delta (b, r) - \ delta (b, v) = \ delta (c, r) - \ Delta (c, v) = \ Delta (e, r) - \ Delta (e, v) = 14-10,5 = 3,5}$

Das Single-Linkage-Dendrogramm

Das Dendrogramm ist jetzt vollständig. Es ist , weil alle Tipps ultrametrische ( , , , , und ) sind gleich weit entfernt von  : ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle c}$${\ displaystyle e}$${\ displaystyle d}$${\ displaystyle r}$

${\ displaystyle \ delta (a, r) ​​= \ delta (b, r) = \ delta (c, r) = \ delta (e, r) = \ delta (d, r) = 14}$

Das Dendrogramm wurzelt daher in seinem tiefsten Knoten. ${\ displaystyle r}$

Andere Verknüpfungen

Der naive Algorithmus für das Clustering einzelner Verknüpfungen ist im Wesentlichen der gleiche wie der Algorithmus von Kruskal für minimale Spannbäume . Beim Clustering mit einer einzelnen Verknüpfung ist jedoch die Reihenfolge wichtig, in der Cluster gebildet werden, während für minimale Spannbäume die Menge der Punktpaare von Bedeutung ist, die vom Algorithmus ausgewählte Abstände bilden.

Alternative Verknüpfungsschemata umfassen vollständiges Verknüpfungsclustering , durchschnittliches Verknüpfungsclustering ( UPGMA und WPGMA ) und die Ward-Methode . In dem naiven Algorithmus für agglomeratives Clustering kann die Implementierung eines anderen Verknüpfungsschemas einfach durch Verwendung einer anderen Formel zur Berechnung der Abstände zwischen Clustern im Algorithmus erreicht werden. Die Formel, die angepasst werden sollte, wurde in der obigen Algorithmusbeschreibung durch Fettdruck hervorgehoben. Effizientere Algorithmen wie der unten beschriebene verallgemeinern jedoch nicht alle Verknüpfungsschemata auf dieselbe Weise.

Vergleich von Dendrogrammen, die unter verschiedenen Clustering-Methoden aus derselben Distanzmatrix erhalten wurden .

Single-Linkage-Clustering .	Clustering mit vollständiger Verknüpfung.	Durchschnittliches Verknüpfungsclustering: WPGMA.	Durchschnittliches Verknüpfungsclustering: UPGMA.

Schnellere Algorithmen

Der naive Algorithmus für Single-Linkage-Clustering ist leicht zu verstehen, aber langsam und zeitaufwändig . 1973 schlug R. Sibson einen Algorithmus mit zeitlicher Komplexität und räumlicher Komplexität (beide optimal) vor, der als SLINK bekannt ist. Der Slink-Algorithmus repräsentiert ein Clustering auf einer Reihe von nummerierten Elementen durch zwei Funktionen. Diese Funktionen werden beide bestimmt, indem der kleinste Cluster gefunden wird , der sowohl ein Element  als auch mindestens ein Element mit größerer Nummer enthält. Die erste Funktion ordnet das Element dem Element  mit der größten Nummer im Cluster zu . Die zweite Funktion ordnet das Element  der Entfernung zu, die mit der Erstellung des Clusters verbunden ist . Das Speichern dieser Funktionen in zwei Arrays, die jede Elementnummer ihrem Funktionswert zuordnen , benötigt Speicherplatz . Diese Informationen reichen aus, um das Clustering selbst zu bestimmen. Wie Sibson zeigt, können beim Hinzufügen eines neuen Elements zum Elementsatz die aktualisierten Funktionen, die das neue Single-Linkage-Clustering für das erweiterte Set darstellen, das auf die gleiche Weise dargestellt wird, rechtzeitig aus dem alten Clustering erstellt werden . Der SLINK-Algorithmus durchläuft dann nacheinander die Elemente und fügt sie der Darstellung des Clusters hinzu. ${\ displaystyle O (n ^ {3})}$${\ displaystyle O (n ^ {2})}$${\ displaystyle O (n)}$${\ displaystyle n}$${\ displaystyle C}$${\ displaystyle i}$${\ displaystyle \ pi}$${\ displaystyle i}$${\ displaystyle C}$${\ displaystyle \ lambda}$${\ displaystyle i}$${\ displaystyle C}$${\ displaystyle O (n)}$${\ displaystyle O (n)}$

Ein alternativer Algorithmus, der in denselben optimalen Zeit- und Raumgrenzen ausgeführt wird, basiert auf der Äquivalenz zwischen dem naiven Algorithmus und dem Kruskal-Algorithmus für minimale Spannbäume. Anstatt den Kruskal-Algorithmus zu verwenden, kann der Prim-Algorithmus in einer Variation ohne binäre Haufen verwendet werden, die Zeit und Raum benötigt , um den minimalen Spannbaum (aber nicht die Clusterbildung) der angegebenen Elemente und Entfernungen zu erstellen. Wenn Sie dann den Kruskal-Algorithmus auf den spärlichen Graphen anwenden, der durch die Kanten des minimalen Spannbaums gebildet wird, wird die Clusterbildung selbst in einer zusätzlichen Zeit und in einem zusätzlichen Raum erzeugt . ${\ displaystyle O (n ^ {2})}$${\ displaystyle O (n)}$${\ displaystyle O (n \ log n)}$${\ displaystyle O (n)}$

Siehe auch

• Clusteranalyse
• Clustering mit vollständiger Verknüpfung
• Hierarchisches Clustering
• Molekularuhr
• Nachbarschaftsverknüpfung
• UPGMA
• WPGMA

Verweise

Externe Links

• In Matlab verwendete Verknüpfungen