// シス担のミカタ
古典的機械学習

DBSCAN でぃーびーすきゃん

DBSCAN密度ベースクラスタリングノイズ検出外れ値検出任意形状クラスター
DBSCANについて教えて

簡単に言うとこんな感じ！

「密度が高いエリア」をクラスターと見なす手法だよ。k-meansと違ってクラスター数を事前に決めなくていいし、丸以外の形（三日月・Cの字など）のクラスターも検出できる。おまけに「どのクラスターにも属さない孤立点（外れ値）」を自動で検出してくれるのが嬉しいんだ！

DBSCANとは

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）は、データの密度に基づいてクラスターを形成する手法です。1996年に発表されました。

密度が十分高い領域をクラスターとして認識し、密度の低い領域にある点をノイズ（外れ値）として扱います。

アルゴリズムの概念

2つのパラメータを使います：

  • ε（epsilon）：近傍と見なす半径
  • MinPts：コアポイントになる最低近傍点数
点の種類定義
コアポイント半径ε内にMinPts個以上の点がある
ボーダーポイントコアポイントの近傍内にあるが、自身はコアでない
ノイズポイントどのコアポイントの近傍にも属さない

k-meansとの違い

k-means が苦手なパターン：
   ○ ○ ○          ○ ○ ○
  ○   ○        ×  ×  ×  ← 異なる形状・密度のクラスター
 ○     ○          × ×

DBSCAN はこれを正しくクラスタリングできる

特徴

長所：
  ✓ クラスター数を事前指定不要
  ✓ 任意の形状のクラスターを検出
  ✓ ノイズ（外れ値）を自動検出
  ✓ 大きさが不均一なクラスターに対応

短所：
  ✗ ε と MinPts の設定が難しい
  ✗ 密度が大きく異なるクラスターが混在すると苦手
  ✗ 高次元データでは距離の意味が薄れる

歴史と背景

  • 1996年：Ester らが KDD 1996 で発表。データマイニングの古典的名著に
  • 2014年：KDD 「Test of Time Award」を受賞（当時最も重要な論文として）
  • 現在：異常検知・地理空間データ分析・画像セグメンテーションで活用

関連用語