Reciprocal Nearest Neighbor

前回の階層型クラスタリングの話で変数の数が数万の場合、普通のPCではメモリ不足になると書きました。距離行列の空間オーダーはO(N^2)です。もう少し細かく計算すると距離行列は対象行列なのでN(N-1)/2個の要素で記述できます。double型は8byteなのでN変数に対して、4N(N-1)byteのメモリ空間が要求されます。



図の横軸は変数の数N、縦軸は対応するメモリ量です。2万くらいまでは、普通のPCで計算できそうですが、マイクロアレイのプローブは4万くらいのものもあるので、その類いは厳しそうです。※もっとも、最近はメモリも安いので64bitコードで8Gぐらいメモリを積めばいけますが...。さて、メモリが足りないときどうしようか？前回も書きましたが、簡単に思いつくのは以下。

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

1 は解析対象にバイアスをかけるのでできれば使用したくない手です。※ただ、マイクロアレイの場合、probe to geneで遺伝子単位で解析するのは有効かと思います。2はクラスタ数を指定する必要があり、一般にクラスタ数は未知です。階層型クラスタリングでの結果を求めれば、3を選択するのがよいと思います。多変数のクラスタリングのときよく使っています。ということでRNNですが"Reciprocal"とは" 相互"という意味です。つまり、お互いにNNということです。NN(i)=j, NN(j)=i：iのNNはjでjのNNはiということになります。RNNを用いたクラスタリングは以下の通り（Ward法の結果と一致します）。

1. NN-chianを構築する。NN-chianとはNN(i)=j, NN(j)=k, NN(k)=l, ...とNNの数珠つなぎの構造です。
2. NN-chianを作っていくと末尾にRNNが現れます。これを統合し新クラスタとします。このとき新クラスタのデータをDk=(Ni*Di+Nj*Dj)/(Ni+Nj)で更新します。
3. NN-chainを再構築します。これを繰り返します。

※ 距離行列を使わない事がミソです。データの更新のみでクラスタリングが完遂されるので必要なメモリオーダーはO(N)です。おおよそ最初に入力したデータ領域があればよいことになります。この方法はNN-chainがreducibilityを満たす事により成立します。reducibilityとは、 NN-chainの順番に２変数の距離が単調増加することを意味します。簡単にいえば、先頭のペアは最も近く、次のペアは２番目に近く...といった具合です。RNNを統合して1つのクラスタにしてもこの法則は崩れません。この手法であれば数万変数のクラスタリングも少ないメモリで計算できます。この手法は化合物のクラスタリング"BCI Ward"のような数万〜十万変数を扱う分野で使用されています。