DBSCAN

DBSCAN（Density-based spatial clustering of applications with noise）は、1996 年に Martin Ester、Hans-Peter Kriegel、Jörg Sander および Xiaowei Xu によって提案されたデータクラスタリングアルゴリズムである。これは密度準拠クラスタリングアルゴリズムである。ある空間に点集合が与えられたとき、互いに密接にきっちり詰まっている点をグループにまとめ（多くの隣接点を持つ点、en:Fixed-radius_near_neighbors）、低密度領域にある点（その最近接点が遠すぎる点）を外れ値とする。DBSCAN は最も一般的なクラスタリングアルゴリズムのひとつであり、科学文献の中で最も引用されている。

2014年、このアルゴリズムは主要なデータマイニングカンファレンスの KDD にて、the test of time award（理論および実践にてかなりの注目を集めたアルゴリズムに与えられる賞）を受賞した。

概要

ある空間内にある、クラスタリングしたい点集合を考える。ε はある点からの半径を表すパラメータとする。DBSCAN クラスタリングの目的として、点は、コア点 (core points)、（密度）到達可能点、外れ値に分類される。以下のように行う。

• 点 p を含め、点 p から距離 ε 以内に少なくとも minPts 個の点があれば、点 p はコア点である。
• 点 q がコア点 p から距離 ε 以内にあれば、q は p から「直接到達可能」であるという。
• 各 p_i+1 が p_i から直接到達可能であり、p₁ = p かつ p_n = q であるパス p₁, ..., p_n があれば、q は p から「到達可能」である。ここでパス上のすべての点は、 q が例外である可能性があるが、コア点で無ければならない。
• 他のどの点からも到達可能でないすべての点は外れ値である。

今、p がコア点であれば、点p から到達可能なすべての点（コア点または非コア点）と一緒にクラスタを形成する。各クラスタは少なくともひとつのコア点を含む。非コア点はあるクラスタの一部となるが、非コア点はその"端"を形成する。非コア点はより多くの点に到達するのに使用できないためである。

上図において、minPts = 4 である。点 A およびその他の赤点はコア点である。その理由は、半径 ε でこれらの点を囲んでいる領域は少なくとも（その点自身を含めて）4 つの点を含んでいるからである。上図のコア点はすべて互いに到達可能であり、単一のクラスタを形成する。点 B および C はコア点ではない。しかし、A から（他のコア点を介して）到達可能であり、それゆえこのクラスタに属す。点 N はコア点でなければ密度到達可能点でもないので、ノイズ点である。

到達可能性は対称関係ではない。なぜなら、定義により、距離にかかわらず、非コア点から到達可能な点は存在しないためである。非コア点は他の点から到達可能になる可能性があるが、非コア点から他のどの点にも到達不可能である。それゆえ、DBSCAN によって発見されるクラスタの範囲を形式的に定義するために、連結性の新たな概念が必要とされる。点o から2点 p と q へ到達可能であるような点o が存在するとき、p と q は 密度連結 (density-connected) である。密度連結性 (density-connectedness) は対称的である。

クラスタは、次の 2 つの特徴を満たす。

1. クラスタ内のすべての点は、相互に密度連結 (density-connected) である。
2. ある点がクラスタのどの点からも密度到達可能 (density-reachable) ならば、その点もクラスタの一部である。

アルゴリズム

DBSCAN は 2 つのパラメータを必要とする。ε (eps) および密領域を形成するのに必要となる点の最小数である (minPts)。アルゴリズムでは、まだ訪れていない任意の開始点から処理を始める。この点の ε 近傍を検索し、それが十分に多くの点を含んでいるなら、クラスタが開始される。そうでなければ、その点はノイズ点とラベル付けされる。注意として、この点は後に、異なる点から見て閾値以上の点を含んだ ε 近傍の一部となり、それゆえあるクラスタの一部になるかもしれない。

