【数学】k-means法とは

グループ化（クラスタリング）には、様々な手法がありますが、k-means法とは、その中でも単純な手法です。

■アルゴリズム
1. 各データに対して、ランダムにクラスタを割り当てる。
2. 各クラスタに対して、データの中心（クラスタ中心）を算出する。
3. 各データと各クラスタ中心の距離を算出し、最も距離が近いクラスタ中心と同じクラスタに再度割り当てる。
4. 2と3を繰り返し実施し、割り当てが変化しなくなった時に終了する。

■アルゴリズムの具体的説明
①変数の定義
記号、ベクトルの要素の割り当てなどは、下記の限りではありません。（例えば、記号はxでなくてyでもよいし、gなんてものを用意しないでベクトルxの要素に足してもよい。私のやりやすいようにやってます。）

<変数>
$\quad \begin{align} \boldsymbol{x}& \mbox{：データ} \\ \boldsymbol{v}& \mbox{：クラスタ中心} \\ d& \mbox{：データとクラスタ中心の距離} \\ g& \mbox{：各データに対してのクラスタ番号} \\ \end{align}$
f:id:lm4183:20200822185141p:plain

②アルゴリズム
1. 各データに対して、ランダムにクラスタを割り当てる。
1.1. データを取得する。
当然ですが、クラスタリングするにはデータが必要です。
ここでは例として、下図のように $\boldsymbol{x_1}\mbox{・・・}\boldsymbol{x_6}$ のデータがあったとします。
f:id:lm4183:20200822213241p:plain

1.2. 各データに対して、ランダムにクラスタを割り当てる。
下図のように、各データ $\boldsymbol{x}$ に対して、ランダムにクラスタ番号を割り当てます。
※下図の例では、 $\boldsymbol{x_1}$ , $\boldsymbol{x_2}$ はクラスタ1、 $\boldsymbol{x_3}$ ～ $\boldsymbol{x_6}$ はクラスタ2となっています。

また、各データ $\boldsymbol{x}$ のクラスタ番号の情報は、各クラスタ $g$ が持つこととします。
※例えば、 $\boldsymbol{x_1}$ はクラスタ1であるので、 $\boldsymbol{x_1}$ に対応した $g_1$ は1となっています。
f:id:lm4183:20200822213605p:plain

2. 各クラスタに対して、データの中心（クラスタ中心）を算出する。
各クラスタに対して、データ $\boldsymbol{x}$ の中心（クラスタ中心） $\boldsymbol{v}$ を算出します。
f:id:lm4183:20200822222613p:plain
クラスタ中心は、一般的には相加平均（一般的に平均と呼ばれるもの）で計算します。
数学っぽく式で表せば下記となります。
$\begin{align} \quad\boldsymbol{v} &= \cfrac{1}{N}\sum_{\boldsymbol{x}\in X} \boldsymbol{x}\\ \quad where\\ \quad n &= \mbox{クラスタに含まれる}\boldsymbol{x}\mbox{の数}\\ \quad X &= \mbox{クラスタに含まれる}\boldsymbol{x}\mbox{の集合} \end{align}$

例えば、クラスタ1の場合は、クラスタ1に含まれる $\boldsymbol{x_1}$ , $\boldsymbol{x_2}$ からクラスタ中心 $\boldsymbol{v_1}$ を計算します。
$\quad \begin{align} \boldsymbol{v_1} = \cfrac{1}{2}(\boldsymbol{x_1}+\boldsymbol{x_2}) \end{align}$

3. 各データと各クラスタ中心の距離を算出し、最も距離が近いクラスタ中心と同じクラスタに再度割り当てる。
各データ $\boldsymbol{x}$ と各クラスタ中心 $\boldsymbol{v}$ の距離を算出し、最も距離 $d$ が近いクラスタ中心と同じクラスタに再度割り当てます。

例えば、下図のように $\boldsymbol{x_6}$ について考えます。
f:id:lm4183:20200822223319p:plain
データ $\boldsymbol{x_6}$ と各クラスタ中心 $\boldsymbol{v_1}$ , $\boldsymbol{v_2}$ との距離をそれぞれ $d_{61}$ , $d_{62}$ とした時、図のように $d_{61} < d_{62}$ だったとします。（ $\boldsymbol{x_6}$ が $\boldsymbol{v_1}$ の方が近いとします。）
この場合、データ $\boldsymbol{x_6}$ をクラスタ1に割り当て直します。

全データに対して行い、本例の場合、下図のよう $\boldsymbol{x_1}$ , $\boldsymbol{x_2}$ , $\boldsymbol{x_6}$ はクラスタ1、 $\boldsymbol{x_3}$ , $\boldsymbol{x_4}$ , $\boldsymbol{x_5}$ はクラスタ2と割り当て直されます。
f:id:lm4183:20200822223328p:plain

4. 2と3を繰り返し実施し、割り当てが変化しなくなった時に終了する。
2と3を繰り返すと、いずれ収束して、割り当てが変化しなくなります。（アルゴリズムの作り方によっては例外あるかもですが。。）
割り当てが変化しなくなった時に終了となります。

本例だと、「2. 各クラスタに対して、データの中心（クラスタ中心）を算出する。」を再度行うと下図のようになり、これ以上クラスタ中心が変化しなくなります。
f:id:lm4183:20200822225535p:plain

以上、無事にクラスタリングされました。

ただ、よく言われるデメリットとして、クラスタの初期割り当てによっては、私達が思うクラスタの割り当てと実行結果に差が出ることがあります。
本例で言えば、 $\boldsymbol{x_1}$ だけがクラスタ1に割り当てられて、 $\boldsymbol{x_2}$ ～ $\boldsymbol{x_6}$ がクラスタ2に割り当てられることがあります。
これは、私達が思うクラスタの割り当てと異なりますよね。