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 では、パラメータ ε および minPts が必要とされる。パラメータはユーザーが指定する必要があるさ。理想的には、ε の値は解くべき問題によって与えられ(たとえば、物理的な距離)、minPts は望む最小クラスターのサイズである。
minPts - 大まかなやり方では、最小の minPts はデータセットの次元 D から引き出され、minPts ≥ D + 1 である。minPts = 1 の低い値は意味を成さない。どの点もそのままクラスタであるからである。minPts ≤ 2 では、結果は single link metric での階層クラスタリングと同じになり、デンドログラム (dendrogram) は高さ ε でカットされる。それゆえ、minPts は少なくとも 3 に選ばれなければならない。しかし、より大きい値はたいていの場合ノイズを持ったデータ集合に対してより有効であり、かなりのクラスタを生じるだろう。データ集合が大きくなれば、minPts の値はより大きく選ばれるべきである。
ε - ε の値は、k距離グラフ を用い、 k = minPts の最近傍への距離をプロットすることで選ばれる。