実務で役立つKメドイド法（K-medoids）入門：PAM・CLARA・CLARANSの比較と距離尺度選択のポイント
エバープレイ編集部概要：kメドイド法とは何か
kメドイド法（k-medoids）は、与えられたデータセットをk個のクラスタに分割するための代表的な分割型クラスタリング手法の一つです。各クラスタは「メドイド（medoid）」と呼ばれる代表点によって表され、各データ点は自分に最も近いメドイドに割り当てられます。メドイドはクラスタ内の実データ点のうち、クラスタ内の総距離（または総類似度）を最小化する点であり、クラスタ中心としての「中央値」に近い役割を果たします。
基本的な考え方と目的関数
kメドイド法の目的は、以下の目的関数を最小化することです。
- 総距離：各データ点とその属するメドイドとの距離和（あるいは不類似度）の合計
kメドイド法はユークリッド距離に限定されない任意の距離（不類似度）を扱えるため、数値データのみならずカテゴリカルデータや混合データにも適用可能です。メドイドはデータ集合内の一つの点であるため、外れ値に対してロバスト（頑健）である点も重要な特徴です。
代表的なアルゴリズム
kメドイド法にはいくつかの実装・改良アルゴリズムがあります。よく知られているものを挙げます。
- PAM（Partitioning Around Medoids）
PAMは最も基本的でかつ古典的なkメドイドのアルゴリズムです。初期メドイドを選び、"swap"（既存メドイドと非メドイド点を入れ替える）操作を繰り返して目的関数を改善します。swapで改善が見られなくなるまで反復します。精度は高いですが、計算コストが高いため大規模データには不向きです。
- CLARA（Clustering Large Applications）
CLARAはPAMの拡張で、大規模データ向けにサンプリングを取り入れた手法です。データから複数回小さなサンプルを抽出し、各サンプルにPAMを適用、得られたメドイドを元に全データの評価を行って最良解を選びます。サンプリングにより計算量を削減できますが、サンプルの取り方次第で結果の安定性が影響を受けます。
- CLARANS（Clustering Large Applications based upon RANdomized Search）
CLARANSはランダム化探索を導入した手法で、部分探索空間をランダムに探索して近似的な最適解を見つけます。PAMと比べて探索空間を全探索しないため大きなデータに適用しやすく、パラメータで探索度合いを制御できます。
PAMの処理イメージ（簡易擬似コード）
1. 初期メドイドをk個選ぶ（ランダムやBUILD法など）
2. 各点を最も近いメドイドに割り当てる
3. すべてのメドイド候補（メドイドと非メドイドのペア）についてswapを試し、
目的関数が改善する場合はswapを実行する
4. 改善がなくなるまで2〜3を繰り返す
k-meanとの比較：違いと長所短所
- 代表点：k-meansは「平均（centroid）」を用いるのに対し、k-medoidsは実際のデータ点（medoid）を代表点にします。
- 距離尺度の柔軟性：k-meansは通常ユークリッド距離を前提としており連続値に適するが、k-medoidsは任意の距離や不類似度を扱えるため、カテゴリ変数や混合データにも使えます（例：ゴワー距離/Gower）。
- 外れ値への頑健性：メドイドが実データ点であるため外れ値に引きずられにくく、k-meansよりロバストです。
- 計算コスト：PAMのような厳密最適化法は計算量が大きく、k-means（特にLloyd法）より時間・計算負荷が高いことが多いです。
距離尺度とデータ型への対応
kメドイド法の大きな利点は距離関数の自由度です。いくつかの例：
- 数値データ：ユークリッド距離、マンハッタン距離など
- カテゴリデータ：ハミング距離や単純一致係数
- 混合データ：ゴワー距離（Gower distance）が一般的
- 系列データ：DTW（動的時間伸縮）や編集距離も利用可能
適切な距離尺度を選ぶことがクラスタリング品質に直結します。数値変数が異なるスケールを持つ場合は標準化を行うべきです。
計算量とスケーリング（実務上の考慮）
PAMのような完全探索的手法は、距離行列の計算とswap評価により計算量・メモリ消費が大きくなります。実務では以下のような工夫が取られます。
- 小〜中規模データ（数千〜万点）ではPAMが有効だが、数十万点以上では計算困難
- CLARAのようなサンプリングを使うことで大規模化に対応
- CLARANSやヒューリスティック（ランダム初期化、局所探索の制限）で近似解を素早く取得
- 距離行列をメモリに全保持する場合はO(n^2)のメモリが必要。可能なら距離をオンザフライで計算するか、近似的手法を使う
- 実装ライブラリは並列化やC言語実装があるものを選ぶと高速
kの決め方と評価指標
k（クラスタ数）を決める方法としては次のような手法が一般的です。
- エルボー法：目的関数（総距離）のkに対する減少が鈍化する点を選ぶ
- シルエット係数：各点のシルエット幅の平均が最大になるkを選ぶ
- ギャップ統計量（Gap statistic）：観測データと参照データ（ランダム）との差を測る手法
- 業務知識や可視化（t-SNE, UMAP）に基づいた判断
いずれも指標は絶対解を与えるものではないため、成果物（解釈の意味・業務上の妥当性）を最終判断に用いることが重要です。
実装上の実務的注意点・チューニング
- 初期化：PAMのBUILDメソッド（貪欲初期化）やランダム初期化、複数回の再実行でローカルミニマムからの脱出を図る。
- スケーリングと前処理：数値変数はスケールを揃える。欠損値は距離計算に先立ち適切に処理する（除外、補完、距離定義の拡張）。
- 距離行列の扱い：可能なら距離行列を事前計算してキャッシュすると計算が高速化するが、nが大きいとメモリが問題になる。
- ライブラリ選択：Pythonでは scikit-learn-extra の KMedoids、Rでは cluster::pam が代表的。大規模データ向けに並列・近似実装を検討する。
- 評価と可視化：クラスタの代表点（メドイド）を確認し、各クラスタの特徴量分布をプロファイリングする。外れ値や不均衡クラスタに注意する。
適用例（ユースケース）
- 市場セグメンテーション：顧客プロファイルが混合データの場合に有効
- 施設配置（ロケーション分析）：候補地点が離散的で実在点を中心にしたい場合
- バイオインフォマティクス：配列類似度（編集距離）を用いたクラスタリング
- 異常検知や代表事例の抽出：外れ値に頑健な性質を活かす
まとめ（実務者向けの判断基準）
kメドイド法は、任意の距離尺度を扱い、代表点が実データであるため実務的解釈がしやすく外れ値に強いという利点があります。一方で計算量が大きくスケーリングが課題となるため、データサイズや用途に応じてPAM／CLARA／CLARANSのいずれかや近似法を選択する必要があります。距離尺度の設計、スケーリング、初期化、およびkの選定が結果に大きく影響するため、複数手法の比較と可視化を併用することを推奨します。
参考文献
- K-medoids — Wikipedia
- scikit-learn-extra: KMedoids (ドキュメント)
- R package "cluster"（pam を含む） — CRAN
- R.T. Ng and J. Han, "CLARANS: A Clustering Algorithm for Large Databases"（論文）
- CLARANS — Wikipedia
- CLARA — Wikipedia
投稿者プロフィール
