k-means++ についてまとめてみた
この記事で学べること
みなさん、こんにちは。りゅう9です。この記事では、クラスタリングの代表格、k-means法 (k平均法) を使うときに役立つk-means＋＋について解説します。
そもそもk-means法 (k平均法) とは?
クラスタリングとは「データを似ているもの同士でグループ分けする」手法のことです。
その代表がk-means法です。
k-means法では以下のような手法でクラスタリングを行います。
-
初期化
まずは、データの中から設定したクラスタ数分だけランダムに点を選びます。この点をクラスタ中心 (重心) とします。 -
データの割り当て
各データ点を、最も近いクラスタ中心に所属させます。 -
クラスタ中心の再計算
各クラスタに所属するデータの平均位置 (重心) を計算し、その位置を新しいクラスタ中心とします。 -
繰り返し
クラスタ中心が変わらなくなる (もしくは、変化が設定した閾値以下になる、データの割り当てが変化しなくなる、設定した繰り返し回数に到達する) まで2と3を繰り返します。
詳しくはこちらの記事をご覧ください。
k-means++とは? ざっくりとした流れ
k-means++はk-means法の初期化の部分に工夫を加えた手法です。通常のk-means法では「ランダム」に初期値を選んでいたのに対して、k-means++では以下の手法で初期中心を選びます。
- データ点からランダムに1点を選び、最初の中心とする。
-
残りのデータ点に対して、1. の点 (既存の中心) との距離の2乗を計算する。
2回目以降は最も近い中心との距離を計算します。 -
先ほどの2. の距離の2乗を使って確率を計算する。（この式は後ほど解説します。）
この確率は、既存の中心から離れているほど選ばれやすいように設定します。 - k個 (指定したクラスタ数分) の中心が選ばれるまで2. と3. を繰り返す。
- 中心を選び終えたら通常のk-means法の手法でクラスタリングをする。
各ステップの紹介
以下のようなデータから初期値を選ぶ問題を考えます。今回k=3とします。つまり、3つの初期点を選びます。
Fig. 1 データ
-
データ点からランダムに1点を選び、最初の中心とする。
まずは、初期点をランダムに選びます。Fig. 1の点0を初期点とします。 -
残りのデータ点に対して、1. の点 (既存の中心) との距離の2乗を計算する。
現在は点0だけ選ばれているので、点0とそのほかの点との距離を計算します。
今回は各点間の距離を以下のように設定して、0-i D_{0-i}^2 D_{0-1}^2 = 8^2 = 64 D_{0-2}^2 = 6^2 = 36 D_{0-3}^2 = D_{0-4}^2 = 4^2 = 16 D_{0-5}^2 = 3^2 = 9 D_{0-6}^2 = 1^2 = 1 -
先ほどの2. の距離の2乗を使って確率を計算する。
各点に対して、以下の式で定義される確率を計算します。\frac{{D_x}^2}{\sum{D_x}^2} つまり、分母には各点間距離の合計、分子には対象の点との距離が入ります。
実際に上の例で計算してみると以下のようになります。点1: \frac{64}{64+36+16+16+9+1}\thickapprox0.451 同じようにやると、
点2 \thickapprox0.254 点3 \thickapprox0.113 点4 \thickapprox0.113 点5 \thickapprox0.063 点6 \thickapprox0.007
よって、今回は点1が最も選ばれる確率が高くなり (45%)、次に点2が選ばれやすく (25%) なります。ここで注意が必要なのは、最も高い確率の点が選ばれるわけではなく、あくまで、確率的に選ぶということです。点1が選ばれやすいですが、6%くらいの確率で点5が選ばれます。
今回は確率通り、点1が2つ目の中心として選ばれたとします。(Fig. 2)
Fig. 2 2点目が選ばれた様子 -
k個 (指定したクラスタ数分) の中心が選ばれるまで2. と3. を繰り返す。
次に3点目を選びます。まずは2. と同じように距離を計算するのですが、この時、既存の中心の中で最も近い点との距離を計算します。
今回は、ここまでで点0と点1がクラスタ中心として選ばれていますが、点5の確率を計算するときは、0-5間の距離は3、1-5間の距離は2であることより、1-間の距離の二乗 4を使います。これにより、すでに選ばれた中心から近い点は選ばれにくくなり、データ全体をカバーするようにクラスタ中心を得ることが出来ます。
各点の距離を計算した後は同じなので割愛します。これを、指定のクラスタ数kに達するまで続けます。 -
中心を選び終えたら通常のk-means法の手法でクラスタリングをする。
Fig. 3のような3点のクラスタ中心が初期値として選ばれたとして、ここからは、通常のk-means法と同じような手法で全データ点をいずれかのクラスタに所属させます。
Fig. 2 全ての初期値が選ばれた様子k-means法の方法はこちらの記事を参照してください。初期化は終了しており、ステップ2から始めます。
k-means++のメリット
このようにk-means++は賢く初期値を選ぶことが出来ます。これにより以下のようなメリットがあります。
- 完全ランダムで選ぶよりもクラスタの精度が上がる。
- 無駄な計算を減らすことが出来て、収束が速い。
- 実行するごとの結果のブレが減る (安定性が高い)。
このk-means++はscikit-learnのKMeansでもデフォルトで使用されています。
まとめ
今回はk-means法 (k平均法) で賢く初期値を決める方法であるk-means++についてその手法を見てきました。今後は、クラスタ数を根拠を持って決める方法 (エルボー法) などについての記事も投稿予定です。
この記事に誤りがありましたらご指摘ください。
最後までお読みいただきありがとうございました。
Discussion