DBSCAN

DBSCANはラベルのついていないデータ点に対してクラスタ数を指定することなくクラスタリングすることが可能な手法. 各クラスタ以外にノイズが含まれるデータセットでもノイズ(外れ値)を無視した上でクラスタリングが可能 DBSCAN処理の概要 全てのデータを「ノイズ」か「クラスタのコア」か「クラスタの到達可能点」のどれかに分類し、各点のクラスタを決定する. パラメータ 予め必要なパラメータは二つのみ ・クラスタのコアと判定する最低隣接点数:minPts ・隣接点と判定する距離閾値: ε これらを使い 「コア点」: 距離閾値以内の点の数が最低隣接点数を満たす点 「到達可能点」: コア点から距離閾値以内にあるが、最低隣接点数が満たない点 「ノイズ」: 距離閾値以内にコア点が存在しない点 と決める メリット ・クラスタ数は自動的に決まるため、予め決めておく必要がない(kmeansの場合は必要) ・どのような形状のクラスタでも密になっていればクラスタリング可能 デメリット ・距離算出方法によるが、一般的なユークリッドでは、次元の呪いにより高次元ではうまくクラスタリングできない ・密度が異なるクラスタがあると適切にクラスタリングできない.

どのような二点間の距離計算を行っても良いが、ここではユークリッド算出であるとする. DBSCANの処理の流れ 全ての点に関して下記処理を行う. 1. 対象の点Pの距離閾値εの隣接点数がminPts以下なら 　　　→一旦ノイズとラベル付して、次の点の処理へ. そうでない場合は2.へ 2. 点Pにこれまでつけていないクラスタ番号を割り当てる 3. 点PのクラスタリストNeighborListに隣接点を加える 4. 以下NeighborListの各点Qに対して 4.1 Qがノイズの点があればPに割り当てたクラスタ番号を割り当て 　 4.2 Qが既にクラスタが割り当たっていれば、次の点の処理に4.1へ 　 4.3 QにPのクラスタ番号を割り当て 　 4.4 もしQの距離閾値εの隣接点数がminPts以上ならそれら隣接点をNeighborListに追加 1.の処理で密度が十分にあるかを判定している. これによってコア点になりうるかどうかが決まる. 密度が足りないものは一度ノイズと分類し、コア点から距離閾値以内にあれば、到達可能点として復活する. 4.2.の処理でわかるように、既に割り当たっているものにはラベルを付け替えないため、このDBSCANは走査するデータ点の順序によってクラスタリング結果は異なる.