斯坦福机器学习课程 第八周 (2)降维

在这个模块中,我们将介绍主成分分析(PCA),并显示它可以用于数据压缩,加快学习算法,以及可视化的复杂数据集。

动机

动机I:数据压缩

视频地址

本节我将开始介绍第二种无监督学习问题,它叫降维(dimensionality reduction)

我们希望使用降维的一个主要原因是数据压缩。我们会在后几节中看到,数据压缩不仅通过压缩数据使得数据占用更少的计算机内存和硬盘空间,它还能给算法提速。

首先我们来介绍什么是降维。

例子

举一个例子,假如我们有一个有很多很多很多特征变量的数据集:

这里为了方便展示,只画了其中两个。

假设我们不知道这两个特征量。其中$x_1$是某个物体的长度,以厘米为单位;另一个$x_2$是它以英寸为单位的长度。所以这是一个非常冗余的数据,与其用两个特征变量$x_1$和$x_2$,它们都是测量到的长度,或许我们应该把这个数据降到一维,只用一个长度的数据。

这个例子可能看起来好像是我生造的,但这个厘米英寸的例子其实还真不是那么无聊。我在工业界看到的情况也是大同小异。

如果你有上百或者上千的特征变量,很容易就会忘记你到底有什么特征变量,而且有时候可能有几个不同的工程师团队。一队工程师可能给你200个特征变量,第二队工程师可能再给你300个特征变量,然后第三队工程师给你500个特征变量。所以你一共有1000个特征变量,这样就很难搞清哪个队给了你什么特征变量。实际上得到这样冗余的特征变量并不难。

所以如果以厘米计的长度被取整到最近的厘米整数,以英寸计的长度被取整到最近的英寸整数。这就是为什么这些样本没有完美地在一条直线上。就是因为取整所造成的误差。

这种情况下,如果我们可以把数据降到一维而不是二维,就可以减少冗余。

降维含义

让我们再详细讲讲从二维降到一维到底意味着什么。

二维降到一维

让我给这些样本涂上不同的颜色涂上不同的颜色:

在这个例子中降低维度的意思是:我希望找到一条线,基本所有数据映射到这条线上。这样做之后,我就可以直接测量这条线上每个样本的位置。我想把这个新特征叫做$z_1$。

要确定这条线上的位置,我只需要一个数字。这就是说新特征变量$z_1$能够表示这条绿线上每一个点的位置。

在之前如果想要表示一个样本点,我需要一个二维向量$(x_1,x_2)$,但是现在我可以用一个一维向量$z_1$来表示这个样本点:

总结一下,在把所有训练样本映射到一条线上之后,我就能做到只用一个数字来表示每个训练样本的位置。这是一个对原始训练样本的近似。相对于之前需要用两个数字来表示一个样本而言,现在我只需要一个数字就可以表示了。这样就减少了一半的内存需求或者硬盘需求。

更重要的是,数据压缩还会让我们的学习算法运行地更快。

三维降到二维

现在,我展示一个把三维数据降到二维的例子。

顺便说一下,在更典型的降维例子中,我们可能有1000维的数据,我们可能想降低到100维,但是因为我在这里能可视化的展示数据的维度是有限制的,所以我要用的例子是三维到二维的。

我们有一个图上这样的数据集,我有一个样本$x^{(i)}$的集合,$x^{(i)}$是一个三维实数的点,所以我的样本是三维的:

$$
x^{(i)} \in R^3
$$

实际上,这些样本点,差不多都处于同一平面上。降维在这里的作用,就是把所有的数据,都投影到一个二维的平面内。所以,我们要对所有的数据进行投影,使得它们落在这个平面上:

最后为了表示一个点在平面上的位置,我们需要两个数来表示平面上一个点的位置。这两个数可能叫做$z_1$和$z_2$:

这也意味着我们现在可以用一个二维向量$z$来表示每一个训练样本了:

$$
z^{(i)} \in R^2
$$


为了更好的理解降维的过程,现在让我们用3D绘图来重现上面的整个过程:

我们走的过程是这样的:左边是原始数据集,中间是投影到2D的数据集,右边是以$z_1$和$z_2$为坐标轴的2D数据集。

我们来更详细地看一下:

原始数据集是这样的:

可以看出来,大部分数据差不多可能都落在某个2D平面上,或者说距离某个2D平面不远。

所以我们可以把它们投影到2D平面上。下面是投影后的效果:

