これの階層化バージョンがHDBSCAN(処理速度は重くなるがパラメータ調整が楽になる)

Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. 1996. A density-based algorithm for discovering

clusters in large spatial databases with noise. In Proceedings of the 2nd ACM International Conference on Knowledge

Discovery and Data Mining (KDD). 226–231.

A density-based algorithm for discovering clusters in large spatial databases with noise | Proceedings of the Second International Conference on Knowledge Discovery and Data Mining PDF

これは1996年のKDD会議で発表されたDBSCAN(Density-Based Spatial Clustering of Applications with Noise)アルゴリズムの原論文です。主なポイントは:

1. DBSCANの特徴と利点:

密度ベースのクラスタリング手法で、任意の形状のクラスタを発見可能

ノイズ(外れ値)を自然に検出できる

入力パラメータが少なく(Eps, MinPtsの2つのみ)、パラメータの選択も比較的容易

大規模空間データベースに対して効率的

2. アルゴリズムの仕組み:

密度到達可能性(density-reachability)と密度連結性(density-connectivity)の概念を導入

コアポイント、ボーダーポイント、ノイズポイントという3種類の点を定義

R*-treeなどの空間インデックスを利用して効率的に近傍点を探索

3. 性能評価:

当時の代表的なクラスタリング手法CLARANSと比較

任意形状のクラスタ発見において優れた精度を示す

実行時間はCLARANSの100倍以上高速

4. パラメータ設定:

MinPtsは通常4に設定(2次元データの場合)

Epsはk-dist plotというグラフを用いて対話的に決定

この論文はDBSCANの基礎となる重要な論文で、密度ベースクラスタリングの分野に大きな影響を与えました。2014年にはSIGKDD Test of Time Awardを受賞しています。