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のセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
クラウドネイティブ技術とアジャイル手法を駆使し、市場投入スピード（Time-to-Market）を最大化。「進化し続けるアプリケーション」を開発します。初期リリースを最速化し、拡張性と柔軟性を備えた、ビジネスの成長に追従できるアプリケーションを開発します。
DX・AI戦略支援
「何から手を付けるべきか分からない」「AIを導入したいが、費用対効果が見えない」といった経営課題に対し、技術とビジネスの両面から解を導き出します。 絵に描いた餅で終わる戦略ではなく、エンジニアリングの実装能力に基づいた、「実現可能で、勝てる技術戦略」を策定します。
リファクタリング・リアーキテクチャ
「システムが古くて改修できない」「障害が頻発する」といった技術的負債を解消します。既存資産の徹底的な診断に基づき、コードのクリーン化（リファクタリング）や、クラウドへの移行（リアーキテクチャ）を行い、システムの寿命を延ばしコストを最適化します。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。