1. 雑要約
今回はざっくり Reduced K-meansクラスタリング解説(実装編)で説明しなかったモデル式や更新式について説明しています．
2. 記号等
- X: データ行列($n\times p)，x_i\ (p\times 1$)はその行ベクトルで個体に対応します．
- G: メンバーシップ行列($n\times g$)．gはグループの数で，Gは以下のように個体がどのグループに所属するかを表す行列．
\begin{eqnarray}
g_{ik}=\left\{
\begin{array}
1 1 &if\ x_i \in G_k\\
0 & otherwise
\end{array}
\right.
\end{eqnarray}
- C: セントロイド行列($g\times m$)．グループの中心の座標の行列．mは次元縮約した後の次元数を表しています．
- A: 負荷行列($p\times m)．A^TA=I_m$となるような列直交行列．
- E: モデルとデータ行列Xの誤差を含む行列($n\times p$)
- $||B||_F ^2:\ ||B||_F^2=trB^TB=trBB^T$で定義されるFrobeniusノルム
3. 損失関数とアルゴリズム
3.1 目的関数
Reduced K-means(以下RKMと書きます)のモデル式は，$$X = GCA^T + E$$であり，交互最小二乗法によってパラメータを計算するとすると，損失関数(loss function)は
f(G,C,A)=||E||_F^2=||X-GCA^T||_F^2
となります．アルゴリズムの説明のために，損失関数を展開します．
\begin{eqnarray}
f(G,C,A) &=& tr(X-GCA^T)^T(X-GCA^T)\\
&=& trX^TX-2trX^TGCA^T+trAC^TG^TGCA^T\\
&=& trX^TX-2trX^TGCA^T+trC^TG^TGC\\
&&(\because trVWZ=trWZV,A^TA=I_m)\\
\end{eqnarray}
ここでパラメータに関係しているのは，最右辺の第2項と第3項であり，損失関数を減少させるためには，これらを最適化すれば良いことがわかります．まずはGとCを固定してAを更新することを考えます．損失関数のAに関する項は$-2trX^TGCA^T$のみであり，$trX^TGCA^T$を最大化することと損失関数の最小化が等価であるということがわかります．よって損失関数の最小化が$trX^TGCA^T=trAC^TG^TX$を最大化するような列直交行列Aを計算する問題に置き換えられます(このような問題を直交プロクラステス問題といいます．)．そのようなAは$C^TG^TX$の特異値分解を$Q\Sigma P^T$とすると，ten Berge(1983)の定理から $$\widehat{A}=PQ^T\tag{1}$$で求まります．このAとCを固定してメンバーシップ行列Gを計算します．これは，通常のK-meansクラスタリングと同様に，$A^Tx_i(i=1,\cdots,n)$(負荷行列Aでデータ行列Xの各点を低次元空間に布置したもの)と各クラスター中心の距離を計算して，最も近いクラスターに割り当てます．
\begin{eqnarray}
g_{ik}=\left\{
\begin{array}
1 1&if\ ||A^Tx_i-c_k||^2\le||A^Tx_i-c_{k'}||^2\\
0 &otherwise
\end{array}
\right.\tag{2}
\end{eqnarray}
以上のように更新したAとGを固定して，損失関数を最小にするセントロイド行列Cを計算します．そのようなCは損失関数をCで偏微分したものを$\bf{O}$と置くことによって，
\begin{eqnarray}
\frac{\partial}{\partial C}f(G,C,A)&=&-2G^TXA+2G^TGC=\bf{O}\\
&\Leftrightarrow&G^TGC=G^TXA\\
&\Leftrightarrow&\widehat{C} = (G^TG)^{-1}G^TXA\tag{3}
\end{eqnarray}
と更新すれば良いことがわかります．以上のように求めたG,C,Aの更新式はそれぞれお互いに影響し合っているので，１つ更新するたびに他のパラメータも変化します．従って目的関数が収束する($\fallingdotseq$変化量があらかじめ決めた基準より小さくなる)まで反復計算する必要があります．
3.2 アルゴリズム
以上をまとめると，RKMのアルゴリズムは以下のようになります．
step0. クラスター数gと低次元空間の次元mを設定
step1. セントロイド行列C，負荷行列Aのメンバーシップ行列Gの初期化
step2. (1)のようにAを更新
step3. (2)のようにGを更新
step4. (3)のようにCを更新
step5. 目的関数の値が収束していなければstep2へ戻る．収束していれば終了．
これをpythonで実装したものはざっくり Reduced K-meansクラスタリング解説(実装編)に載せてあります．