你可以看到所有的数据落在一个平面上,因为我们把所有的东西都投影到一个平面上了。所以我们现在只需要两个数:$z_1$和$z_2$来表示点在平面上的位置即可:

这就是把数据从三维降到二维的过程。

这就是降维以及如何使用它来压缩数据的过程。

动机II:可视化数据

视频地址

在上节中,我们讲到一种通过数据降维来进行数据压缩的方法。在本节我将会讲到第二种数据降维的应用,那就是可视化数据

对于大多数的机器学习应用,它真的可以帮助我们来开发高效的学习算法,但前提是我们能更好地理解数据。降维就是数据可视化的一种方法。

假如我们已经收集了大量的有关全世界不同国家的统计数据集:

第一个特征$x_1$是国家的国内生产总值;第二个特征$x_2$是一个百分比,表示人均占有的GDP;第三个特征$x_3$是人类发展指数;第四个特征$x_4$是预期寿命;…直到$x_{50}$

在这里我们有大量的国家的数据,对于每个国家有50个特征。我们有这样的众多国家的数据集,为了使得我们能更好地来理解数据,我们需要对数据进行可视化展示。这里我们有50个特征,但绘制一幅50维度的图是异常困难的,因此我们需要对数据进行降维,然后再可视化。

具体做法如下:

我们使用特征向量$x^{(i)}$来表示每个国家。$x^{(i)}$有着50个维度。我们需要对这50个特征降维之后,我们可以用另一种方式来代表$x^{(i)}$:使用一个二维的向量$z$来代替之前50维的$x$。

$$
z^{(i)} \in R^2
$$

我们用$z_1$和$z_2$这两个数来总结50个维度的数据,我们可以使用这两个数来绘制出这些国家的二维图,使用这样的方法尝试去理解二维空间下不同国家在不同特征的差异会变得更容易。

在降维处理时,我们用$z_1$来表示那些象征着国家整体情况的数据,例如”国家总面积”、”国家总体经济水平”等;用$z_2$来表示象征着人均情况的数据,例如”人均GDP”,”人均幸福感”等。

降维处理之后,将数据按照这两个维度展示如下:

在图中,右侧的点,象征着国家整体经济比较好的国家;上方的点,象征着人均经济比较好、人均幸福感较高、人均寿命较长…的国家。


那么具体我们要如何去压缩数据达到降维的效果呢?在下一节视频中我们将会开始开发一种特别的算法。简称PCA或者主成分分析 。这个算法允许我们进行数据可视化,同时可以进行早先我们提到的一些有关数据压缩方面的应用。

PCA

主成分分析(PCA)相关概念

视频地址

对于降维问题来说,目前最流行最常用的算法是主成分分析法(Principal Componet Analysis, PCA)

在本节中,我想首先开始讨论PCA问题的公式描述,也就是说,我们用公式准确地精确地描述:我们想让PCA来做什么。

PCA的执行过程2D -> 1D

假设我们有这样的一个数据集:

这个数据集含有二维实数空间内的样本X。

假设我想对数据进行降维,从二维降到一维。也就是说我想找到一条直线将数据投影到这条直线上,那怎么找到一条好的直线来投影这些数据呢?

这样的一条直线也许是个不错的选择:

你认为这是一个不错的选择的原因是:如果你观察投影到直线上的点的位置,我们发现每个点到它们对应的投影到直线上的点之间的距离非常小。(也就是说这些蓝色的线段非常的短):

所以,正式的说PCA所做的就是寻找一个低维的面(在这个例子中,其实是一条直线)数据投射在上面,使得这些蓝色小线段的平方和达到最小值。这些蓝色线段的长度被叫做投影误差

所以PCA所做的就是寻找一个投影平面,对数据进行投影,使得这个能够最小化。

另外在应用PCA之前,通常的做法是先进行均值归一化特征规范化,使得特征$x_1$和$x_2$均值为0,数值在可比较的范围之内。

在这个例子里,我已经这么做了。但是在后面我还将回过来讨论更多有关PCA背景下的特征规范化和均值归一化问题。


我们正式一点地写出PCA的目标是这样的:

如果我们将数据从二维降到一维的话,我们需要试着寻找一个向量$u^{(i)}$,该向量属于$n$维空间中的向量(在这个例子中是二维的),我们将寻找一个对数据进行投影的方向,使得投影误差能够最小(在这个例子里,我们把PCA寻找到这个向量记做$u^{(1)}$):

所以当我把数据投影到这条向量所在的直线上时,最后我将得到非常小的重建误差。

