DBSCAN

DBSCAN (Density-Based Spatial Clustering) †

超球状ではない任意形状のクラスタの抽出を目的としたクラスタリング手法．

MinPts と Eps の二つのパラメータをとる．ある点 \(x\) から，距離 Eps 内にある点集合を近傍 \(N_{\mathrm{Eps}}(x)\) と定義．

\(x\)から\(y\)が直接密度到達可能 (directly density-rechable) は次の条件を満たすこと

• \(y\in N_{\mathrm{Eps}}(x)\)
• \(|N_{\mathrm{Eps}}(x)|\ge\mathrm{MinPts}\)

あるseed点から，この直接密度到達可能な関係を推移的にたどって到達可能な極大集合を一つのクラスタとして抽出する．

MinPts や Eps のパラメータを変化させたクラスタを抽出できる OPTICS など数多くの拡張が開発グループによりなされている．

-- しましま

関連項目 †

• OPTICS
   
• クラスタリング
   
• 検索:DBSCAN OPTICS

リンク集 †

• Wikipedia:DBSCAN

Freeware †

• fpc@CRAN：DBSCAN を含むRのパッケージ
• Weka：3.6以降の開発版に含まれている

関連文献 †

• DBSCANの基本文献
  M.Ester, H.-P.Kriegel, J.Sander, and X.Xu "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", KDD1996
  GoogleScholarAll: Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise
• OPTICSの基本文献
  M.Ankerst, M.M.Breunig, H.-P.Kriegel, and J. Sander, "OPTICS: Ordering Points to Identify The Clustering Structure", SIGMOD2000
  GoogleScholarAll:OPTICS: Ordering Points to Identify The Clustering Structure
• Book/Data Mining - Concepts and Techniques 7.6.1〜7.6.1節