クラスタリングの手法の1つ　k-means法 (k平均法) についてまとめてみた

この記事で学べること

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

k-means法 (k平均法) とは

k-means法はクラスタリング手法の中で最も有名といえる非階層型クラスタリングの1つです。非階層型クラスタリングの多くの手法ではあらかじめクラスタ数を決める必要があります。^[1]「クラスタ数を決める」というのは、データをいくつのグループに分けるかを決めるということです。データをいくつに分けるかをあらかじめ決めて、データをその数に分けます。各クラスタの「中心（重心、centroid）」を基準に、データを分類します。
k-meansという名前のkはクラスタ数、meansは平均のことで、各クラスタの中心点がそのクラスター内のデータの平均値で表されることからこう呼ばれています。

ざっくりとしたk-means法の流れ

1. 初期化
   まずは、データの中から設定したクラスタ数分だけランダムに点を選びます。この点をクラスタ中心 (重心) とします。
2. データの割り当て
   各データ点を、最も近いクラスタ中心に所属させます。
3. クラスタ中心の再計算
   各クラスタに所属するデータの平均位置 (重心) を計算し、その位置を新しいクラスタ中心とします。
4. 繰り返し
   クラスタ中心が変わらなくなる (もしくは、変化が設定した閾値以下になる、データの割り当てが変化しなくなる、設定した繰り返し回数に到達する) まで2と3を繰り返します。

各ステップの紹介

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

Fig. 1 初期データ

1. 初期化
   データの中からランダムに指定したクラスタの数だけ点を選んでクラスタ中心とします。(今回は3)
   Fig. 2ではランダムに選んだ点を★として描画しています。
   
   Fig. 2 初期化

2. データの割り当て
   各データを最も近いクラスタ中心に所属させます。所属させた結果はFig. 3です。
   
   Fig. 3 データの割り当て

   「最も近い」ってどうやって計算する?
   各データとすべてのクラスタ間の距離を計算して最もその値が小さいクラスタに所属させます。この「距離」の計算には主に3つの方法が使われます。

   • ユークリッド距離
     2点間の直線距離 (最短距離) を計算します。一般的に、k-means法ではこの計算方法で距離を得ます。
     2次元空間上でのあるデータ $(x_1, y_1)$ と、あるクラスタ中心 $(x_2, y_2)$ のユークリッド距離は以下の式で計算されます。

   $$d = \sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$$

   • マンハッタン距離
     2点間を、縦横だけで進む距離の合計です。横に移動してから縦に移動するイメージです。マンハッタンの碁盤の目の街並みからこの名前になったようです。
     2次元空間上でのあるデータ $(x_1, y_1)$ と、あるクラスタ中心 $(x_2, y_2)$ のマンハッタン距離は以下の式で計算されます。

   $$d = |x_1-x_2|+|y_1-y_2|$$

   • コサイン距離
     コサイン類似度を使って計算されます。これは、ベクトルの方向の違いを測るもので、大きさは無視して、方向の違いを知りたいときに使われます。コサイン距離は0~2の値 (データが非負の場合0~1、多くはこちら) の値をとります。以下の定義通りに考えると0~2の値をとり、0のときには同じ方向を向いており、1のときには90°の角度なしており、2のときには180°の角度をなしている (真逆を向いている) ことがわかります。
     2次元空間上でのあるデータ $\boldsymbol{p_1}=(x_1, y_1)$ と、あるクラスタ中心 $\boldsymbol{p_2}=(x_2, y_2)$ のコサイン類似度とコサイン距離は以下の式で計算されます。

   $$コサイン類似度 = \frac{\boldsymbol{p_1} \cdot \boldsymbol{p_2}}{||\boldsymbol{p_1}||\times||\boldsymbol{p_2}||}$$

   $$コサイン距離 = 1 - コサイン類似度$$

