PCA

样本矩阵

设一个随机变量有$p$个维度，那么第$i$个样本$a_i$可以用$p$维向量来描述：

$${\mathit{r}}_n=[a_1,a_2,\cdots ,a_p]$$

样本集合有$n$个样本，每个维度的样本构成一个列向量$c$：

$${\mathit{c}}_p=\left[\begin{array}{c}{a}_1\\ a_2\\ ⋮\\ a_n\end{array}\right]$$

那么就形成了$n\times p$的样本矩阵：

$$A=\left[\begin{array}{c}{\mathit{r}}_1\\ {\mathit{r}}_2\\ ⋮\\ {\mathit{r}}_n\end{array}\right]=\left[\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1p}\\ a_{21}& a_{22}& \dots & a_{2p}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \dots & a_{np}\end{array}\right]=[{\mathit{c}}_1,{\mathit{c}}_2,\cdots ,{\mathit{c}}_p]$$

对每一列求均值，第$p$列的均值${\overline{a}}_p$为：

$${\overline{a}}_p=\sum _{i=1}^n{a}_{i,p}$$

进行样本中心化，每一列的值减去该列的平均值，得到新矩阵：

$$A=[{\mathit{c}}_1-{\overline{a}}_1,{\mathit{c}}_2-{\overline{a}}_2,\cdots ,{\mathit{c}}_p-{\overline{a}}_p]$$

协方差矩阵

协方差计算公式为：

$$\text{Cov}(X,Y)=\frac{1}{n-1}\sum _{i=1}^n(X_i-\overline{X})(Y_i-\overline{Y})$$

对于$p$维变量的协方差矩阵是分别计算每个维度之间的协方差：

$$C=\left[\begin{array}{cccc}\text{Cov}({\mathit{c}}_1,{\mathit{c}}_1)& \text{Cov}({\mathit{c}}_1,{\mathit{c}}_2)& \cdots & \text{Cov}({\mathit{c}}_1,{\mathit{c}}_p)\\ \text{Cov}({\mathit{c}}_2,{\mathit{c}}_1)& \text{Cov}({\mathit{c}}_2,{\mathit{c}}_2)& \cdots & \text{Cov}({\mathit{c}}_2,{\mathit{c}}_p)\\ ⋮& ⋮& \ddots & ⋮\\ \text{Cov}({\mathit{c}}_p,{\mathit{c}}_1)& \text{Cov}({\mathit{c}}_p,{\mathit{c}}_2)& \cdots & \text{Cov}({\mathit{c}}_p,{\mathit{c}}_p)\end{array}\right]$$

协方差矩阵的每个值$C_{i,j}$表示第$i$和第$j$个维度的协方差，而对角线的值表示方差。

把协方差公式展开后，提出公共的$\frac{1}{n-1}$项，得到：

$$C=\frac{1}{n-1}\left[\begin{array}{cccc}\sum _{i=1}^n{a}_{i,1}\cdot a_{i,1}& \sum _{i=1}^n{a}_{i,1}\cdot a_{i,2}& \cdots & \sum _{i=1}^n{a}_{i,1}\cdot a_{i,p}\\ \sum _{i=1}^n{a}_{i,2}\cdot a_{i,1}& \sum _{i=1}^n{a}_{i,2}\cdot a_{i,2}& \cdots & \sum _{i=1}^n{a}_{i,2}\cdot a_{i,p}\\ ⋮& ⋮& \ddots & ⋮\\ \sum _{i=1}^n{a}_{i,p}\cdot a_{i,1}& \sum _{i=1}^n{a}_{i,p}\cdot a_{i,2}& \cdots & \sum _{i=1}^n{a}_{i,p}\cdot a_{i,p}\end{array}\right]$$

上述矩阵中的每个值：

$$\begin{array}{rl}\sum _{i=1}^n{a}_{i,p}\cdot a_{i,p}& =a_{1,p}\cdot a_{1,p}+a_{2,p}\cdot a_{2,p}+\cdots +a_{n,p}\cdot a_{n,p}\\ & =\left[\begin{array}{cccc}{a}_{1,p}& a_{2,p}& \cdots & a_{n,p}\end{array}\right]\times \left[\begin{array}{c}{a}_{1,p}\\ a_{2,p}\\ ⋮\\ a_{n,p}\end{array}\right]\\ & ={\mathit{c}}_p^T\cdot {\mathit{c}}_p\end{array}$$

整个矩阵可以最终化简得到：

