Hierarchical clustering algorithm

• 複数のデータをクラスターに分類する手法の一つ。以下のwikipediaの記事の概略
  • http://en.wikipedia.org/wiki/Hierarchical_clustering
• N個の要素それぞれのペアに対して、要素間の距離 $d(i,j)$ が定義できれば適用できる手法。
  • agglomerative (バラバラの状態から大きなクラスターを作っていく手法）、divisive（一つの大きなクラスターから分割して行く手法）の２種類がある。
    • ここでは agglomorative のみ説明する

アルゴリズム

• このようなa~fの要素をクラスタリングする事を考える
  • 
  • ここでは説明のために要素間の距離は図の要素間のユークリッド距離で定義するとする。
    • 任意の２要素間の距離さえ定義されていればこの手法は適用できる。
• a~fのうち、最も近い２要素をクラスタリングする。
  • (b,c), (d,e) をそれぞれ一つのクラスターにする
• 以降、同様に近いクラスター同士をマージして行く。
  • 次に近いクラスターは (de, f) なので、これらをマージする。
  • ２つのクラスター $\mathcal{A}$, $\mathcal{B}$ 間の距離は複数の定義方法があり得る
    • complete-linkage clustering: \max {, d(x,y) : x \in \mathcal{A},, y \in \mathcal{B},}.
      • それぞれのクラスター内要素の最大距離
    • single-linkage clusteirng: \min {, d(x,y) : x \in \mathcal{A},, y \in \mathcal{B} ,}.
      • それぞれのクラスター内要素の最小距離
    • 他にも、 average-linkage clustering など複数の手法がある。
  • 
• 最終的に一つのクラスターになるまで続けられるが、クラスターの個数(number criterion)や、クラスター間の距離(distance criterion)などを決めてどこかでクラスタリングを停止する。
• 一般にはaggomerativeの計算量は $O(N^3)$ であるが、complete-linkage clustering, single-linkage clusteringの場合には $O(N^2)$ のアルゴリズム(CLINK, SLINK) が知られている。

SLINKアルゴリズム

• 論文はこちら

  • 計算量 $O(N^2)$, メモリ $O(N)$.
  • 計算量の $O(N^2)$ は各要素間の距離を必ず一度は計算する必要があるため。$O(N)$ のメモリは結果の格納のために必ず必要。

• 系統樹 (dendrogram) を要素Nの配列２つ $\Pi$, $\Lambda$ で表現する。論文では pointer representation と呼ばれている。

  • $\Pi$ : 所属するクラスターのindexを格納する。クラスターのindexは、クラスター内のnodeのindexで最大のもの。
  • $\Lambda$ : そのnodeがクラスターに所属したときの距離を保持する。

• 例えば、以下のような dendrogram を表現する時、$\Pi$, $\Lambda$ はそれぞれ以下のようになる。

  • 

• SLINKはこれらの二つのベクトルを作成して左から計算していく

algorithm

• 配列の左（インデックスの小さい方）から順番にdendrogramを更新していく。
  • 左側のn個でdendrogramを作成し、一番右に要素を追加して既存のデータを更新して行くイメージ

pi = Array.new(N, 0)
lambda = Array.new(N, 0.0)

N.times do |n|
  # STEP 1
  pi[n] = n
  lambda[n] = Float::INFINITY

  # STEP 2
  m = Array.new(n) {|idx| d(n, idx) }

  # STEP 3
  n.times do |i|
    parent = pi[i]
    if lambda[i] >= m[i]
      m[parent] = [ m[parent], lambda[i] ].min
      lambda[i] = m[i]
      pi[i] = n
    else      
      m[parent] = [ m[parent], m[i] ].min
    end
  end

  # STEP 4
  n.times do |i|
    parent = pi[i]
    pi[i] = n if lambda[i] >= lambda[parent]
  end
end

• STEP 1: 一番右に要素(n)を追加する。その際に、pi[n] = n, lambda[n] = infinity となる。
• STEP 2: 配列mにi番目の要素との距離をストアする。この配列mは順次更新されていく
• STEP 3:
  • lambda[i]>=m[i] の時（iとnとの距離が既存の要素よりも近い時）、
    • parentとnとの距離 m[parent]を d(i,parent), d(parent,n)のどちらか短い方に更新。（iとnは同じクラスターに属するため）
    • lambda[i] を m[i] に更新
    • 親をnに更新
  • lambda[i]<m[i] の時（iとnの距離が離れている時）
    • m[parent] を d(parent,n), d(i,n) のどちらか短い方に更新。parentとnの距離を計算するためには、子供とnの距離とも比較する必要がある
• STEP 4:
  • あるノードiの親のpiがnに更新された時に、ノードiの親をnに変える