PCA(主成分分析)

PCA(principal component analysis,主成分分析) 是一种常见的数据分析的方法,它通过线性变换将原始数据降维,同时降维后的特征。

一些基础概念

数据的每一条向量一般用列向量进行表示,并且是用列向量表示。如$(3,4,5,1,2)^{T}$,这里我们用行向量的转置来表示了。

在机器学习算法中的复杂度和数据的维数有着密切的关系,有些机器学习处理的特征数达到几十万。但与此同时,有些特征是冗余的,也就是A特征和B特征表达了类似的信息,此时如果去掉一个特征没有任何信息的损失。

的要求是线性无关,非正交(内积为0,即相互垂直)也是可以的。

关于基变换的矩阵表示,比如我们想把一个点从正常的坐标系变换到$(\frac{1}{\sqrt{2}}, \frac{1}{\sqrt{2}})$和$(-\frac{1}{\sqrt{2}}, -\frac{1}{\sqrt{2}})$为基的坐标,只需要将每个基作为行向量的矩阵和我们的坐标进行相乘就可以得到新的坐标。或者是这个解释也是非常形象的,两个矩阵相乘的意义是将右边矩阵中的每一列列向量变换到左边矩阵中每一行行向量为基所表示的空间中去。更抽象的说,一个矩阵可以表示一种线性变换。

协方差矩阵及优化步骤

假设我们的数据由五条记录组成,如下:

$$
\begin{matrix}
1 & 1 & 2 & 4 & 2 \newline
1 & 3 & 3 & 4 & 4 \newline
\end{matrix}
$$

每一列均为一条数据记录,一行为一个字段。为了后续处理的方便,我们先将每个字段的数据的均值变为0。即每个字段的每个值减去这个字段的平均值,处理后如下:

$$
\begin{matrix}
-1 & -1 & 0 & 2 & 0 \newline
-2 & 0 & 0 & 1 & 1 \newline
\end{matrix}
$$

现在我们的目的是要在二维平面内选择一个方向,将所有数据都投影到这个方向所在的直线。我们希望投影后的数据能够充分表示原来的信息,或者说希望投影后的点尽量分散。

方差衡量分散程度

由于我们之前已经处理过使得每个字段的均值都为0了,因此方差如下:

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

即原问题形式表述为:寻找一个基,使得所有的数据变换为这个基的坐标表示后,方差值最大。

协方差来衡量相关度

对于三维的情况,我们通过上述的方差最大来选出了最分散的第一维后,选择第二个投影方向的时候就不能单纯地选择方差最大的了,因为我们不希望投影的方向和第一维很相似,即又重复了。我们可以用协方差来衡量其相关性。因为每个字段的均值都为0了,此时的协方差为:

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

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

当协方差为0的时候,代表两个字段完全独立。如果让协方差为0,第二个方向与第一个方向肯定是正交的。

所以原问题的优化目标如下:将一组N维数据降为K维,即选择K个单位基(模为1),使得数据变换到这组基上后,各字段两两协方差为0,而字段的方差尽可能大。

协方差矩阵

假设只有a和b两个字段,我们将它们按行组成矩阵X:

$$
\begin{matrix}
a1 & a2 & … \newline
b1 & b2 & … \newline
\end{matrix}
$$

然后我们用X乘上X的转置,并乘上系数1/m:

$$
\begin{matrix}
\frac{1}{m}\sum_{i=1}^{m}a_i^2 & \frac{1}{m}\sum_{i=1}^{m}a_ib_i \newline
\frac{1}{m}\sum_{i=1}^{m}a_ib_i & \frac{1}{m}\sum_{i=1}^{m}b_i^2 \newline
\end{matrix}
$$

这个矩阵的对角线上的两个元素就是两个字段的方差,而其它元素就是a和b的协方差。

协方差矩阵对角化

我们的优化目标此时等价于如下:除了对角线外的其它元素化为0,并且在对角线上将元素按大小从上到下排列,最后选取前面的K个特征。

我们用数学推导再来看下。设原始数据矩阵X对应的协方差矩阵为C,而C是一组基按行组成的矩阵,设Y=PX,即Y是X对P做基变换后的数据。设Y的协方差矩阵为D,D与C关系如下:

$$D=\frac{1}{m}YY^T = \frac{1}{m}(PX)(PX)^T = P(\frac{1}{m}XX^T)P^T=PCP^T$$

所以P矩阵就是这样的一个矩阵,它能够使得原始协方差矩阵变成一个对角矩阵,并且对角元素从大到小排列。此时P的前K行的就是我们要寻找的基。

选取特征向量

我们是需要投影的和最大。

设给定的数据为{a1,a2,…an},中心化后为{a1-avg_a,a2-avg_a…},投影变换的新坐标系为{w1,w2…wn},其中||w||=1,且$w_i^Tw_j=0$。

如果我们将数据从n维降低到n’维,即丢弃新坐标系中的部分坐标,则新的坐标系为${w_1,w_2,…w_n’}$,样本点$x^{(i)}$ 在低维坐标系里的第j维的坐标是$w_{j}^{T}x^{(i)}$,样本点$x^{(i)}$在n’维坐标系中的投影记为$z^{(i)}=(z_1^{(i)},z_2^{(i)},…z_{n’}^{(i)})$.

对于任意一个样本$x^{(i)}$,在新坐标系中的投影为$W^Tx^{(i)}$,在新坐标系中的投影方差为$W^Tx^{(i)}x^{(i)T}W$(因为是一维的,矩阵V的方差为$VV^{T}$),要使所有的样本的投影方差和最大,也就是最大化$\sum_{i=1}^{m}W^Tx^{(i)}x^{(i)T}W$,即:

$$\underbrace{argmax}_{W} \ tr(W^TXX^TW)\ s.t. W^TW = I$$

利用拉格朗日函数可以得到:

$$J(W) = tr(W^TXX^TW) + λ(W^TXX^TW-I)$$

对J求导有$XX^TW+ λW=0$, 即:

$$XX^TW = (-λ)W$$

W为$XX^T$的n’个特征向量组成的矩阵,而$-λ $为$XX^T$的特征值(因为$AX=λX$)。我们将数据集从n维降到n’维的时候,需要找到最大的n’个特征值对应的特征向量。这n’个特征向量组成的矩阵W即为我们需要的矩阵。对于原始数据集,我们只需要用$z^{(i)}=W^Tx^{(i)}$,就可以把原始数据集降维到最小投影距离的n’维数据集。

算法

总结一下PCA的算法步骤:

设有m条n维数据。

1)将原始数据组成n行m列的数据X
2)将X的每一行(代表一个属性字段)进行中心化,即减去这一行的均值
3) 求出协方差矩阵$C=\frac{1}{m}XX^T$
4)求出协方差矩阵的特征值及对应的特征的特征向量
5)将特征向量按对应特征值大小从上到下进行按行排列成矩阵,取前k行组成矩阵P
6)Y=PX即为降维到K维后的数据

Ref

PCA算法详解
主成分分析(PCA)原理总结
【机器学习算法实现】主成分分析(PCA)——基于python+numpy

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注