机器学习(8) -- 降维

核心思想：将数据沿方差最大方向投影，数据更易于区分

简而言之：PCA算法其表现形式是降维，同时也是一种特征融合算法。

对于正交属性空间(对2维空间即为直角坐标系)中的样本点，如何用一个超平面(直线/平面的高维推广)对所有样本进行恰当的表达？

事实上，若存在这样的超平面，那么它大概应具有这样的性质：

• 最近重构性 : 样本点到这个超平面的距离都足够近；

• 最大可分性：样本点在这个超平面上的投影能尽可能分开。

一般的，将特征量从n维降到k维：

• 以最近重构性为目标，PCA的目标是找到k个向量，将所有样本投影到这k个向量构成的超平面，使得投影的距离最小（或者说投影误差projection error最小）。

• 以最大可分性为目标，PCA的目标是找到k个向量，将所有样本投影到这k个向量构成的超平面，使得样本点的投影能够尽可能的分开，也就是使投影后的样本点方差最大化。

注意: PCA和线性回归是不同的，如图10-6所示，线性回归是以平方误差和(SSE)最小为目标；而PCA是使投影(二维即垂直)距离最小；PCA与标记或者预测值完全无关，而线性回归是为了预测y的值。

PCA不是线性回归

两种等价的推导结论是：对协方差矩阵，进行特征值分解，将求得的特征值进行降序排序，再去前k个特征值对应的特征向量构成。

证明看周志华机器学习

PCA为什么要用协方差矩阵？

其中

协方差矩阵

其中表示两个维度之间的协方差

若要方差最大，只要特征值最大即可。

算法步骤

输入：训练集：

• 步骤一：数据中心化——去均值（(即使得样本和为0)），根据需要，有的需要归一化——Normalized；
• 步骤二：求解协方差矩阵；
• 步骤三：利用特征值分解/奇异值分解 求解特征值以及特征向量；
• 步骤四：利用特征向量构造投影矩阵；选择前k个特征值对应的特征向量，Ureduce = U( : , 1:k); 其中Ureduce为n*k的矩阵
• 步骤五：利用投影矩阵，得出降维的数据。利用Ureduce就可以得到投影后的样本值
   （z⁽ⁱ⁾为k*1的向量）

使用要点

1. PCA通常用来加快监督学习算法。

2. PCA应该只是通过训练集的特征量来获取投影矩阵，而不是交叉检验集或测试集。但是获取到之后可以应用在交叉检验集和测试集。

3. 避免使用PCA来防止过拟合，PCA只是对特征量X进行降维，并没有考虑Y的值；正则化是防止过拟合的有效方法。

4. 不应该在项目一开始就使用PCA: 花大量时间来选择k值，很可能当前项目并不需要使用PCA来降维。同时，PCA将特征量从n维降到k维，一定会丢失一些信息。

5. 仅仅在我们需要用PCA的时候使用PCA: 降维丢失的信息可能在一定程度上是噪声，使用PCA可以起到一定的去噪效果。

6. PCA通常用来压缩数据以加快算法，减少内存使用或磁盘占用，或者用于可视化(k=2, 3)。

ICA独立成分分析

比较：

一、PCA和ICA的用途完全不同。如果只在意数据的能量或方差、假设噪声或不感兴趣的信号都比较微弱，那么用PCA就能把主要信号留下来。在某种意义上，ICA更智能——它不在意信号的能量或方差，只看独立性。所以给定的待分析的混合信号经任意的线性变换都不会影响ICA的输出结果，但会严重影响PCA的结果。

二、若多于一个原始独立信号是正态的，那么ICA的结果不唯一。若数据在两个正交方向方差相同（比如协方差是isotropic的），PCA结果不唯一。

简单讲：PCA是一个降维的过程，ICA则是帮助你从多个维度分离有用数据的过程。

线性分类与Principal Component Analysis

LDA线性判别分析：

LDA的全称是Linear Discriminant Analysis（线性判别分析），是一种supervised learning。

Discriminant这次词我个人的理解是，一个模型，不需要去通过概率的方法来训练、预测数据，比如说各种贝叶斯方法，就需要获取数据的先验、后验概率等等。

LDA的原理是，将带上标签的数据（点），通过投影的方法，投影到维度更低的空间中，使得投影后的点，会形成按类别区分，一簇一簇的情况，相同类别的点，将会在投影后的空间中更接近。

因为LDA是一种线性分类器。对于K-分类的一个分类问题，会有K个线性函数：

当满足条件：对于所有的j，都有Yk > Yj,的时候，我们就说x属于类别k。

对于每一个分类，都有一个公式去算一个分值，在所有的公式得到的分值中，找一个最大的，就是所属的分类了。

上式实际上就是一种投影，是将一个高维的点投影到一条高维的直线上，LDA最求的目标是，给出一个标注了类别的数据集，投影到了一条直线之后，能够使得点尽量的按类别区分开，当k=2即二分类问题的时候，如下图所示：

红色的方形的点为0类的原始点、蓝色的方形点为1类的原始点，经过原点的那条线就是投影的直线，从图上可以清楚的看到，红色的点和蓝色的点被原点明显的分开了，这个数据只是随便画的，如果在高维的情况下，看起来会更好一点。

 

下面我来推导一下二分类LDA问题的公式：

假设用来区分二分类的直线（投影函数)为：

LDA分类的一个目标是使得不同类别之间的距离越远越好，同一类别之中的距离越近越好，所以我们需要定义几个关键的值。

类别i的原始中心点为：（Di表示属于类别i的点)

类别i投影后的中心点为

衡量类别i投影后，类别点之间的分散程度（方差）为：

