教師なし学習の問題。クラスタリング。
クラスタの個数を事前に指定するタイプと、自分でクラスタ数を設定できるタイプがあります。
今回、前者のk-means法をアイデアを聞いたので、まとめなおしてみようと思います。
k-means法
\(C_1,\cdots,C_K\)がクラスタ。各々のクラスタにおける中心は\(\bar{x_k}\)(centroid)。
各々のクラスタにおけるcentroidとの距離の2乗を全部足して、
それが最小になるようなクラスタ\(C_1,\cdots,C_K\)を求めるという問題。
\begin{eqnarray}
\newcommand{\argmin}[1]{\underset{#1}{\operatorname{arg}\,\operatorname{min}}\;}
\hat{c_1},\cdots,\hat{c_K} = \argmin {c_1,\cdots,c_K} \sum_{k=1}^K \sum_{i \in C_k} || x_i – \bar{x_k}||^2
\end{eqnarray}
距離の2乗なので異常値があると異常値に引っ張られて、クラスタが大きく変わってしまう。
centroid(標本平均)も異常値に引っ張られる。外れ値を除去しないといけない。
距離の2乗を計算するので、ベクトル\(v_i\)の各次元のスケールが揃っていないと、
計算の過程で単位が大きい要素に引っ張られてしまう。
単位の大きさは重要度とは関係ないのに、単位が大きいことが距離に影響を与えることは
避けないといけない。その対応として単位を揃える（正規化）する。
\begin{eqnarray}
|x_i-\bar{x}|^2 =
\begin{pmatrix}
x_{i1} – \bar{x_1} \\
x_{i2} – \bar{x_2} \\
\vdots \\
x_{in} – \bar{x_n} \\
\end{pmatrix} = \sum_{i=1}^{n} \sqrt{x_{i1}-\bar{x_1}}^2
\end{eqnarray}
そのままだとNP困難->近似解法
データポイントの個数、centroidの位置がそれぞれ自由だと、
定義通りに実装しようとしても\(\mathcal{O}(n^3)\)となって使えない。
\begin{eqnarray}
\newcommand{\argmin}[1]{\underset{#1}{\operatorname{arg}\,\operatorname{min}}\;}
\hat{c_1},\cdots,\hat{c_K} = \argmin {c_1,\cdots,c_K} \sum_{k=1}^K \sum_{i \in C_k} || x_i – \bar{x_k}||^2
\end{eqnarray}
以下のようにランダムなクラスタを初期値として設定し、
より良いクラスタに更新することで計算量を下げる。
データ数\(n\)、クラスタ数\(k\)だと\(\mathcal{O}(nk)\)。
- 各データポイントにランダムなクラスタを割り当てる
- 以下の処理を繰り返す
- 各データポイントに割り当てられたクラスタのクラスタ中心を計算する
- 各データポイントについてクラスタ中心との距離を計算する
- 各データポイントについて距離が最小のクラスタを設定する
k-meansで実際にクラスタリングするコードを書いてみようと思いましたが、
そろそろ適当なデータを見つけてくるのではなく、シミュレーション用のデータを作るところも
やってみようと思います。次回、pythonでコード書きます。