[機械学習のはじめ方] Part27: DBSCANと密度に基づくクラスタリング

機械学習
入門学習教科書機械学習

はじめに: なぜ密度ベース？ 🤔

みなさん、こんにちは！機械学習の旅、Step 5へようこそ！今回は教師なし学習の中でも、特にユニークなアプローチをとる「クラスタリング」の手法、DBSCAN (Density-Based Spatial Clustering of Applications with Noise) について学びます。

これまでに学んだ k-means クラスタリングは、クラスタの中心からの距離に基づいてデータをグループ分けしましたね。しかし、k-means はクラスタの形状が球状であることを仮定しており、複雑な形（例えば、三日月形やドーナツ形）のデータや、外れ値（ノイズ）が多いデータにはうまく対応できないことがあります。また、事前にクラスタ数を決める必要がありました。

そこで登場するのが密度ベースのクラスタリングです！🚀 このアプローチは、データが密集している領域を一つのクラスタとして捉えます。DBSCAN はその代表的なアルゴリズムで、「データ点の密集度合い」に着目することで、以下のような利点があります。

  • クラスタの形状を仮定しない（任意の形状のクラスタを発見可能）
  • クラスタ数を事前に指定する必要がない
  • ノイズ（外れ値）を自動的に識別できる

このブログでは、DBSCAN がどのようにしてこれらの課題を解決するのか、その仕組みから実装までをわかりやすく解説していきます。さっそく、密度ベースの世界を探検しましょう！

DBSCANの仕組みを解き明かす 💡

DBSCAN は、データ点がどれだけ密集しているかに基づいてクラスタを形成します。その中心となる考え方を理解するために、まずは重要なキーワードを押さえましょう。

重要なキーワード

  • ε (イプシロン / eps): ある点から見て、「近傍」とみなす範囲の半径。この円内に入る点が探索対象となります。
  • MinPts (最小近傍点数 / min_samples): ある点が「密な領域」の中心（コア点）であるとみなされるために、ε の範囲内に最低限含まれるべきデータ点の数（自分自身を含む）。
  • コア点 (Core Point): ε の範囲内に MinPts 以上の点を持つ点。クラスタの中心的な存在です。
  • ボーダー点 (Border Point): 自身の ε の範囲内には MinPts 未満の点しか持たないが、いずれかのコア点の ε の範囲内には含まれる点。クラスタの端に位置します。
  • ノイズ点 (Noise Point / Outlier): コア点でもボーダー点でもない点。どのクラスタにも属さない、いわゆる外れ値です。

アルゴリズムの流れ

DBSCAN は以下のステップでクラスタを形成していきます。

  1. 点の選択: まだどのクラスタにも割り当てられていない（未訪問の）データ点 P を一つ選びます。
  2. 近傍の探索: 点 P の ε 半径内にあるデータ点の数を数えます。
  3. コア点判定:
    • もし近傍点の数が MinPts 以上であれば、点 P はコア点と認定されます。新しいクラスタが誕生し 🎉、P はこのクラスタに属します。さらに、P の ε 近傍にある全ての点も、同じクラスタに（一時的に）属するものとします。
    • もし P の近傍にある点が他のコア点 Q であれば、Q の ε 近傍にある点も再帰的に探索し、同じクラスタに追加していきます（密度到達可能）。これにより、密度の高い領域が連結されて一つのクラスタとして成長していきます。
  4. ノイズ点 or ボーダー点判定:
    • もし近傍点の数が MinPts 未満であれば、点 P は現時点ではコア点ではありません。
    • この P が、他のコア点の ε 近傍に含まれていれば、P はボーダー点として、そのコア点が属するクラスタの一部となります。
    • どのコア点の ε 近傍にも含まれていなければ、P はノイズ点と判定されます。
  5. 繰り返し: 全てのデータ点が訪問され、いずれかのクラスタに属するか、ノイズ点として判定されるまで、ステップ 1 から 4 を繰り返します。

このプロセスにより、データが密な領域は連結されてクラスタとなり、どのクラスタにも属さない疎な領域の点はノイズとして扱われます。

DBSCANの強みと弱み 💪😥

メリット

  • ✅ クラスタ数の自動決定: k-means のように事前にクラスタ数を指定する必要がありません。データの中から適切なクラスタ数を自動で見つけ出します。
  • ✅ 任意の形状のクラスタ検出: データの密集度を見るため、k-means が苦手とする複雑な形状（例: 三日月、ドーナツ）のクラスタも得意です。
  • ✅ ノイズ（外れ値）の検出: どのクラスタにも属さない点をノイズとして明確に区別できます。これはデータ分析において非常に役立ちます。

