Aritalab:Lecture/Bioinformatics/Clustering

クラスタリング

データを分類するという作業は "人にわかりやすくする" という目的で行われるため、結果に正解があるわけではありません。与えられたデータを幾つかのまとまりに分ける作業を、クラスタリングといいます。大まかに

• 同じまとまりの中にある要素は均質であり
• 違うまとまりの中にある要素は質が異なっていること

が分類の基準になります。

階層法

最もよく用いられるクラスタリング手法です。全体のまとまりから、距離に応じてトップダウンに分割していく方法 (divisive method といいます) と、個々の要素からボトムアップにまとめ上げていく手法 (agglomerative method といいます)があります。通常はボトムアップ手法のことを意味します。

基本は大変簡単で、要素全体がひとつのまとまりになるまで以下を繰り返します。

1. もっとも距離が近いグループ A, B を探す
2. A と B をまとめて、他のグループとの距離を計算し直す

要素数が 1 より大きいグループに対する距離の計算方法には様々なバリエーションがあります。

• 最短距離を使う場合 $d(A,B) = \mbox{min}_{x \in A, y \in B} d(x,y)$

1つでも距離が近いものがあれば併合する可能性があるので、シングルリンケージ法 (single linkage) とも呼ばれます

• 最長距離を使う場合 $d(A,B) = \mbox{max}_{x \in A, y \in B} d(x,y)$

全ての要素が近くならないと併合しないので、総リンケージ法 (complete linkage) とも呼ばれます

• 平均距離を使う場合 $d(A,B) = \textstyle\frac{1}{|A| |B|}\sum_{x \in A, y \in B} d(x,y)$

それぞれの距離における利点と欠点を考えてみてください。実際によく使われるのは Ward 法と呼ばれる距離の定義です。

Ward 法 

クラスタをまとめたときに、中心からの距離がどれだけ増加するかを計算して距離とみなします。ここで m は各クラスタの重心を意味します。

$d(A,B) =\textstyle \sum_{x \in A\cup B} (m_{A\cup B} - x)^2 - \sum_{x \in A} (m_{A} - x)^2 - \sum_{x \in B} (m_{B} - x)^2$

k-平均法

あらかじめクラスターの個数がわかっている場合 (k 個)、その個数ぶんクラスターを返す手法です。

1. 各データに対してランダムにクラスタを割り振る。
2. 各クラスタの中心を計算する。（通常は割り当てたデータの平均値）
3. 各データに対してクラスタとの距離を求め、最も近いクラスタに割り当て直す
4. 割り当ての変更がなくなったら処理を終了。それ以外の場合はステップ2に戻る

データが散らばっている場合は最初のクラスタ割り振りに大きく依存することが知られています。