K_DM Book
用語集
対象者 標準
対象者別の入口 →

対象者の設定はこのブラウザの中にだけ保存されます。

言語 JA

DBSCAN

入門

02.5.4

DBSCAN

最終更新 2020-03-11 読了時間 4 分
まとめ
DBSCAN(Density-Based Spatial Clustering of Applications with Noise)は、点が密集している場所をクラスタ、まばらな場所をノイズとして切り分ける手法です。指定するのは半径 eps と、その円の中に必要な点数 min_samples の 2 つだけで、クラスタ数は結果として決まります。各点は円の中の仲間の数でコア・境界・ノイズに分類され、コア同士の円が重なってつながった範囲が 1 つのクラスタになります。月型のように丸くないクラスタも追えますが、距離で判定するので StandardScaler で列のスケールを揃えておかないと eps の意味が列ごとにずれます。

直感 #

夜景の写真で「街」を数える場面を考えます。明かりが密に集まっている範囲をひとかたまりの街と見なし、ぽつんと離れた 1 つの明かりは街に数えない。DBSCAN がやっているのはこの判定で、各点を中心に半径 eps の円を描き、円の中に自分を含めて min_samples 個以上の点があればその点をコアポイントと呼びます。自分の円には点が足りないがコアポイントの円の中には入っている点は境界ポイント、どのコアの円にも入らない点はノイズ(ラベル -1)です。

コアポイントの円が重なり合って鎖のようにつながると、その鎖全体が同じ密度領域、つまり 1 つのクラスタになります。円をつないでいくだけなので、make_moons の三日月や輪のような形でも途切れずに追いかけられます。弱点は密度の差で、密なクラスタと疎なクラスタが混ざっていると 1 つの eps では両方を拾えません。

何が起きているか(ステップで見る) #

コードを読む前に、この手法が図の上で何をしているかを追ってみましょう。「再生」を押すか、スライダーを動かすと 1 手順ずつ進みます。

見るポイント:クラスターは「円がつながる範囲」。丸くない形でも追いかけられ、どの円にも入らない点はノイズになる。

式で書くと何を数えているか #

「円の中の仲間」を式にすると、点 \(x_i\) から距離 \(\varepsilon\)(引数 eps)以内にある点の集合になります。

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

この集合の要素数が min_samples 以上ならコアポイントです。図の上では「円の中に点が 10 個以上あるか」を数えているだけです。

$$ |\mathcal{N}_\varepsilon(x_i)| \ge \texttt{min\_samples} $$

コアポイント \(x_i\) の近傍 \(\mathcal{N}_\varepsilon(x_i)\) に別のコアポイント \(x_j\) が入っていれば 2 点は直接つながり、この関係をたどって到達できるコア全体が 1 つのクラスタになります(密度連結)。境界ポイントは自分がコアでなくても、どれかのコアの近傍に入っていればそのクラスタに所属します。ノイズはどのコアの \(\varepsilon\)-近傍にも入らない点です。scikit-learn ではラベル -1 が付きます。

Pythonで確かめる #

次のコードは make_moons で三日月 2 つの形をした 600 点を作り、標準化してから DBSCAN(eps=0.3, min_samples=10) を当てます。コアと境界を点の大きさで、ノイズを灰色の × で描き分け、最後にクラスタ数とノイズ点数を表示します。

 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によるクラスタリング結果

実行結果の読み方 #

出力は「検出されたクラスタ数: 2」と 1 桁の「ノイズ点の数」で、図では上下 2 つの三日月がそれぞれ別の色に塗られます。k-means なら月の中央で縦に割るデータです。DBSCAN は円をつないでいくので、月の端まで同じ色が続きます。大きい点が密な芯(コア)、小さい点が縁(境界)、× がノイズで、× は月の先端や外側に出やすい点だけに付きます。

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

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

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

スライダーで eps を 0.1 から 1.5 まで動かすと、同じ 200 点がどう分かれるかが変わります。0.1 ではほぼ全点がノイズ(188 点)、0.2 では 11 個の小さな破片、0.3〜0.4 で 2 つの月がきれいに分かれ、0.5 以上では全体が 1 つに融合します。

使いどころと落とし穴 #

DBSCAN が向いているのは、三日月や輪のように重心で表せない形のクラスタと、外れ値を明示的に捨てたいデータです。クラスタ数を決めずに済む代わりに、eps と min_samples の 2 つが結果を左右します。min_samples は次元数 +1 を目安にまず固定し、eps は NearestNeighbors で求めた k 距離プロットの肘から選ぶと、総当たりより早く妥当な値にたどり着けます。距離が全ての判断材料なので、StandardScaler を忘れると値の範囲が広い列だけで近傍が決まります。高次元では距離が均一化して密度の差が消えるため、UMAP などで 2〜10 次元に落としてから適用するか、密度差に強い HDBSCAN に切り替えるのが次の一手です。

まとめ #

DBSCAN は半径 eps の円に min_samples 個以上の点があるかで各点をコア・境界・ノイズに分け、コアの円がつながった範囲を 1 つのクラスタにします。n_clusters を指定せずに月型のような非凸クラスタを拾え、ノイズにはラベル -1 が付くので外れ値検出にも使えます。結果を決めるのは eps と min_samples の 2 つで、上のスライダーの通り eps を 0.2 から 0.5 に変えるだけでクラスタ数は 11 から 1 まで動きます。StandardScaler で列のスケールを揃えるのは前提条件で、密度差が大きいデータでは HDBSCAN を選びます。

参考文献 #

  • 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 — eps を 1 つに固定せず密度差のあるクラスタを階層的に取り出す拡張
  • k-means — 重心ベースの代替手法
  • スペクトラルクラスタリング — 近傍グラフの固有ベクトルで分けるグラフベースの手法
  • UMAP — 高次元データを DBSCAN にかける前の次元削減に有効