デメリット

  • ❌ 密度の違いに弱い: クラスタによって密度が大きく異なる場合、単一の ε と MinPts 設定ではうまく全てのクラスタを捉えられないことがあります。密度の低いクラスタがノイズと判定されたり、逆に密度の異なるクラスタが一つにまとまってしまう可能性があります。
  • ❌ 高次元データでの性能: データが高次元になると、点と点の距離が離れてしまい、「密な領域」という概念自体が曖昧になりがちです（次元の呪い）。これにより、適切なパラメータ設定が難しくなり、性能が低下することがあります。
  • ❌ パラメータ依存性: ε と MinPts の値によってクラスタリング結果が大きく変わります。これらのパラメータを適切に設定することが重要ですが、試行錯誤が必要になる場合があります。

ハイパーパラメータをどう決める？ ⚙️

DBSCAN の性能は、ハイパーパラメータである ε と MinPts の設定に大きく左右されます。適切な値を見つけるための一般的な指針を紹介します。

MinPtsの決め方

MinPts は、ノイズとみなす点の最低密度を決定します。

  • 一般的に、MinPts はデータセットの次元数 D に対して MinPts ≥ D + 1 が推奨されます。これは、D次元空間で点を定義するには最低 D+1 個の点が必要だからです。
  • 経験則として、MinPts = 2 * D を出発点とすることが多いです。
  • データセットが大きい場合やノイズが多い場合は、MinPts を大きめに設定すると、より頑健なクラスタリングが期待できます。ただし、大きくしすぎると小さなクラスタが検出されにくくなります。

εの決め方 (k-distance graph)

ε は、点の「近傍」の範囲を定義します。適切な ε を見つける一般的な方法として、k-distance graph を用いる方法があります。ここで、k は MinPts – 1 とします（自分自身を除いた近傍点の数）。

  1. 各データ点について、自身から k 番目に近い点までの距離（k-distance）を計算します。
  2. 計算した k-distance を降順（または昇順）にソートし、グラフにプロットします。（縦軸: k-distance, 横軸: データ点のインデックス）
  3. グラフ上で、距離が急激に変化する点、いわゆる「肘 (elbow)」を探します。この肘の部分に対応する距離の値が、ε の良い候補となります。
  4. 肘が見つからない場合は、データが均一に分布しているか、MinPts の設定が適切でない可能性があります。

これらの方法はあくまで目安であり、最終的にはデータの特性や分析の目的に合わせて、いくつかの値を試し、結果を評価しながら調整することが重要です。（モデル評価については Step 4 で詳しく学びます！）

Python (scikit-learn) でDBSCANを動かしてみよう！ 💻

理論を学んだところで、実際に Python のライブラリ scikit-learn を使って DBSCAN を動かしてみましょう。ここでは、簡単な2次元のデータセット（三日月形）を使って、DBSCAN がどのようにクラスタリングを行うかを見ていきます。


# 必要なライブラリのインポート
import numpy as np
from sklearn.cluster import DBSCAN
from sklearn.datasets import make_moons
from sklearn.preprocessing import StandardScaler
# import matplotlib.pyplot as plt # 可視化用 (今回はグラフ表示はしない)

# データの生成 (三日月形データ)
# 200個のサンプルを生成し、ノイズを少し加える
X, y_true = make_moons(n_samples=200, noise=0.05, random_state=42)

# データの前処理 (標準化)
# DBSCANは距離に基づいて計算するため、特徴量のスケールを揃えることが重要
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# DBSCANモデルの作成と学習・予測
# eps: ε (探索半径) - 事前にk-distance graphなどで検討することが望ましい
# min_samples: MinPts (最小近傍点数) - 今回は次元数2の2倍+1で5とする
dbscan = DBSCAN(eps=0.3, min_samples=5)

# fit_predictメソッドで学習とクラスタラベルの予測を同時に行う
clusters = dbscan.fit_predict(X_scaled)

# 結果の確認
# clusters 配列には、各データ点がどのクラスタに属するかのラベルが入る
# ラベルが -1 のものはノイズ点として扱われる
print("データ点ごとのクラスタラベル:")
print(clusters)

# 推定されたクラスタの数とノイズ点の数を計算
# set(clusters) でユニークなラベルを取得し、-1 (ノイズ) があればその分を除く
labels_unique = set(clusters)
n_clusters_ = len(labels_unique) - (1 if -1 in labels_unique else 0)
n_noise_ = list(clusters).count(-1) # 配列中の -1 の数を数える

print(f"\n推定されたクラスタ数: {n_clusters_}")
print(f"推定されたノイズ点の数: {n_noise_}")

