CS229 主成分分析(Principal components analysis)

Posted on | Edited on | Comments: | Views:

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

引入

假如样本$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的效果大打折扣。

引用