$$\begin{array}{rl}C& =\left[\begin{array}{cccc}{\mathit{c}}_1^T\cdot {\mathit{c}}_1& {\mathit{c}}_1^T\cdot {\mathit{c}}_2& \cdots & {\mathit{c}}_1^T\cdot {\mathit{c}}_p\\ {\mathit{c}}_2^T\cdot {\mathit{c}}_1& {\mathit{c}}_2^T\cdot {\mathit{c}}_2& \cdots & {\mathit{c}}_2^T\cdot {\mathit{c}}_p\\ ⋮& ⋮& \ddots & ⋮\\ {\mathit{c}}_p^T\cdot {\mathit{c}}_1& {\mathit{c}}_p^T\cdot {\mathit{c}}_2& \cdots & {\mathit{c}}_p^T\cdot {\mathit{c}}_p\end{array}\right]\\ & =\left[\begin{array}{c}{\mathit{c}}_1\\ {\mathit{c}}_2\\ ⋮\\ {\mathit{c}}_p\end{array}\right]\times \left[\begin{array}{cccc}{\mathit{c}}_1& {\mathit{c}}_2& \cdots & {\mathit{c}}_p\end{array}\right]\\ & =\frac{1}{n-1}{A}^{T}A\end{array}$$

主成分1

求第一主成分PC1的问题可转化为计算每个样本向量在$\overrightarrow{v}$上投影点的方差最大问题：

$$max{s}^2=\frac{1}{n-1}\sum _{i=1}^n{S}_i^2$$

式子中的$S^2$是每个样本在$\overrightarrow{v}$向量上的投影值：

$$S^2=(\overrightarrow{a}\cdot \overrightarrow{v}{)}^2$$

$\overrightarrow{a}\cdot \overrightarrow{v}$得到一个标量，而行向量乘以列向量也得到标量（一维矩阵），$\overrightarrow{a}\cdot \overrightarrow{v}={\overrightarrow{v}}^T{\overrightarrow{a}}_i={\overrightarrow{a}}_i^T\overrightarrow{v}$，那么可以代换得到：

$$\sum _{i=1}^n{S}_i^2=\sum _{i=1}^n({\overrightarrow{a}}_i\cdot \overrightarrow{v}{)}^2=\sum _{i=1}^n({\overrightarrow{v}}^T{\overrightarrow{a}}_i)({\overrightarrow{a}}_i^T\overrightarrow{v})$$

这时公共项可以提出求和式：

$$\sum _{i=1}^n({\overrightarrow{v}}^T{\overrightarrow{a}}_i)({\overrightarrow{a}}_i^T\overrightarrow{v})={\overrightarrow{v}}^T(\sum _{i=1}^n{\overrightarrow{a}}_i{\overrightarrow{a}}_i^T)\overrightarrow{v}$$$$\sum _{i=1}^n{\overrightarrow{a}}_i{\overrightarrow{a}}_i^T=A^{T}A$$

用$A{A}^T$代换1求和式：

$${\overrightarrow{v}}^T(\sum _{i=1}^n{\overrightarrow{a}}_i{\overrightarrow{a}}_i^T)\overrightarrow{v}={\overrightarrow{v}}^T(A^{T}A)\overrightarrow{v}$$

根据上文的推导，最终样本方差$s^2$就转化为下式：

$$s^2=\frac{1}{n-1}\sum _{i=1}^n{S}_i^2=\frac{1}{n-1}{\overrightarrow{v}}^T(A^{T}A)\overrightarrow{v}={\overrightarrow{v}}^{T}C\overrightarrow{v}$$

求极大值问题

最终将问题转变为已知条件下的最大值问题，可以利用拉格朗日乘数法求解：

$$\begin{array}{rl}max& s^2={\overrightarrow{v}}^{T}C\overrightarrow{v}\\ s.t.& \overrightarrow{v}{\overrightarrow{v}}^T=1\end{array}$$

构造拉格朗日函数：

$$F(\overrightarrow{v})=\overrightarrow{v}\cdot C\cdot {\overrightarrow{v}}^T-\lambda (1-\overrightarrow{v}\cdot {\overrightarrow{v}}^T)$$

对函数求偏导：

$$\frac{\partial F}{\partial \overrightarrow{v}}=2C\overrightarrow{v^T}-2\lambda {\overrightarrow{v}}^T=0$$

最后就得到了：

$$C{\overrightarrow{v}}^T=\lambda {\overrightarrow{v}}^T$$

这说明，${\overrightarrow{v}}^T$是协方差矩阵$C$的特征向量，$\lambda$是对应的特征值，把上式带入目标函数，得到：

$${\overrightarrow{v}}^{T}C\overrightarrow{v}={\overrightarrow{v}}^T(\lambda \overrightarrow{v})=\lambda ({\overrightarrow{v}}^T\overrightarrow{v})=\lambda$$

最大化目标函数就等价于最大化特征值$\lambda$，求每个主成分就相当于对协方差矩阵$C$做特征值分解，选前$k$个特征值。