PCA降维算法

2020-02-06 本文已影响0人爱吃鱼的夏侯莲子

降维是机器学习中很重要的一种思想。在机器学习中经常会碰到一些高维的数据集，它们会占用计算机的内存和硬盘空间，而且在运算时会减缓速度。
降维能够使得数据量被压缩，加快运算速度，减小储存空间，以及方便可视化的观察数据特点。

PS：在降维中，我们减少的是特征种类而不是样本数量，样本数量m不变，特征值数量n会减少。

主成分分析算法（PCA）

一种常用的降维算法是主成分分析算法（Principal Component Analysis），简称PCA。

PCA是通过找到一个低维的线或面，然后将数据投影到线或面上去，然后通过减少投影误差（即每个特征到投影的距离的平均值）来实现降维。

上图是一个包含二维特征值的样本集。黑色的叉代表样本，红色的线表示找到的低维的线，绿色的叉则是样本投影在线上的位置。而它们的投影距离就是PCA算法所需要考虑的。

通过上图可以看出PCA算法就是找出一个线，在数学上就是一个向量，使得其他样本投影到该向量上的距离最小。

推而广之：
一般情况下，将特征值的维度从n降到k，就是找到k个向量 $u^{(1)},u^{(2)},...,u^{(k)}$ ，使得样本在这些向量上的投影最小。

例如，2维降到1维，就是找到1个向量，即一条线；3维降到2维，就是找到2向量，即一个平面。

PCA和线性回归的区别

在线性回归中，最小化的是没有样本到预测线的平方误差，它们之间的距离是垂直距离。
在PCA中，最小化的是投影距离，或者说是正交距离。

算法过程

数据处理

假设有m个样本集： $x^{(1)},x^{(2)},...,x^{(m)}$
下面需要对数据做一下特征值缩放或者均值归一化。
先计算出平均值，然后用样本值减去平均值。
$\mu_i=\frac{1}{m}\sum_{i=1}^m x_j^{(i)}$
然后用 $\frac{x_j^{(i)}-\mu_i}{s_j}$ 替换 $x_j^{(i)}$ ， $s_j$ 可以是数据最大值最小值的范围或者标准差。

算法部分

计算协方差矩阵（covariance matrix）
$\Sigma = \frac{1}{m}\sum^m_{i=1}(x^{(i)})(x^{(i)})^T$
PS：假设 $x^{(i)}$ 为一个n维向量（n * 1）, $(x^{(i)})(x^{(i)})^T$ 则是一个n维方阵。
计算协方差矩阵的特征向量（eigenvectors）
可以通过奇异值分解（SVD）来获得：

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

我们需要的就是矩阵U，他是一个n维方阵 $U \in \mathbb{R}^{n \times n}$ ，它的每一列就是我们需要的向量：
$U = \left[ \begin{matrix} u^{(1)} & u^{(2)} & ... & u^{(n)} \\ \end{matrix} \right]$

获取Ureduce矩阵
当要从n降维到k，从矩阵U中取前k个向量就可以了：
$Ureduce = \left[ \begin{matrix} u^{(1)} & u^{(2)} & ... & u^{(k)} \\ \end{matrix} \right]$
计算投影后的矩阵
$z^{(i)} = Ureduce^T \cdot x^{(i)}$
PS： $Ureduce^T$ 是一个 k×n 维的矩阵， $x^{(i)}$ 是一个n×1维的向量，两者点乘后就是一个z×1的向量，这样就得到了我们需要的。

回到原来的维度

使用 $Ureduce$ 矩阵可以降维：
$z^{(i)} = Ureduce^T \cdot x^{(i)}$
那么要回到原来的维度上去就需要：
$x_{approx}^{(i)} = Ureduce \cdot z^{(i)}$

这里我们只能得到原来的近似值

选择降维的维度

$x_{approx}^{(i)}$ 与 $x^{(i)}$ 近似相等，两者之间的差就是投影误差，或平均平方映射误差：
$\frac{1}{m}\sum_{i=1}^m || x^{(i)} - x_{approx}^{(i)} ||^2$

数据的总变差（total variation），即样本的长度平方的均值：
$\frac{1}{m}\sum_{i=1}^m || x^{(i)} ||^2$

选择维度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} \leq 0.01$

表示平方投影误差除以总变差的值小于0.01，用PCA的语言称之为保留了99%的差异性。
PS：这个值是可以变化的，可以是95%，90%，85%等等。

使用循环验证的办法：
初始化 $k=1$ ，然后计算出 $Ureduce$ ，通过 $Ureduce$ 计算出 $z^{(1)},z^{(2)},...,z^{(m)}$ 和 $x_{approx}^{(1)},x_{approx}^{(2)},...,x_{approx}^{(m)}$ ，然后通过上方的公式计算出值是不是小于0.01。
如果不是，增加k值，直到获得最小的k值满足条件。

快捷办法

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

通过奇异值分解的到的矩阵 $S$ 是一个n维的对角矩阵：
$S = \left[ \begin{matrix} s_{11} & 0 & ... & 0 \\\ 0 & s_{22} & ... & 0 \\\ ... & ... & ... & ... \\\ 0 & 0 & ... & s_{nn} \end{matrix} \right]$

通过这个矩阵可以来计算：
$1 - \frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}} \leq 0.01$
也可以用下面的式子：
$\frac{\sum_{i=1}^k S_{ii}}{\sum_{i=1}^n S_{ii}} \geq 0.99$
这种方法就非常快捷高效。

使用PCA的建议

我们在训练集上通过PCA获得矩阵 $Ureduce$ ，在交叉验证集和测试集上就不能再使用PCA来计算矩阵了，而是直接用训练集里的矩阵来映射交叉验证集和测试集上的数据。

PCA最常用的就是压缩数据，加速算法的学习，或者可视化数据。

压缩数据
将数据压缩到合适的维度，用来加速算法。
数据可视化
将数据的维度降到2或3维以便画出图像。

PCA的错误用法，用来防止算法过拟合
算法过拟合的原因之一是算法过于复杂，特征值的维度过高，使用PCA可以降低维度，看起来会有效，但是实际上效果很差。防止算法过拟合还是使用正则化的方法来实现。

还有一个注意点。就是在设计一个机器学习算法时，不用一开始就考虑降维，先在不使用PCA的条件下设计算法，当算法出现问题，例如，算法计算过慢，占用大量内存...，之后当确定需要使用PCA的时候再继续使用。

转载自：
https://codeeper.com/2020/02/06/tech/machine_learning/dimensionality_reduction.html