降维（Dimensionality Reduction）也是一种无监督学习。

目标

降维的目标之一是数据压缩，使得硬盘、内存占用更少，并且对学习算法进行加速。

如上图所示，通过映射我们可以将二维平面的特征数据 $(x_1,x_2)$ 投影到一维的直线上 $(z_1)$ 。也可以把三维空间的特征数据 $(x_1,x_2,x_3)$ 投影到二维平面上 $(z_1,z_2)$ ，如下图所示：

降维的另一个目标则是数据可视化，这可以帮助我们更好地了解数据，从而更好地对算法进行优化。

上图为全世界各个国家的各项指标统计情况，每个国家包含50个特征，这很难可视化。我们尝试将 50 维数据降到 2 维，并且将其在二维平面上画出来，如下图所示：

这时的两个特征 $(z_1,z_2)$ 已经不是具有单个物理意义的特征，通过画图可以发现， $z_1$ 是国家总体的经济活跃度，国家 GDP 等的综合体现，而 $z_2$ 是个人经济活跃度，人均 GDP，人均幸福指数，人均收入，医疗保障等的综合体现。

PCA

PCA（主成分分析）是解决降维问题最常用的算法。如图，PCA 会将数据投影到一个低维平面（或直线）上，使得原数据到投影数据的距离（即投影误差）最小。为了计算出这个低维平面，PCA 要尝试找到一个向量 $u$ ，图中是一维向量（即直线），要找一个能够最小化投影误差的方向，从而得到最小的重构误差，比如 $u^{(1)}$ 这条向量延展的直线。无论是 $u^{(1)}$ 还是 $-u^{(1)}$ ，都定义了相同的直线。如果有 N 维数据，目标是要降到 K 维，那么需要寻找 K 个向量 $u_1,u_2,\cdots,u_k$ ，将数据投影到 K 个向量展开的线性子空间上，也就是 K 维平面，来对数据进行投影，并最小化投影误差。如下图是从 3 维降到 2 维，就需要两个方向的向量，因为两个向量即可定义一个 2 维平面。

下图展示了线性回归和 PCA 的区别，线性回归是拟合一条直线，最小化点到直线的平方误差，点到直线的垂直距离是和 $x$ 轴垂直的。而 PAC 是计算点到投影平面的距离，即正交距离，是与投影平面垂直的。线性回归是根据给定 $x$ 值来预测 $y$ 的值。而 PAC 是拟合投影平面，用投影的低维数据来表示原有的高维数据。

PCA 计算过程

在应用 PCA 前，需要对数据进行预处理，包括均值标准化和特征缩放，使得特征数据的均值为 0，且数值在可比较的范围内。对于均值标准化，首先计算每个特征的均值，用原特征值 $x_j^{(i)}$ 减去其均值 $u_j$ 的结果作为新的特征值，即 $x_j^{(i)}=x_j^{(i)}-u_j$ ，其中 $u_j=\frac{1}{m}\sum_{i=1}^mx_j^{(i)}$ ，这将使得每个特征的均值正好为 0。如果特征值的差异较大，则需在均值标准化的基础上再除以一个值 ${s_j}$ （该值可以是最大值与最小值的差也可以是标准差），将特征值限制在一定范围之内，即 $x_j^{(i)}=\frac{x_j^{(i)}-u_j}{s_j}$ 。

为了得到 K 维向量 $u_1,u_2,\cdots,u_k$ ，和低维数据 $z$ 。首先，PCA 需要计算协方差矩阵 $\Sigma$ ：
$\Sigma=\frac{1}{m}\sum_{i=1}^n (x^{(i)})(x^{(i)})^T$

协方差矩阵 $\Sigma$ 可以通过 SVD （奇异值分解）计算得出，由于 $(x^{(i)})$ 是 N * 1 维的向量， $(x^{(i)})^T$ 是 1 * N 维的向量，所以 $(x^{(i)})(x^{(i)})^T$ 是 N * N 的矩阵，所以 $\Sigma$ 也是一个 N * N 的矩阵。SVD 的结果会输出三个矩阵 $U,S,V$ ，我们只需要其中的矩阵 $U$ ， $U$ 也是一个 N * N 的矩阵， $U$ 矩阵的列为 $u_1,u_2,\cdots,u_n$ ，如果我们想要将数据从 N 维降到 K 维，只需要提取前 K 个向量 $u_1,u_2,\cdots,u_k$ ，这时我们就得到了 K 个方向，即数据投影的方向。即通过 N * N 维的矩阵 $U$ 得到 N * K 维的矩阵 $U_{reduce}$ 。