ある点があるクラスタの密部分であることが判明した場合、その ε 近傍もまたそのクラスタの一部である。それゆえ、ε 近傍内にあるすべての点が加えられ、それらが稠密であるときにはそれら自身のε-近傍も同様に加算される。この過程は密度連結クラスタ (density-connected cluster) が完全に発見されるまで続く。そして、まだ訪問されていない新しい点が検索および処理され、さらなるクラスタまたはノイズが発見される。

アルゴリズムは以下の元々投稿された命名法に従う擬似コードのようにして導かれる。

DBSCAN(D, eps, MinPts) {
   C = 0
   for each point P in dataset D {
      if P is visited
         continue next point
      mark P as visited
      NeighborPts = regionQuery(P, eps)
      if sizeof(NeighborPts) < MinPts
         mark P as NOISE
      else {
         C = next cluster
         expandCluster(P, NeighborPts, C, eps, MinPts)
      }
   }
}

expandCluster(P, NeighborPts, C, eps, MinPts) {
   add P to cluster C
   for each point P' in NeighborPts { 
      if P' is not visited {
         mark P' as visited
         NeighborPts' = regionQuery(P', eps)
         if sizeof(NeighborPts') >= MinPts
            NeighborPts = NeighborPts joined with NeighborPts'
      }
      if P' is not yet member of any cluster
         add P' to cluster C
   }
}

regionQuery(P, eps)
   return all points within P's eps-neighborhood (including P)

このアルゴリズムは、"expandCluster" サブルーチンの内容（これは 1 箇所からのみよばれる）のインライン化 および、点ごとの "すでに訪れた点" および "クラスタ C に所属する" ロジックを統合することによって、単純にすることができる。これらの単純化は、元々投稿されたバージョンを反映するために、上記の擬似コードでは省略されている。また、regionQuery関数は、ローカル密度推定でまだカウントされている限り、訪問されるべき点のリスト内でPを返す必要はない。

計算量

DBSCAN はデータベースの各点を訪れる。複数回訪れることもある（たとえば、異なるクラスタへの候補として）。しかし、実践の考慮のため、時間計算量はたいてい regionQuery の呼び出しの回数によって支配される。DBSCAN は各点でそのようなクエリをまさに 1 度だけ実行し、O(log n) で近隣クエリ（en:Fixed-radius_near_neighbors）を実行するインデックス構造が使用されるならば、O(n log n) の全体平均のランタイム複雑性が獲得される(パラメータ ε が意味のある中で選ばれたならば。すなわち、平均して O(log n) の点が返される場合ならば)。加速させるようなインデックス構造を使用しない場合、または縮退データ（たとえばすべての点が ε より小さい距離内にある）の場合は、その最悪計算時間は O(n²) のままである。サイズ (n²-n)/2 の距離行列は距離の再計算を回避するために出現しうるが、これは O(n²) のメモリを必要とする。一方、DBSCAN の非行列に基づく実装はわずか O(n) のメモリを必要とする。

DBSCAN は非線形分離されるクラスタを見つけ出すことができる。このデータセットは、k-means や 混合ガウシアン EM アルゴリズムでは十分にクラスタリングされない。

利点

1. k平均法とは対照的に、DBSCAN は事前にデータのクラスタ数を明示的に指定する必要は無い。
2. DBSCAN は任意の形状のクラスタを見つけることができる。DBSCAN は他のクラスタによって完全に囲まれた（しかし接続していない）クラスタさえ見つけることができる。MinPts パラメータのため、いわゆる single-link 効果（異なるクラスタが細い線によって結ばれてしまうこと）は減少している。
3. DBSCAN はノイズという概念を持っており、外れ値に対してロバストである。
4. DBSCAN に必要なパラメータは 2 つだけであり、たいていはデータ点の順序に影響を受けない。（しかし、2 つの異なるクラスタのどちらからも端に位置する点は、点の順序が変えられ、クラスタの割り当てが同型写像までしかユニークではないならば、どちらのクラスタに属するかが入れ替わるかもしれない。）
5. DBSCAN は、たとえばR*木を使用するような region query を加速させることができるデータベースでの使用に対して設計されている。
6. minPts および ε パラメータは、もしデータがよく理解されているならば、ドメインの専門家によって設定できる。

