【数据挖掘】解码数据降维：主成分分析（PCA）和奇异值分解（SVD）

译者按：当拥有非常高纬度的数据集时，给数据降低纬度对于分析来说是非常重要的。降维要求分析人员在最大程度降低数据纬度的同时，尽可能多的保留原数据中包含的信息。主成分分析（PCA）是降维的常用方法之一，而奇异值分解（SVD）则是实现主成分分析的重要手法。本文在不涉及太多数学细节的条件下，形象生动地解析数据降维的过程，并通过人脸识别的例子，直观地展示了主成分分析的显著降维效果。

每一天，IBM会产生250万的三次方比特的数据，而这些生成的数据中的大部分是高纬度的。顾名思义，为使工作更为有效，给数据降维是必不可少的。

最被人熟知的降维技术之一，是过滤。这种方法是舍弃大多数维度，而只关注那些未被舍弃的。但是，这种方法并不总是可行。比如当你在处理图像数据时，像素的数量代表图像中维度的个数。当你拥有很多很多的维度，此时你并不会想为了使你的整个数据集合理化而舍弃维度。

当你的数据集的维度增加，那么数据集所占空间的大小也将增加，某种意义上来说，也就是你拥有的数据将变得越来越离散（稀疏）。一种思考的方法是，一个比较高纬度的数据集可能存在于某个较高维度的复印簿里，当你增加维度的数量时，这个复印簿将变得越来越大（厚）。

当你想要构建任何统计模型，你必须要增加所拥有的数据点和样本的数量，而不幸的是这样也将会使你拥有数据的维度出现指数级的增长。你拥有的维度越高，想要得到运用统计方法得到推论时需要的数据就越多。基本思想是，数据集的容量必须要大于数据集的维度。

这里有一张图片（如下图），图片拥有64*64的像素（即4096个维度）。为了降低纬度，你会想要把这些高纬度的数据用线性或非线性的变换投影到一个比较低维度的子平面上。

广泛运用的方法是线性投影，而线性投影中最主要的方法是主成分分析（Principal Component Analysis, PCA）。

主成分分析（PCA）

假设你拥有一个在2D平面（X1和X2）上的数据集，而你想要将它们渐进到一个比较低维度的嵌入平面上。显而易见地，向量V（已在下图中标注）对于这个数据集来说已经是一个比较不错的渐进方式。与其为数据集中的每一个点存储两个坐标（译者注：即X1和X2上的坐标），渐进之后，你将只存储一个标量值加上一个向量V，而这个向量V几乎横跨数据集中所有的点，所以你只需要对它存储一次。所以，对于数据集中的每一个点，你只需要存储这个标量值s，而它就给出了沿着向量V的距离。

在下面的图里，我们把数据集中的所有点都投影到了向量V上。接下来还需要从最小二乘的角度，尝试把原数据与投影之间的差异最小化。你应该选择一个能够使得残差平方最小的向量V。在这里，残差指数据点与它在向量V上投影的差异。

在这种情况下，投影是垂直于向量V的。你需要最小化数据的残差平方和，通过使数据点的残差平方和最小来选择向量V。你会发现，选出来的这个向量，也正好可以用最小二乘误差来重建原始数据的向量。直观来说，这是非常合理的，因为你是从数据集最扩散最平铺的方向来选择的向量V。当然，你也可以将这种方法扩展到多个成分的条件下。这就是我们称为“主成分”的主要成分，而向量V则是用来将数据投影上去的向量。接着，你可以重复这个进程，寻找拥有第二大数据方差的第二个成分，也就是下图中principalcomp2的方向。

（主成分向量是正交的。）

理解主成分分析（PCA）和最小二乘法（OLS）之间的差别的非常重要的。在这里我建议您移步http://stats.stackexchange.com/questions/2691/making-sense-of-principal-component-analysis-eigenvectors-eigenvalues浏览这方面的例子。

总而言之，PCA的主要思想就是把拥有的数据投影到那些子平面上（也就是主成分上），从而最大化投影数据的方差。

奇异值分解（SVD）

主成分分析算法通过以下步骤实现：

1）提取数据的均值；

2）用每个维度自有的方差来衡量它们；

3）计算协方差矩阵S。在这里假设X为数据矩阵；

4）计算协方差矩阵前K个最大的特征向量。这些特征向量就是数据集的主成分。

注解：特征向量与特征值是成对出现的。每个特征向量都有一个对应的特征值。特征向量表示直线（竖直的、水平的、45度角的等等）的方向。一个特征值是一个数字，告诉你这个方向包含了多少数据中所带的方差，同时也是一个数字，让你知道数据在这条直线上的离散程度。

但是，当X是一个规模很小或者很大的矩阵时，这些操作（即前述的PCA实现步骤）是非常昂贵的。所以，计算主成分最优的方法是使用奇异值分解（Singular ValueDecomposition, SVD）。SVD是现有的最优秀的线性转换方法中的一种。

你可以拿任意一个矩阵X，它是否是方阵、是否奇异、是否是对角阵，都无所谓，你都可以将它分解成三个矩阵的积（如下图所示）：两个正交矩阵U和V，还有一个对角阵D。正交矩阵与原矩阵是同纬度的，对角阵是方阵，它的维度是k*k（k是原矩阵中变量的个数），然后V也是一个方阵。

在这里我将要在S（协方差矩阵）上演算SVD，以获得它的特征向量。

这里有一些关于因式分解结果的有趣注释：

1）矩阵U的列组成S的特征向量；

2）矩阵D是一个对角阵。对角线上的值称为特征值，它们在对角线上是逐个递减的。

这种方法与直接进行主成分分析是等价的，但却是一种更具有鲁棒性的方法。你只需要将SVD运用在你的原始矩阵上即可。

为什么SVD会和降维有关？

下图表示了如何将k个维度降低到q个维度（k>q）。如果将列向量的个数从k减少到q，那么在这个例子中，你就得到了一个q维的超平面。D的值将告诉你这次降维所保留下来的方差。

想要知道降维捕捉了多少原数据的方差，最好的办法是做一张碎石图（Scree Plot）。

事实证明，每个主成分的方差与d的平方（矩阵D的对角元素）有关。在碎石图（上图）中，第一个主成分解释了37%的方差，紧接着解释的方差迅速下降。比较好的方式，是寻找能解释原数据所带方差80%-90%的主成分。

举例：图像识别（Image Recognition）

假设你的任务是识别人们的脸，从给人们拍照开始，接着制作小图，并将所有的脸都摆在图的中心使它们粗略地对齐（如下图）。

假设这些图像都是64*64的像素。那么你就有了4096个维度，把每个图像展开成为一个向量，然后将它们堆积起来组成你的数据矩阵。每一个像素都是一个维度，每一行代表一个不同的人（如下图）。

至此，你就有了如上图所示的数据矩阵。将PCA应用在这个矩阵上，你会得到一些我们称之为特征脸（Eigenfaces）的东西（如下图所示）。左手边的图像就是所谓的平均脸。右手边第一个图像大致解释了“左右”维度的方差，第二个图像大约解释了“前后”维度的方差。

在下图中，你可以亲自观察各成分的方差。事实证明，想要解释这张图（下图左）90%的方差，你需要50个特征向量。

正如你所看到的（上图右），在提取了50个特征向量之后，一个非常不错的面部重建产生了。如此，你就实现了从4096个维度到50个维度的蜕变，并且不会在质量上打太多折扣。

本人写作此文的目的，是希望在不涉及太多数学细节的情况下，给读者提供关于降维、PCA和SVD的比较宽泛的概念。