另外需要说明的时无论PCA给出的是这个$u^{(1)}$是正还是负都没关系。因为无论给的是正的还是负的$u^{(1)}$它对应的直线都是同一条,也就是我将投影的方向。

这就是将二维数据降到一维的例子。

更一般的情况是我们有$n$维的数据想降到$k$维。在这种情况下我们不仅仅只寻找单个的向量($u^{(1)}$)来对数据进行投影,我们要找到$k$个方向($u^{(k)}$)来对数据进行投影,从而最小化投影误差。

PCA的执行过程3D -> 2D

下面的例子中,假设我有一些三维数据点:

我想要做的是是寻找两个向量$u^{(1)}$和$u^{(2)}$:

这两个向量一起定义了一个二维平面,我将把数据投影到这个二维平面上。

如果你精通线性代数,那么这里更正式的定义是:我们将寻找一组向量$u^{(1)}$,$u^{(2)}$,…,$u^{(k)}$,我们将要做的是将数据投影到这$k$个向量展开的线性子空间上。

但是如果你不熟悉线性代数,那就想成是寻找$k$个方向(而不是之寻找一个方向)对数据进行投影。

所以对于3D降维到2D的这个例子来说,寻找一个$k$维的平面,就是在寻找二维的平面。


因此PCA做的就是:寻找一组$k$维向量(一条直线、或者平面、或者诸如此类等等)对数据进行投影,来最小化正交投影误差。

PCA和线性回归的关系

最后一个我有时会被问到的问题是:PCA和线性回归有怎么样的关系?

因为当我解释PCA的时候,我有时候会画出这样看上去有点像线性回归的图:

但是,事实上PCA不是线性回归。尽管看上去有一些相似,但是它们确实是两种不同的算法。

不同点 之一

如果我们做线性回归,我们做的是在给定某个输入特征$x$的情况下预测某个变量$y$的数值。因此对于线性回归,我们想做的是拟合一条直线,来最小化点和直线之间的平方误差:

所以我们要最小化的是,上图中蓝线幅值的平方。注意我画的这些蓝色的垂直线,这是垂直距离。它是某个点与通过假设的得到的其预测值之间的距离。

与此想反,PCA要做的是最小化这些样本点与直线的最短距离(直角距离):

这是一种非常不同的效果。

不同点 之二

更更更一般的是,当你做线性回归的时候,有一个特别的变量$y$作为我们即将预测的值,线性回归所要做的就是用$x$的所有的值来预测$y$。然而在PCA中,没有这么一个特殊的变量$y$是我们要预测的。我们所拥有的是特征$x_1$,$x_2$,…,$x_n$,所有的这些特征都是被同样地对待。

在上面那个从3维降到2维的例子中,原先的3个特征$x_1$,$x_2$,$x_3$都是被同样地对待的,没有特殊的变量$y$需要被预测。


因此,PCA不是线性回归。尽管有一定程度的相似性,使得它们看上去是有关联的,但它们实际上是非常不同的算法。

因此,希望你们能理解PCA是做什么的:它是寻找到一个低维的平面,对数据进行投影,以便最小化投影误差平方的(最小化每个点与投影后的对应点之间的距离的平方值)。

PCA算法 实现过程

视频地址

本节,将介绍PCA算法的具体细节,学完本节后,你就应该知道PCA的实现过程,并且应用PCA来给你的数据降维了。

数据预处理

在使用PCA之前,我们通常会有一个数据预处理的过程。

拿到某组有m个无标签样本的训练集,一般先进行均值归一化(mean normalization)。这一步很重要。然后还可以进行特征缩放(feature scaling),这根据你的数据而定。

这跟我们之前在监督学习中提到的均值归一特征缩放是一样的。

数据预处理第一步:均值归一化(mean normalization)

对于均值归一,我们首先应该计算出每个特征的均值$μ$,然后我们用$x-μ$来替换掉$x$。这样就使得所有特征的均值为0。

举例说明:

比如说,如果$x_1$表示房子的面积,$x_2$表示房屋的卧室数量,然后我们可以把每个特征进行缩放,使其处于同一可比的范围内。

同样地,跟之前的监督学习类似,我们可以首先计算出每个特征的均值:

$$
μ_j=\frac{1}{m}\sum_{i=1}^{m}x_j^{(i)}
$$

然后每个样本值对应的特征减去其对应的均值:

$$
x_j^{(i)} ← x_j^{(i)}-μ_j
$$

将所有的特征替换为这种形式的结果。这样就保证了所有特征的均值为0。

