「主成分分析(PCA)」について

主成分分析(PCA)の考え方

* 参考にしたもの：[機械学習のエッセンス](https://www.sbcr.jp/product/4797393965/)の第05章「機械学習アルゴリズム」

# 主成分分析(PCA)とは

* 機械学習のうち、教師なし学習の次元圧縮に用いられる手法の一種
* **元データの情報をできるだけ損わずに低次元空間に縮約する**
* 人間が認識することが難しい多次元データを視覚化するために、２次元・３次元データに縮約したり

# 考え方

* 元データを、分散が大きくなるようにベクトル変換する。
* 分散が大きいベクトルを選び、射影する(一次元なら分散が一番大きいもの、二次元なら分散が大きい順に2つ)
* **次数を削るのでどうしても情報量は減るが、できるだけばらつきが大きくなるように変換して射影することで、残る情報量が多くなる。(特徴が見えやすくなる)**
* 実際に「 https://archive.ics.uci.edu/ml/machine-learning-databases/wine-quality/ 」にある「winequality-red.csv」や「winequality-white.csv」(11次元データ)を二次元に圧縮してプロットすると↓のようになる。

![PCA_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/0c83dd04-61e5-530d-f6b8-a8069672b402.png)
![PCA_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/563901/f0c9c781-a984-9acc-44af-f58a96041ea8.png)


# 解き方

- 元データ$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)$とする。

```math
||\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}}$は

```math
\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)$の平均は

```math
\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)$の分散は

```math
\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されている）

```math
\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)](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)で解くと、ラグランジュ関数は

```math
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)
```

となり

```math
\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のアルゴリズム(多次元への射影)

ここで、

```math
\mathbf{W} = (\mathbf{w_1}, \mathbf{w_2}, \cdots, \mathbf{w_d})
```

とおくと、

```math
\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} \\
```

となり、まとめると

```math
\mathbf{S} \mathbf{W} = \mathbf{W} \mathbf{\Lambda} \\
```

となる。ここで$\mathbf{\Lambda}$は

```math
\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}$)なので

```math
\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}$は

```math
\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}
```

とおくと、以下のように計算できる。

```math
\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}$を計算し、プロットする。

# 図作ったときのコード置き場

- https://github.com/kzy611/qiita/blob/master/PCA.ipynb

# 参考リンク

- [主成分分析(Wikipedia)](https://ja.wikipedia.org/wiki/%E4%B8%BB%E6%88%90%E5%88%86%E5%88%86%E6%9E%90)
- [主成分分析の考え方](https://logics-of-blue.com/principal-components-analysis/)
- [主成分分析 - 統計科学研究所](https://statistics.co.jp/reference/software_R/statR_9_principal.pdf)
- [ラグランジュの未定乗数法(Wikipedia)](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%B0%E3%83%A9%E3%83%B3%E3%82%B8%E3%83%A5%E3%81%AE%E6%9C%AA%E5%AE%9A%E4%B9%97%E6%95%B0%E6%B3%95)
- [特異値分解(Wikipedia)](https://ja.wikipedia.org/wiki/%E7%89%B9%E7%95%B0%E5%80%A4%E5%88%86%E8%A7%A3)
- [Pythonで特異値分解(SVD)を理解する](https://ohke.hateblo.jp/entry/2017/12/14/230500)