クラスタリングを勉強してみる（3） partitioning clustering（k-medoids）

1. k-medoids（PAM, CLARA, CLARANS）

k-means は、クラスターの中心（centroid）を代表(represented object)とするのに対し、k-medoids は medoid を代表とします。medoid とは、クラスター内の点で、その点以外のクラスター内の点との非類似度の総和が最小になる点です。

クラスターを X_i = \{ x \}、データ間の非類似度を d(x,y) とした時、 medoid は次式で表現されます。

arg\ min_{x \in X}\sum_{ y \in (X - \{x\}) }{d(x,y)}

2. PAM（Partitioning Around Medoids）

2-1. アルゴリズム

  1. k個の medoid を選択する
  2. k-means と同様に、すべてのオブジェクトに対して、非類似度が最も小さい medoid を持つクラスターに割当てる
  3. すべてのクラスターの medoid を再計算する
  4. すべてのオブジェクトに対して、非類似度が最も小さい medoid を持つクラスターに再割当てする
  5. 3 ~ 4 を繰り返し、medoid となるオブジェクトを交換することで、より最適なオブジェクトへと近づけていく

2-2. Pros.

  • k-means がエラーを距離の2乗で評価するのに対し、距離の1乗で評価するので、ノイズ（noise）や外れ値（outlier）の影響を受けにくい

2-3. Cons.

  • k-means と比較して、処理コスト（time complexity）が掛かる：O(N^2k)

3. CLARA

3-1. アルゴリズム

  1. PAM がデータ集合全体について考えるのに対し、CLARA はデータ集合全体から ランダムにサンプル（経験則によると、40 + k 個） を抽出する
  2. 抽出したサンプルから PAM を用いて medoid を算出する
  3. 1 ~ 2 の試行を複数回（経験則によると i = 1 \ to\ 5 ）実行し、その中で最適なオブジェクトを medoid とする

3-2. Pros.

  • PAM と比較して、処理コストが掛からない：O(k(40+k)^2+ k(n-k))

4. CLARANS

4-1. アルゴリズム

  • CLARA を改良したアルゴリズム
  • CLARA は、最初にサンプリングして、後の処理はサンプルを対象とするのに対し、CLARANS は medoid を 更新した際に、新たにサンプリングを行う

4-2. Pros.

  • CLARA と比較して、高いクオリティのクラスタリングができる
  • PAM および CLARA と比較して、効率的でスケーラブルである

5. 参考文献

  • [KR 90] Kaufman L., Rousseeuw P.J.: "Finding Groups in Data: An Introduction to Cluster Analysis", John Wiley & Sons, 1990
  • [NH 94] Ng R. T., Han J.: "Efficient and Effective Clustering Methods for Spatial Data Mining", Proc. 20th Int. Conf. on Very Large Data Bases, Santiago, Chile, Morgan Kaufmann Publishers, San Francisco, CA, 1994, pp.144-155