数据预处理第二步:特征缩放(feature scaling)

然后,由于不同特征的取值范围都很不一样,我们还需要进行特征缩放

我们需要将每个特征的取值范围都划定在同一范围内,因此对于均值化处理之后的特征值$x_j^{(i)}-μ_j$,我们还需要做进一步处理:

$$
x_j^{(i)} ← \frac{x_j^{(i)}-μ_j}{s_j}
$$

这里$s_j$表示特征$j$度量范围,即该特征的最大值减去最小值。

PCA算法

接下来就正式进入PCA的算法部分。

在之前的视频中,我们已经知道了PCA的原理。PCA是在试图找到一个低维的子空间,然后把原数据投影到子空间上,并且最小化平方投影误差的值(投影误差的平方和,即下图中蓝色线段长度的平方和):

那么应该怎样来计算这个子空间呢? 实际上这个问题有完整的数学证明来解释如何找到这样的子空间,不过这个数学证明过程是非常复杂的,同时也超出了本课程的范围。但如果你推导一遍这个数学证明过程,你就会发现要找到$u^{(1)}$的值,也不是一件很难的事。但在这里,我不会给出证明,我只是简单描述一下实现PCA所需要进行的步骤。

假如说我们想要把数据从$n$维降低到$k$维,我们首先要做的是计算出下面这个协方差矩阵(通常用$∑$来表示):

$$
∑=\frac{1}{m}\sum_{i=1}^n(x^{(i)})(x^{(i)})^T
$$

很不幸的是,这个希腊符号$∑$和求和符号重复了。希望你对这里不要产生混淆。

计算出这个协方差矩阵后,假如我们把它存为Octave中的一个名为Sigma的变量,我们需要做的是计算出Sigma矩阵的特征向量(eigenvectors)

在Octave中,你可以使用如下命令来实现这一功能:

1
[U,S,V] = svd(Sigma);

顺便说一下,svd表示奇异值分解(singular value decomposition),这是某种更高级的奇异值分解,这是比较高级的线性代数的内容。你不必掌握这些,但实际上Sigma是一个协方差矩阵。有很多种方法来计算它的特征向量。

如果你线性代数学得很好,或者你之前听说过特征向量的话,那也许知道在Octave中还有另一个eig命令,可以用来计算特征向量。实际上svd命令和eig命令将得到相同的结果。但svd其实要更稳定一些,所以我一般选择用svd,不过我也有一些朋友喜欢用eig函数。

在这里对协方差矩阵Sigma使用eigsvd时,你会得到同样的答案。这是因为协方差均值总满足一个数学性质,称为对称正定(symmetric positive definite),其实你不必细究这个具体是什么意思,只要知道这种情况下,使用eigsvd结果是一样的就可以了。

好了,这就是你需要了解的一点线性代数知识,如果有任何地方不清楚的话不必在意。你只需要知道上面这行Octave代码就行了。

如果你用除了Octave或者MATLAB之外的其他编程环境,你要做的是找到某个可以计算svd,即奇异值分解的函数库文件。在主流的编程语言中,应该有不少这样的库文件。我们可以用它们来计算出协方差矩阵的$U$ $S$ $V$矩阵。


我再提几个细节问题。

这个协方差矩阵Sigma应该是一个$n×n$的矩阵,通过定义可以发现这是一个$n×1$的向量,和它自身的转置(一个$1×n$的向量)相乘得到的结果,这个结果自然是一个$n×n$的矩阵。

然后把这n个$n×n$的矩阵加起来,当然还是$n×n$矩阵。

然后svd将输出三个矩阵,分别是$U$ $S$ $V$。你真正需要的是$U$矩阵。

$U$矩阵也是一个$n×n$矩阵:

实际上$U$矩阵的列元素就是我们需要的$u^{(1)}$,$u^{(1)}$等等。

如果我们想将数据的维度从$n$降低到$k$的话,我们只需要提取前$k$列向量。这样我们就得到了$u^{(1)}$到$u^{(k)}$,也就是我们用来投影数据的$k$个方向。

我们取出$U$矩阵的前$k$列得到一个新的,由$u^{(1)}$到$u^{(k)}$组成的矩阵$U_{reduce}$:

$$
\begin{equation}
U_{reduce}=\left[
\begin{matrix}
|&|&|&…&|\\
|&|&|&…&|\\
u^{(1)}&u^{(2)}&u^{(3)}&…&u^{(k)}\\
|&|&|&…&|\\
|&|&|&…&|\\
\end{matrix}
\right]
\end{equation}
$$