欠点

1. DBSCAN は完全に決定論的というわけではない。ひとつよりも多くのクラスタから到達できる境界点は、データが処理される順序に依存して、どちらのクラスタにもなることができる。幸運にも、この状況は頻繁には起きない。また、クラスタリング結果に与える影響は小さい。コア点とノイズ点に関しては、DBSCAN は決定論的である。DBSCAN* は境界点をノイズとして扱う変種であり、この方法では、密度連結成分 (density-connected components) のより一貫した統計的解釈と同様に、完全に決定論的な結果となる。
2. DBSCAN の質は、関数 regionQuery(P, ε) で使用される距離尺度に依存する。最も一般的に使用される尺度はユークリッド距離である。特に、高次元データに対しては、この尺度はいわゆる「次元の呪い」のために、ほとんど使えないものとなってしまい、ε の適切な値を見つけるのは困難となる。しかしこの欠点は、ユークリッド距離に基づく他のアルゴリズムにも当てはまる。
3. DBSCAN は密度に大きな違いのあるデータ集合をクラスタリングできない。すべてのクラスタに対して適切な minPts-ε の組み合わせを選ぶことができないためである。
4. データおよびスケールがよく理解されていないならば、意味のある距離閾値 ε を選ぶことは困難である。

これらの問題を扱うためのアルゴリズムの修正に関する拡張については下記のセクションを参照すること。

パラメータ評価

どのデータマイニングタスクもパラメータの問題がある。どのパラメータも明確な方法でアルゴリズムに影響を与える。DBSCAN では、パラメータ ε および minPts が必要とされる。パラメータはユーザーが指定する必要があるさ。理想的には、ε の値は解くべき問題によって与えられ（たとえば、物理的な距離）、minPts は望む最小クラスターのサイズである。

• minPts - 大まかなやり方では、最小の minPts はデータセットの次元 D から引き出され、minPts ≥ D + 1 である。minPts = 1 の低い値は意味を成さない。どの点もそのままクラスタであるからである。minPts ≤ 2 では、結果は single link metric での階層クラスタリングと同じになり、デンドログラム (dendrogram) は高さ ε でカットされる。それゆえ、minPts は少なくとも 3 に選ばれなければならない。しかし、より大きい値はたいていの場合ノイズを持ったデータ集合に対してより有効であり、かなりのクラスタを生じるだろう。データ集合が大きくなれば、minPts の値はより大きく選ばれるべきである。
• ε - ε の値は、k距離グラフ を用い、 k = minPts の最近傍への距離をプロットすることで選ばれる。ε が良い値であると、このプロットが強く結ばれている。ε が非常に小さい値に選ばれると、データの大部分はクラスタリングされない。一方、大きな値が選ばれると、クラスタは併合され、オブジェクトの大多数は同一のクラスタにあることになる。一般に、小さな ε 値が好ましく、大まかにいって点の小片がお互いにこの距離内にあるべきである。
• 距離関数 - 距離関数の選択は ε の選択に密に結合しており、結果に大きな影響を与える。一般に、パラメータ ε が選ばれる前に、データセットに対する類似度の合理的な尺度を最初に特定することが必要である。

OPTICS は、パフォーマンスに大部分の影響を与える最大値で ε を置換した、DBSCAN の一般化と見なされる。minPts は、発見される最小のクラスターサイズとなる。このアルゴリズムは DBSCAN よりもずっとパラメータ化しやすい一方で、結果を使うのにはもうすこし困難がある。たいてい、DBSCAN が生成する単純なデータパーティショニングの代わりに、階層クラスタリングを生成するためである。 最近、DBSCAN の元々の著者の一人が DBSCAN と OPTICS を再訪し、階層 DBSCAN (HDBSCAN*) の洗練バージョンを投稿した。これはもはや境界点の考え方をもっていない。

