CS229 主成分分析(Principal components analysis)

今天是校庆,学校难得开灯,放一张图书馆的照片。

引入

假如样本$x_i$代表一种类型的车,$x_i^{(1)}$,即第一个特征代表速度mile/h,$x_i^{(2)}$,第二个特征代表km/h,这两个特征是线性的,都只能表示速度这一信息,为了避免信息冗余,减少样本输入算法的计算量,我们可以在二者中去掉任意一个。但是在一些样本中,可能存在两个特征之间这样的相关性特别强,但是无法通过经验判断,此时就需要一个算法来自动对样本的维度进行缩减,同时尽可能保留有用的信息,这就是主成分分析法。

线性代数基础

在推导算法之前,先复习一下需要用到的数学知识。

向量的投影与内积

考虑有向量$\overrightarrow{A},\overrightarrow{B}$,其内积为

设$\overrightarrow{B}$的模为1,那么$\overrightarrow{A}$在$\overrightarrow{B}$上的投影为

要描述一个向量,首先要确定一组基,然后给出向量在基所在方向上的投影值,如最普通的二维空间中向量(3,2),它所在空间的基就是$ \begin{bmatrix} 1 \\ 0 \end{bmatrix} $与$ \begin{bmatrix} 0 \\ 1 \end{bmatrix} $,它们的方向分别是$x$轴和$y$轴,向量(3,2)在这两个方向上的投影分别是3和2。

矩阵乘法的意义(基变换)

考虑普通二维空间中的向量(3,2),使用一个矩阵$ \begin{bmatrix} 1/\sqrt{2} & 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2} \end{bmatrix} $去乘向量$\begin{bmatrix} 3 \\ 2 \end{bmatrix} $,我们会得到一个结果$\begin{bmatrix} 5/\sqrt{2} \\ -1/\sqrt{2} \end{bmatrix}$。现在通过下图来观察这个乘法到底做了什么。可以发现,结果就是向量$\begin{bmatrix} 3 \\ 2 \end{bmatrix}$在方向$\begin{bmatrix} 1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$和方向$\begin{bmatrix} -1/\sqrt{2} \\ 1/\sqrt{2} \end{bmatrix}$上的投影,我们把这两个方向看作基的方向。所以,矩阵乘法的几何意义可以看作基变换,即改变基向量后,将原始空间中的向量转变为新空间中的向量。

主成分分析

优化目标

有一组$D$维向量,要将维度降为$d$,$d < D$,降维操作,可以使用基变换来实现,即使用基向量矩阵$W$(d*D)来乘每一个样本$x_i$(D*1),那么维度缩减后的新样本就是$y_i$(d*1)。但是基可以构造无数种,哪一种才是最好的呢?答案是寻求使新样本方差最大的基,要想说明这个问题十分复杂,直观的理解,方差越大,代表数据偏离中心的程度越大,由于维度减小,这些点已经越来越近了,这是没有办法避免的,如果维度变小后,再把方差变得更小,即把样本再变得更集中,这样只会丢失更多信息(极端的情况下可能会有更多的样本重叠),所以为了在降维的同时尽量保留更多的信息,需要让样本更加偏离中心,即让方差最大化。

方差最大化

设新空间的基向量矩阵为$W$,我们先考虑最简单的情况,即基向量矩阵$W$只有一个方向,那么他就只有D行1列,每个样本$x_i$的投影为$W^Tx_i$,样本的均值$\bar{x}=\frac{1}{N}\sum_{n=1}^NX_n$,那么投影后的新样本方差为

$S$就是原样本的协方差矩阵

如果事先将新样本进行均值归一化,则均值为0(先减去均值再除以方差),那么上面的公式将更好理解而且易用。

现在,我们要最大化$W^TSW$,同时有一个约束条件$W^TW=1$,此时运用拉格朗日乘子法既可以求解:
构建拉格朗日函数:

要最大化这个函数,首先对$W$求偏导置0
最后发现
出现了一个神奇的结果,这是一个特征向量和特征值的定义式,关于特征值和特征值的定义在线代中有详细描述,即对于矩阵$S$,$W$是一个特征向量,$\lambda_1$是对应的特征值,所以要使$W^TSW$最大,即让$\lambda_1$最大,所以在将原始样本投影到一个维度时,基向量的方向应该是协方差矩阵特征值最大的特征向量的方向,此时满足投影方差最大。
那么如果基向量有两个,希望投影到两个方向上呢?
假设有$W = \begin{bmatrix} W_1 & W_2 \\ \end{bmatrix} $
同理,使用拉格朗日乘子法,仍然有$SW=\lambda W$
要让投影方差最大,有

由于$SW=\lambda W$且S是实对称矩阵,此时因为有所有特征向量都是正交的结论,所以上面的协方差矩阵中,由于$W_i$是特征向量,互相正交,所以非对角位的值都是0,只剩下对角位上的方差,此时选取矩阵$S$前两个特征值最大的特征向量作为基向量,此时投影的方差是最大的。

如果要让方差最大,我出现了一个不算疑问的疑问,就是为什么不所有基向量都选特征值最大的特征向量呢?这是不可能的,因为基向量代表投影方向,都选取特征值最大的特征向量作为基向量,到最后还是只有一个方向。所以结合基向量是实对称矩阵的特征向量,这些基向量必定是正交的。

总结

PCA是一种无参数技术,便于通用实现而无法个性化优化。
至此,主成分分析的步骤是:
有m条n维数据

  • 将原始数据组成n行m列的矩阵X
  • 将X的每一行进行0均值化
  • 计算协方差矩阵$S = \frac{1}{m}XX^T$
  • 求出协方差矩阵的特征值和特征向量
  • 如果要将矩阵规约为k维的矩阵,则选取前k个特征值最大的特征值对应的特征向量组成基向量矩阵P。
  • 计算$Y=PX$即为降维到k维后的数据。

PCA的限制:无法应用于高阶相关性(非线性相关)、算法假设主成分位于正交方向,如果非正交方向存在方差较大的特征,PCA的效果大打折扣。

引用