階層型クラスタリング

階層型クラスタリングの代表的な手続きは以下の通り：

1. 距離を定義
2. クラスタリング手法を定義
3. 1.に基づきNearest Neighbor Pair (最も距離が近いクラスタペア) をサーチ
4. 3.をマージし1つのクラスタとする
5. 4.と他のすべてのクラスタとの距離を2.の方法で更新する
6. 3-5をクラスタが1つになるまで繰り返す

クラスタリング手法は複数知られていますが、距離更新の方法は以下の式で一般化されます。



クラスタiとクラスタjをマージしてクラスタkとしたときのk以外のクラスタhとの距離を表します。Dは２つのクラスタの距離を表します。係数α, β, γを以下のように設定することが種々のクラスタリング手法に対応します。



nはクラスタの要素数です。beta-Flexibleではβをパラメータとしています。
この一般式により任意の距離行列を与えることで各クラスタリング法が適用可能となります。しかし、網羅解析データのクラスタリングにはしばしば距離行列のストアに問題が発生します。計算に必要なメモリ空間のオーダーは O(N^2) となります。マイクロアレイなどのように数万プローブが解析対象である場合、実メモリが足りなくなってしまいます。その場合...

1. 変数の数を減らす
2. K-means等の非階層型クラスタリングを使う
3. Reciprocal Nearest Neighbor (RNN) 法を使う

1は解析対象にバイアスをかけるのでできれば使用したくない手です。2はクラスタ数を指定する必要があり、一般にクラスタ数は未知です。階層型クラスタリングでの結果を求めれば、3を選択するのがよいと思います。RNNについては次回。