这是一个$n × k$维的矩阵。

然后我们用这个$U_{reduce}$来对我的数据进行降维。我们定义:

$$
\begin{equation}
z=\left[
\begin{matrix}
|&|&|&…&|\\
|&|&|&…&|\\
u^{(1)}&u^{(2)}&u^{(3)}&…&u^{(k)}\\
|&|&|&…&|\\
|&|&|&…&|\\
\end{matrix}
\right]
^{T}x
\\
=
\left[
\begin{matrix}
-&-&u^{(1)}&…&-\\
-&-&u^{(2)}&…&-\\
-&-&u^{(3)}&…&-\\
.&.&.&…&.\\
-&-&u^{(k)}&…&-\\
\end{matrix}
\right]
x
\end{equation}
$$

$$
z \in R^k
$$

其中$\left[
\begin{matrix}
-&-&u^{(1)}&…&-\\
-&-&u^{(2)}&…&-\\
-&-&u^{(3)}&…&-\\
.&.&.&…&.\\
-&-&u^{(k)}&…&-\\
\end{matrix}
\right]$是$k×n$的矩阵,$x$是$n×1$的矩阵,因此$z$是$k×1$的矩阵。

这里的$x$可以是训练集中的样本,也可以是交叉验证集中的样本,也可以是测试集样本。

总结

总结一下,这就是PCA的全过程:

  • 首先进行均值归一化

    • 保证所有的特征量都是均值为0的。
  • 然后可以选择进行特征缩放

    • 如果不同特征量的范围跨度很大的话,你确实需要进行特征缩放这一步。
  • 在以上的预处理之后,我们计算出这个协方差Sigma矩阵:

$$
Sigma = \frac{1}{m}\sum_{i=1}^m(x^{(i)})(x^{(i)})^T
$$

  • 然后我们可以应用svd函数来计算出U S V矩阵:
1
[U,S,V] = svd(Sigma);
  • 然后,我们取出$U$矩阵的前$k$列元素组成新的$U_{reduce}$矩阵:
1
Ureduce = U(:,1:k);
  • 最后这个式子给出了我们从原来的特征$x$变成降维后的$z$的过程:
