Anmeldung
Anmelden

Mindmap-Galerie hierarchische Clusterbildung

hierarchische Clusterbildung

Hierarchisches Clustering ist ein Clustering-Algorithmus. Seine Grundidee besteht darin, alle zu klassifizierenden Beobachtungen (oder Stichproben) als anfängliche Clustering-Gruppe zu betrachten und diese Clustering-Gruppe dann gemäß einem bestimmten Clustering-Kriterium in mehrere Untergruppen zu zerlegen an der Reihe, bis bestimmte Beendigungsbedingungen erfüllt sind.

Bearbeitet um 2023-12-23 14:06:33

Deu-Martina

hierarchische Clusterbildung

Deu-Martina

Für Sie empfohlen
Gliederung

Neuronale Netze und wiederkehrende Deep-Learning-Neuronale Netze
tyyii7sc@bccto.c
Neuronale Netze und Deep Learning Convolutional Neural Networks
tyyii7sc@bccto.c
Die Grundlage neuronaler Netze und Deep Learning
tyyii7sc@bccto.c
traditionelles neuronales Netzwerk
tyyii7sc@bccto.c
Computer-Data-Mining-Kurs
tyyii7sc@bccto.c
Ensemble-Lernen
Deu-Martina
DBSCAN
Deu-Martina
K-bedeutet
Deu-Martina
Maschinelles Lernen (Xigua-Buch) Kapitel 1 Mind Map
Deu-Martina
KI
- 1
Deu-Martina

hierarchische Clusterbildung

Einführung

Algorithmische Idee: Hierarchien nach einer bestimmten Methode aufteilen, bis bestimmte Bedingungen erfüllt sind.

Illustration:

Zwei hierarchische Clustering-Methoden

Agglomerationsmethode

Algorithmusidee: Von unten nach oben wird jedes Objekt zunächst als Cluster behandelt und dann die Cluster zu immer größeren Clustern zusammengeführt, bis sich alle Objekte in einem Cluster befinden oder eine bestimmte Beendigungsbedingung erfüllen

Algorithmusschritte

Schritt 1: Berechnen Sie den Abstand zwischen den einzelnen Proben

Schritt 2: Die beiden Stichproben mit dem kleinsten Abstand werden in einer Kategorie zusammengefasst, nämlich Cluster C1

Schritt 3: Berechnen Sie den Abstand von anderen Proben zu C1

Entfernungsmessmethode zwischen Clustern

Methode 1: Methode des kürzesten Abstands (der Mindestabstand zwischen den Proben in Cluster Ci und Cluster Cj wird als Abstand zwischen den Clustern verwendet)

Methode 2: Methode des längsten Abstands (der maximale Abstand zwischen den Proben in Cluster Ci und Cluster Cj wird als Abstand zwischen den Clustern verwendet)

Methode 3: Klassendurchschnittsmethode (der Mittelwert der Abstände zwischen Cluster Ci und allen Stichproben im Cluster Cj wird als Abstand zwischen den Clustern verwendet)

Methode 4: Zentrumsmethode (der Abstand zwischen den Mittelpunkten von Cluster Ci und Cluster Cj (der Mittelwert der Stichproben im Cluster) wird als Abstand zwischen den Clustern verwendet)

Schritt 4: Führen Sie die Schritte 2 und 3 durch, bis sich alle Objekte in einem Cluster befinden oder eine bestimmte Beendigungsbedingung erfüllen

Illustration:

Split-Methode

Algorithmusidee: Platzieren Sie von oben nach unten zunächst alle Objekte im selben Cluster und teilen Sie sie dann schrittweise in immer kleinere Cluster auf, bis jedes Objekt einen eigenen Cluster bildet oder eine bestimmte Beendigungsbedingung erfüllt

Algorithmusschritte

Schritt 1: Gruppieren Sie alle Proben in einem Cluster, berechnen Sie den Abstand zwischen den einzelnen Proben und wählen Sie die beiden Proben mit dem größten Abstand aus.

Schritt 2: Teilen Sie die beiden am weitesten entfernten Proben in zwei Cluster auf und berechnen Sie die Abstände der anderen Proben zu den beiden Clustern.

Die Entfernungsmessmethode ist genau die gleiche wie die Agglomerationsmethode

Schritt 3: Teilen Sie andere Proben in engere Cluster auf

Schritt 4: Durchlaufen Sie die Schritte 2 und 3, bis jedes Objekt einen Cluster bildet oder eine bestimmte Beendigungsbedingung erfüllt.

Illustration:

