主成分分析(PCA)の考え方
- 参考にしたもの：機械学習のエッセンスの第05章「機械学習アルゴリズム」
主成分分析(PCA)とは
- 機械学習のうち、教師なし学習の次元圧縮に用いられる手法の一種
- 元データの情報をできるだけ損わずに低次元空間に縮約する
- 人間が認識することが難しい多次元データを視覚化するために、２次元・３次元データに縮約したり
考え方
- 元データを、分散が大きくなるようにベクトル変換する。
- 分散が大きいベクトルを選び、射影する(一次元なら分散が一番大きいもの、二次元なら分散が大きい順に2つ)
- 次数を削るのでどうしても情報量は減るが、できるだけばらつきが大きくなるように変換して射影することで、残る情報量が多くなる。(特徴が見えやすくなる)
- 実際に「 https://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality/ 」にある「winequality-red.csv」や「winequality-white.csv」(11次元データ)を二次元に圧縮してプロットすると↓のようになる。
解き方
- 元データ$x$の数を$n$, 1つずつのデータの次数を$d$として、$\mathbf{x_i} = (x_1, x_2, \cdots, x_d) ; (for ; i = 1, 2, \cdots, n)$と表す。(通常は$n>d$)
- 変換するベクトルを$\mathbf{w}^T = (w_1, \cdots, w_d)$とする。
||\mathbf{w_i}||=1 \; \Leftrightarrow \; \mathbf{w_i}^T \mathbf{w_i} = 1
\\
\mathbf{w_i}^T \mathbf{w_j} =0 \; (for \; i \neq j)
一次元への圧縮
まず$\mathbf{w_1}$による一次元への変換・圧縮・射影を考える。
$\mathbf{x_i} ; (for ; i = 1, 2, \cdots, n)$の平均$\bar{\mathbf{x}}$は
\bar{\mathbf{x}} = \frac{1}{n} \sum_{i=1}^{n} \mathbf{x_i}
また、$\mathbf{w_1}^T \mathbf{x_i} ; (for ; i = 1, 2, \cdots, n)$の平均は
\frac{1}{n} \sum_{i=1}^{n} \mathbf{w_1}^T \mathbf{x_i} = \mathbf{w_1}^T \frac{1}{n} \sum_{i=1}^{n} \mathbf{x_i} = \mathbf{w_1}^T \bar{\mathbf{x}}
よって$\mathbf{w_1}^T \mathbf{x_i} ; (for ; i = 1, 2, \cdots, n)$の分散は
\begin{align}
&\frac{1}{n} \sum_{i=1}^{n} ||\mathbf{w_1}^T \mathbf{x_i} - \mathbf{w_1}^T \bar{\mathbf{x}}||^2 \\
= &\frac{1}{n} \sum_{i=1}^{n} ||\mathbf{w_1}^T (\mathbf{x_i} - \bar{\mathbf{x}})||^2 \\
= &\frac{1}{n} \sum_{i=1}^{n} \bigl( \mathbf{w_1}^T (\mathbf{x_i} - \bar{\mathbf{x}}) \bigr) \bigl( (\mathbf{x_i} - \bar{\mathbf{x}})^T \mathbf{w_1} \bigr) \\
= &\mathbf{w_1}^T \bigl( \frac{1}{n} \sum_{i=1}^{n} (\mathbf{x_i} - \bar{\mathbf{x}}) (\mathbf{x_i} - \bar{\mathbf{x}})^T \bigr) \mathbf{w_1} \\
= &\mathbf{w_1}^T \mathbf{S} \mathbf{w_1} \\
\end{align}
$\frac{1}{n} \sum_{i=1}^{n} (\mathbf{x_i} - \bar{\mathbf{x}}) (\mathbf{x_i} - \bar{\mathbf{x}})^T = \mathbf{S}$はd×d行列
よって解くべき最適化問題は↓になる（後の計算のために1/2されている）
\begin{align}
Maximize \; &\frac{1}{2} \mathbf{w_1}^T \mathbf{S} \mathbf{w_1} \\
Subject \; to \; &\mathbf{w_1}^T \mathbf{w_1} = 1 \\
\Leftrightarrow \; &\mathbf{w_1}^T \mathbf{w_1} - 1 = 0 \\
\end{align}
コレをラグランジュの未定乗数法(Wikipedia)で解くと、ラグランジュ関数は
L(\mathbf{w_1}, \lambda_1) = \frac{1}{2} \mathbf{w_1}^T \mathbf{S} \mathbf{w_1} - \lambda_1 (\mathbf{w_1}^T \mathbf{w_1} - 1) \; \cdots (i)
となり
\frac{\partial L}{\partial \mathbf{w_1}} = \mathbf{S} \mathbf{w_1} - \lambda_1 \mathbf{w_1} = 0 \\
\mathbf{S} \mathbf{w_1} = \lambda_1 \mathbf{w_1} \\
より、$\lambda_1$は$\mathbf{S}$の固有値となる。
- このとき$\mathbf{w_1}^T \mathbf{S} \mathbf{w_1} = \mathbf{w_1}^T \lambda_1 \mathbf{w_1} = \lambda_1$なので、$\frac{1}{2} \mathbf{w_1}^T \mathbf{S} \mathbf{w_1}$を最大とするためには$\lambda_1$を最大とすればよい。
- $(i)$を満たす$\mathbf{w_1}$は複数あるので、そのうち$\lambda_1$が最大のものを見つける。
- 二次元に圧縮する場合は$\lambda$が大きい順に2つ、三次元に圧縮する場合は3つ見つける
PCAのアルゴリズム(多次元への射影)
ここで、
\mathbf{W} = (\mathbf{w_1}, \mathbf{w_2}, \cdots, \mathbf{w_d})
とおくと、
\mathbf{S} \mathbf{w_1} = \lambda_1 \mathbf{w_1} \\
\mathbf{S} \mathbf{w_2} = \lambda_2 \mathbf{w_2} \\
\vdots \\
\mathbf{S} \mathbf{w_d} = \lambda_d \mathbf{w_d} \\
となり、まとめると
\mathbf{S} \mathbf{W} = \mathbf{W} \mathbf{\Lambda} \\
となる。ここで$\mathbf{\Lambda}$は
\mathbf{\Lambda} = \begin{pmatrix}
\lambda_1 & & & \\
& \lambda_2 & & \\
& & \ddots & \\
& & & \lambda_d
\end{pmatrix}\\
最初の$\mathbf{w}$のおきかた$||\mathbf{w_i}||=1 , ; \mathbf{w_i}^T \mathbf{w_j} =0 ; (for ; i \neq j)$より$\mathbf{W}$は直行行列($\mathbf{W}^T = \mathbf{W}^{-1}$)なので
\mathbf{S} = \mathbf{W} \mathbf{\Lambda} \mathbf{W}^{-1} = \mathbf{W} \mathbf{\Lambda} \mathbf{W}^T \; \cdots (ii) \\
この形になると、$\mathbf{S}$がわかればSciPyの中の特異値分解(Singular Value Decomposition, SVD)を用いて$\mathbf{W}, ; \mathbf{\Lambda}$を求めることができる。
ここで、$\mathbf{S}$は
\mathbf{Y} = \begin{pmatrix}
(\mathbf{x_1} - \bar{\mathbf{x}})^T \\
(\mathbf{x_2} - \bar{\mathbf{x}})^T \\
\vdots \\
(\mathbf{x_n} - \bar{\mathbf{x}})^T \\
\end{pmatrix}
とおくと、以下のように計算できる。
\mathbf{S} = \frac{1}{n} \sum_{i=1}^{n} (\mathbf{x_i} - \bar{\mathbf{x}}) (\mathbf{x_i} - \bar{\mathbf{x}})^T = \frac{1}{n} \mathbf{Y}^T \mathbf{Y}
あとは、以下の流れでプロットできる。
- （二次元でプロットする場合）$\lambda_i$が大きい順に$\mathbf{w_i}$を2つ取り出す。($\mathbf{w_i}, \mathbf{w_2}$)
- $(\mathbf{w_1} \mathbf{w_2})^T \mathbf{x}$を計算し、プロットする。