Demo des HDBSCAN-Clustering-Algorithmus

In dieser Demo werden wir uns cluster.HDBSCAN aus der Perspektive der Verallgemeinerung des cluster.DBSCAN-Algorithmus ansehen. Wir werden beide Algorithmen auf spezifischen Datensätzen vergleichen. Schließlich werden wir die Sensitivität von HDBSCAN gegenüber bestimmten Hyperparametern bewerten.

Wir definieren zunächst ein paar Hilfsfunktionen für den Komfort.

# Authors: The scikit-learn developers
# SPDX-License-Identifier: BSD-3-Clause

import matplotlib.pyplot as plt
import numpy as np

from sklearn.cluster import DBSCAN, HDBSCAN
from sklearn.datasets import make_blobs


def plot(X, labels, probabilities=None, parameters=None, ground_truth=False, ax=None):
    if ax is None:
        _, ax = plt.subplots(figsize=(10, 4))
    labels = labels if labels is not None else np.ones(X.shape[0])
    probabilities = probabilities if probabilities is not None else np.ones(X.shape[0])
    # Black removed and is used for noise instead.
    unique_labels = set(labels)
    colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]
    # The probability of a point belonging to its labeled cluster determines
    # the size of its marker
    proba_map = {idx: probabilities[idx] for idx in range(len(labels))}
    for k, col in zip(unique_labels, colors):
        if k == -1:
            # Black used for noise.
            col = [0, 0, 0, 1]

        class_index = (labels == k).nonzero()[0]
        for ci in class_index:
            ax.plot(
                X[ci, 0],
                X[ci, 1],
                "x" if k == -1 else "o",
                markerfacecolor=tuple(col),
                markeredgecolor="k",
                markersize=4 if k == -1 else 1 + 5 * proba_map[ci],
            )
    n_clusters_ = len(set(labels)) - (1 if -1 in labels else 0)
    preamble = "True" if ground_truth else "Estimated"
    title = f"{preamble} number of clusters: {n_clusters_}"
    if parameters is not None:
        parameters_str = ", ".join(f"{k}={v}" for k, v in parameters.items())
        title += f" | {parameters_str}"
    ax.set_title(title)
    plt.tight_layout()

Beispieldaten generieren

Einer der größten Vorteile von HDBSCAN gegenüber DBSCAN ist seine Out-of-the-Box-Robustheit. Dies ist besonders bemerkenswert bei heterogenen Datenmischungen. Wie DBSCAN kann es beliebige Formen und Verteilungen modellieren, im Gegensatz zu DBSCAN erfordert es jedoch keine Angabe eines willkürlichen und empfindlichen eps-Hyperparameters.

Zum Beispiel generieren wir unten einen Datensatz aus einer Mischung von drei zweidimensionalen und isotropen Gauß-Verteilungen.

centers = [[1, 1], [-1, -1], [1.5, -1.5]]
X, labels_true = make_blobs(
    n_samples=750, centers=centers, cluster_std=[0.4, 0.1, 0.75], random_state=0
)
plot(X, labels=labels_true, ground_truth=True)

Skaleninvarianz

Es ist erwähnenswert, dass DBSCAN zwar einen Standardwert für den Parameter eps bereitstellt, dieser aber kaum einen richtigen Standardwert hat und für den jeweiligen Datensatz abgestimmt werden muss.

Als einfache Demonstration betrachten wir das Clustering für einen eps-Wert, der für einen Datensatz abgestimmt wurde, und das Clustering, das mit demselben Wert erzielt wurde, aber auf skalierte Versionen des Datensatzes angewendet wird.

fig, axes = plt.subplots(3, 1, figsize=(10, 12))
dbs = DBSCAN(eps=0.3)
for idx, scale in enumerate([1, 0.5, 3]):
    dbs.fit(X * scale)
    plot(X * scale, dbs.labels_, parameters={"scale": scale, "eps": 0.3}, ax=axes[idx])

Tatsächlich müssten wir, um dieselben Ergebnisse zu erzielen, eps mit demselben Faktor skalieren.

fig, axis = plt.subplots(1, 1, figsize=(12, 5))
dbs = DBSCAN(eps=0.9).fit(3 * X)
plot(3 * X, dbs.labels_, parameters={"scale": 3, "eps": 0.9}, ax=axis)

