PCA原理详解

PCA原理详解

虽然之前看过PCA，但说实话不是特别理解，今天在人工智能的课堂上再次学了一下，感觉还是有点收获的。就随便写写吧

What is PCA？

PCA（Principle Component Analysis）是一种常用的数据分析方法

PCA通过线性变换将原始数据变换为一组各维度线性无关的表示，可用于提取数据的主要特征分量，常用于高维数据的降维

数据的向量表示

一般情况下，在数据挖掘和机器学习中，数据被表示为向量

例如：某宝2012年全年的流量以及交易情况可以看成一组记录的集合，其中每一天的数据是一条记录，列向量格式如下：

$（浏览量，访客数，下单数，成交数，成交金额）^T $

$(500, 240, 25, 13, 2312.15)^T$

降维问题：目的和原则

机器学习算法的复杂度通常与数据的维数有着密切关系，甚至与维数呈指数级关联

机器学习在实际中处理成千上万甚至几十万维的情况也不罕见，在这种情况下，机器学习的资源消耗是不可接受的，因此我们必须对数据进行降维

降维当然意味着信息的丢失，不过鉴于实际数据本身常常存在的相关性，我们可以想办法在降维的同时将信息的损失尽量降低

降维的数学支撑

向量的表示和基变换：内积和投影

两个维数相同的向量的内积被定义为：

$(a_1, a_2, ..., a_n) * (b_1, b_2,..., b_n)^T = a_1 b_1 + a_2 b_2 +... + a_n b_n$

内积运算将两个向量映射为一个实数

设A和B是两个n维向量，n维向量可以等价表示为n维空间中的一条从原点发射的有向线段：

$A=(x_1, y_1)$ $B=(x_2, y_2)$

从A点向B所在直线上引一条垂线。垂线与B的交点叫做A在B上的投影，设A与B的夹角为$\alpha$，则投影的矢量长度为$|A|cos(\alpha)$

其中$|A|=\sqrt{x_1^2+y_1^2}$是向量$A$的模，也就是$A$线段的标量长度

可以将内积表示成另外一种我们熟悉的形式

$A \cdot B = |A||B|cos(\alpha)$

A与B的内积等于A到B的投影长度乘以B的模

设B的模为1，即让$|B| = 1$,那么就变成了$A \cdot B = |A|cos(\alpha)$

即A与B的内积等于A向B所在直线投影的矢量长度

基的数学含义

要准确描述向量，首先要确定一组基，然后给出在基所在的各个直线上的投影值

例如，$(1, 1)$和$(-1, 1)$也可以成为一组基，标准化之后变成$(\frac 1 {\sqrt{2}}, \frac 1 {\sqrt{2}})$和$(-\frac 1 {\sqrt{2}}, \frac 1 {\sqrt{2}})$

$(3, 2)$在新基上的坐标为$(\frac 5 {\sqrt{2}}, -\frac 1 {\sqrt{2}})$

基变换的矩阵表示

$(3, 2)$的基变换（基是：$\left(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right) 和\left(-\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}}\right)$）

$\left(\begin{array}{cc}{1 / \sqrt{2}} & {1 / \sqrt{2}} \\ {-1 / \sqrt{2}} & {1 / \sqrt{2}}\end{array}\right)\left(\begin{array}{l}{3} \\ {2}\end{array}\right)=\left(\begin{array}{c}{5 / \sqrt{2}} \\ {-1 / \sqrt{2}}\end{array}\right)$

例如$(1,1),(2,2),(3,3)$的基变换：

$\left(\begin{array}{cc}{1 / \sqrt{2}} & {1 / \sqrt{2}} \\ {-1 / \sqrt{2}} & {1 / \sqrt{2}}\end{array}\right)\left(\begin{array}{ccc}{1} & {2} & {3} \\ {1} & {2} & {3}\end{array}\right)=\left(\begin{array}{ccc}{2 / \sqrt{2}} & {4 / \sqrt{2}} & {6 / \sqrt{2}} \\ {0} & {0} & {0}\end{array}\right)$