接下来我们要通过原始数据集 $x$ ，计算出低维数据 $z$ 。 $z=U_{reduce}^T\cdot x$ ，其中 $U_{reduce}^T$ 是 K * N 维的矩阵， $x$ 是 N * 1 维的矩阵，所以结果 $z$ 是 K * 1 维的矩阵，即 K 维向量。

协方差矩阵 $\Sigma$ 的向量化计算为：
$\Sigma=\frac{1}{m}\cdot x^T \cdot x$

通过提取 $U$ 矩阵的前 K 列，计算得出低维数据 $z$ ：
$z=U_{reduce}^T \cdot x$

原始数据重构

有时我们会想要通过压缩的低维数据 $z$ 来重构原有的高维数据 $x$ 。

由于 $z=U_{reduce}^T \cdot x$ ，原始数据 $x$ 的近似值 $x_{approx}=U_{reduce}*z$

其中 $U_{reduce}$ 是 N * K 维的向量， $z$ 是 K * 1 维的向量，所以 $x_{approx}$ 是 N 维向量，如果投影误差不是很大的话， $x_{approx}$ 会接近 $x$ 。

主成分数量 K 的选择

PCA 的目的是减小投影误差平方的均值（即 $x$ 和 $x$ 在低维平面的投影距离的平方和的均值）：
$\frac{1}{m}\sum_{i=1}^m||x^{(i)}-x_{approx}^{(i)}||^2$

数据集的总方差等于每个训练样本的平均长度（即 $x$ 到原点的距离和的均值）：
$\frac{1}{m}\sum_{i=1}^m||x^{(i)}||^2$

限定 K 值可以使得上面两个公式的比值小于一个阈值，如 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} < 0.01$

即如果选择的 K 使得平均投影误差平方 / 数据的总方差 < 0.01，代表这个 K 保留了数据 99% 的方差。通常可以先将 K 赋值为 1，计算 $U_{reduce}$ 和 $z^{(1)},z^{(2)},\cdots,z^{(m)}$ 以及 $x_{approx}^{(1)},x_{approx}^{(2)},\cdots,x_{approx}^{(m)}$ ，然后检查平均投影误差平方 / 数据的总方差是否小于 0.01，如果没有则提高 K 值，重复上述计算步骤，直到小于 0.01 为止。

这里有一个相对高效的计算方法，我们利用 SVD 得出 $U,S,V$ ，其中 $S$ 是一个N * N 的方阵，即对角线 $S_{11},S_{22},\cdots,S_{nn}$ 是这个矩阵唯一的非零元素，对角线之外的所有元素都是 0。平均投影误差平方 / 数据的总方差的值可以用下述公式计算得出：
$1-\frac{\sum_{i=1}^KSii}{\sum_{i=1}^NSii}$

这种方式只需要调用一次 SVD 算法即可，所以计算效率更高。

PCA 应用

数据压缩、算法加速

对于数据压缩或算法加速，通常选择的 K 值能够保留数据 99% 的方差。

假设我们需要对像素为 100 * 100 的图片进行分类，输入特征就是 10000 个像素值，计算速度将会非常缓慢。我们可以通过 PCA 将 10000 维特征的训练集 $x$ 映射为 1000 维特征的训练集 $z$ ，然后将 $z$ 输入到学习算法，拟合得到假设函数，接着用训练集得到的 PCA 对验证集和测试集进行映射，再用映射后的数据来进行评估。通常情况下，我们可以利用 PCA 减少 $\frac{1}{5}$ 或 $\frac{1}{10}$ 的维度，减少对内存和硬盘的需求，提高运行效率，并且不影响分类精度。

可视化

对于可视化应用，通常可以设置 K 等于 2 或 3，通过 2D 或 3D 的形式来展示数据。

Bad Case

PCA 并不适合解决过拟合问题，虽然 PCA 可以通过减小特征数来减小过拟合的可能性，但是 PCA 不会学习到标签信息，所以有可能会舍掉一些对学习标签有价值的特征信息。

在项目开始阶段并不适合直接使用 PCA，可以先尝试不使用 PCA，当原始数据达不到目的的情况下再考虑 PCA。

参考

https://study.163.com/course/introduction/1004570029.htm

降维

降维

目标

PCA