Hierarchical clustering algorithm #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に変える