主成分分析 PCA

算法概述

相关数学概念：

• 从矩阵空间角度分析PCA方法：

  • 对于原始样本来说，其基向量为d个形如(1,0,0,…,0)，(0,1,0,…,0)，(0,0,0,…,1)的单位正交向量，这些向量张成d维样本空间，样本点的坐标代表着d个基向量的线性组合：

  $$x_i=(x_{i1},x_{i2},...,x_{i,d}{)}^T=x_{i1}(1,0,0,...,0{)}^T+...+x_{id}(0,0,0,...,1{)}^T$$

  • PCA方法的目的是找到原始样本空间中的m个正交向量p1,p2,…pm，以这些向量张成一个原空间的一个子空间，降维的方法就是将原空间中的样本点映射到子空间中，具体映射方法如下：
    $$\begin{gathered} W_{d\ast m}=[p_1,p_2,...,p_m] \\ X=[x_1,x_2,...x_n]=\left[\begin{array}{cccc}{x}_{11}& x_{21}& ...& x_{n1}\\ x_{12}& x_{22}& ...& x_{n2}\\ ...& ...& ...& ...\\ x_{1d}& x_{2d}& ...& x_{nd}\end{array}\right] \end{gathered}$$
    $$\begin{gathered} Y=[y_1,y_2,...,y_n]=W^{T}X=[p_1^T,p_2^T,...,p_m^T{]}^T[x_1,x_2,...,x_n] \\ =\left[\begin{array}{cccc}{p}_1^T{x}_1& p_1^T{x}_2& ...& p_1^T{x}_n\\ p_2^T{x}_1& p_2^T{x}_2& ...& p_2^T{x}_n\\ ...& ...& ...& ...\\ p_m^T{x}_1& p_m^T{x}_2& ...& p_m^T{x}_n\end{array}\right] \end{gathered}$$
    得到目标矩阵Y，是投影到子空间后在新基上的n个新点坐标集合，每个yi是一个m维向量，

  • 低维样本向量$$y_i$$中的m个值只是新基下的坐标值，为了恢复原始的高维坐标，需要将坐标值与对应基向量相乘并求和

    因此有重构方法：
    $$X’=W{W}^{T}X=[p1,p2,...,p_m{]}_{d\ast m}[y_1,y_2,...,y_n{]}_{m\ast n}$$

• 协方差矩阵

  • 方差：衡量变量值的分散程度
    $$Var(a)=\frac{1}{N}\sum _{i=1}^N(a_i-{\mu }_a{)}^2$$

  • 协方差：协方差可以表示两个变量的相关性，其公式为：
    $$Cov(a,b)=E[(a-{\mu }_a)(b-{\mu }_b)]=\frac{1}{N-1}\sum _{i=1}^N(a_i-{\mu }_a)(b_i-{\mu }_b)$$
    当预先对属性进行规范化（令均值为0，方差为1）后，有：
    $$Cov(a,b)=\frac{1}{n-1}\sum _{i=1}^N{a}_i{b}_i\approx \frac{1}{n}\sum _{i=1}^N{a}_i{b}_i$$

  • 协方差矩阵：

    对含有n个d维数据样本的样本矩阵X
    $$X=\left[\begin{array}{cccc}{x}_{11}& x_{21}& ...& x_{n1}\\ x_{12}& x_{22}& ...& x_{n2}\\ ...& ...& ...& \\ x_{1d}& x_{2d}& ...& x_{n3}\end{array}\right]$$
    其协方差矩阵为
    $$\sum _{d\ast d}=X{X}^T=\left[\begin{array}{cccc}Cov(att{r}_1,att{r}_1)& Cov(att{r}_1,att{r}_2)& ...& Cov(att{r}_1,att{r}_d)\\ Cov(att{r}_2,att{r}_1)& Cov(att{r}_2,att{r}_2)& ...& Cov(att{r}_2,att{r}_d)\\ ...& ...& ...& ...\\ Cov(att{r}_d,att{r}_1)& Cov(att{r}_d,att{r}_2)& ...& Cov(att{r}_d,att{r}_d)\end{array}\right]$$

核心思路：

• 最大化方差（最大可分性）:

  • 直观来讲，PCA方法的目的是在原样本空间中找到m个方向，使原始样本点在这m个方向上的投影尽可能地分散，以此保证原始样本点在投影时不会出现多点投影到一点，进而导致较大信息损失的情况

如上图，投影到方差小的坐标轴方向会出现多对一的映射，原本可分的样本变得不可分，信息损失较大同时，对于目标维度d>1的情况，为了尽可能表示更多的原始信息，希望各个基向量不存在线性相关性，即基向量相互正交

• 目标维度上方差最大化的思路可以用数学语言表示为：
  $$\begin{gathered} \underset{W}{\mathrm{argmax}}=tr(W^{T}X{X}^{T}W) \\ s.t.W^{T}W=I \end{gathered}$$

  就目标函数而言，基向量有正交限制，但如果不对基向量的模长进行限制，目标函数无上限，因此该目标函数需要对W进行单位正交限制