Während die Standardisierung von Daten (z. B. unter Verwendung von sklearn.preprocessing.StandardScaler) zur Minderung dieses Problems beiträgt, muss darauf geachtet werden, den geeigneten Wert für eps auszuwählen.

HDBSCAN ist in diesem Sinne viel robuster: HDBSCAN kann als Clustering über alle möglichen Werte von eps betrachtet werden, wobei die besten Cluster aus allen möglichen Clustern extrahiert werden (siehe Benutzerhandbuch). Ein unmittelbarer Vorteil ist, dass HDBSCAN skaleninvariant ist.

fig, axes = plt.subplots(3, 1, figsize=(10, 12))
hdb = HDBSCAN(copy=True)
for idx, scale in enumerate([1, 0.5, 3]):
    hdb.fit(X * scale)
    plot(
        X * scale,
        hdb.labels_,
        hdb.probabilities_,
        ax=axes[idx],
        parameters={"scale": scale},
    )

Multiskalen-Clustering

HDBSCAN ist jedoch viel mehr als skaleninvariant – es ist in der Lage, multiskales Clustering durchzuführen, das Cluster mit unterschiedlicher Dichte berücksichtigt. Traditionelles DBSCAN geht davon aus, dass alle potenziellen Cluster eine homogene Dichte aufweisen. HDBSCAN ist frei von solchen Einschränkungen. Um dies zu demonstrieren, betrachten wir den folgenden Datensatz

centers = [[-0.85, -0.85], [-0.85, 0.85], [3, 3], [3, -3]]
X, labels_true = make_blobs(
    n_samples=750, centers=centers, cluster_std=[0.2, 0.35, 1.35, 1.35], random_state=0
)
plot(X, labels=labels_true, ground_truth=True)

Dieser Datensatz ist für DBSCAN aufgrund der unterschiedlichen Dichten und räumlichen Trennung schwieriger

• Wenn eps zu groß ist, riskieren wir, die beiden dichten Cluster fälschlicherweise als einen zu gruppieren, da ihre gegenseitige Erreichbarkeit die Cluster erweitert.

• Wenn eps zu klein ist, riskieren wir, die dichteren Cluster in viele falsche Cluster zu fragmentieren.

Ganz zu schweigen davon, dass dies manuelles Tuning von eps-Wahlmöglichkeiten erfordert, bis wir einen Kompromiss gefunden haben, mit dem wir zufrieden sind.

fig, axes = plt.subplots(2, 1, figsize=(10, 8))
params = {"eps": 0.7}
dbs = DBSCAN(**params).fit(X)
plot(X, dbs.labels_, parameters=params, ax=axes[0])
params = {"eps": 0.3}
dbs = DBSCAN(**params).fit(X)
plot(X, dbs.labels_, parameters=params, ax=axes[1])

Um die beiden dichten Cluster richtig zu gruppieren, bräuchten wir einen kleineren eps-Wert, aber bei eps=0.3 fragmentieren wir bereits die spärlichen Cluster, was mit abnehmendem eps nur noch schlimmer würde. Tatsächlich scheint DBSCAN unfähig zu sein, gleichzeitig die beiden dichten Cluster zu trennen und gleichzeitig zu verhindern, dass die spärlichen Cluster fragmentieren. Vergleichen wir dies mit HDBSCAN.

hdb = HDBSCAN(copy=True).fit(X)
plot(X, hdb.labels_, hdb.probabilities_)

HDBSCAN ist in der Lage, sich an die Multiskalen-Struktur des Datensatzes anzupassen, ohne dass eine Parameterabstimmung erforderlich ist. Während jeder ausreichend interessante Datensatz eine Abstimmung erfordert, zeigt dieser Fall, dass HDBSCAN qualitativ bessere Clusterings liefern kann, ohne dass der Benutzer eingreifen muss, was mit DBSCAN nicht zugänglich ist.

Hyperparameter-Robustheit