最终我们可以得到一个下面的公式，表示LDA投影到w后的损失函数：

我们分类的目标是，使得类别内的点距离越近越好（集中），类别间的点越远越好。分母表示每一个类别内的方差之和，方差越大表示一个类别内的点越分散，分子为两个类别各自的中心点的距离的平方，我们最大化J(w)就可以求出最优的w了。想要求出最优的w，可以使用拉格朗日乘子法，但是现在我们得到的J(w)里面，w是不能被单独提出来的，我们就得想办法将w单独提出来。

我们定义一个投影前的各类别分散程度的矩阵，这个矩阵看起来有一点麻烦，其实意思是，如果某一个分类的输入点集Di里面的点距离这个分类的中心店mi越近，则Si里面元素的值就越小，如果分类的点都紧紧地围绕着mi，则Si里面的元素值越更接近0.

带入Si，将J(w)分母化为：

同样的将J(w)分子化为：

这样损失函数可以化成下面的形式：

这样就可以用最喜欢的拉格朗日乘子法了，但是还有一个问题，如果分子、分母是都可以取任意值的，那就会使得有无穷解，我们将分母限制为长度为1（这是用拉格朗日乘子法一个很重要的技巧，在下面将说的PCA里面也会用到，如果忘记了，请复习一下高数），并作为拉格朗日乘子法的限制条件，带入得到：

这样的式子就是一个求特征值的问题了。

对于N(N>2)分类的问题，我就直接写出下面的结论了：

这同样是一个求特征值的问题，我们求出的第i大的特征向量，就是对应的Wi了。

线性判别分析LDA原理总结

LDA算法流程

现在我们对LDA降维的流程做一个总结。

　　　　输入：数据集$D=\{(x_1,y_1), (x_2,y_2), ...,((x_m,y_m))\}$,其中任意样本$x_i$为n维向量，$y_i \in \{C_1,C_2,...,C_k\}$，降维到的维度d。

　　　　输出：降维后的样本集$D′$

　　　　　　1) 计算类内散度矩阵$S_w$

　　　　　　2) 计算类间散度矩阵$S_b$

　　　　　　3) 计算矩阵$S_w^{-1}S_b$

　　　　　　4）计算$S_w^{-1}S_b$的最大的d个特征值和对应的d个特征向量$(w_1,w_2,...w_d)$,得到投影矩阵$W$

　　　　　　5)对样本集中的每一个样本特征$x_i$,转化为新的样本$z_i=W^Tx_i$

　　　　　　6) 得到输出样本集$D'=\{(z_1,y_1), (z_2,y_2), ...,((z_m,y_m))\}$

　　　以上就是使用LDA进行降维的算法流程。实际上LDA除了可以用于降维以外，还可以用于分类。一个常见的LDA分类基本思想是假设各个类别的样本数据符合高斯分布，这样利用LDA进行投影后，可以利用极大似然估计计算各个类别投影数据的均值和方差，进而得到该类别高斯分布的概率密度函数。当一个新的样本到来后，我们可以将它投影，然后将投影后的样本特征分别带入各个类别的高斯分布概率密度函数，计算它属于这个类别的概率，最大的概率对应的类别即为预测类别。

　　　由于LDA应用于分类现在似乎也不是那么流行，至少我们公司里没有用过，这里我就不多讲了。

LDA vs PCA

LDA用于降维，和PCA有很多相同，也有很多不同的地方，因此值得好好的比较一下两者的降维异同点。

首先我们看看相同点：

　　　　1）两者均可以对数据进行降维。

　　　　2）两者在降维时均使用了矩阵特征分解的思想。

　　　　3）两者都假设数据符合高斯分布。

我们接着看看不同点：

　　　　1）LDA是有监督的降维方法，而PCA是无监督的降维方法

　　　　2）LDA降维最多降到类别数k-1的维数，而PCA没有这个限制。

　　　　3）LDA除了可以用于降维，还可以用于分类。

　　　　4）LDA选择分类性能最好的投影方向，而PCA选择样本点投影具有最大方差的方向。

这点可以从下图形象的看出，在某些数据分布下LDA比PCA降维较优。

当然，某些某些数据分布下PCA比LDA降维较优，如下图所示：

LDA算法小结

LDA算法既可以用来降维，又可以用来分类，但是目前来说，主要还是用于降维。在我们进行图像识别图像识别相关的数据分析时，LDA是一个有力的工具。下面总结下LDA算法的优缺点。

LDA算法的主要优点有：

　　　　1）在降维过程中可以使用类别的先验知识经验，而像PCA这样的无监督学习则无法使用类别先验知识。

　　　　2）LDA在样本分类信息依赖均值而不是方差的时候，比PCA之类的算法较优。

LDA算法的主要缺点有：

　　　　1）LDA不适合对非高斯分布样本进行降维，PCA也有这个问题。

　　　　2）LDA降维最多降到类别数k-1的维数，如果我们降维的维度大于k-1，则不能使用LDA。当然目前有一些LDA的进化版算法可以绕过这个问题。

　　　　3）LDA在样本分类信息依赖方差而不是均值的时候，降维效果不好。

　　　　4）LDA可能过度拟合数据。

SVD的一些性质

对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上的比例。也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。也就是说：

$A_{m \times n} = U_{m \times m}\Sigma_{m \times n} V^T_{n \times n} \approx U_{m \times k}\Sigma_{k \times k} V^T_{k \times n}$

　　　　其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵$U_{m \times k},\Sigma_{k \times k} ,V^T_{k \times n}$来表示。如下图所示，现在我们的矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。

　　　　由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。