K-meansクラスタリング — アルゴリズムと仕組み

K-meansクラスタリングは、数値データを $k$ 個のクラスタに分ける方法です。$k$ を決めて標準的なユークリッド距離版を使うと、アルゴリズムは1つのループを繰り返します。各点を最も近い中心に割り当て、その後で各中心を、割り当てられた点の平均へ移動します。

平たく言えば、同じグループ内の点どうしは近く、異なるグループの点どうしは遠くなるようにします。高速で便利な方法ですが、こうした「グループ」がある程度コンパクトで、距離に意味がある場合にうまく機能します。

K-meansクラスタリングが最適化しているもの

標準的なユークリッド距離版では、K-meansは各クラスタ内の点が、そのクラスタの重心にできるだけ近くなるようにします。よく使われる目的関数は次の通りです。

$$\sum_{j=1}^{k} \sum_{x_i \in C_j} \|x_i - \mu_j\|^2$$

ここで、$C_j$ は $j$ 番目のクラスタ、$\mu_j$ はその重心です。

これはクラスタ内平方和です。値が小さいほど、割り当てられた点がそれぞれの重心のまわりにより密に集まっていることを意味します。

この目的関数を見ると、アルゴリズムの2つの部分が説明できます。

• 重心が固定されているなら、各点を最も近い重心に割り当てるのが最善です。
• 割り当てが固定されているなら、最適な重心は割り当てられた点の平均です。

だから更新規則は適当に決められているわけではありません。K-means の "means" は、文字通り算術平均を指しています。

K-meansアルゴリズムの仕組み

通常のループは短く、次のようになります。

1. 初期重心を $k$ 個選ぶ。
2. 各点を最も近い重心に割り当てる。
3. 各重心を、割り当てられた点の平均として再計算する。
4. 割り当てが変わらなくなるか、改善がごく小さくなるまで繰り返す。

この過程はたいていすぐに収束しますが、必ずしも最良のクラスタリングに到達するとは限りません。初期重心が違うと最終結果も変わることがあるため、初期化は重要です。

K-meansクラスタリングの例を順を追って見る

次の1次元データ点を考えます。

$$1,\ 2,\ 3,\ 10,\ 11,\ 12$$

$k = 2$ 個のクラスタを作りたいとして、重心を $1$ と $10$ から始めるとします。この例がよいのは、最初の更新のあとで重心が実際に動くからです。

ステップ1: 各点を最も近い重心に割り当てる

点 $1, 2, 3$ は $1$ に近いです。

点 $10, 11, 12$ は $10$ に近いです。

したがって、クラスタは次のようになります。

$$C_1 = \{1,2,3\}, \qquad C_2 = \{10,11,12\}$$

ステップ2: 重心を更新する

最初のクラスタの新しい重心は

$$\mu_1 = \frac{1+2+3}{3} = 2$$

2つ目のクラスタの新しい重心は

$$\mu_2 = \frac{10+11+12}{3} = 11$$

両方の重心が動き、$1$ は $2$ に、$10$ は $11$ になりました。

ステップ3: もう一度割り当てる

次に、$2$ と $11$ を使って、再び最も近い重心を確認します。

点 $1, 2, 3$ は引き続き最初のクラスタに属し、点 $10, 11, 12$ は引き続き2つ目のクラスタに属します。割り当てがもう変わらないので、アルゴリズムは収束しました。

この例がわかりやすいのは、データが自然に2つのコンパクトなグループへ分かれているからです。実際のデータセットはもっと複雑で、そうした場面ではK-meansが誤解を招くことがあります。

K-meansがうまく機能する場面

K-meansは、次の条件がだいたい成り立つときに最もよく機能します。

• 特徴量が数値である。
• 類似性を測る方法としてユークリッド距離が妥当である。
• クラスタが細長かったり曲がっていたりせず、比較的コンパクトである。
• ある変数だけが他を支配しないように、特徴量がスケーリングされている。

これらの条件が満たされない場合、出力は整って見えても、データの本当の構造を捉えられていないことがあります。

K-meansでよくある誤り

K-meansを万能なクラスタリング手法だと考える

K-meansは、クラスタがある程度コンパクトで、平均が妥当な要約になるときに最もよく機能します。すべてのデータセットに対する万能な標準手法ではありません。

特徴量のスケーリングを無視する

ある特徴量の尺度が他よりずっと大きいと、その特徴量が距離計算を支配してしまうことがあります。K-meansを実行する前に、標準化や正規化が重要になることはよくあります。

答えが一意だと思い込む

K-meansは、初期値が異なると別の局所最小値に収束することがあります。そのため、複数回実行したり、k-means++ のような初期化法を使ったりするのが一般的です。

数値でない特徴量や不適切に符号化された特徴量を使う

重心は平均なので、標準的なK-meansは数値変数を前提にしています。特徴量がカテゴリ変数なら、算術平均を取っても意味がないことがあります。

強く非球状なクラスタに使う

真のグループが細長い、曲がっている、あるいは密度が大きく不均一な場合、K-meansは1つの自然なグループを分割したり、異なる2つのグループをまとめてしまったりすることがあります。この手法は、コンパクトで重心ベースのクラスタを好みます。

外れ値が重心を引っ張ることを忘れる

重心は平均なので、極端な値があると重心が目に見えてずれることがあります。データにおいて外れ値が重要なら、結果を信頼する前にこの点を確認しましょう。

K-meansクラスタリングの用途

K-meansは、探索的なグループ分け、顧客や行動のセグメンテーション、画像の色量子化、そして教師なし学習における手早いベースラインとしてよく使われます。

特に、数値特徴量があり、高速で単純なモデルを求めていて、ユークリッド空間でクラスタがおおむねコンパクトだと期待できる場合に役立ちます。

シンプルなイメージ

散布図の上に、動かせるピンを $k$ 本置くところを想像してください。各点は最も近いピンに結びつきます。そのあと各ピンは、自分に結びついた点の平均位置へ滑るように移動します。これを、ピンがほとんど動かなくなるまで繰り返します。

このイメージは単なる直感ではありません。ほぼそのままアルゴリズム全体を表しています。

似たクラスタリング問題を試してみる

直線上の小さな点集合を用意し、$k = 2$ を選んで、割り当てと更新の1サイクルを手で実行してみましょう。次に、初期重心を変えたり、外れ値を1つ加えたりして、結果がどう変わるか見てみてください。さらに一歩進めたいなら、小さなデータセットで自分なりに試し、特徴量のスケーリング前後で何が起こるか比べてみましょう。