DBSCAN
Density-Based Spatial Clustering of Applications with Noiseの略です。アルゴリズムは非常に単純な部類に入ると思います。近傍探索アルゴリズムと組み合わせ、各サンプルの近くにある程度のサンプル数があればクラスターを形成し、サンプル数が少なければ外れ値となります。
Kmeansとの大きな相違点は以下のような2点があるかと思います。
- 球以外の形状のクラスタにも対応可能
- 外れ値検知にも使える
一方、Kmeans（そのほかの機械学習モデルもですが）では一度学習したモデルを新規データに対しても適用できますが、DBSCANは新規データと既存データを合わせて再度学習をする必要があります。また異なる密度のクラスターがあった場合に、密度の濃いクラスターに合わせると薄い側がすべて外れ値となりやすく、逆の場合は濃い側に余計な点をクラスターに組み込んでしまう可能性があります。このようにハイパーパラメータの調整が難しいため、リアルタイムに異常検知を行わなければならない場合には不向きではないかと思います。
アルゴリズム
DBSCAN自体のアルゴリズムは非常に単純です。KDTreeなどの近傍探索アルゴリズムを実装する方が時間がかかりました。近傍探索アルゴリズムについてはまた後日実施します。
ハイパーパラメータ
ハイパーパラメータは半径Rと近傍点の数Mです。少ないですが、決定木などのようにとりあえずこれくらいにしておけばある程度の性能が出るということがしにくいと思います。
詳細
3つの性質をもつ点が定義されています。
- core点：半径R中に点がM+1個以上ある(自分自身を含んでしまうため1を足す)
- 到達可能点：上記でない点の内、半径R中に1がある
- 外れ値：上記のどれでもない
以下の手順で進めます。
- 近傍探索アルゴリズムを適用し、各サンプルの半径R中のインデックスを取得。もしくはクエリを投入すれば取得できる状態にしておく
- 全サンプルをスキャンする
- 未スキャンであれば処理を継続。スキャン済みであれば（＝すでにラベルが付与されていれば）スキップ
- ラベルを付与
- 現在のサンプルからクラスターを拡張する
- 近傍点がM+1個以上であれば処理を継続。そうでなければ異常ラベルを付与。クラスターはcore点からしか広がらないため。
- 近傍点分のスキャン
- スキャン済みであればここでもスキップ
- ラベルを付与
- さらに近傍点を取得し、スキャン対象に加える
- ラベルをインクリメント
イメージ
言葉で説明するよりはgifで見ていただいた方が良いと思います。非常にわかりやすいものを作成していただいています。
まず、顔の輪郭に沿ってクラスターが成長しています。途中で上側で成長が止まっているのは半径R中にサンプルがなくなってしまったからです。輪郭部分をすべてスキャンして後は口、目ときて最後に外れ値をスキャンしています。
以上