拡張

一般化 DBSCAN (GDBSCAN) は、DBSCAN と同一の著者が、任意の"近隣" ("neighborhood") および"密度" ("dense") という述語を一般化したものである。ε および minPts パラメータは元々のアルゴリズムから除外され、述語 (predicates) に移る。たとえば、ポリゴンデータでは、"近隣"は任意の交差するポリゴンである。一方、密度 (density predicate) はオブジェクト数の代わりにポリゴンの領域を使用する。

DBSCAN アルゴリズムへの様々な拡張が提案されてきた。これには、並列化、パラメータ推定、不確かなデータのサポートに対する手法を含む。基本的な考え方は OPTICS アルゴリズム による階層クラスタリングに拡張されてきた。DBSCAN もまた PreDeCon や SUBCLU のような部分空間クラスタリングアルゴリズムの一部として使用されてきた。HDBSCAN は OPTICS よりも高速な DBSCAN の階層バージョンである。そこから、最も卓越したクラスタを構成するフラットなパーティションがその階層から抽出される。

実用性

このアルゴリズムの様々な実装があり、大きなパフォーマンスの違いがある。あるデータセットに対して、最も早いアルゴリズムでは 1.4 秒で終わるが、最も遅いものでは 13803 秒かかる。この差異は実装の質、言語、コンパイラの違い、またアクセラレーションのためのインデックス(索引)の使用による。

• Apache_Commons Math は 2 次のオーダーで動作するアルゴリズムの Java 実装を含む。
• ELKI はDBSCAN、GDBSCAN とその変種、の実装を提供している。この実装はほぼ 2 次の計算オーダーのための様々なインデックス（索引）構造を使用できる。また、任意の距離関数および任意のデータ型をサポートしている。しかし、小規模データに関する低レベルの最適化（および特殊化）実装が性能を上回るかもしれない。
• R は fpc パッケージに DBSCAN を含み、距離行列を介した任意の距離関数をサポートしている。しかし、インデックス（索引）のサポートをしていない。（それゆえ、2 次の計算オーダーおよびメモリ消費の計算複雑性を持つ。）また、R インタープリタのため、かなり遅い。高速バージョンが kd木 を用いた C++ で実装されており、dbscan パッケージにある。
• Scikit-learn は、任意のミンコフスキー距離に対して、DBSCAN の Python 実装を含む。これはkd木およびen:Ball_treeを用いて高速化させることができるが、最悪な場合における 2 次オーダーのメモリ使用量となる。HDBSCAN* アルゴリズム が github から提供されている。
• SPMF は kd木をサポート（ただしユークリッド距離のみ）したDBSCAN アルゴリズムの GPL-V3 Java 実装を提供している。
• Weka は 2 次オーダーの計算時間および線形メモリ使用量で動作するDBSCAN の基本的な実装を（最新バージョンのオプショナルパッケージとして）含む。

関連項目

• OPTICS アルゴリズム - 複数レンジへの DBSCAN の一般化。パラメータ ε を最大探索半径に効率的に置き換える。
• 連結成分
• 素集合データ構造

参考文献

• Arlia, Domenica; Coppola, Massimo. "Experiments in Parallel Clustering with DBSCAN". Euro-Par 2001: Parallel Processing: 7th International Euro-Par Conference Manchester, UK August 28–31, 2001, Proceedings. Springer Berlin.
• Kriegel, Hans-Peter; Kröger, Peer (2011). “Density-based Clustering”. WIREs Data Mining and Knowledge Discovery 1 (3): 231–240. doi:10.1002/widm.30. http://wires.wiley.com/WileyCDA/WiresArticle/wisId-WIDM30.html.