クラスタリング 機械学習

k-means法と近似解法 考え方

投稿日:


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

  1. 各データポイントにランダムなクラスタを割り当てる
  2. 以下の処理を繰り返す
    1. 各データポイントに割り当てられたクラスタのクラスタ中心を計算する
    2. 各データポイントについてクラスタ中心との距離を計算する
    3. 各データポイントについて距離が最小のクラスタを設定する

k-meansで実際にクラスタリングするコードを書いてみようと思いましたが、
そろそろ適当なデータを見つけてくるのではなく、シミュレーション用のデータを作るところも
やってみようと思います。次回、pythonでコード書きます。

-クラスタリング, 機械学習
-

Copyright© ikuty.com , 2019 AllRights Reserved Powered by AFFINGER4.