DBSCAN
DBSCAN は完全に決定論的というわけではない。ひとつよりも多くのクラスタから到達できる境界点は、データが処理される順序に依存して、どちらのクラスタにもなることができる。幸運にも、この状況は頻繁には起きない。また、クラスタリング結果に与える影響は小さい。コア点とノイズ点に関しては、DBSCAN は決定論的である。DBSCAN* は境界点をノイズとして扱う変種であり、この方法では、密度連結成分 (density-connected components) のより一貫した統計的解釈と同様に、完全に決定論的な結果となる。
DBSCAN の質は、関数 regionQuery(P, ε) で使用される距離尺度に依存する。最も一般的に使用される尺度はユークリッド距離である。特に、高次元データに対しては、この尺度はいわゆる「次元の呪い」のために、ほとんど使えないものとなってしまい、ε の適切な値を見つけるのは困難となる。しかしこの欠点は、ユークリッド距離に基づく他のアルゴリズムにも当てはまる。
DBSCAN は密度に大きな違いのあるデータ集合をクラスタリングできない。すべてのクラスタに対して適切な minPts-ε の組み合わせを選ぶことができないためである。
データおよびスケールがよく理解されていないならば、意味のある距離閾値 ε を選ぶことは困難である。
これらの問題を扱うためのアルゴリズムの修正に関する拡張については下記のセクションを参照すること。
k平均法とは対照的に、DBSCAN は事前にデータのクラスタ数を明示的に指定する必要は無い。
DBSCAN は任意の形状のクラスタを見つけることができる。DBSCAN は他のクラスタによって完全に囲まれた(しかし接続していない)クラスタさえ見つけることができる。MinPts パラメータのため、いわゆる single-link 効果(異なるクラスタが細い線によって結ばれてしまうこと)は減少している。
DBSCAN はノイズという概念を持っており、外れ値に対してロバストである。
DBSCAN に必要なパラメータは 2 つだけであり、たいていはデータ点の順序に影響を受けない。(しかし、2 つの異なるクラスタのどちらからも端に位置する点は、点の順序が変えられ、クラスタの割り当てが同型写像までしかユニークではないならば、どちらのクラスタに属するかが入れ替わるかもしれない。)
DBSCAN は、たとえばR*木を使用するような region query を加速させることができるデータベースでの使用に対して設計されている。
minPts および ε パラメータは、もしデータがよく理解されているならば、ドメインの専門家によって設定できる。
しかし、インデックス(索引)のサポートをしていない。(それゆえ、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 の基本的な実装を(最新バージョンのオプショナルパッケージとして)含む。