# コア点のインデックスも取得できる
# core_sample_indices_ 属性にはコア点のインデックスが格納されている
core_samples_mask = np.zeros_like(dbscan.labels_, dtype=bool)
core_samples_mask[dbscan.core_sample_indices_] = True
print(f"コア点の数: {len(dbscan.core_sample_indices_)}")

# --- 可視化コード (参考) ---
# 実際には matplotlib などを使って結果をプロットすると、
# どのようにクラスタリングされたか（特にノイズ点の分離や形状）を
# 視覚的に理解しやすくなります。

# plt.figure(figsize=(8, 6))
# unique_labels = set(clusters)
# # クラスタごとに色分け
# colors = [plt.cm.Spectral(each) for each in np.linspace(0, 1, len(unique_labels))]

# for k, col in zip(unique_labels, colors):
#     if k == -1:
#         # ノイズ点は黒色でプロット
#         col = [0, 0, 0, 1]

#     class_member_mask = (clusters == k)

#     # コア点を大きく表示
#     xy = X_scaled[class_member_mask & core_samples_mask]
#     plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
#              markeredgecolor='k', markersize=14)

#     # ボーダー点を小さく表示
#     xy = X_scaled[class_member_mask & ~core_samples_mask]
#     plt.plot(xy[:, 0], xy[:, 1], 'o', markerfacecolor=tuple(col),
#              markeredgecolor='k', markersize=6)

# plt.title(f'DBSCAN Estimated number of clusters: {n_clusters_}')
# plt.xlabel("Feature 1 (scaled)")
# plt.ylabel("Feature 2 (scaled)")
# plt.grid(True)
# # plt.show() # グラフを表示

このコードを実行すると、各データ点がどのクラスタに割り当てられたか（またはノイズか）を示すラベルの配列が得られます。また、推定されたクラスタ数やノイズ点の数も確認できます。eps や min_samples の値を変えて実行してみると、結果がどのように変化するかを観察するのも良い学習になりますよ！🧪

DBSCANだけじゃない！他の密度ベースの手法たち 🚀

DBSCAN は非常に強力なアルゴリズムですが、万能ではありません。特に、密度が異なるクラスタが混在するデータに対しては、パラメータ設定が難しいという課題がありました。この課題に対応するために、DBSCAN を拡張したアルゴリズムも提案されています。

  • OPTICS (Ordering Points To Identify the Clustering Structure): DBSCAN のように固定の ε を使うのではなく、各点に対して「到達可能距離」という指標を計算し、点の到達可能性に基づいた順序付けを行います。この順序から、密度の異なるクラスタ構造を抽出することができます。ε の設定にそれほど敏感ではないという利点がありますが、計算コストは DBSCAN より高くなる傾向があります。
  • HDBSCAN (Hierarchical DBSCAN): OPTICS の考え方をさらに発展させ、階層的なクラスタ構造を抽出するアルゴリズムです。密度の変化に非常に頑健で、パラメータ設定が DBSCAN よりも容易になることが多いです（特に MinPts のみに焦点を当てて調整できる場合が多い）。現在、密度ベースクラスタリングの中でも非常に人気のある手法の一つです。（scikit-learn 本体には含まれていませんが、独立したライブラリとして利用可能です。）

これらのアルゴリズムは、DBSCAN の基本的な考え方である「密度」を核としながら、より複雑なデータ構造に対応できるように進化しています。データや目的に合わせて、これらの手法を選択肢に入れることも検討してみましょう。

まとめ 🎉

今回は、密度ベースのクラスタリングアルゴリズムの代表格である DBSCAN について詳しく見てきました。

  • DBSCAN はデータ点の密集度に基づいてクラスタを発見します。
  • ε (半径) と MinPts (最小近傍点数) という2つの重要なパラメータを使います。
  • コア点、ボーダー点、ノイズ点 という概念で点を分類します。
  • メリットとして、クラスタ数の自動決定、任意の形状のクラスタ検出、ノイズ除去が挙げられます。
  • デメリットとして、密度の違いへの弱さ、高次元データでの課題、パラメータ依存性があります。
  • scikit-learn を使って簡単に実装できますが、パラメータ調整が重要です (k-distance graph などが参考になります)。
  • より発展的な手法として OPTICS や HDBSCAN も存在します。

DBSCAN は、そのユニークなアプローチにより、k-means ではうまく扱えなかった種類のデータに対しても効果を発揮します。特に、地理空間データや不正検知など、形状が不定でノイズが含まれる可能性のあるデータの分析に適しています。

これで、教師なし学習のツールボックスにまた一つ強力な道具が加わりましたね！次は、次元削減の代表的な手法である PCA について学びます。引き続き、機械学習の旅を楽しんでいきましょう！🚀

コメント

タイトルとURLをコピーしました