k-means

データを教師ラベルなしでクラスタ分けする手法をクラスタリングという。似ているかどうかは距離や類似度によって計算する。

• ユークリッド距離
  • $d(\mathbf{x},\mathbf{y})=(\mathbf{x}-\mathbf{y}{)}^T(\mathbf{x}-\mathbf{y})$
• コサイン類似度
  • $s(\mathbf{x},\mathbf{y})=\frac{{\mathbf{x}}^T\mathbf{y}}{\sqrt{({\mathbf{x}}^T\mathbf{x})({\mathbf{y}}^T\mathbf{y})}}$

ユークリッド距離におけるクラスタリングをk-meansという。 また、クラスタの代表点をプロトタイプという。

• データ: $\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_N\},{\mathbf{x}}_i\in {\mathbb{R}}^D$
• プロトタイプ: $\{{\mathbf{\mu }}_1,\dots ,{\mathbf{\mu }}_K\},{\mathbf{\mu }}_j\in {\mathbb{R}}^D$

割当変数 $r_{ik}$ は次のように定義される。

$$r_{ik}=\{\begin{array}{rl}& 1\text{if}{\mathbf{x}}_i\text{is assigned to}{\mathbf{\mu }}_k\\ & 0\text{o.w.}\end{array}$$

プロトタイプ ${\mu }_k$ に割り当てられているデータがどのくらい散らばっているかを最小化する = 歪み尺度最小化問題。

$$J({\mathbf{\mu }}_1,\dots ,{\mathbf{\mu }}_{\mathbf{K}},r_{11},\dots ,r_{nk})=\sum _{k=1}^K\sum _{n=1}^N{r}_{nk}||{\mathbf{x}}_n-{\mathbf{\mu }}_k|{|}_2^2$$

これを $J({\mathbf{\mu }}_k,r_{nk})$ と書くことにすると、k-meansは以下の最適化問題を解くのと同等である。

$$\underset{{\mathbf{\mu }}_k,r_{nk}}{\mathrm{argmin}}J({\mu }_k,r_{nk})$$