scikit-learn-extraのKMedoidsの実装を読んだ

概要

scikit-learn-extraのKMedoidsの実装を読んだので備忘録として残しておく。

KMedoidsとは

KMeansと同種のクラスタリングアルゴリズムで、クラスタの代表点としてクラスタの重心(centroid)でなくメドイド(medoid)を使う。メドイドは1次元における中央値(median)を多次元に拡張した概念で、「全サンプル点との距離の総和が最小となる点」として定義される。

$$\text{Medoid}=\min_{x_i} \sum_i | x - x_i |$$

アルゴリズムの概要

KMedoidsのアルゴリズムにはいくつか存在するが、ここではPAMというアルゴリズムについて説明する。

1. BUILD: greedyなアルゴリズムを使って初期値を選択する。
2. SWAP: クラスタの代表点以外の点の集合のうち、代表点のいずれかと交換することでコストが最小になるものを見つける。この点と代表点を交換し、クラスタの再割り当てを行う。この処理を収束するまで繰り返す。

以下ではSWAP処理について説明する。

SWAP

タスクを書き直すと、「(代表点、非代表点)のペアの集合から、両者を交換することでコストが最小になる点を見つける」となる。コストは「代表点とクラスタ内の全点との距離の総和」で定義される。したがって、計算量は O(k(N-k)²) となる（N: サンプル数、k: クラスタ数）。KMeansがサンプル数に比例する計算量なので、KMeansよりも計算コストが高い。

pythonの擬似コードを書くと、以下のような3重のforループを使って計算する。

for h in non_medoid_points:
    for i in medoids:
        for j in non_medoid_points:
            ....

このコードはメドイドiを非メドイド点hと交換した場合のコストを(h, i)の全ての組み合わせについて計算している。jのループについては、「h, iを交換した場合のコストの変化の総和」を計算している。このコストの変化の総和が負の値になる場合はコストが現在よりも下がるということなので、交換する候補になる。最終的に(h, i)の全ての組み合わせについて、交換によるコストが負の最小値になるような組み合わせについて(h, i)を交換する。

なお、ナイーブに実装するとコストの計算に距離の計算が重複して計算してしまい、計算量が増加する。これを避けるために、scikit-learn-extraの実装では1度だけ計算すれば良いような工夫がされている。

まず、以下の3つの値を計算しておく。

1. サンプル点のうち任意の2点間の距離: D_i, j (N, N)-行列
2. サンプル点と、一番近いメドイドとの距離: C_i, j (N,)-行列
3. サンプル点と、2番目に近いメドイドとの距離: S_i, j (N,)-行列

これらの3つの値を使って、「hとiを交換した場合のコストの変化」を以下のように場合分けして計算する（図1 (a)-(c)）。

1. jがiのクラスタに所属し、かつ、hがjの二番目に近いメドイドとの距離よりも近い場合
2. jがiのクラスタに所属し、かつ、hがjの二番目に近いメドイドとの距離よりも同じか遠い場合
3. jがiのクラスタに所属せず、かつ、hがjの最も近いメドイドとの距離よりも近い場合

上記以外の場合は交換によりコストの変化が生じないのでコストの変化は0となる。

最後に、iとhを交換することにより、新たにiが非メドイド点に変わるため、新たにiとメドイドとの距離がコストとして追加される。この時のコストの変化を以下のように場合わけして計算する（図1 (d)-(e)）。

1. hがiの2番目に近いメドイドとの距離よりも近い場合
2. hがiの2番目に近いメドイドの距離よりも同じか遠い場合

a-eのそれぞれのケースにおけるコストの変化量は以下のようになる。

1. D(j, h) - Cj
2. Sj - Cj
3. Cj - D(j, h)
4. D(i, h)
5. Sj

図1. コスト変化の場合分け

参考

本記事におけるKMedoidsの実装はscikit-learn-extraのものを参考にした。

github.com