注意，这里的每一组向量都需要以列向量的形式来表示

一般的，如果有M个N维向量，想将其变换为由R个N维向量表示的新空间。那么首先将R个基按行组成矩阵A，然后将向量按列组成矩阵B，那么两矩阵的乘积AB就是变换结果，其中AB的第m列为A中第m列变换后的结果

数学表示为：

$\left(\begin{array}{c}{p_{1}} \\ {p_{2}} \\ {\vdots} \\ {p_{R}}\end{array}\right)\left(\begin{array}{cccc}{a_{1}} & {a_{2}} & {\cdots} & {a_{M}}\end{array}\right)=\left(\begin{array}{cccc}{p_{1} a_{1}} & {p_{1} a_{2}} & {\cdots} & {p_{1} a_{M}} \\ {p_{2} a_{1}} & {p_{2} a_{2}} & {\cdots} & {p_{2} a_{M}} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} \\ {p_{R} a_{1}} & {p_{R} a_{2}} & {\cdots} & {p_{R} a_{M}}\end{array}\right)$

其中$p_i$是一个行向量，表示第$i$个基，$a_j$是一个列向量，表示第$j$个原始数据记录

协方差矩阵及优化目标

如果我们有一组N维向量，现在要将其降到K维（K小于N），应该如何选择K个基才能最大程度保留原有信息呢？

假设数据由五条记录构成，将他们表示成矩阵形式：
$\left(\begin{array}{lllll}{1} & {1} & {2} & {4} & {2} \\ {1} & {3} & {3} & {4} & {4}\end{array}\right)$

其中每一列为一条数据，而一行为一个字段，为了后续处理方便，首先将每个字段的所有值都减去字段均值（后面会解释原因）

结果如下：

$\left(\begin{array}{ccccc}{-1} & {-1} & {0} & {2} & {0} \\ {-2} & {0} & {0} & {1} & {1}\end{array}\right)$

图上显示为：

我们希望使用一维来表示这些数据，但是又希望尽量保留原始数据，要如何选择呢？

通过基变换的讨论我们知道，这个问题实际上是要在二维平面中选择一个方向，将所有数据都投影到这个方向所在直线上，用投影值表示原始记录。这是一个实际的二维降到一维的问题。

如果向X轴投影，则最左边的两个点会重叠在一起，中间的两个点也会重叠在一起，于是本身五个各不相同的点投影之后只剩下两个不同的值了，这是一种严重的信息丢失。投影到Y轴也会发生先这样的问题，所以，单独选择X轴和Y轴都不是最好的投影选择

方差

目标：投影后投影值尽可能分散，而这种程度的分散，可以用数学上的方差来表述。此处，一个字段的方差可以看做是每个元素与字段均值的差的平方和的均值，即

$\operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^{m}\left(a_{i}-\mu\right)^{2}$

由于上面已经将每个字段的均值都化为0了，因此方差可以直接用每个元素的平方和除以元素个数表示：

$\operatorname{Var}(a)=\frac{1}{m} \sum_{i=1}^{m} a_{i}^{2}$

于是上面的问题被形式化的表述为：寻找一个一维基，使得所有数据变换为这个基上的坐标表示后，方差值最大

协方差

目的：从直观上说，让两个字段尽可能表示更多的原始信息，不希望他们之间存在线性（相关性）的，因为相关性意味着这两个字段不是完全独立，必然存在重复表示的信息

数学上可以用两个字段的协方差来表示其相关性，由于已经让每个字段均值为0，则：

$\operatorname{Cov}(a, b)=\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}$

可以看到，在字段均值为0的情况下，两个字段的协方差简洁的表示为其内积除以元素数m

当协方差为0时，表示两个字段完全独立。为了让协方差为0，我们选择第二个基时，只能与在第一个基正交的方向上选择。因此最终选择的两个方向一定是正交的