Vor- und Nachteile des hierarchischen Clusterings

Vorteil

Abstand und Regelähnlichkeit sind einfach zu definieren

Es ist nicht erforderlich, die Anzahl der Cluster im Voraus anzugeben

Sie können die hierarchische Beziehung von Klassen entdecken

Mangel

Der Rechenaufwand ist zu hoch und die Datenmenge ist zu groß, um anwendbar zu sein.

Das Modell reagiert empfindlicher auf Ausreißer

Die Clusterform neigt dazu, kettenförmig zu sein

Optimierung

Ziel ist es, das Problem zu lösen, dass hierarchische Clustering-Daten zu groß sind, um verwendet zu werden

Methode: Verwenden Sie die mehrstufige Clustering-Technologie, um das Clustering inkrementell durchzuführen und die Clustering-Zeit erheblich zu verkürzen, d. h. den BIRCH-Algorithmus

Inkrementell: Die Clustering-Entscheidung jedes Datenpunkts basiert auf den aktuell verarbeiteten Datenpunkten und nicht auf den globalen Datenpunkten.

BIRCH-Algorithmus

Algorithmusprinzip: Clustering-Features verwenden 3-Tupel, um relevante Informationen über einen Cluster zu erhalten, indem ein Clustering-Feature-Baum erstellt wird, der die Einschränkungen des Verzweigungsfaktors und des Clusterdurchmessers erfüllt.

mehrere Konzepte

Clustering-Funktionen (CF)

Definition: CF ist ein Triplett, das durch (N, LS, SS) dargestellt werden kann. Unter diesen stellt N die Anzahl der Stichproben in dieser CF dar; LS stellt den Summenvektor jeder Merkmalsdimension der Stichprobenpunkte in dieser CF dar, und SS stellt die Summe der Quadrate jeder Merkmalsdimension der Stichprobenpunkte in dieser CF dar.

Eigenschaften: Erfüllen Sie die lineare Beziehung, d. h. CF1 CF2=(N1 N2,LS1 LS2,SS1 SS2)

Beispiel: Angenommen, eine bestimmte CF enthält 5 zweidimensionale Merkmalsproben (3,4), (2,6), (4,5), (4,7), (3,8).

CFs N=5

LS von CF=(3 2 4 4 3,4 6 5 7 8)=(16,30)

SS von CF=(3^2 2^2 4^2 4^2 3^2 4^2 6^2 5^2 7^2 8^2)=54 190=244

Cluster-Feature-Baum (CF-Baum)

Definition: Blattknoten sind Cluster, und Nicht-Blattknoten speichern die CF-Summe ihrer Nachkommen.

Parameter des CF-Baums

Maximale Anzahl von Nicht-Blattknoten: B (Verzweigungsfaktor)

Die maximale Anzahl von CFs, die in jedem Blattknoten enthalten sind: L

Maximaler Radiusschwellenwert für jede CF von Blattknoten: T

CF-Baum-Erstellungsprozess

Schritt 1: Lesen Sie die erste Probe ein und integrieren Sie sie in das neue Triplett LN1

Illustration:

Schritt 2: Lesen Sie die zweite Probe ab. Wenn sie sich innerhalb einer Kugel mit dem Radius T wie die vorherige Probe befindet, stellen Sie sie auf dasselbe Triplett LN2 ein.

Illustration:

Schritt 3: Wenn die neue Stichprobe dem LN1-Knoten am nächsten liegt, sich aber nicht mehr innerhalb des Hypersphärenradius T von SC1, SC2 und SC3 befindet und L=3 ist, muss sie geteilt werden.

Illustration:

Schritt 4: Finden Sie unter allen CF-Tupeln in LN1 die beiden am weitesten entfernten CFs, die die Start-CFs dieser beiden neuen Blattknoten sind, und fügen Sie dann alle CFs sc1, sc2, sc3 im LN1-Knoten sowie die neuen Elemente des hinzu Der neue Beispielpunkt sc6 ist in zwei neue Blattknoten unterteilt

Illustration:

Schritt 5: Wiederholen Sie die Schritte 2, 3 und 4, bis die Beendigungsbedingung erfüllt ist

Vorteile und Nachteile

Vorteil

Die Clustering-Geschwindigkeit ist hoch und Rauschpunkte können identifiziert werden

Lineare Skalierbarkeit, gute Clustering-Qualität

Mangel

Kann nur numerische Daten verarbeiten

Empfindlich gegenüber der Reihenfolge der Dateneingabe

Funktioniert nicht gut, wenn Cluster nicht sphärisch sind