DBSCAN
DBSCAN はデータベースの各点を訪れる。複数回訪れることもある(たとえば、異なるクラスタへの候補として)。しかし、実践の考慮のため、時間計算量はたいてい regionQuery の呼び出しの回数によって支配される。DBSCAN は各点でそのようなクエリをまさに 1 度だけ実行し、O(log n) で近隣クエリ(en:Fixed-radius_near_neighbors)を実行するインデックス構造が使用されるならば、O(n log n) の全体平均のランタイム複雑性が獲得される(パラメータ ε が意味のある中で選ばれたならば。すなわち、平均して O(log n) の点が返される場合ならば)。加速させるようなインデックス構造を使用しない場合、または縮退データ(たとえばすべての点が ε より小さい距離内にある)の場合は、その最悪計算時間は O(n2) のままである。サイズ (n2-n)/2 の距離行列は距離の再計算を回避するために出現しうるが、これは O(n2) のメモリを必要とする。一方、DBSCAN の非行列に基づく実装はわずか O(n) のメモリを必要とする。
DBSCAN は 2 つのパラメータを必要とする。ε (eps) および密領域を形成するのに必要となる点の最小数である (minPts)。アルゴリズムでは、まだ訪れていない任意の開始点から処理を始める。この点の ε 近傍を検索し、それが十分に多くの点を含んでいるなら、クラスタが開始される。そうでなければ、その点はノイズ点とラベル付けされる。注意として、この点は後に、異なる点から見て閾値以上の点を含んだ ε 近傍の一部となり、それゆえあるクラスタの一部になるかもしれない。
ある点があるクラスタの密部分であることが判明した場合、その ε 近傍もまたそのクラスタの一部である。それゆえ、ε 近傍内にあるすべての点が加えられ、それらが稠密であるときにはそれら自身のε-近傍も同様に加算される。この過程は密度連結クラスタ (density-connected cluster) が完全に発見されるまで続く。そして、まだ訪問されていない新しい点が検索および処理され、さらなるクラスタまたはノイズが発見される。
アルゴリズムは以下の元々投稿された命名法に従う擬似コードのようにして導かれる。
このアルゴリズムは、"expandCluster" サブルーチンの内容(これは 1 箇所からのみよばれる)のインライン化 および、点ごとの "すでに訪れた点" および "クラスタ C に所属する" ロジックを統合することによって、単純にすることができる。これらの単純化は、元々投稿されたバージョンを反映するために、上記の擬似コードでは省略されている。また、regionQuery関数は、ローカル密度推定でまだカウントされている限り、訪問されるべき点のリスト内でPを返す必要はない。
このアルゴリズムの様々な実装があり、大きなパフォーマンスの違いがある。あるデータセットに対して、最も早いアルゴリズムでは 1.4 秒で終わるが、最も遅いものでは 13803 秒かかる。この差異は実装の質、言語、コンパイラの違い、またアクセラレーションのためのインデックス(索引)の使用による。
Apache_Commons Math は 2 次のオーダーで動作するアルゴリズムの Java 実装を含む。
ELKI(英語版) はDBSCAN、GDBSCAN とその変種、の実装を提供している。この実装はほぼ 2 次の計算オーダーのための様々なインデックス(索引)構造を使用できる。また、任意の距離関数および任意のデータ型をサポートしている。しかし、小規模データに関する低レベルの最適化(および特殊化)実装が性能を上回るかもしれない。
R は fpc パッケージに DBSCAN を含み、距離行列を介した任意の距離関数をサポートしている。