K-meansクラスタリングとは？基本概念からアルゴリズムの仕組みまで徹底解説

K-meansクラスタリングの概要

K-meansクラスタリングは、最も広く使われている分割型（パーティショニング）クラスタリングアルゴリズムです。K-meansでは、データセット内の各データを、新しく形成されるクラスタのいずれか1つに割り当てます。個々のレコード（データポイント）は、距離や類似度の尺度を用いて、最も近いクラスタに割り当てられる仕組みです。

k-meansアルゴリズムは、入力パラメータとしてクラスタ数 k を受け取り、n個のオブジェクトからなる集合をk個のクラスタに分割します。その結果、クラスタ内の類似度（intracluster similarity）は高く、クラスタ間の類似度（intercluster similarity）は低くなるように分割が行われます。クラスタの類似度は、クラスタ内のオブジェクトの平均値に基づいて計算され、この平均値はクラスタの「重心（centroid）」または「重心（center of gravity）」とみなすことができます。

K-meansクラスタリングの手順

K-meansクラスタリングは、以下のステップで実行されます。

• K個の初期クラスタ重心 c₁, c₂, c₃ … c_k を選択する。
• 集合S内の各インスタンスxを、重心がxに最も近いクラスタに割り当てる。
• 各クラスタについて、そのクラスタに含まれる要素に基づいて重心を再計算する。
• 収束が完了するまで、割り当て処理を繰り返す。
• オブジェクト（データポイント）をK個のクラスタに分割する。
• クラスタ中心（重心）は、クラスタ内のすべてのデータポイントの平均値として定義される。
• 距離関数を用いて、各ポイントを重心が最も近いクラスタに割り当てる。

平均値の初期値は任意に設定されます。ランダムに割り当てることもできれば、最初のk個の入力データの値をそのまま利用することも可能です。収束条件としては二乗誤差（squared error）がよく使われますが、必ずしもこれに限定されるわけではありません。その他の終了条件として、単純に反復回数を固定回数に制限する手法もあります。収束しない場合でも確実に処理を停止できるよう、最大反復回数を設定しておくのが一般的です。

K-meansアルゴリズムの定義

入力

D = {t1, t2, …, tn} // 要素の集合
k // 目標とするクラスタ数

出力

K // クラスタの集合

アルゴリズムの流れ

平均値 m1, m2, …, mk の初期値を設定する
repeat
    各項目 ti を、最も近い平均値を持つクラスタに割り当てる
    各クラスタの新しい平均値を計算する
until 収束条件が満たされるまで繰り返す

クラスタリングの進行イメージ

まず、3つのオブジェクトを3つの初期クラスタ中心として任意に選択します（クラスタ中心は「+」で表現されます）。各オブジェクトは、最も近いクラスタ中心に基づいてそれぞれのクラスタに割り当てられます。

次に、クラスタ中心が更新されます。各クラスタの平均値は、そのクラスタに現在属しているオブジェクトに基づいて再計算されます。そして、新しいクラスタ中心を利用して、各オブジェクトを最も近いクラスタ中心へ再分配します。この再分配によって、破線で囲まれた新しいクラスタの輪郭が形成されます。

反復再配置（Iterative Relocation）

パーティショニングの品質を向上させるために、オブジェクトをクラスタへ繰り返し再割り当てするこの手順は、反復再配置（repetitive relocation）と呼ばれます。どのクラスタにもオブジェクトの移動が発生しなくなった時点で、プロセスは終了します。最終的に得られたクラスタは、クラスタリングの結果として出力されます。

K-meansは計算コストが比較的低く、大規模データにも適用しやすいことから、データマイニングや機械学習の分野で広く活用されている基本的な手法です。