DBSCAN

最終更新 2020-03-11 読了時間 3 分

まとめ

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）は、密度が高い領域をクラスタ、疎な領域をノイズとして扱うアルゴリズムです。
距離の半径 eps と近傍に必要な点数 min_samples を指定し、点をコア・境界・ノイズの 3 種類に分類します。
クラスタ数を事前に決める必要がなく、非凸な形のクラスタやノイズを含むデータに強いのが特徴です。
min_samples-距離プロットを手掛かりに eps を調整し、距離のスケールを揃えるために標準化しておくと安定します。

直感 #

DBSCAN は「点の周囲に十分な仲間がいるかどうか」を基準にクラスタを構成します。

コアポイント: 半径 eps の円内に min_samples 個以上の点がある点。
境界ポイント: コアポイントの近傍に存在するが、自分自身は条件を満たさない点。
ノイズ: コアにも境界にも分類されない孤立した点。

コアポイント同士が鎖のようにつながると同じ密度領域として扱われ、その領域が 1 つのクラスタになります。クラスタの形が不規則でも対応できますが、密度差が大きいデータではパラメータ調整が重要です。

flowchart LR A["各点のε近傍\nを計算"] --> B{"min_samples\n以上？"} B -->|Yes| C["コアポイント"] B -->|No| D{"コアの\n近傍？"} D -->|Yes| E["境界ポイント"] D -->|No| F["ノイズ"] C --> G["密度連結な\nコアを統合"] G --> H["クラスタ形成"] style A fill:#2563eb,color:#fff style C fill:#1e40af,color:#fff style H fill:#10b981,color:#fff style F fill:#ef4444,color:#fff

数式で見る #

データ集合 $\mathcal{X}$ の点 $x_i$ に対し、eps で定義される $\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} $$

コアポイント同士が密度連結であれば同じクラスタに属し、境界ポイントはクラスタにぶら下がる形で所属します。ノイズはどのクラスタにも属さない点です。

Pythonで確かめる #

標準化した月型データに DBSCAN を適用し、クラスタ数とノイズ点の数を確認します。

 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
from __future__ import annotations

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]:
    """DBSCAN で月型データをクラスタリングし、クラスタ数とノイズ点を調べる。"""
    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_id}（コア）",
        )
        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_id}（境界）",
        )

    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="ノイズ",
        )

    ax.set_title("DBSCAN によるクラスタリング")
    ax.set_xlabel("特徴量 1")
    ax.set_ylabel("特徴量 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"検出されたクラスタ数: {result['n_clusters']}")
print(f"ノイズ点の数: {result['n_noise']}")

DBSCANによるクラスタリング結果

DBSCANはクラスター間の密度が大きく異なるデータには苦手です。epsを小さくすると疎なクラスターがノイズに分解され、大きくすると密なクラスターが結合してしまいます。密度差が大きい場合はHDBSCANを検討してください。

epsの選び方に迷ったら、各点のmin_samples番目に近い点までの距離をソートしてプロットし、急激に増加する「肘」の位置をepsの候補にしてください。NearestNeighborsのkneighborsメソッドで簡単に計算できます。

eps とクラスタリング結果 #

eps を変えるとクラスタの数とノイズ点がどう変わるか確認できます。

まとめ #

DBSCANは密度が高い領域をクラスター、疎な領域をノイズとして自動的に分離します。
クラスター数を事前に指定する必要がなく、非凸な形のクラスターも扱えます。
epsとmin_samplesの2つのパラメーターがクラスタリングの品質を決定します。
特徴量の標準化は必須で、スケールが揃っていないと距離計算が偏りクラスター構造を正しく捉えられません。

参考文献 #

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

HDBSCAN — DBSCAN の階層的拡張
k-means — セントロイドベースの代替手法
スペクトラルクラスタリング — グラフベースの手法
UMAP — クラスタリング前の次元削減に有効