至此，我们得到了降维问题的优化目标：将一组N为向量降为K维（K大于0，小于N），其目标是选择K个单位（模为1）正交基，使得原始数据变换到这组基上后，各字段两辆间协方差为0，而字段的方差则尽可能大（在正交的约束下，取最大的K个方差）

协方差矩阵

目的：降维的指标与字段内方差及字段间协方差有密切关系。因此，可将两者统一表示

$X=\left(\begin{array}{llll}{a_{1}} & {a_{2}} & {\cdots} & {a_{m}} \\ {b_{1}} & {b_{2}} & {\cdots} & {b_{m}}\end{array}\right)$

用X乘以X的转置，并乘上系数1/m

$\frac{1}{m} X X^{\top}=\left(\begin{array}{cc}{\frac{1}{m} \sum_{i=1}^{m} a_{i}^{2}} & {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} \\ {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} & {\frac{1}{m} \sum_{i=1}^{m} b_{i}^{2}}\end{array}\right)$

• 矩阵对角线上的两个元素分别是两个字段的方差，而其他元素是a和b的协方差
• 两者被统一到了一个矩阵

协方差矩阵推广

我们有m个n维数据记录，将其按列排成n乘m的矩阵X，设$C=\frac 1 m X X^T$，则C是一个对称矩阵，其对角线分别为各个字段的方差

而第i行j列的元素和第j行i列的元素相同，表示i和j两个字段的协方差

$\frac{1}{m} X X^{\top}=\left(\begin{array}{cc}{\frac{1}{m} \sum_{i=1}^{m} a_{i}^{2}} & {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} \\ {\frac{1}{m} \sum_{i=1}^{m} a_{i} b_{i}} & {\frac{1}{m} \sum_{i=1}^{m} b_{i}^{2}}\end{array}\right)$

协方差矩阵对角化

目标：将协方差矩阵对角化，即除对角线外的其他元素化为0，并且在对角线上将元素按大小从上到下排列

原矩阵与基变换后矩阵协方差矩阵的关系：

设原始数据矩阵$X$对应的协方差矩阵为$C$，而$P$是一组基按行组成的矩阵，设$Y=PX$，则$Y$为$X$对$P$做基变换后的数据。设$Y$的协方差矩阵为$D$，我们推导一下$D$与$C$的关系：

$\begin{aligned} D &=\frac{1}{m} Y Y^{\top} \\ &=\frac{1}{m}(P X)(P X)^{\top} \\ &=\frac{1}{m} P X X^{\top} P^{\top} \\ &=P\left(\frac{1}{m} X X^{\top}\right) P^{\top} \\ &=P C P^{\top} \end{aligned}$

$P$能让原始的协方差矩阵对角化的$P$。换句话说，优化目标变成了寻找一个矩阵$P$，满足$PCP^T$是一个对角矩阵，并且对角元素按大到小一次排列，那么$P$的前$K$行就是要寻找的基，用$P$的前$K$行组成的矩阵乘以$X$就是的$X$从$N$维降到了$K$维并满足上述优化条件

由上文知道，协方差矩阵C是一个对称矩阵，在线性代数上，实对称矩阵有一系列非常好的性质：

• 实对称矩阵不同特征值对应的特征向量必然正交

• 设特征向量$\lambda$重数为$r$，则必然存在r个线性无关的特征向量对应于$\lambda$，因此可以将这r个特征向量单位正交化。由上面两条可知，一个n行n列的实对称矩阵一定可以找到n个单位正交特征向量，设这n个特征向量为e1, e2, …, en，将其按列组成矩阵：

  $E=(e_1, e_2, ..., e_n)$

  则对协方差矩阵C有如下结论：

  $E^{\top} C E=\Lambda=\left(\begin{array}{cccc}{\lambda_{1}} & {} & {} & {} \\ {} & {\lambda_{2}} & {} & {} \\ {} & {} & {\ddots} & {} \\ {} & {} & {} & {\lambda_{n}}\end{array}\right)$

