目次
- PAMとは
- AI on Browserで動かしてみる
- 実際のコード
- PAMを応用した手法
PAMとは
PAM (Partitioning Around Medoids) とは、クラスタリングの手法の1つです。
PAMを用いたクラスタリングの流れは以下の通りです。
- ランダムに$k$個の点 (medoid) を選択する
- 各点を最も近いmedoidのクラスタに振り分け、コストを計算する
- 各medoidについて、medoidでない点と交換してみて、コストを計算する
- 3で計算したコストがこれまでのコスト未満の場合、交換した点を新たなmedoidとする
- どの点を交換してもコストが改善されなくなるまで、2から4を繰り返す
コストはクラスタ内の点の非類似度の総和を表しています。
非類似度として用いる関数には複数の種類がありますが、後述するAI on Browserではユークリッド距離を用いています。
ところで、有名なクラスタリングの手法で、k-means法があります。
PAMとk-means法では、コストとして用いる関数が異なります。
PAMではmedoidと各点の距離を、k-means法ではクラスタの重心と各点の距離の2乗をコストとして用います。
このため、PAMはk-means法よりも外れ値の影響を受けにくいというメリットがあります。
AI on Browserで動かしてみる
ブラウザ上で機械学習のデモを実施できるサイトAI on Browserを用いて、実際にPAMを実行してみます。
画像の中で「Step」ボタンを1回押すごとにEpochの数値が1増えています。
この瞬間に、上述の3と4に該当する処理が1回行われています。
最初の2回はクラスタの分け方に変化が見られますが、それ以降は変化が見られません。
3回目以降の処理では、既にどの点を交換してもコストが改善されない状態になっていると考えられます。
AI on Browserについて詳しく知りたい方は、こちらの記事をご覧ください。
実際のコード
AI on BrowserのコードはGithub上に公開されています。
PAMの実装コード
PAMを応用した手法
PAMを応用した手法として、以下の2つが挙げられます。
- CLARA (Clustering LARge Applications)
- CLARANS (Clustering Large Applications based on RANdomized Search)
CLARAとは、データの中からランダムにサンプルを抽出し、そのサンプルに対してPAMを用いることで、処理を高速化する手法です。
CLARANSとは、$N$個のデータを$k$個に分類するパターンをランダムに1つ定め、それに近いパターンとコストを比較していくことで、最適な分類パターンを探していく手法です。
また、これらの手法についても、AI on Browserでデモを行うことができます。