主成分分析法

降维(Dimensionality Reduction)

降维是一种无监督学习问题，把一组维度很大的数据通过一种方法它的为度降低。也就是让这些数据抛弃一些我们不需要的特征，减小数据的规模，这样因而使用较少的计算机内存或磁盘空间，也让可以加快我们的学习算法。还有一点，如果把数据降维至二维或者三维，有助于我们对数据的可视化，便于直观的解决问题。降维也可以解决模型过拟合的问题。

主成分分析法(Principal Component Analysis)

主成分分析法(PCA)是一种常见的降维方法，这个方法的思想就是寻找一组坐标系，让样本空间中所有的样本点投影到这个坐标系，经过降维后的样本点损失的数据最小化。

看下图：

上图是一组二维数据集，我们要做的就是想找一个坐标轴$u$，可以让所有样本点都投影到坐标轴上，从而实现降维。但要想找到最好的坐标轴，就得想办法让数据集的数据损失最小化$\min_u{\sum lost_i}$，也就是最小重构代价。

我们的目标是：找出一个方向，使数据的损失最小。因为所有的样本点是已知的、确定的，也就是$||x^{(i)}||$是确定的，$lost=||x^{(i)}||\times\cos\theta$我们就可以将目标转化成令$x$与$u$的夹角$\theta$最小。又因为

$$x^Tu=x\cdot u=||x||\times||u||\times\cos\theta$$

我们不用在意$||u||$，可以令其为$1$。所以我们可以将问题转变成：找到数据投影方差最大的方向作为坐标轴$u$（主成分）的方向，即

$$\max_u\frac{1}{m}\sum_{i=1}^{m}||{x^{(i)}}^Tu||^2$$

上述的最小重构代价和最大投影方差是PCA降维的两个思路，但是殊途同归，最后两个模型实际上是等价的，这里先说最大投影方差：

协方差矩阵

在说最大投影方差之前，先来了解一下协方差矩阵：

假设大样本数据$(X,Y)$，想要知道特征的协同相关性，就可以用$cov(X,Y)$来表示：

$$cov(X,Y)=E(X-\overline X)(Y-\overline Y)=\sum_{i=1}^m\frac{(x^{(i)}-\overline x)(y^{(i)}-\overline y)}{m-1}$$

当$cov(X,Y)>0$时，$X$与$Y$正相关；当$cov(X,Y)<0$时，$X$与$Y$负相关；当$cov(X,Y)=0$时，$X$与$Y$不相关。

上面是我们之前接触的协方差定义，大都是二维数据，那么现在接触的多维数据$x^{(i)}\in \mathbb R^n$该怎么求协方差呢？什么是协方差矩阵呢？

协方差矩阵描述的不是描述两个大样本之间的相关关系，而是描述的是任意两个特征之间的相关程度。可见协方差矩阵$C\in \mathbb R^{n\times n}$。如果我么想知道样本中的$a$特征与$b$特征的相关程度，可知

$$C_{ab}=cov(x_a,x_b)=\frac{1}{m}\sum_{i=1}^m(x_a^{(i)}-\overline x_a)(x_b^{(i)}-\overline x_b)$$

我们令标准化之后的数据集

$$X=\begin{pmatrix}x^{(1)^T}\\x^{(2)^T}\\\vdots\\x^{(m)^T}\end{pmatrix}=\begin{pmatrix}x^{(1)}_1 & x^{(1)}_2 & \cdots & x^{(1)}_n\\x^{(2)}_1 & x^{(2)}_2 & \cdots & x^{(2)}_n\\\vdots &\vdots & \ddots & \vdots \\x^{(m)}_1 & x^{(m)}_2 & \cdots & x^{(m)}_n\end{pmatrix}_{m\times n}$$

则有：

$$\begin{align}C &= \begin{pmatrix}cov(x_1,x_1) & cov(x_1,x_2) & \cdots & cov(x_1,x_n)\\cov(x_2,x_1) & cov(x_2,x_2) & \cdots & cov(x_1,x_n)\\\vdots &\vdots & \ddots & \vdots \\cov(x_n,x_1) & cov(x_n,x_2) & \cdots & cov(x_n,x_n)\\\end{pmatrix}= X^TX=\frac{1}{m}\sum_{i=1}^{m}({x^{(i)}}{x^{(i)}}^T)\end{align}$$

最大投影方差

最大投影方差指的是在重构数据之后获得的新的数据样本点的方差最大，也就是说样本点要很分散，很好的保留了他们的特征，让这些样本点都是与众不同的宝宝，这样的降维才是最好的(๑•̀ㅂ•́)و✧

首先要做的是标准化数据集$x^{(i)}\in \mathbb R^n$:

$$x^{(i)}:=\frac{x^{(i)}-\overline x}{\sigma}$$

我们先找$u_1$，也就是最投影方差最大的坐标轴：

$$\max_{u_1}\frac{1}{m}\sum_{i=1}^{m}||{x^{(i)}}^Tu_1||^2$$

将式子展开，有

$$\begin{align} \frac{1}{m}\sum_{i=1}^{m}||{x^{(i)}}^Tu_1||^2 &= \frac{1}{m}\sum_{i=1}^{m}({x^{(i)}}^Tu_1)^T({x^{(i)}}^Tu_1)\\ &= \frac{1}{m}\sum_{i=1}^{m}u_1^T{x^{(i)}}{x^{(i)}}^Tu_1\\ &= u^T_1\sum_{i=1}^{m}\frac{1}{m}\bigr({x^{(i)}}{x^{(i)}}^T\bigr)u_1 \end{align}$$

而上式的$\frac{1}{m}\sum_{i=1}^{m}({x^{(i)}}{x^{(i)}}^T)$就是一个协方差矩阵$C$。