其中$\Lambda$为对角矩阵，其对角元素为各特征向量对应的特征值（可能有重复）

到这里，我们已经找到了需要的矩阵P：

$P=E^T$

P是协方差矩阵的特征向量单位化后按行排列出的矩阵，其中每一行都是C的一个特征向量。如果设P按照$\Lambda$中特征值的从大到小，将特征向量从上到下排列，则用P的前K行组成的矩阵乘以原始数据矩阵X，就得到了我们需要的降维后的数据矩阵Y

PCA算法

设有m条n维数据

• 将原始数据按列组成n行m列矩阵X

• 将X的每一行（代表一个属性字段）进行零均值化，即减去这一行的均值

• 求出协方差矩阵$C=\frac 1 m X X^T$

• 求出协方差矩阵的特征值以及对应的特征向量

• 将特征向量按对应特征值大小从上到下按行排列成矩阵，取前k行组成矩阵P

• $Y=PX$即为降维到K为之后的数据

举例

以上文提到的

$\left(\begin{array}{ccccc}{-1} & {-1} & {0} & {2} & {0} \\ {-2} & {0} & {0} & {1} & {1}\end{array}\right)$

为例，我们用PCA方法将这组二维数据降到一维

因为每行已经是零均值，所以直接求协方差矩阵

$C=\frac{1}{5}\left(\begin{array}{ccccc}{-1} & {-1} & {0} & {2} & {0} \\ {-2} & {0} & {0} & {1} & {1}\end{array}\right)\left(\begin{array}{cc}{-1} & {-2} \\ {-1} & {0} \\ {0} & {0} \\ {2} & {1} \\ {0} & {1}\end{array}\right)=\left(\begin{array}{cc}{\frac{6}{5}} & {\frac{4}{5}} \\ {\frac{4}{5}} & {\frac{6}{5}}\end{array}\right)$

然后求其特征值和特征向量

$\lambda_{1}=2, \lambda_{2}=2 / 5$

其对应的特征向量分别是：

$c_{1}\left(\begin{array}{c}{1} \\ {1}\end{array}\right), c_{2}\left(\begin{array}{c}{-1} \\ {1}\end{array}\right)$

其中对应的特征向量分别是一个通解，$c_1$和$c_2$可取任意实数，那么标准化后的特征向量为：

$\left(\begin{array}{c}{1 / \sqrt{2}} \\ {1 / \sqrt{2}}\end{array}\right),\left(\begin{array}{c}{-1 / \sqrt{2}} \\ {1 / \sqrt{2}}\end{array}\right)$

矩阵P为：

$P=\left(\begin{array}{cc}{1 / \sqrt{2}} & {1 / \sqrt{2}} \\ {-1 / \sqrt{2}} & {1 / \sqrt{2}}\end{array}\right)$

可以验证协方差矩阵C的对角化：

$P C P^{\top}=\left(\begin{array}{cc}{1 / \sqrt{2}} & {1 / \sqrt{2}} \\ {-1 / \sqrt{2}} & {1 / \sqrt{2}}\end{array}\right)\left(\begin{array}{cc}{6 / 5} & {4 / 5} \\ {4 / 5} & {6 / 5}\end{array}\right)\left(\begin{array}{cc}{1 / \sqrt{2}} & {-1 / \sqrt{2}} \\ {1 / \sqrt{2}} & {1 / \sqrt{2}}\end{array}\right)=\left(\begin{array}{cc}{2} & {0} \\ {0} & {2 / 5}\end{array}\right)$

最后我们用P的第一行乘以数据矩阵，就得到的降维后的表示：

$Y=\left(\begin{array}{llllll}{-1} & {-1} & {0} & {2} & {0} \\ {-2} & {0} & {0} & {1} & {1}\end{array}\right)=\left(\begin{array}{cccc}{-3 / \sqrt{2}} & {-1 / \sqrt{2}} & {0} & {3 / \sqrt{2}} & {-1 / \sqrt{2}}\end{array}\right)$