K-medoids入門: 実データ点を代表点に選ぶクラスタリングの仕組みと主要アルゴリズムの比較
エバープレイ編集部K-medoids とは — 概要
K-medoids（ケー・メドイド）は、クラスタリング手法の一つで、各クラスタの代表点（medoid：メドイド）を実データ点の中から選び、クラスタ内の点と代表点との距離（もしくは不相違度）の総和を最小化することを目的とします。k-means と似た「k 個の代表を選ぶ」枠組みですが、代表点がデータ集合の実際の観測点である点、そして任意の距離・不相違度を扱える点で k-means と異なります。
目的関数とメドイドの定義
K-medoids の目的は、各クラスタ C_j に対してそのクラスタ内のある点 m_j（メドイド）を選び、全データに対する総距離
sum_over_i d(x_i, m_{cluster(x_i)})
を最小化することです。ここで d(·,·) はユークリッド距離に限らずハミング距離やマンハッタン距離、あるいは任意の不相違度（dissimilarity）を用いることができます。メドイド m_j はクラスタ内で他の点との距離和が最小となる実際の観測点です（平均ではありません）。
代表的なアルゴリズム
- PAM（Partitioning Around Medoids）
Kaufman と Rousseeuw が提案した標準的アルゴリズム。初期メドイドを決める「BUILD」段階と、メドイドの入れ替えを試して改善する「SWAP」段階から成ります。局所最適に収束しますが、全組合せの入れ替え評価を行うため計算コストが高く、大規模データには不向きです。 - CLARA（Clustering Large Applications）
PAM を大規模データに適用するためにサンプリングを使う手法。複数回ランダムサンプリングして各サンプル上で PAM を実行し、元データ全体に対して良いメドイドを評価して選びます。サンプリングにより精度と速度のトレードオフを調整します。 - CLARANS（Clustering Large Applications based upon RANdomized Search）
ランダム化された探索を用いる手法で、すべての入れ替え候補を評価する代わりにランダムにいくつか探索して局所最適を探します。探索の深さを制御することで計算量と解の品質を調整できます。 - 改良アルゴリズム・近年の実装
PAM の高速化や、k-means++ に相当する初期化（k-medoids++ と呼ばれることもある）を取り入れた手法、近似アルゴリズムなど多数の改良が提案されています。実装面では scikit-learn 互換のライブラリ（scikit-learn-extra など）で利用可能です。
k-means との違い（利点・欠点）
- 代表点の性質
k-means はクラスタ中心を平均（重心）で定義するため連続値かつユークリッド距離が前提になりやすい。一方 k-medoids は代表点を実データの点に限定するため、外れ値やノイズに対して頑健（ロバスト）です。 - 距離の柔軟性
k-medoids は任意の距離（あるいは不相違度行列）を扱えるため、カテゴリ変数や混合データ、非ユークリッド距離を扱う場面で有利です。 - 計算コスト
一般に k-medoids（特に PAM）は k-means より計算コストが高いです。PAM は距離行列を前提に多数の組み合わせ評価を行うため、大きなデータセットではそのままでは現実的でないことが多いです。
実用上の注意点とTips
- データサイズ
データ点数 n が数千〜数万を超える場合、PAM は計算負荷が大きくなるため CLARA や CLARANS、あるいはサンプリング・近似手法を検討します。 - 距離行列の事前計算
距離行列を事前に計算すると同じ距離を何度も計算するオーバーヘッドを減らせますが、距離行列自体が O(n^2) のメモリを必要とするため n が大きいと不可能になります。必要に応じてオンザフライでの計算や近似を検討してください。 - 初期化
初期メドイドの選び方で結果が変わることがあるため、複数回のランダム初期化や改良初期化（BUILD, k-medoids++ など）を試し、最良解を選びます。 - クラスタ数 k の選定
シルエット係数、Davies–Bouldin 指数、ギャップ統計量などの評価指標を用いて k を決めます。可視化（2次元や主成分）での確認も重要です。 - 実装
Python では scikit-learn-extra の KMedoids クラスが広く使われます。距離行列を渡せる実装もあり、カテゴリデータや任意の不相違度を扱えます。
応用例
- 代表サンプルの抽出（代表的な顧客、代表商品など）
- カテゴリ混合データのクラスタリング（カテゴリ変数を含む顧客セグメンテーション）
- 異常検知（外れ値があっても代表点が平均に引っ張られにくいため安定）
- 距離行列が与えられる生物学データやテキスト類似度に基づくクラスタリング
簡単な擬似アルゴリズム（PAM の考え方）
- 1) 初期メドイドを k 個選ぶ（ランダムまたは BUILD）
- 2) 各点を最も近いメドイドに割り当てる
- 3) 各メドイドについて候補データ点と入れ替え（swap）を試し、総距離が改善する場合は入れ替える
- 4) もはや改善が得られなければ終了、得られたメドイドと割当が解
まとめ（いつ使うべきか）
K-medoids は「代表点を実データから選びたい」「距離がユークリッドに限定されない」「外れ値の影響を抑えたい」といった要件がある場合に非常に有用です。一方で計算コストが高いため、データ規模が大きい場合はサンプリングや近似法、改良アルゴリズムを併用する必要があります。実務ではまず小規模なサブセットでアルゴリズムの挙動を把握し、必要に応じてスケーリング戦略（CLARA, CLARANS, 近似初期化）を検討すると良いでしょう。
参考文献
- K-medoids — Wikipedia
- L. Kaufman, P. J. Rousseeuw, "Finding Groups in Data: An Introduction to Cluster Analysis" (1990)
- Park, H. S., & Jun, C. H. (2009). A simple and fast algorithm for K-medoids clustering. Expert Systems with Applications, 36(2), 3336–3341. doi:10.1016/j.eswa.2008.01.039
- scikit-learn-extra: KMedoids (ドキュメント)
投稿者プロフィール
