PAM(Partitioning Around Medoids）とは
PAMは、クラスタリングアルゴリズムの一つであるK-medoids法の中核をなすアルゴリズムであり、データセットの中から実際に存在するデータ点（メドイド）をクラスタの中心として選択し、メドイドと非メドイド点の間の距離の合計を最小化することを目的とした手法のことです。
PAMの概要とクラスタリングにおける特徴
PAM（Partitioning Around Medoids、メドイド周辺分割法）は、広く用いられるパーティショニング型クラスタリングアルゴリズムであるK-means法と概念的には似ていますが、クラスタの中心を定義する点に決定的な違いがあります。
- K-means法: クラスタ内のデータの平均値（重心、Centroid）をクラスタの中心とします。重心は、データ空間内の任意の点である可能性があり、必ずしもデータセットの実際のメンバーではありません。
- PAM（K-medoids法）: クラスタ内のデータの代表点（メドイド、Medoid）をクラスタの中心とします。メドイドは、必ずデータセット内の実際のデータ点から選ばれます。
この「実際のデータ点」を中心とする特性により、PAMは外れ値（ノイズ）に対して非常に頑健であるという大きな利点があります。外れ値は平均値（K-meansの重心）を大きく引きずることがありますが、PAMでは外れ値がメドイドとして選ばれる可能性は低いからです。
主な目的は、指定されたクラスタ数 $K$ に基づき、外れ値の影響を受けにくい、より代表性の高いデータ点を中心とするクラスタリングを実現することです。
PAMアルゴリズムの動作原理
PAMアルゴリズムは、以下の2つのフェーズ（段階）を通じて、最適なメドイドのセットを見つけようと試みます。
フェーズ 1: BUILD（構築フェーズ）
このフェーズでは、初期のメドイドのセットが決定されます。
- データセットから $K$ 個のメドイドをランダムに選択するか、または貪欲なアプローチを用いて、初期コスト（メドイドと非メドイド間の距離合計）を最小化するように選択します。
- 選択された各メドイドに対し、残りのすべての非メドイド点を、最も近いメドイドが所属するクラスタに割り当てます。
フェーズ 2: SWAP（交換フェーズ）
このフェーズでは、クラスタリングの品質を向上させるために、メドイドと非メドイドの間の交換を繰り返し試行します。
- 現在のメドイドセット $M$ に含まれるすべてのメドイド $m_i$ と、データセットに含まれるすべての非メドイド点 $o_i$ の組み合わせに対して、交換を試みます。
- 交換の評価: $m_i$ を $o_i$ で置き換えた場合、クラスタリングのコスト（メドイドとデータ点との距離の合計）がどれだけ変化するかを計算します。
- コスト最小化: すべての可能な交換の中から、コストを最も大きく削減する交換ペアを選択します。
- 実行: コストが削減される交換が存在する場合、その交換を実行し、$M$ を新しいメドイドセットに更新します。
- 繰り返し: 交換によってコストが削減されなくなるまで、ステップ1から4を繰り返します。
最終的にSWAPフェーズが終了した時点でのメドイドのセットが、局所的に最適なクラスタリング結果となります。
PAMの計算量と発展
1. 距離尺度
PAMは、K-means法とは異なり、距離尺度として必ずしもユークリッド距離である必要はなく、マンハッタン距離やその他の任意の非類似度（Dissimilarity）尺度を使用できる柔軟性があります。
2. 計算量と課題
PAMは外れ値に強いという大きな利点がある反面、計算コストが非常に高くなるという課題を抱えています。
- 計算量: データの総数 $N$ とクラスタ数 $K$ に対して、交換フェーズでは $O(K(N-K)^2)$ 程度の時間計算量が必要となり、大規模なデータセットでは実用的に適用が困難になります。
この計算量の問題を克服し、大規模データにも対応できるように開発されたのが、CLARA（Clustering LARge Applications）やCLARANS（Clustering Large Applications based upon RANdomized Search）といった、サンプリングベースのK-medoids派生アルゴリズムです。これらのアルゴリズムは、データ全体ではなくその一部をサンプリングして処理することで、PAMの頑健性を維持しつつ計算効率を改善しています。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
