k-means 法

k-means法とは

k-means法は、データの集まりをK個のクラスタに分ける手法です。Kは分ける数で、使う人があらかじめ決めておきます。分けた結果、どのデータもK個のクラスタのうちちょうど1つに属し、2つのクラスタに同時に属するデータはありません。このように重なりのない明確なグループに分けることが、k-means法の出発点です。

良い分け方をどう測るか

k-means法は「良い分け方」を1つの数で測り、その数を小さくする問題として組み立てられています。その数がクラスタ内変動です。

k番目のクラスタをCkと書き、そこに属するデータの個数を|Ck|と書きます。各データはp個の特徴量を持つとします。クラスタ内変動W(Ck)は、クラスタCkに属するデータのすべての組について2乗ユークリッド距離を求めて足し合わせ、それを|Ck|で割った値です。式で書くと次のようになります。

W(Ck) = (1 / |Ck|) × Σ(i, i' は Ck に属する) Σ(j = 1 から p) (x_ij - x_i'j)^2

ここでx_ijはi番目のデータのj番目の特徴量です。同じクラスタのデータどうしが近いほど、この値は小さくなります。

k-means法が目指すのは、K個すべてのクラスタについてクラスタ内変動を足した合計

W(C1) + W(C2) + ... + W(CK)

が最も小さくなる分け方を見つけることです。つまり「各クラスタの中身ができるだけまとまっている分け方」を探します。

重心の計算と割り当て直しを繰り返す手順

この最小化の問題を解く手順は、次のとおりです。

1. 各データに1からKまでの番号を無作為に割り当てる。これが最初のクラスタの割り当てになる。
2. クラスタの割り当てが変わらなくなるまで、次の2つを繰り返す。
1. K個のクラスタそれぞれについて重心(centroid)を計算する。k番目のクラスタの重心は、そのクラスタに属するデータのp個の特徴量それぞれの平均を並べたベクトルである。
2. 各データについて最も近い重心を探し、そのクラスタへ割り当て直す。

重心を求め直すと、データにとって最も近い重心が変わることがあります。そこで割り当てを直し、直した割り当てでまた重心を求めます。どのデータの所属も変わらなくなった時点で手順は終わります。

得られるのは局所最適解

この手順で得られるのは、クラスタ内変動の合計を最小にする厳密な解ではなく、局所最適解です。局所最適解とは、その近くでは良いものの、全体で最も良いとは限らない解のことです。

厳密な解を求めるのが非常に難しいのは、分け方の数が膨大だからです。n個のデータをK個のクラスタに分ける分け方はおよそKのn乗通りあり、データが少し増えるだけでもすべてを調べることはできません。そのため、k-means法は上の単純な手順で、そこそこ良い解を得ることで折り合いをつけています。

手順の最初の割り当ては無作為に決めるので、最初の割り当てが違えば、たどり着く局所最適解も違うものになりえます。

押さえておきたい点

k-means法を使うときは、次の3点が要になります。

• クラスタの数Kは、手順を始める前に使う人が決める。
• 目指すのは、クラスタ内変動の合計を小さくすることである。
• 割り当てが変わらなくなるまで、重心の計算と最も近い重心への割り当て直しを繰り返す。結果は局所最適解である。