1
z = Ureduce`*x;

另外,跟k均值算法类似,如果你使用PCA的话,你的$x$应该是$n$维实数。所以没有$x_0 = 1$这一项。

有一件事儿我没做:$u^{(1)},u^{(2)}…u^{(k)}$通过将数据投影到$k$维的子平面上确实使得投影误差的平方和为最小值,但是我并没有证明这一点,因为这已经超出了这门课的范围。

幸运的是PCA算法能够用不多的几行代码就能实现它。

应用PCA

对压缩数据的还原

视频地址

在前面的视频中我们介绍了PCA (主成分分析)作为压缩数据的算法,你会发现它能将高达一千维度的数据压缩到只有一百个维度;或者将三维数据压缩到两个维度的情况。

如果有一个这样的压缩算法,那么也应该有一种方法可以从压缩过的数据近似地回到原始高维度的数据。

假设有一个已经被压缩过的$z^{(i)}$它有100个维度,怎样使它回到其最初的表示$x^{(i)}$也就是压缩前的1000维的数据呢?

在本节,我将会告诉你如何做到。

在PCA算法中,我们有下面这些样本:

我们让这些样本投影在一维平面$z_1$上,并且明确地指定其位置:

那么给出一个一维实数点$z$我们能否,让$z$重新变成原来的二维实数点$x$呢?

即做到:

$$
z \in R → x \in R^2
$$


我们知道:

$$
z = U^T_{reduce}x
$$

如果想得到相反的情形,方程应这样变化:

$$
x_{approx} = U_{reduce}z
$$

为了检查维度,在这里$U_{reduce}$是一个$n×k$矩阵,$z$就是一个$k×1$维向量。将它们相乘得到的就是$n×1$维。

所以$x_{approx}$是一个$n$维向量。

同时根据PCA的意图,投影的平方误差不能很大。也就是说$x_{approx}$将会与最开始用来导出$z$的原始$x$很接近。用图表示出来就是这样:

这已经与原始数据非常近似了。

这就是用低维度的特征数据$z$还原到未被压缩的特征数据的过程。我们找到一个与原始数据$x$近似的$x_{approx}$。我们也称这一过程为原始数据的重构(reconstruction)

选择主成分的数量k

视频地址

在PCA算法中,我们把n维特征变量降维到k维特征变量。这个数字k是PCA算法的一个参数。这个数字k也被称作主成分的数量。在本节中我会给你们一些参考,告诉你们人们是怎样思考如何选择PCA的参数k的。

算法原理:最小化平均平方映射误差

为了选择参数k(也就是要选择主成分的数量),这里有几个有用的概念:

PCA所做的是尽量最小化平均平方映射误差 (Average Squared Projection Error)

因此PCA就是要将下面这个量最小化:

$$
\frac{1}{m}\sum_{i=1}^m||x^{i}-x_{approx}^{(i)}||^2
$$

即最小化$x$和其在低维表面上的映射点之间的距离的平方。这就是平均平方映射误差。

同时我们还要定义一下数据的总变差(Total Variation)

$$
\frac{1}{m}\sum_{1=m}^m||x^{(i)}||^2
$$

数据的总变差 (Total Variation) 是这些样本的长度的平方的均值。它的意思是 “平均来看,我的训练样本距离零向量(原点)多远?”。

当我们去选择k值的时候,我们通过平均平方映射误差除以数据的总变差来表示数据的变化有多大。我们想要这个比值能够小于1%:

$$
\frac{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2
}{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2
}
\le0.01
$$

大部分人在考虑,选择k的方法时,不是直接选择k值,而是这里的数字应该设置为多少:

它应该是0.01还是其它的数?如果选择了0.01,那么用PCA的语言说就是保留了99%的差异性。

数字0.01是人们经常用的一个值,另一个常用的值是0.05。如果选择了0.05,就意味着95%的差异性被保留了。从95到99是人们最为常用的取值范围。

你可能会惊讶的发现,对于许多数据集,即使保留了99%的差异性,可以大幅地降低数据的维度。因为大部分现实中的数据,许多特征变量都是高度相关的。所以实际上大量压缩数据是可能的,而且仍然会保留99%或95%的差异性。

具体实现

那么你该如何实现它呢?

原始的算法

有一种方式是从1开始,依次递增k的值,尝试检查差异性是否达到预设值。

例如:

  • 尝试$k=1$时的PCA。
  • 计算出$U_{reduce},z^{(1)},z^{(2)},…,z^{(m)},x^{(1)}_{approx},…,x^{(m)}_{approx}$
  • 检查是否满足:

$$
\frac{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2
}{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2
}
\le0.01
$$

如果满足条件,我们就用$k=1$;但如果不满足,那么我们接下来尝试$k=2$,然后我们要重新走一遍这整个过程。

以此类推一直试到上面不等式成立为止。

一种更快的算法

可以想象,上面这种方式非常低效。每次尝试使用新的$k$值带入计算时,整个计算过程都需要重新执行一遍,还好我没有一种更快捷方便的计算方式。

当你调用svd来计算PCA时,你会得到三个矩阵[U,S,V]:

1
[U,S,V]=svd(Sigma)

除了之前提到的U矩阵之外,当你对协方差的矩阵Sigma调用svd时,我没还会得到中间的这个S矩阵。S矩阵是一个$n×n$的对角矩阵,它只有在对角线上的元素不为0,其余的元素都是0。并且显而易见,它是一个方阵:

$$
\begin{equation}
S=\left[
\begin{matrix}
s_{11}&0&0&…&0\\
0&s_{22}&0&…&0\\
0&0&s_{33}&…&0\\
┋&┋&┋&…&┋\\
0&0&0&…&s_{nn}\\
\end{matrix}
\right]
\end{equation}
$$

可以证明的是(我不会在此证明)实际上对于一个给定的k值,可以通过这个$S$矩阵方便的计算出差异性那一项的值:

$$
\frac{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2
}{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2
}
=
1-\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}}
$$


例如,假设差异性要满足小于$0.01$,那么可以得出:

$$
\frac{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2
}{
\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2
}
=
1-\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}}
\le0.01
$$

即:

$$
\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}}
\ge0.99
$$

那么你可以从1开始,慢慢增大$k$的值,来计算上面这个不等式,直到满足为止即可(得到满足上面不等式的最小$k$值)。


通过这种方式,你只需要调用一次svd函数,通过svd给出的S矩阵你就可以通过依次增加$k$值的方式来求解了。这样以来就大幅的提升了计算效率。

总结

总结一下,使用PCA算法时寻找合适$k$值的方法:

  • 首先对协方差矩阵Sigma调用一次svd
1
[U,S,V] = svd(Sigma)
  • 然后使用下面的不等式求得满足条件的最小$k$值:

$$
\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}}
\ge0.99
$$


顺便说一下,即使你想要手动挑选$k$值,如果你想要向别人解释你实现的PCA的性能具体如何,那么一个好方法就是算出这个值:

$$
\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}}
$$

它会告诉你百分之多少的差异性被保留了下来。

如果你把这个数值展现出来,那么熟悉PCA的人们就可以通过它来更好地理解你用来代表原始数据的压缩后的数据近似得有多好。因为有99%的差异性被保留了。

这就是一个平方投影误差的测量指标。它可以带给你对于数据压缩后是否与原始数据相似带来一种很好的直观感受。

应用PCA的建议

视频地址

在之前的课程中,我已经提到过PCA有时可以用来提高机器学习算法的速度。在本节,我将讲解如何在实际操作中来实现。同时列举一些例子来说明PCA在具体应用过程中的使用建议。

PCA应用场景总结

迄今为止我们讨论过的有关PCA的应用中有如下应用场景:

  • 数据压缩
    • 减少内存或者磁盘空间的使用
    • 提升学习算法的效率(k值的选择是关键)
  • 数据可视化
    • 将数据降维到二/三维度进行可视化展示

通过PCA来提高学习算法的速度

举例说明,假如你正在用机器学习来处理图片数据。假设每张输入的图片尺寸是$100×100$的,那么对于每张图片来说,都有10000个像素点。假设样本$x^{(i)}$是包含了10000像素强度值的特征向量,即:

$$
x^{(i)}\in R
$$

那么对于我们的样本数据集来说:

$$
(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),…,(x^{(m)},y^{(m)})
$$

每个样本中,对应的$x^{(i)}$都是10000维的特征向量。

可想而知,这么高维度的数据带入到逻辑回归、神经网络、支持向量机或者任何别的算法中,学习算法运行的都会很慢。

幸运的是,通过使用PCA,我们能够降低数据的维数,从而使得算法能够更加高效地运行。这就是PCA提高算法运算效率的原理。

降维步骤

首先我们需要检查带标签的训练数据集,并提取出输入数据。我们只需要提取出$x$并暂时把$y$放在一边。这一步我们会得到一组无标签的训练集:

$$
x^{(1)},x^{(2)},…,x^{(m)}\in R^{10000}
$$

从$x^{(1)}$到$x^{(m)}$,每个样本都是10000维的数据。然后我们应用PCA降维,我们会得到一个降维后的1000维的数据集:

$$
z^{(1)},z^{(2)},…,z^{(m)}\in R^{1000}
$$

这样我们就得到了一个新的训练集:

$$
(z^{(1)},y^{(1)}),(z^{(2)},y^{(2)}),…,(z^{(m)},y^{(m)})
$$

现在,我可以将这个已经降维的数据集输入到学习算法中,来得出假设函数,并把降维后的数据作为输入带入,做出预测。

逻辑回归为例:

逻辑回归中,我们得到的假设函数如下:

$$
h_{\theta}(z) = \frac{1}{1+e^{-\theta^{T}z}}
$$

我们将$z$向量作为输入带入,并得出一个预测值。

最后,如果你有一个新的样本$x$,那么你所要做的是将你的测试样本$x$通过同样的PCA降维之后,你会得到这个样本所对应的$z$。然后将这个$z$值带入到这个假设函数中进行预测。

注意(重要):

最后要注意一点,PCA定义了从$x$到$z$的对应关系,这种对应关系只可以通过在训练集上运行PCA定义出来。

具体来讲,这种PCA所学习出的对应关系,所做的就是计算出一系列的参数。这些参数这就是特征缩放均值归一化以及降维矩阵$U_{reduce}$。但是对于降维矩阵$U_{reduce}$中的数据,我们需要使我们的参数唯一地适应训练集,而不是适应交叉验证或者测试集。因此我们通过在训练集中找到了降维矩阵$U_{reduce}$,我们就可以将同样的对应关系应用到其他样本中了,比如交叉验证数集样本,或者用在测试数据集中。

总结一下,当你在运行PCA的时候,只是在训练集那一部分来进行的,而不是在交叉验证的数据集或者测试集上运行。在训练集上运行PCA后,得到了从$x$到$z$的映射,然后你就可以将这个映射应用到交叉验证数据集,和测试数据集中。

通过这个例子中的这种方式,我们讨论了将数据从上万维降到千维。在实际应用场景中,我们经常发现,将数据降维到原有维度的五分之一或者十分之一,就分类的精确度而言,降维后的数据对学习算法几乎没有什么影响。如果我们将降维用在低维数据上,我们的学习算法会运行得更快。

PCA的错误使用

有一个值得提醒的频繁被误用的PCA应用场景,那就是使用它来避免过拟合。

具体原因是将高维度数据降维处理后,相较于原先的数据,会更不容易出现过拟合的现象。例如我们将10000维的数据降到了1000维,那么降维后的1000维数据相较于降维前的10000维数据更不容易产生过拟合。

因此有人认为PCA是一种避免过拟合的方法,但在这里,我需要强调一下,为了解决过拟合问题而使用PCA是不适合的!并且我不建议这么做。

如果你比较担心过拟合问题,那么你应该使用正则化方法,而不是使用PCA来对数据进行降维。

PCA会丢失信息:如果你仔细想想PCA的工作原理,你会发现它并不需要使用数据的标签,你只需要设定好输入数据$x^{(i)}$,同时使用这个方法来寻找更低维度的数据近似,在这个过程中,PCA实际上已经把某些信息舍弃掉了。

舍弃掉一些数据,并在你对数据标签$y$值毫不知情的情况下对数据进行降维,所以这或许是一个使用PCA方法的可行之路。如果保留99%的方差,即保留绝大部分的方差,那也是舍弃了某些有用的信息。事实证明,当你在保留99%或者95%或者其它百分比的方差时,结果表明只使用正则化对于避免过拟合,会带来比较好的效果。

同时对于过拟合问题,正则化效果也会比PCA更好,因为当你使用线性回归或者逻辑回归或其他的方法配合正则化时,这个最小化问题实际就变成了y值是什么,才不至于将有用的信息舍弃掉。然而PCA不需要使用到这些标签,它更容易将有价值信息舍弃。

总之,使用PCA的目的是加速学习算法,但不应该用它来避免过拟合

两个建议

真的需要PCA吗?

有时候人们正在设计机器学习系统,或许会写下像这样的计划:

设计一个机器学习系统:

  • 收集训练数据集${(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),…,(x^{(m)},y^{(m)})}$
  • 运行PCA将数据$x^{(i)}$降维到$z^{(i)}$
  • 对降维后的数据训练逻辑回归算法${(z^{(1)},y^{(1)}),(z^{(2)},y^{(2)}),…,(z^{(m)},y^{(m)})}$
  • 在测试集上测试结果:将$x_{test}^{(i)}$映射到$z_{test}^{(i)}$。对映射后的数据集${(z_{test}^{(1)},y_{test}^{(1)}),…,(z_{test}^{(m)},y_{test}^{(m)})}$运行假设函数$h_{\theta}(z)$

通常在一个项目的初期,有些人便直接写出这样的项目计划。

在写下这样一个使用PCA方法的项目计划前,一个非常好的问题是:如果我们在整个项目中不使用PCA效果会怎样?

通常人们不会去思考这个问题,尤其是当人们提出一个复杂的项目并且其中使用了PCA或其它方法时,我经常建议大家在使用PCA之前,首先要想清楚你自己做的是什么,以及你想要做什么。这也是你首先需要在原始数据$x^{(i)}$上考虑的问题。并且根据具体情况来分析是否适合使用PCA,还是直接将原始数据带入到学习算法中。

不要一开始就带入PCA

同时我也建议一开始不要将PCA方法就直接放到算法里,先使用原始数据$x^{(i)}$看看效果。只有一个原因让我们相信算法出现了问题,那就是你的学习算法收敛地非常缓慢,占用内存或者硬盘空间非常大,所以你想来压缩数据。只有当你的$x^{(i)}$效果不好的时候,那么就考虑用PCA来进行压缩数据。

因为我常常看到某些人在项目开始时便将PCA考虑进去,有时他们并没有仔细思考他们做了什么使得结果表现地好,更没有考虑在不用PCA下的情景会是什么样的效果。如果某个数据不使用PCA也可以工作的很好,但我们对于这些数据使用PCA耗费了大量时间,这是不值得的。

然而,尽管有这些需要注意的地方,PCA仍旧是一种不可思议的有用的算法。PCA的使用频率也很高,大部分时候我都用它来加快学习算法。但我认为PCA通常都是被用来压缩数据以减少内存使用或硬盘空间占用的、或者用来可视化数据的。

同时PCA也是一种强有力的无监督学习算法。

坚持原创技术分享,您的支持将鼓励我继续创作!