降维与PCA算法

2019-05-08 本文已影响70人此间不留白

前言

在之前的学习中，已经学习了无监督学习中的K均值算法。除此算法之外，无监督学习还有另外一种新的算法，该算法被称之为降维。使用降维算法的目的之一就是实现数据压缩，数据压缩不仅可以对数据进行优化，减少算法对硬盘空间和内存的消耗，还可以减少算法运行所消耗的时间。

降维

数据压缩

降维，简而言之就是减少数据维度，对于一组数据，可能存在高度冗余的特征。例如同一物体的体积和质量，可以用二维矩阵表示物体的体积和质量特征，但是由于其密度一样，体积和质量特征重合，可以只选择体积或者质量一个特征来表示物体的大小，即也就是降维，将用来表示物体大小的二维矩阵转化为一维向量。
如下图所示的，可以用变量 $(x_1,x_2)$ 表示某种事物，而变量 $(x_1,x_2)$ 之间近似存在着线性关系，可以将二维变量 $(x_1,x_2)$ 投影到一维变量 $z$ 上，用变量 $z$ 的位置表示变量 $(x_1,x_2)$ 的位置，二维变量变为一维变量，减小了数据冗余，实现了数据压缩。

可视化

以上，讨论了降维在对于数据压缩方面的应用。而降维的另外一个作用就是实现数据可视化。对于一个超过三维的高维数据集，很难用图形或者图像化的方式描述这些数据，而通过降维，可以将高维数据转化为二维或者三维，以方便数据可视化的实现。例如，在描述一个国家发展水平方面可以有多项数据作为指标，包括GDP，人均GDP，人均寿命，人均收入，人均消费支出等，将这些指标构成的高维数据及进行可视化是很难实现的。通过降维算法，可以将以上指标化为国家发展指数和国家GDP两个指标，将高维数据集化为二维数据集，如此，对于二维数据集就很容易地实现了可视化操作。如下图所示：

主成分分析算法（PCA算法）

概述

降维实现中，最常用的算法就是主成分分析算法。如下图所示，假设有一个二维数据集需要通过降维算法实现为一维数据集，就像线性回归一样，需要找到一条二维数据集的回归直线，使得二维数据集的每一个点到这条直线的投影距离最小。

推而广之，PCA算法的主要实现思路如下所示：

将 ${n}$ 维数据降维形成 $k$ 维数据时: 寻找 ${k}$ 维向量 ${v_1,v_2,v_3 ……v_k}$ 投影这些数据，并且使得投影误差最小。用线性代数解释就是将这些数据集投影到这 ${k}$ 个向量展开的线性子空间上。如下图所示，三维数据降为二维向量。

注意，线性回归与PCA之间的区别，以二维数据集为例，线性回归是寻找一条拟合直线，根据输入，对输出做出预测，其点到回归直线的距离表示输入值与输出值之间的差值，这个差值所形成的直线一定与 $y$ 轴平行，而PCA算法中，点到向量的距离是点与向量之间的正交距离。如下图所示：

PCA算法的主要实现过程如下所示：

特征缩放/均值标准化
假设有 $m$ 个数据构成的训练集 $x^{(1)},x^{(2)},……x^{(m)}$ ，
则定义 $u_j=\frac{1}{m}\sum_{i=1}^{m}x_j^{(i)}$
则令 $x_j = x_j-u_j$
通过以上特征缩放，能够将相差较大的特征值调整至相同的变化范围。
协方差矩阵(Covariance Matrix)
将 $n$ 维数据降维至 $k$ 维，计算每个特征的协方差矩阵，具体可由如下公式表示：
$A = \frac{1}{m}\sum_{i=1}^{m}(x^{(i)})(x^{(i)})^T$
计算协方差矩阵 $A$ 的特征向量
协方差矩阵 $A$ 总是一个正定矩阵，通过计算这个正定矩阵的特征向量，得到三个矩阵，如下所示：
$[U,S,V] = SVD(A)$

SVD 即是线性代数中的奇异值分解算法。

得到降维后的矩阵
通过以上计算，得到3个 $n*n$ 的方阵，选取矩阵 $U$ 的前 $k$ 个向量，记作 $U_{k}$ ，该矩阵是一个 $k*n$ 的矩阵，若降维后的矩阵用 $Z$ 表示，则有：
$Z = U_{k}^T*x$

$U_{k}^T$ 是一个 $k*n$ 维的矩阵，而 $x$ 是一个 $n*1$ 的矩阵，最后得到的矩阵 $Z\in R^k$

最后，通过以上步骤，实现了使用PCA算法的降维过程。

主成分数量选择

为了尽可能的减小 $k$ 的值，即也就是主成分的数量，应该满足以下计算公式:

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

其中 $x_{approx}^{(i)}$ 表示第 $i$ 个数据的投影值。

压缩重现

通过PCA算法，可以实现数据降维，降维后的数据也可以通过PCA算法得到的参数映射得到原来的高维数据，如下所示：

$x_{approx} = U_k*z$
以上公式中，若 $||x^{(i)}-x_{approx}||^{2}$ 越小，压缩重#

监督学习中使用PCA算法

以上，主要介绍了在无监督学习中是使用PCA算法。但是在实际应用中，有大量的监督学习算法涉及到高维数据，例如，计算机视觉中，经常涉及到图像处理问题。
监督学习中PCA算法的使用如下所示:
假设有数据为 $(x^{(1)},y^{(1)}),(x^{(2)},y^{(2)}),……(x^{(m)},y^{(m)})$ ，
其中， $x \in R^{100}$

以对训练集中的输入变量 $x$ 进行无标签处理，即也就是当作无监督学习中的数据，不进行标签划分；
再使用PCA算法，得到一组新的数据集,得到降维后的数据 $z^{(1)},z^{(2)}……z^{(m)}$ 。
最后对新的数据集 $(z^{(1)},y^{(1)}),(z^{(2)},y^{(2)}),……(z^{(m)},y^{(m)})$ 运行监督学习算法。

注意：只能对训练集使用PCA算法，而不能对交叉验证集和测试集使用。