DBSCAN

DBSCAN（Density-based spatial clustering of applications with noise）は、1996 年に Martin Ester、Hans-Peter Kriegel、Jörg Sander および Xiaowei Xu によって提案されたデータクラスタリングアルゴリズムである。これはアルゴリズムである。ある空間に点集合が与えられたとき、互いに密接にきっちり詰まっている点をグループにまとめ（多くの隣接点を持つ点、）、低密度領域にある点（その最近接点が遠すぎる点）を外れ値とする。DBSCAN は最も一般的なクラスタリングアルゴリズムのひとつであり、科学文献の中で最も引用されている。
2014年、このアルゴリズムは主要なデータマイニングカンファレンスの KDD にて、the test of time award（理論および実践にてかなりの注目を集めたアルゴリズムに与えられる賞）を受賞した。
概要.
ある空間内にある、クラスタリングしたい点集合を考える。 はある点からの半径を表すパラメータとする。DBSCAN クラスタリングの目的として、点は、コア点 ("core points")、（密度）到達可能点、外れ値に分類される。以下のように行う。
今、 がコア点であれば、点 から到達可能なすべての点（コア点または非コア点）と一緒にクラスタを形成する。各クラスタは少なくともひとつのコア点を含む。非コア点はあるクラスタの一部となるが、非コア点はその"端"を形成する。非コア点はより多くの点に到達するのに使用できないためである。
到達可能性は対称関係ではない。なぜなら、定義により、距離にかかわらず、非コア点から到達可能な点は存在しないためである。非コア点は他の点から到達可能になる可能性があるが、非コア点から他のどの点にも到達不可能である。それゆえ、DBSCAN によって発見されるクラスタの範囲を形式的に定義するために、"連結性"の新たな概念が必要とされる。点o から2点 p と q へ到達可能であるような点o が存在するとき、p と q は 密度連結 (density-connected) である。密度連結性 (density-connectedness) は対称的である。
クラスタは、次の 2 つの特徴を満たす。
アルゴリズム.
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 度だけ実行し、 で近隣クエリ（）を実行するインデックス構造が使用されるならば、 の全体平均のランタイム複雑性が獲得される(パラメータ が意味のある中で選ばれたならば。すなわち、平均して の点が返される場合ならば)。加速させるようなインデックス構造を使用しない場合、または縮退データ（たとえばすべての点が より小さい距離内にある）の場合は、その最悪計算時間は のままである。サイズ の距離行列は距離の再計算を回避するために出現しうるが、これは のメモリを必要とする。一方、DBSCAN の非行列に基づく実装はわずか のメモリを必要とする。
欠点.
これらの問題を扱うためのアルゴリズムの修正に関する拡張については下記のセクションを参照すること。
パラメータ評価.
どのデータマイニングタスクもパラメータの問題がある。どのパラメータも明確な方法でアルゴリズムに影響を与える。DBSCAN では、パラメータ ε および "minPts" が必要とされる。パラメータはユーザーが指定する必要があるさ。理想的には、ε の値は解くべき問題によって与えられ（たとえば、物理的な距離）、"minPts" は望む最小クラスターのサイズである。
OPTICS は、パフォーマンスに大部分の影響を与える最大値で ε を置換した、DBSCAN の一般化と見なされる。"minPts" は、発見される最小のクラスターサイズとなる。このアルゴリズムは DBSCAN よりもずっとパラメータ化しやすい一方で、結果を使うのにはもうすこし困難がある。たいてい、DBSCAN が生成する単純なデータパーティショニングの代わりに、階層クラスタリングを生成するためである。
最近、DBSCAN の元々の著者の一人が DBSCAN と OPTICS を再訪し、階層 DBSCAN (HDBSCAN*) の洗練バージョンを投稿した。これはもはや境界点の考え方をもっていない。
拡張.
一般化 DBSCAN (GDBSCAN) は、DBSCAN と同一の著者が、任意の"近隣" ("neighborhood") および"密度" ("dense") という述語を一般化したものである。ε および minPts パラメータは元々のアルゴリズムから除外され、述語 (predicates) に移る。たとえば、ポリゴンデータでは、"近隣"は任意の交差するポリゴンである。一方、密度 (density predicate) はオブジェクト数の代わりにポリゴンの領域を使用する。
DBSCAN アルゴリズムへの様々な拡張が提案されてきた。これには、並列化、パラメータ推定、不確かなデータのサポートに対する手法を含む。基本的な考え方は OPTICS アルゴリズム による階層クラスタリングに拡張されてきた。DBSCAN もまた PreDeCon や のような部分空間クラスタリングアルゴリズムの一部として使用されてきた。HDBSCAN は OPTICS よりも高速な DBSCAN の階層バージョンである。そこから、最も卓越したクラスタを構成するフラットなパーティションがその階層から抽出される。
実用性.
このアルゴリズムの様々な実装があり、大きなパフォーマンスの違いがある。あるデータセットに対して、最も早いアルゴリズムでは 1.4 秒で終わるが、最も遅いものでは 13803 秒かかる。この差異は実装の質、言語、コンパイラの違い、またアクセラレーションのためのインデックス(索引)の使用による。