3. クラスタ中心の再計算
   すべての点をいずれかのクラスタに所属させたら新たなクラスタ中心を定義します。このクラスタ中心は重心を使って計算されます。もっと平たく言うと平均をとります。
   クラスタ1 $\boldsymbol{c_1}$ に所属する点を $\boldsymbol{d_1}, \boldsymbol{d_2}, … \boldsymbol{d_n}$ とすると、新しいクラスタ中心 (重心) $\boldsymbol{c'_1}$ は以下のように計算されます。ここで $n$ はクラスタ1内の点の数です。

   $$\boldsymbol{c'_1} = \frac{1}{n} \sum_{i=1}^{n} \boldsymbol{d_i}$$

   Fig. 4は新たなクラスタ中心を★で表した結果です。
   
   Fig. 4 クラスタ中心の再計算

4. 繰り返し
   2のデータの割り当てと3のクラスタ中心の再計算を繰り返しながら最終的な結果を得ます。Fig. 5に新たなクラスタ中心に対して各データを割り当てた様子を示します。これに対して再びクラスタ中心の計算、割り当て・・・を繰り返していきFig. 6のような結果を得ます。
   
   Fig. 5 新たなクラスタ中心に対して割り当て
   
   Fig. 6 最終結果

   繰り返しの終了条件は?
   この繰り返しを終了する条件はいくつか考えられます。求める精度や許容する計算時間によって使い分けます。上限回数＋ほかの条件とすることが多いです。

   1. クラスタ中心が変化しなくなったとき
      前回のクラスタ中心と、新たなクラスタ中心の座標が同じになったら終了するという条件です。計算誤差などを考えて、変化が閾値以下になったら終了という条件にすることが多いです。
   2. データの割り当てが変化しなくなったとき
      各データがどのクラスタに属しているかが前回と全く変わらなければ終了という条件です。所属するクラスタが全く一緒なら、重心も変化しませんからそれ以上繰り返しても結果は変わりません。
   3. 最大繰り返し回数に達したとき
      収束しない場合や計算時間に制限を設ける時には繰り返しの回数の上限を設けます。この上限に達したら終了します。この条件とほかの条件を組み合わせることが多いです。
   4. SSEの変化量が閾値以下になったとき
      この記事では触れませんでしたが、クラスタリングの性能評価の指標にSSE (Sum of Squared Errors, クラスタ内平方和) というものがあります。簡単に言うと、各クラスタのクラスタ中心と属する点の距離の二乗和です。これをどんどん小さくしていくようにクラスタリングをしていくのですが、改善量が閾値以下になったら終了するという条件です。

k-means法のメリット・デメリット

ここまで、k-means法のアルゴリズムを見てきました。このk-means法にはいくつかのメリット・デメリットがあります。

メリット

• シンプルである
  先ほど見たようにとても簡単なアルゴリズムです。難しい計算式もないです。
• 計算速度が速い
  各ステップが単純な計算なので大規模なデータにも適用できます。計算量は、データ数・クラスタ数・繰り返し回数 (終了条件) で決まります。
• ライブラリが豊富に存在し実装しやすい
  多くのライブラリで実装できます。scikit-learnではわずか数行で実装可能です。

デメリット

• クラスタ数を事前に決める必要がある
  適切なクラスタ数を決めないとクラスタリングはうまくいきません。しかし、未知のデータのクラスタ数を決めるのは容易ではありません。クラスタ数を決める手段としてシルエットスコアを参照する方法やエルボー法と言われるものがあります。こちらについての記事も投稿予定です。
• 初期値依存性がある
  初期のクラスタ中心はランダムで決めていました。この選び方で結果が変わることがあり、局所解にハマってしまう可能性もあります。この対策としてk-means++という手法があり、こちらについても記事を投稿予定です。
• 外れ値に弱い
  平均値を使うため、極端な値（外れ値）が中心を引っ張ってしまい精度に問題が出る可能性があります。
• クラスタ中心が実データにならない
  クラスタ内のデータの重心をクラスタ中心とするため、最終的なクラスタ中心は実データとはなりません。代表を選びたいときには架空のデータとなり不都合です。これに対処する方法としてk-medoids法という手法があります。こちらは上の「外れ値に弱い」というデメリットにも対処することが出来ます。こちらについても記事を投稿予定です。

まとめ

クラスタリングの代表格、k-means法 (k平均法) についてそのアルゴリズムやメリット・デメリットを見てきました。とても分かりやすいアルゴリズムで簡単に実装できることがわかったと思います。今後は、k-means++やk-medoids法といった派生手法、クラスタ数を根拠を持って決める方法 (エルボー法) などについての記事も投稿予定です。
この記事に誤りがありましたらご指摘ください。
最後までお読みいただきありがとうございました。
(2025/8/17追記: k-medoids法についての記事をアップしました)
(2025/8/30追記: k-means++についての記事をアップしました)

脚注

1. クラスタリングとは? ~各手法説明のための導入として~