Letztendlich wird die Abstimmung ein wichtiger Schritt in jeder realen Anwendung sein, also werfen wir einen Blick auf einige der wichtigsten Hyperparameter für HDBSCAN. Während HDBSCAN frei vom eps-Parameter von DBSCAN ist, hat es immer noch einige Hyperparameter wie min_cluster_size und min_samples, die seine Ergebnisse in Bezug auf die Dichte steuern. Wir werden jedoch sehen, dass HDBSCAN dank dieser Parameter, deren klare Bedeutung die Abstimmung erleichtert, relativ robust gegenüber verschiedenen realen Beispielen ist.

min_cluster_size

min_cluster_size ist die Mindestanzahl von Stichproben in einer Gruppe, damit diese Gruppe als Cluster betrachtet wird.

Cluster, die kleiner als diese Größe sind, werden als Rauschen behandelt. Der Standardwert ist 5. Dieser Parameter wird im Allgemeinen bei Bedarf auf größere Werte abgestimmt. Kleinere Werte führen wahrscheinlich zu Ergebnissen mit weniger als Rauschen gekennzeichneten Punkten. Werte, die zu klein sind, führen jedoch dazu, dass falsche Untercluster erkannt und bevorzugt werden. Größere Werte sind tendenziell robuster gegenüber verrauschten Datensätzen, z. B. Clustern mit hoher Varianz und signifikanter Überlappung.

PARAM = ({"min_cluster_size": 5}, {"min_cluster_size": 3}, {"min_cluster_size": 25})
fig, axes = plt.subplots(3, 1, figsize=(10, 12))
for i, param in enumerate(PARAM):
    hdb = HDBSCAN(copy=True, **param).fit(X)
    labels = hdb.labels_

    plot(X, labels, hdb.probabilities_, param, ax=axes[i])

min_samples

min_samples ist die Anzahl der Stichproben in einer Nachbarschaft, damit ein Punkt als Kernpunkt betrachtet wird, einschließlich des Punktes selbst. min_samples hat standardmäßig den Wert min_cluster_size. Ähnlich wie bei min_cluster_size erhöhen größere Werte für min_samples die Robustheit des Modells gegenüber Rauschen, bergen aber das Risiko, potenziell gültige, aber kleine Cluster zu ignorieren oder zu verwerfen. min_samples sollte besser abgestimmt werden, nachdem ein guter Wert für min_cluster_size gefunden wurde.

PARAM = (
    {"min_cluster_size": 20, "min_samples": 5},
    {"min_cluster_size": 20, "min_samples": 3},
    {"min_cluster_size": 20, "min_samples": 25},
)
fig, axes = plt.subplots(3, 1, figsize=(10, 12))
for i, param in enumerate(PARAM):
    hdb = HDBSCAN(copy=True, **param).fit(X)
    labels = hdb.labels_

    plot(X, labels, hdb.probabilities_, param, ax=axes[i])

dbscan_clustering

Während des fit-Vorgangs erstellt HDBSCAN einen Single-Linkage-Baum, der das Clustering aller Punkte für alle Werte des eps-Parameters von DBSCAN kodiert. Wir können diese Clusterings somit effizient darstellen und bewerten, ohne Zwischenwerte wie Kern-Distanzen, gegenseitige Erreichbarkeiten und den minimalen Spannbaum vollständig neu zu berechnen. Alles, was wir tun müssen, ist die cut_distance (entspricht eps) anzugeben, mit der wir gruppieren möchten.

PARAM = (
    {"cut_distance": 0.1},
    {"cut_distance": 0.5},
    {"cut_distance": 1.0},
)
hdb = HDBSCAN(copy=True)
hdb.fit(X)
fig, axes = plt.subplots(len(PARAM), 1, figsize=(10, 12))
for i, param in enumerate(PARAM):
    labels = hdb.dbscan_clustering(**param)

    plot(X, labels, hdb.probabilities_, param, ax=axes[i])

Verwandte Beispiele

Vergleich verschiedener Clustering-Algorithmen auf Toy-Datensätzen

Vergleich verschiedener Clustering-Algorithmen auf Toy-Datensätzen

Release Highlights für scikit-learn 1.3

Release Highlights für scikit-learn 1.3

Demo des DBSCAN Clustering Algorithmus

Demo des DBSCAN Clustering Algorithmus

Die Johnson-Lindenstrauss-Schranke für Einbettung mit zufälligen Projektionen

Die Johnson-Lindenstrauss-Schranke für Einbettung mit zufälligen Projektionen