メドイド法入門から応用まで：PAM/CLARA/CLARANSで学ぶ頑健なクラスタリングの実務ガイド
エバープレイ編集部メドイド法とは
メドイド法（k-medoids、Partitioning Around Medoids：PAM など）は、クラスタリング手法の一つで、各クラスタを代表する「メドイド（medoid）」という実データ点を中心としてクラスタを定義します。メドイドはクラスタ内の点の総距離（または総非類似度）を最小にする代表点であり、平均（セントロイド）を用いる k-means と異なり、必ずデータ集合に含まれる観測点を代表点に選ぶため、外れ値やノイズに対して頑健（ロバスト）という特徴があります。
基本的な概念と比較
主要な違いは以下の通りです。
- 代表点の定義：k-means はクラスタの平均（セントロイド）を用いるのに対し、メドイド法は実データ点の中から代表点（メドイド）を選ぶ。
- 距離（非類似度）の扱い：k-means はユークリッド距離や平方誤差に基づく最適化が前提だが、メドイド法は任意の距離・非類似度行列を扱える。
- 頑健性：外れ値がセントロイドに大きな影響を与えるのに対し、メドイドは代表点がデータ点なので外れ値に引きずられにくい。
代表的なアルゴリズム
メドイドに基づく代表的なアルゴリズムには以下があります。
- PAM（Partitioning Around Medoids）：Kaufman と Rousseeuw によって広く知られる手法。初期メドイドを選ぶ BUILD フェーズと、メドイドと非メドイドを入れ替えてコスト（クラスタ内の総非類似度）を改善する SWAP フェーズからなる。スワップで改善がなくなるまで繰り返す。
- CLARA（Clustering Large Applications）：大規模データ向けに PAM を改良したもの。データ全体ではなくランダムサンプリングを複数回行い、それぞれに対して PAM を適用してよい解を得る。全体に対する近似解を得る手法。
- CLARANS（Clustering Large Applications based upon RANdomized Search）：ランダム化探索を取り入れた手法。局所最適に陥るのを避けるため、近傍探索をランダムに行い、有望な探索に絞って効率化する。
PAM の基本的な流れ（概要）
- BUILD（初期化）：貪欲法で k 個の初期メドイドを選ぶ。
- ASSIGN：各点を最も近いメドイドに割り当てる。
- SWAP：非メドイド点とメドイド点の入れ替え（swap）を試し、総コストが減少する入れ替えを採用。改善がなくなるまで繰り返す。
SWAP により局所最適を探るため、初期化やランダム再実行が解の質に影響します。
利点と欠点
- 利点
- 任意の距離・非類似度を使えるため、カテゴリカルデータや混合型データに適用可能。
- メドイドが実データ点なので解釈性が高い（代表観測が直接示される）。
- 外れ値に対して k-means より頑健。
- 欠点
- PAM の計算コストは高く、距離行列を扱うためメモリと計算時間が問題になりやすい（大規模データには不向き）。
- 局所最適に陥りやすく、初期化や反復回数に依存する。
計算量と大規模データへの対応
PAM は内部で多くの距離計算やスワップ候補の評価を行うため、データ点数 n が大きくなると O(n^2) に近い計算や距離行列の保存がボトルネックになります。そのため大規模データでは CLARA（サンプリング）や CLARANS（ランダム探索）のような近似アルゴリズム、あるいは距離行列を分割・近似する手法を併用するのが一般的です。また、最近は効率的な近似距離計算やインデックス手法を利用して高速化する実装もあります。
評価指標と k の決め方
k（クラスタ数）の決定は難しい問題です。メドイド法でよく使われる評価指標には以下があります。
- シルエット幅（Silhouette）：各点のクラスタ内距離と最近接クラスタまでの距離の差を正規化した指標。平均シルエット幅が大きいほど良い。
- 総コスト（クラスタ内総距離）のプロット（肘法）：k を変化させて総コストの減少が鈍る点を探す。
- ギャップ統計量や外部ラベルに基づく指標（ARI など）も適用可能。
実装上の注意点と実務的なコツ
- 距離行列の事前計算：計算回数を減らすために距離行列を事前に計算してキャッシュする。ただし n が大きいとメモリが問題になる。
- 初期化を複数回試す：局所最適回避のために複数の初期化を試して最良解を選ぶ。
- 使う距離の選定：データの性質に合わせてユークリッド、マンハッタン、レーベンシュタイン（文字列）、カイ二乗（カテゴリ分布）などを選ぶ。
- 実装ライブラリ：R の cluster パッケージの pam、Python では scikit-learn-extra の KMedoids、pyclustering ライブラリなどが利用可能。
ユースケース（適用例）
- カテゴリカルデータのクラスタリング（例えば顧客属性のセグメンテーション）
- テキストやシーケンス（編集距離など任意の非類似度で測れる場合）
- 距離行列が事前に与えられる場合（例えば生物学での相同性行列や距離行列）
- 外れ値が存在するデータセットで k-means より信頼性の高い代表点を得たい場合
まとめ
メドイド法は、実データ点を代表として用いることで解釈性や頑健性に優れるクラスタリング手法です。任意の距離を扱えるため応用範囲は広い一方、計算コストが高いため大規模データには工夫（サンプリング、ランダム探索、近似手法など）が必要です。実務ではデータの性質や目的（解釈性重視か、スケーラビリティ重視か）に応じて k-means と使い分けたり、PAM をベースにした近似アルゴリズムを採用したりするのが一般的です。
参考文献
- K-medoids — Wikipedia
- Partitioning Around Medoids (PAM) — Wikipedia
- CLARA — Wikipedia
- CLARANS — Wikipedia
- Silhouette (clustering) — Wikipedia
- R package "cluster"（pam 実装） — CRAN
- scikit-learn-extra: KMedoids（Python 実装）
- pyclustering: k-medoids（Python 実装）
- Kaufman, L. & Rousseeuw, P.J., "Finding Groups in Data: An Introduction to Cluster Analysis"（書籍）
