クラスタリングを勉強してみる（5） density-based clustering

1. 概要

density-connected points などのような密度に基づいて集合を作成する手法を density-based clustering と言います。

1-1. 背景

density-based clustering を理解する上で、2つのパラメータと3つの形式定義について理解する必要があります。

1-1-1. パラメータ
  1. \epsilon : 近傍の最大半径（maximum radius of the neighbourhood）
  2. MinPts : ε近傍内に含む最小のオブジェクト数（minimum number of points in an ε-neighbourhood of that point）

N_\epsilon(q) : \{ p\in{D} | dist(p, q) <= \epsilon \}

1-1-2. 形式定義（formal difinition）

Definition 1. directly density-reachable

以下の条件を満たすものを、"ε, MinPts に関して、点p は点q から directly density-reachable である" と言います。

  1. p \in {N_\epsilon(q)}
  2. Card(N_\epsilon(q)) \geq MinPts}

f:id:somathor:20130423141234j:plain

Definition 2. density-reachable

以下の条件を満たすものを、"ε, MinPts に関して、点p は点q から density-reachable である" と言います。

  1. 有限列（chain of points） : p_1, ...,p_n
  2. 関係 _{p_{i}}R_{p_{i+1}} : ε, MinPts に関して、点 p_{i+1} は点 p_{i} から directly density-reachable である
  3. p_1 = q, p_n = p とした場合、R の推移閉包が成り立つ

R^+ = \bigcup_{i = 1,..,n}{R^i}

f:id:somathor:20130423142352j:plain

Definition 3. density-connected

点p と点q の間に点o があり、"ε, MinPts に関して、点p と点q が点o から density-reachable である"とき、"ε, MinPts に関して、点p は点q から density-connected である" と言います。

f:id:somathor:20130423142415j:plain

2. DBSCAN

以下の条件を満たすものをクラスターとします。

  1. Maximality: データ集合内のすべてのオブジェクトに対して、ε, MinPts に関して、density-reachable なオブジェクトの極大集合
  2. Connectivity: クラスター内のすべてのオブジェクトに対して、ε, MinPts に関して、互いに density-conected である

どのクラスタにも属さないオブジェクトをノイズ（noise）とします。

2-1. Pros.

  • 凸状（convex）だけでなく、任意の形状（arbitrary shape）のクラスターを発見できる
  • ノイズ（noise）を取り除ける
  • データ走査が1回で済む（one scan）

2-2. Cons.

  • 終了条件（termination condition）のような density parameters を必要とする
  • 鎖効果（chaining）が発生する可能性がある

3. 参考文献

  • [EKSX 96] Ester M., Kriegel H.-P., Sander J., Xu X.: "A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise", Proc. 2nd Int. Conf. on Knowledge Discovery and Data Mining, Portland, OR, AAAI Press, 1996, pp. 226-231