k-means法（k-means Clustering）

k-means Clustering

概要

k-means法（k-means Clustering）とは、データをあらかじめ指定したk個のクラスタ（グループ）に分割する教師なし学習のクラスタリング手法です。各クラスタの重心（セントロイド）からの距離を基準にデータを分類し、データの割り当てと重心の更新を反復的に行うことで、クラスタ内の分散を最小化します。

k-means法はアルゴリズムがシンプルで計算が高速であるため、大規模データにも適用しやすく、クラスタリング手法の中で最も広く使われています。顧客セグメンテーション、画像圧縮、文書分類、異常検知の前処理など、幅広い応用があります。G検定では、アルゴリズムの手順、k値の決め方、初期値依存性の問題が出題されます。

詳細解説

アルゴリズムの手順

k-means法のアルゴリズムは、以下の手順で動作します。

1. 初期化：k個の初期重心をランダムに選択する（またはデータ点からランダムに選ぶ）
2. 割り当てステップ：各データ点を、最も近い重心のクラスタに割り当てる（ユークリッド距離を使用）
3. 更新ステップ：各クラスタに割り当てられたデータ点の平均値を計算し、新しい重心とする
4. 収束判定：重心の位置が変化しなくなる（またはデータの割り当てが変化しなくなる）まで、手順2〜3を繰り返す

このアルゴリズムは、各反復でクラスタ内分散（SSE：Sum of Squared Errors）が単調に減少することが保証されており、必ず収束します。ただし、収束先は初期値に依存するため、大域的最適解に到達する保証はありません。

k値の決め方

k-means法ではクラスタ数kを事前に指定する必要がありますが、最適なk値をどのように決めるかは実用上の重要な課題です。以下の方法が一般的に使われます。

エルボー法（Elbow Method）

kの値を1から順に増やしながらクラスタ内分散（SSE）を計算し、kとSSEの関係をグラフにプロットします。SSEの減少率が急激に変化する点（肘のように曲がる点）を最適なk値とします。直感的にわかりやすい方法ですが、明確な肘が見つからない場合もあります。

シルエット分析（Silhouette Analysis）

各データ点が自分のクラスタにどれだけ適切に属しているかを評価するシルエット係数を計算します。シルエット係数の平均値が最大になるkを選択します。

Gap統計量（Gap Statistic）

クラスタリング結果と一様分布からのランダムデータのクラスタリング結果を比較し、最適なk値を統計的に決定する方法です。

初期値依存性の問題

k-means法の大きな課題の一つが初期値依存性です。初期重心の位置によって、収束先のクラスタリング結果が異なる可能性があります。不適切な初期値を選んでしまうと、局所最適解に陥り、望ましくないクラスタリング結果が得られることがあります。

この問題への対処法として、複数回異なる初期値でk-meansを実行し、最もSSEが小さい結果を採用する方法が一般的です。

k-means++

k-means++は、2007年にデイヴィッド・アーサーとセルゲイ・ヴァシリビツキによって提案された初期値選択の改良アルゴリズムです。初期重心を確率的に分散させることで、初期値依存性の問題を大幅に軽減します。

k-means++の初期化手順は以下のとおりです。

1. 最初の重心をデータ点からランダムに1つ選ぶ
2. 各データ点について、最も近い既存重心からの距離の二乗に比例する確率で、次の重心を選ぶ
3. k個の重心が選ばれるまで手順2を繰り返す

この方法により、初期重心が互いに離れた位置に配置されるため、局所最適解に陥りにくくなります。現在のk-means実装の多くで、k-means++がデフォルトの初期化方法として採用されています。

k-means法の長所と短所

• 長所：アルゴリズムがシンプルで理解しやすい、計算が高速で大規模データにも適用可能、実装が容易
• 短所：kの値を事前に指定する必要がある、初期値に依存する、球形のクラスタしか検出できない（非凸形状のクラスタには不向き）、外れ値に敏感

歴史・背景

k-means法のアルゴリズムは、1957年にスチュアート・ロイドがベル研究所で信号量子化の研究として考案しました（ただし、論文としての発表は1982年）。1967年にはジェームズ・マックイーンが「k-means」という名称を初めて使用しました。

その後、k-means法は統計学、パターン認識、データマイニングの分野で広く採用されるようになりました。2007年のk-means++の提案により初期値問題が改善され、実用性がさらに高まりました。現在では、scikit-learnなどの主要な機械学習ライブラリにk-means++がデフォルトで実装されており、最も基本的なクラスタリング手法として定着しています。

具体的な事例

• 顧客セグメンテーション：購買金額、購買頻度、最終購買日（RFM分析）などの指標を用いて、顧客を複数のグループに分け、それぞれに適したマーケティング施策を実施します。
• 画像圧縮：画像の色数をk色に削減することで、データ量を圧縮します。各ピクセルの色をk個のクラスタ重心色に置き換えます。
• 文書クラスタリング：ニュース記事やSNS投稿をトピックごとにグループ分けし、情報の整理や分析に活用します。
• 異常検知の前処理：正常データをクラスタリングし、どのクラスタにも属さないデータ点を異常として検出する手法のベースとして利用されます。
• 地理的分析：店舗の最適な配置場所の決定や、配送ルートの最適化のためのエリア分割に活用されています。

G検定での出題ポイント

• k-means法は教師なし学習のクラスタリング手法であることを理解する
• アルゴリズムの手順（初期化→割り当て→更新→収束判定）を説明できること
• kの値を事前に指定する必要があること、エルボー法による決め方を知っておく
• 初期値依存性の問題とk-means++による改善を理解する
• 球形のクラスタしか検出できないという制約を把握する

関連キーワード

• 教師なし学習
• 主成分分析（PCA）
• 教師あり学習
• 評価指標
• 交差検証と過学習