Agglomerative Clusteranalyse

Agglomerative Clustering ist ein hierarchischer Clustering-Algorithmus, der im maschinellen Lernen und Data Mining verwendet wird: Er gruppiert ähnliche Datenpunkte in verschachtelte Cluster basierend auf ihren paarweisen Abständen. Der Algorithmus besteht aus drei verschiedenen Schritten:

Schritt 1. Machen Sie jeden Datenpunkt zu einem Cluster;

Schritt 2. Nehmen Sie die beiden nächstgelegenen Cluster und machen Sie daraus einen Cluster;

Schritt 3. Wiederholen Sie Schritt 2, bis nur noch ein Cluster übrig ist;

Aber wie führt man Clustering durch, wenn das Ergebnis immer ein Cluster ist? Im Gegensatz zu anderen Clustering-Algorithmen, bei denen die Anzahl der Cluster im Voraus festgelegt werden muss, erzeugt das hierarchische Clustering eine hierarchische baumartige Struktur, die als Dendrogramm bezeichnet wird und die Bestimmung der Anzahl der Cluster nach dem Clustering-Prozess ermöglicht.

Dendrogramm ist ein Diagramm, das die hierarchische Beziehung zwischen Objekten zeigt. So können wir mit Hilfe des Dendrogramms verfolgen, in welcher Reihenfolge welche Cluster während der Ausführung des Algorithmus kombiniert werden. Und es ist mit Hilfe des Dendrogramms, dass die optimale Anzahl von Clustern, in die unsere Daten unterteilt werden können, bestimmt wird:

Identifizieren Sie die längste vertikale Linie: Suchen Sie nach der längsten Linie, die keine horizontalen Linien im Dendrogramm kreuzt. Dies stellt die größte Entfernung zwischen zwei Clustern im Datensatz dar;
Zeichnen Sie eine horizontale Linie: Zeichnen Sie eine horizontale Linie durch die in Schritt 2 identifizierte längste vertikale Linie (die rote gestrichelte Linie im Bild unten). Diese Linie wird in einer Höhe gezeichnet, in der die Dendrogrammzweige relativ lang und klar sind, was auf eine natürliche Trennung zwischen Clustern hinweist;
Die Anzahl der Cluster wird durch die Anzahl der Male bestimmt, die die horizontale Linie das Dendrogramm schneidet.

Hinweis

Selbst mit einem Dendrogramm kann es mehrere Optionen zur Aufteilung der Daten in Cluster geben: Die am besten geeignete Anzahl von Clustern kann durch die Kombination eines Dendrogramms mit Wissen aus dem Fachgebiet definiert werden.

Hinweis

Im agglomerativen Algorithmus können wir auch die Anzahl der Cluster voreinstellen. In diesem Fall wird das Dendrogramm in Cluster unterteilt, sodass die Anzahl der Cluster im Ergebnis der a priori gegebenen entspricht.

Ein sehr wichtiger Parameter des Algorithmus ist die Verknüpfung: die Methode, die zur Berechnung der Entfernung zwischen zwei Clustern verwendet wird. Es gibt mehrere Verknüpfungsmethoden, die verwendet werden können, darunter:

Single Linkage: Diese Methode berechnet die Entfernung zwischen zwei Clustern als die kürzeste Entfernung zwischen zwei Punkten in den beiden Clustern;
Complete Linkage: Diese Methode berechnet die Entfernung zwischen zwei Clustern als die längste Entfernung zwischen zwei Punkten in den beiden Clustern;
Average Linkage: Diese Methode berechnet die Entfernung zwischen zwei Clustern als den durchschnittlichen Abstand zwischen allen Punktpaaren in den beiden Clustern.

Schließlich schauen wir uns die Python-Implementierung des agglomerativen Clustering an:


              123456789101112131415161718192021
            
from sklearn.cluster import AgglomerativeClustering
import numpy as np
import matplotlib.pyplot as plt
from sklearn.datasets import make_blobs
# Firstly, we will create our dataset
X, y = make_blobs(n_samples=500, cluster_std=1, centers=4, random_state=170)
transformation = [[0.6, -0.6], [-0.4, 0.8]]
X_aniso = np.matmul(X, transformation)

# In this line we will specify parameters of our Agglomerative model
agglomerative = AgglomerativeClustering(linkage='single',
                                        distance_threshold=0.6, n_clusters=None)
# Training our model
agglomerative.fit(X_aniso)

# Providing visualization of results
fig, axes=plt.subplots(1,2)
axes[0].scatter(X[:, 0], X[:, 1], c=agglomerative.labels_, s=50, cmap='tab20b')
axes[0].set_title('Clustered data')
axes[1].scatter(X[:, 0], X[:, 1], c=y, s=50, cmap='tab20b')
axes[1].set_title('Real data')

Im obigen Code verwenden wir die AgglomerativeClustering-Klasse, um ein Modell zu erstellen, wobei:

der Parameter linkage den Verbindungstyp bestimmt: 'complete', 'average', 'single';
distance_threshold ist der Verbindungsabstandsschwellenwert, bei dem oder über dem Cluster nicht zusammengeführt werden.

Hinweis

Die AgglomerativeClustering-Klasse hat keine Implementierung für die .predict()-Methode: Wir müssen das Modell jedes Mal trainieren, wenn wir neue Daten clustern möchten.

War alles klar?

Danke für Ihr Feedback!

Abschnitt 2. Kapitel 3