那么上式可以写成：

$$\begin{align} \frac{1}{m}\sum_{i=1}^{m}||{x^{(i)}}^Tu_1||^2 &= u^T_1\sum_{i=1}^{m}\frac{1}{m}\bigr({x^{(i)}}{x^{(i)}}^T\bigr)u_1\\ &=u^T_1Cu_1 \end{align}$$

而且在投影时，我们令$||u||=1$，所以我们要遵循约束$u_1^Tu_1=1$。则原问题转化为：

$$\begin{align} \max _{u_1}&\quad u^T_1Cu_1\\ s.t.& \quad u_1^Tu_1-1=0 \end{align}$$

用拉格朗日方程进行求解，则有$L(u_1,\lambda)=u^T_1Cu_1-\lambda(u_1^Tu_1-1)$。

令$\frac{\partial L}{\partial u_1}=0$，则

$$\frac{\partial L}{\partial u_1}=2Cu_1-2\lambda u_1=0$$

有求导公式：

$$\frac{\partial X^TAX}{\partial X} = (A+A^T)X$$

可以观察到：$\lambda$和$u_1$是协方差矩阵$C$的特征值和特征向量！最后的结果等价于

$$\max _{u_1} J=~ u^T_1Cu_1=\lambda$$

那么可以得出结论，$u1$方向就是协方差矩阵$C$最大特征值$\lambda{\max}$对应的特征向量的方向。当然求$u_2,u_3,\cdots,u_q$都是如此循环上面的过程，取前$q$个最大特征值对应的单位特征向量即为降维对应的坐标轴。

最小重构代价

最小重构代价是指数据的丢失最小化$\min_u{\sum lost_i}$，那么这个丢失可以用样本的投影向量与样本向量之差来表示，那么原式可以化成：

$$\min_u~ \sum_{i=1}^m||x^{(i)}-\hat x^{(i)}||^2$$

假设我们对一个二维数据$x(x_1,x_2)$进行重构，如下图：

令$||u||=1$，我们可以知道$x^Tu_1,x^Tu_2$是$x$在$u_1,u_2$坐标轴上的投影，那么可以说$x$用一组新的基向量表示为$x=(x^Tu_1) u_1+(x^Tu_2)u_2$。当我们想将数据降到一维，去掉$u_2$轴时，我们数据的损失为：

$$lost=||x-\hat x||^2=||((x^Tu_1) u_1+(x^Tu_2)u_2)-(x^Tu_1) u_1||$$

上面只是一个简单的例子，我们处理的数据维度会很大，但道理都是一样的。降维后的代价函数为：

$$\begin{align} \min_u~J =& \frac{1}{m}\sum_{i=1}^m||x^{(i)}-\hat x^{(i)}||^2\\ =&\frac{1}{m}\sum_{i=1}^m||\sum_{k=q+1}^n\bigr((x^{(i)^T}) u_k\bigr)u_k||^2\\ =& \frac{1}{m}\sum_{i=1}^m\sum_{k=q+1}^n\bigr((x^{(i)^T}) u_k\bigr)^2\\ =& \sum_{k=q+1}^n\biggr[\frac{1}{m}\sum_{i=1}^m\bigr((x^{(i)^T}) u_k\bigr)^2\biggr]\\ =& \sum_{k=q+1}^nu_k^TCu_k \end{align}$$

则原问题转化为：

$$\begin{align} \min _{u}&~~~\sum_{k=q+1}^nu_k^TCu_k\\ s.t.& \quad u_k^Tu_k-1=0\quad k=q+1,q+2,\dots,n \end{align}$$

根据之前最大投影方差的计算，我们可以知道上式相当于求$\min {u} \sum{k=q+1}^n\lambda_k$，结果是最小的$n-q$个协方差矩阵$C$的特征值。

这两种角度最终求得的结果是一样的，降至$q$维后的主成分坐标轴分别是样本对应的协方差矩阵$C$的最大$q$个特征值对应的单位特征向量。

奇异值分解(Singular Value Decomposition)

奇异值分解是矩阵分解的另一种方式，比起之前学过的特征值分解，奇异值分解更具有一般性。

有$A\in \mathbb R^{n\times n}$，且$A$有$n$个无关的特征向量，则$A$可以被分解为：

$$A=Q\Lambda Q^{-1}$$

上面的是我们之前学过的特征分解，特征分解的要求比较高，必须得是方阵，实际上不是方阵的任意矩阵都可以被分解出对角矩阵，被称为奇异值分解(SVD)。

有$ M\in \mathbb R^{m\times n}$，且$M$有$n$个无关的特征向量，则$M$可以被分解为：

$$M=U\Sigma V^{T}$$

其中$U\in \mathbb R^{m\times m}$是$MM^T$经过单位化的特征矩阵，且$U^T=U^{-1}$；$V\in \mathbb R^{n\times n}$是$M^TM$经过单位化的特征矩阵，且$V^T=V^{-1}$；$\Sigma$是对角矩阵，对角元素$\sigma_i=\sqrt {\lambda_i}$为$M^TM$矩阵特征值的开方。

在上面的两个方法中，如果我们想找到主成分的坐标轴，我们就必须求得样本协方差矩阵$C$，这需要很多的时间才能计算得到的。如果我们用奇异值分解，事情就会好办很多，我们对样本集$ X\in \mathbb R^{m\times n}$进行奇异值分解，则有：

$$X=U\Sigma V^{T}$$

那么$X^TX$的特征向量就是协方差矩阵$C$的特征向量，也就是矩阵$V$，当想数据降至$q$维，那么就选取矩阵$V$的前$q$列作为主成分的方向。

样本降维后的坐标可以表示为：

$$\hat X=XV$$