DBSCAN

Ενημέρωση 2025-11-05 Ανάγνωση 4 λεπτά

Σύνοψη

Ο DBSCAN (Density-Based Spatial Clustering of Applications with Noise) ομαδοποιεί σημεία σύμφωνα με την τοπική πυκνότητα, ώστε οι συστάδες να μπορούν να έχουν οποιοδήποτε σχήμα, ενώ οι αραιές περιοχές γίνονται θόρυβος.
Δύο υπερπαράμετροι ελέγχουν το μοντέλο: eps, η ακτίνα γειτονιάς, και min_samples, ο ελάχιστος αριθμός γειτόνων που απαιτούνται ώστε ένα σημείο να γίνει πυρήνας.
Τα σημεία χαρακτηρίζονται ως πυρήνες, σύνορα ή θόρυβος· οι συστάδες είναι συνεκτικές συνιστώσες σημείων πυρήνα μαζί με τους γείτονες συνόρου τους.
Μια συνηθισμένη συνταγή ρύθμισης είναι να σταθεροποιήσετε το min_samples (≥ διαστασιμότητα + 1) και να σαρώσετε το eps ελέγχοντας το ποσοστό σημείων που επισημαίνονται ως θόρυβος.

Εισαγωγή #

Αυτή η μέθοδος πρέπει να ερμηνεύεται μέσα από τις υποθέσεις της, τις συνθήκες δεδομένων και τον τρόπο με τον οποίο οι επιλογές παραμέτρων επηρεάζουν τη γενίκευση.

Αναλυτική Επεξήγηση #

1. Επισκόπηση #

Ο DBSCAN δεν απαιτεί εκ των προτέρων τον αριθμό των συστάδων. Αντ’ αυτού, εξετάζει κάθε δείγμα:

Σημεία πυρήνα: τουλάχιστον min_samples γείτονες εντός απόστασης eps.
Σημεία συνόρου: βρίσκονται εντός της σφαίρας eps ενός σημείου πυρήνα αλλά δεν πληρούν τα ίδια το κριτήριο πυρήνα.
Σημεία θορύβου: δεν ανήκουν σε καμία γειτονιά πυρήνα.

Λόγω αυτής της οπτικής πυκνότητας, ο DBSCAN είναι ανθεκτικός σε μη κυρτές συστάδες όπως δύο μισοφέγγαρα ή ομόκεντροι κύκλοι. Πάντα κανονικοποιείτε τα χαρακτηριστικά ώστε το eps να έχει ουσιαστική ερμηνεία.

2. Τυπικός ορισμός #

Δεδομένου (x_i \in \mathcal{X}), η (\varepsilon)-γειτονιά του είναι

$$ \mathcal{N}_\varepsilon(x_i) = \{ x_j \in \mathcal{X} \mid \lVert x_i - x_j \rVert \le \varepsilon \}. $$

Αν (|\mathcal{N}_\varepsilon(x_i)| \ge \texttt{min_samples}|), το σημείο είναι πυρήνας. Ο DBSCAN κατασκευάζει συστάδες εξερευνώντας σημεία προσβάσιμα μέσω πυκνότητας· ό,τι μένει ανεπίσκεπτο γίνεται θόρυβος. Με χωρικό ευρετήριο η συνολική πολυπλοκότητα είναι (O(n \log n)).

3. Παράδειγμα σε Python #

Το παρακάτω απόσπασμα χρησιμοποιεί τον DBSCAN του scikit-learn σε ένα σύνολο δεδομένων δύο μισοφέγγαρων, χρωματίζει διαφορετικά τα σημεία πυρήνα/συνόρου και αναφέρει πόσα δείγματα επισημαίνονται ως θόρυβος.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
from __future__ import annotations

import japanize_matplotlib
import matplotlib.pyplot as plt
import numpy as np
from numpy.typing import NDArray
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler

def run_dbscan_demo(
    n_samples: int = 600,
    noise: float = 0.08,
    eps: float = 0.3,
    min_samples: int = 10,
    random_state: int = 0,
) -> dict[str, int]:
    japanize_matplotlib.japanize()
    features, _ = make_moons(
        n_samples=n_samples,
        noise=noise,
        random_state=random_state,
    )
    features = StandardScaler().fit_transform(features)

    model = DBSCAN(eps=eps, min_samples=min_samples)
    labels = model.fit_predict(features)

    unique_labels = sorted(np.unique(labels))
    cluster_ids = [label for label in unique_labels if label != -1]
    noise_count = int(np.sum(labels == -1))

    core_mask = np.zeros(labels.shape[0], dtype=bool)
    if hasattr(model, "core_sample_indices_"):
        core_mask[model.core_sample_indices_] = True

    fig, ax = plt.subplots(figsize=(6.2, 5.2))
    palette = plt.cm.get_cmap("tab10", max(len(cluster_ids), 1))

    for order, cluster_id in enumerate(cluster_ids):
        mask = labels == cluster_id
        color = palette(order)
        ax.scatter(
            features[mask & core_mask, 0],
            features[mask & core_mask, 1],
            c=[color],
            s=36,
            edgecolor="white",
            linewidth=0.2,
            label=f"Cluster {cluster_id} core",
        )
        ax.scatter(
            features[mask & ~core_mask, 0],
            features[mask & ~core_mask, 1],
            c=[color],
            s=24,
            edgecolor="white",
            linewidth=0.2,
            marker="o",
            label=f"Cluster {cluster_id} border",
        )

    if noise_count:
        noise_mask = labels == -1
        ax.scatter(
            features[noise_mask, 0],
            features[noise_mask, 1],
            c="#9ca3af",
            marker="x",
            s=28,
            linewidth=0.8,
            label="Noise",
        )

    ax.set_title("DBSCAN clustering demo")
    ax.set_xlabel("Feature 1")
    ax.set_ylabel("Feature 2")
    ax.grid(alpha=0.2)
    ax.legend(loc="upper right", fontsize=9)
    fig.tight_layout()
    plt.show()

    return {"n_clusters": len(cluster_ids), "n_noise": noise_count}

result = run_dbscan_demo()
print(f"Clusters discovered: {result['n_clusters']}")
print(f"Noise points: {result['n_noise']}")

Αποτέλεσμα ομαδοποίησης DBSCAN

4. Πρακτικές συμβουλές #

Σχεδιάστε τις ταξινομημένες αποστάσεις προς τον k-οστό γείτονα (k = min_samples) για να επιλέξετε το eps εκεί όπου η καμπύλη εμφανίζει αγκώνα.
Χρησιμοποιήστε pipelines ώστε η κανονικοποίηση και η ομαδοποίηση να εκτελούνται μαζί· διαφορετικά οι αποφάσεις βάσει απόστασης γίνονται χωρίς νόημα.
Για πολύ μεγάλα σύνολα δεδομένων εξετάστε προσεγγιστικούς πλησιέστερους γείτονες ή μεταβείτε στον HDBSCAN, ο οποίος επεκτείνει τον DBSCAN σε δεδομένα πολλαπλής πυκνότητας και αφαιρεί την ανάγκη ρύθμισης του eps.

5. Αναφορές #

Ester, M., Kriegel, H.-P., Sander, J., & Xu, X. (1996). A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise. KDD.
Schubert, E., Sander, J., Ester, M., Kriegel, H.-P., & Xu, X. (2017). DBSCAN Revisited, Revisited. ACM Transactions on Database Systems.
scikit-learn developers. (2024). Clustering. https://scikit-learn.org/stable/modules/clustering.html