机器学习之降维算法

降维可以压缩数据，因而使用较少的计算机内存或磁盘空间，加快我们的学习算法。

在数据可视化中，降维也是常用的手段。

PCA算法（Principal Component Analysis）

在PCA中，我们要做的是找到一个方向向量（Vector direction），当我们把所有的数据都投射到该向量上时，我们希望投射平均均方误差能尽可能地小。方向向量是一个经过原点的向量，而投射误差是从特征向量向该方向向量作垂线的长度。

主成分分析与线性回归的比较

尽管主成分分析与线性回归看上去很相似，但两者是两种不同的算法。主成分分析最小化的是投射误差（Projected Error），而线性回归尝试的是最小化预测误差。线性回归的目的是预测结果，而主成分分析不作任何预测。

上图中，左边的是线性回归的误差（垂直于横轴投影），右边则是主要成分分析的误差（垂直于红线投影）。

具体算法：

PCA 减少$n$维到$k$维：

第一步是数据预处理。我们将进行均值归一化(mean normalization)/特征缩放(feature scaling)。普遍的做法是计算出所有特征的均值，然后令 $x_j= x_j-μ_j$。如果特征是在不同的数量级上，我们还需要将其除以标准差 $σ$。

第二步是计算协方差矩阵（covariance matrix）
$$
Σ：
\sum=\dfrac {1}{m}\sum^{n}_{i=1}( x^{(i)}) ( x^{(i)}) ^{T}
$$

第三步是计算协方差矩阵$Σ$的特征向量（eigenvectors）:

在 Octave 里我们可以利用奇异值分解（singular value decomposition）来求解，[U, S, V]= svd(sigma)。

对于一个 $n×n$维度的矩阵，上式中的$U$是一个具有与数据之间最小投射误差的方向向量构成的矩阵。如果我们希望将数据从$n$维降至$k$维，我们只需要从$U$中选取前$k$个向量，获得一个$n×k$维度的矩阵，我们用$U_{reduce}$表示，然后通过如下计算获得要求的新特征向量
$$
z^{(i)}:
z^{(i)}=U^T_{reduce}*x^{(i)}
$$

其中$x$是$n×1$维的，因此结果为$k×1$维度。

选择主成分的数量

主要成分分析是减少投射的平均均方误差：

训练集的方差为：$\dfrac {1}{m}\sum^{m}_{i=1}\left| x^{( i) }\right| ^{2}$

我们希望在平均均方误差与训练集方差的比例尽可能小的情况下选择尽可能小的$k$值。

如果我们希望这个比例小于1%，就意味着原本数据的偏差有99%都保留下来了，如果我们选择保留95%的偏差，便能非常显著地降低模型中特征的维度了。

我们可以先令$k=1$，然后进行主要成分分析，获得$U_{reduce}$和$z$，然后计算比例是否小于1%。如果不是的话再令$k=2$，如此类推，直到找到可以使得比例小于1%的最小$k$ 值（原因是各个特征之间通常情况存在某种相关性）。

还有一些更好的方式来选择$k$，当我们在Octave中调用“svd”函数的时候，我们获得三个参数：[U, S, V] = svd(sigma)。

其中的$S$是一个$n×n$的矩阵，只有对角线上有值，而其它单元都是0，我们可以使用这个矩阵来计算平均均方误差与训练集方差的比例：
$$
\dfrac {\dfrac {1}{m}\sum^{m}{i=1}\left| x^{( i) }-x^{( i) }{approx}\right| ^{2}}{\dfrac {1}{m}\sum^{m}{i=1}\left| x^{(i)}\right| ^{2}}=1-\dfrac {\Sigma^{k}{i=1}S_{ii}}{\Sigma^{m}{i=1}S{ii}}\leq 1%
$$
也就是：
$$
\frac {\Sigma^{k}{i=1}s{ii}}{\Sigma^{n}{i=1}s{ii}}\geq0.99
$$
在压缩过数据后，我们可以采用如下方法来近似地获得原有的特征：
$$
x^{( i) }{approx}=U{reduce}z^{(i)}
$$

压缩重现

PCA算法，我们可能有一个这样的样本。如图中样本$x^{(1)}$,$x^{(2)}$。我们做的是，我们把这些样本投射到图中这个一维平面。然后现在我们需要只使用一个实数，比如$z^{(1)}$，指定这些点的位置后他们被投射到这一个三维曲面。给定一个点$z^{(1)}$，我们怎么能回去这个原始的二维空间呢？$x$为2维，$z$为1维，$z=U^{T}{reduce}x$，相反的方程为：
$$
x{appox}=U_{reduce}\cdot z\ ,\ x_{appox}\approx x
$$

几个错误使用

（一）用来减少过拟合

这样做非常不好，效果也并不优于正则化处理。PCA只是近似地丢弃掉一些特征，它并不考虑任何与结果变量有关的信息，因此可能会丢失非常重要的特征。然而当我们进行正则化处理时，会考虑到结果变量，不会丢掉重要的数据。

(二)滥用PCA

我们经常不管三七二十一就将PCA算法归入我们的学习过程的一部分。吴恩达给出的建议是：当我们在使用PCA时要考虑不用PCA是否能达到我们的目标，只有做不到的时候采取考虑PCA算法。