[mathjax]
教師なし学習の問題。クラスタリング。
クラスタの個数を事前に指定するタイプと、自分でクラスタ数を設定できるタイプがあります。
今回、前者の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でコード書きます。