🐕

クラスタリングの手法の1つ　k-medoids法についてまとめてみた

2025/08/17に公開

 この記事で学べることみなさん、こんにちは。りゅう9です。この記事では、クラスタリングの手法の1つ、k-medoids法 についてそのアルゴリズムを解説します。クラスタリングの代表と言えばk-means法 (k平均法) ですが、このk-means法との違いを含めて解説します。プログラムを用いた実装はやらずに、アルゴリズムの理解をメインとします。

 この記事の想定読者この記事ではk-means法 (k平均法) について理解していることを前提で話を進めます。こちらの記事でk-means法について解説しているので参照してください。

 k-medoids法とは k-means法との違いも含めてk-medoids法はクラスタリング手法の1つで、k-means法と同じ非階層型クラスタリングに分類されます。非階層型クラスタリングの多くの手法ではあらかじめクラスタ数を決める必要があります。[1]「クラスタ数を決める」というのは、データをいくつのグループに分けるかを決めるということです。データをいくつに分けるかをあらかじめ決めて、データをその数に分けます。k-means法では各クラスタの「中心（重心、centroid）」を基準にデータを分類するのに対し、k-medoids法では各クラスタの中の実データの1つを中心にしてデータを分類します。つまり、k-medoids法では実データがクラスタ中心となり、k-means法では重心で計算された仮想的な点 (実データではないことがほとんど) がクラスタ中心となります。k-means法でのクラスタ中心のことをセントロイド (centroid) というのに対し、k-medoids法ではクラスタ中心のことをメドイド (medoid) と言います。イメージをFig. 1に示します。(実際のメドイド、セントロイドではないことに注意して下さい)

Fig. 1 k-medoids法とk-means法のイメージ

 ざっくりとしたk-medoids法の流れ
距離・非類似度の定義

各データ点とメドイドの距離 (非類似度) を定義します。k-means法ではユークリッド距離を使うことが多いですが、k-medoids法では様々な距離関数を使用することができます。

初期化

まずは、データの中から設定したクラスタ数分だけランダムに点を選びます。この点をクラスタ中心 (メドイド) とします。

データの割り当て

各データ点を、最も近いメドイドに所属させます。

メドイドの更新

各クラスタについて、ほかの点をメドイドとしてコスト (クラスタ内の全データ点と中心の距離の合計) を計算します。コストが小さくなるならば、メドイドをその点に入れ替えます。

繰り返し

メドイドが変わらなくなるまで、2と3を繰り返します。
基本的な流れはk-means法と変わらないことがわかったでしょうか?

 各ステップの紹介それでは、各ステップの詳細を説明します。

まずは、下のFig. 2をご覧ください。今回は、xy平面上にランダムに打った60点のデータを3つのクラスタにクラスタリングしてみます。ランダムに打ったことが原因でクラスタリングの例としてはわかりにくいデータになってしまいました。すみません。

Fig. 2 初期データ
距離・非類似度の定義

まずは、距離・非類似度の定義をします。k-medoids法では任意の距離、または非類似度を使用することが出来ます。この定義により、「どの点がどのクラスタに近いか」を判定します。代表的な距離・非類似度には以下のものがあります。詳細はこちらをご覧ください。

ユークリッド距離

2点の直線距離で最も一般的に使用されます。今回の記事でもこちらを使用します。

マンハッタン距離

縦横の移動の合計で表される距離です。

コサイン距離

ベクトルの方向の違いを測る距離です。大きさよりも向きが重視されるとき (文章データや特徴ベクトル) に使用します。
そのほかにも以下のような距離・非類似度の関数があります。ほんの一例です。

チェビシェフ距離

最大の差分だけを距離とします。

マハラノビス距離

データの分散・相関を考慮してスケーリングした距離です。外れ値や異なるスケールの特徴を持つデータに有効です。

DTW距離

DTW (Dynamic Time Warping, 動的時間伸縮) で計算される距離です。時系列が時間軸にずれていても類似度を測ることが出来ます。波形データなどの時系列データに使用されます。
初期化

データの中からランダムに指定したクラスタの数だけ点を選んでクラスタ中心 (メドイド) とします。(今回は3)

Fig. 3ではランダムに選んだ点を★として描画しています。

Fig. 3 初期化
データの割り当て

各データ点をいずれかのクラスタに所属されます。0. で定義した距離関数を使用して、この距離が最も小さくなるようなクラスタに所属させます。所属させた結果はFig. 4です。

Fig. 4 データの割り当て
メドイドの更新

各クラスタについてほかの点をメドイドとしてコスト (クラスタ内の全データ点と中心の距離の合計) を計算します。コストが小さくなるならば、メドイドをその点に入れ替えます。

各データ点 x_i とメドイド m_j とし、距離関数を

く

$$

d(x_i, m_j)

$$
とすると、コストは

   cost = \sum_{i=1}^{n} d(x_i, m(x_i))
   と表されます。ここで、m(x_i) は x_i が割り当てられたクラスタのメドイドです。新たなメドイドはこのコストが最も小さくなるようなデータ点が選ばれます。
!つまりここでは、総当たりで、距離を計算することになります。このため、計算コストは高くなります。
繰り返し

2のデータの割り当てと3のメドイドの更新を繰り返しながら最終的な結果を得ます。つまり、クラスタ内でメドイドを更新した後に、クラスタを飛び越えて最も近いメドイドにデータ点を所属させます。Fig. 4の状態から、1度のメドイドの更新・再割り当てをした様子をFig. 5に示します。

Fig. 5 データの更新
さらに、最終結果をFig. 6に示します。

Fig. 6 最終結果

 k-medoids法のメリット・デメリットk-medoids法のメリットとデメリットをいくつか記します。

 メリット
外れ値に強い

k-meansでは外れ値があるとそれに引っ張られて中心がずれることがありますが、k-medoidsでは実際のデータ点をクラスタ中心に選ぶので外れ値に強くなります。

クラスタ中心が実際のデータ点である

結果として得られるクラスタ中心 (メドイド) が実際のデータ点なので、代表値として使いやすいです。

任意の距離関数を使用できる

ユークリッド距離だけではなく、マンハッタン距離やコサイン距離などでもクラスタリングできます。それ以外にも様々な距離関数を利用することができ、点だけではなく波形のクラスタリングなどもできます。

 デメリット
計算コストが高い

メドイド更新時にクラスタ内のすべての点間距離を計算するため、計算コストが高くなります。

大規模データには不向き

計算コストが高いため、データ数の多い大規模データでは距離が非常に重くなります。

局所最適解に陥ることがある

初期メドイドの選び方によっては最終結果が異なる可能性があり、局所最適解に陥ることがあります。複数回試行して、評価値 (シルエットスコアやSSEなど) が最もよくなる結果を採用します。

 まとめクラスタリングの1つ、k-medoids法についてそのアルゴリズムやメリット・デメリットをk-means法 (k平均法) との比較を含めながら見てきました。基本的にはk-means法と同じようなアルゴリズムで簡単に実装できることがわかったと思います。今後は、k-means++などの派生手法、クラスタ数を根拠を持って決める方法 (エルボー法) などについての記事も投稿予定です。

この記事に誤りがありましたらご指摘ください。

最後までお読みいただきありがとうございました。

(2025/8/30追記: k-means++についての記事をアップしました)

(2025/9/6追記: エルボー法についての記事をアップしました)

脚注
クラスタリングとは? ~各手法説明のための導入として~ ↩︎