• 最小化重构误差：

  • 此为PCA的另一种理解方式，即要求在通过$Y=f(X)$降维之后，再通过$X^{\prime }=f^{-1}(Y)$恢复到原来的高维度，最小化$X$与$X^{\prime }$的距离（差距）

  • 以线性变换为例，如：对$Y=W^{T}X$，可以通过$X^{\prime }=W{W}^{T}X$进行恢复（重构）

  • 最小化重构误差的数学表达：
    $$\begin{gathered} \underset{W}{\mathrm{argmin}}||X-W{W}^{T}X|{|}_F^2 \\ s.t.W^{T}W=I \end{gathered}$$

• 两种思路的一致性：

  • 对于最小化重构误差思路：
    $$\begin{array}{rl}||X-W{W}^{T}X|{|}_F^2& =tr[(X-W{W}^{T}X)(X-W{W}^{T}X{)}^T]\\ & =tr(X{X}^T-X{X}^{T}W{W}^T-W{W}^{T}X{X}^T+W{W}^{T}X{X}^{T}W{W}^T)\\ & =tr(\sum )-tr(W^{T}X{X}^T{W}^{)}-tr(W^{T}X{X}^{T}W)+tr(W^{T}X{X}^{T}W)\\ & =tr(\sum )-tr(W^{T}X{X}^{T}W)\end{array}$$
    由于协方差阵确定，最小化重构误差即为最大化$$tr(W^{T}X{X}^{T}W)$$，即为最大化方差

算法推导

• 矩阵形式目标函数最优化：

  以最大化方差为优化目标：
  $$\begin{gathered} 目标：\underset{W}{argmax}tr(W^T\sum W)s.t.W^{T}W=I \\ 对有约束最优化问题，由拉格朗日乘子法，得：tr(W^T\sum W)-tr(\Lambda (W^{T}W-I)) \\ 求导并令值为0，得:2\sum W-2W\Lambda =0 \\ 即：\sum W=W\Lambda \end{gathered}$$

  证明一：变换矩阵W中的列向量为协方差矩阵$\sum$的特征向量
  $$\begin{gathered} \underset{d\ast m}{W}=[p_1,p_2,...,p_m] \\ \sum _{d\ast d}=X{X}^T=\left[\begin{array}{cccc}Cov(a_1,a_1)& Cov(a_1,a_2)& ...& Cov(a_1,a_d)\\ Cov(a_2,a_1)& Cov(a_2,a_2)& ...& Cov(a_2,a_d)\\ ...& ...& ...& ...\\ Cov(a_d,a_1)& Cov(a_d,a_2)& ...& Cov(a_d,a_d)\end{array}\right] \end{gathered}$$
  $$\underset{d\ast m}{\sum W}=[\sum p_1,\sum p_2,...,\sum p_m]\underset{m\ast m}{\Lambda }=\left[\begin{array}{cccc}{\lambda }_1& 0& ...& 0\\ 0& {\lambda }_2& ...& 0\\ ...& ...& ...& ...\\ 0& 0& ...& {\lambda }_m\end{array}\right]$$
  $$\underset{d\ast m}{\mathrm{W\Lambda }}=[{\lambda }_1{p}_1,{\lambda }_2{p}_2,...,{\lambda }_m{p}_m]$$
  由等式可得：

$$\begin{gathered} \sum W=W\Lambda \\ [\sum p_1,\sum p_2,...,\sum p_m]=[{\lambda }_1{p}_1,{\lambda }_2{p}_2,...,{\lambda }_m{p}_m] \end{gathered}$$
即得到等式组：
$$\{\begin{array}{rl}\sum p_1& ={\lambda }_1{p}_1\\ \sum p_2& ={\lambda }_1{p}_2\\ ...& \\ \sum p_m& ={\lambda }_1{p}_m\end{array}$$

同时存在单位正交约束：
$$\{\begin{array}{r}{p}_i{p}_j=0i\ne j\\ p_i{p}_j=1i=j\end{array}$$

因此可证得，$p_i$为协方差矩阵特征向量，$x_i$ 为特征值。即满足该条件时，该最优化问题取得极值

​ 证明二：当选取的特征向量是对应特征值最大的m个时，方差最大

优化目标：$tr(W^T\sum W)=tr(W^{T}W\Lambda )=tr(\Lambda )$
因此最大化方差等价于最大化对角阵\Lambda的迹，即最大化m个特征向量对应的特征值之和

算法流程

1）标准化样本矩阵X，使样本均值为0，方差为1

2）计算协方差矩阵，进行特征值分解，获取<特征值，特征向量>对

3）选取最大m个特征值对应的特征向量$p_1,...p_m$，组成变换矩阵W

4）通过$Y=W^{T}X$的变换，将样从d维降至m维