机器学习降维算法汇总！

最近看了一些关于降维算法的东西，本文首先给出了七种算法的一个信息表，归纳了关于每个算法可以调节的(超)参数、算法主要目的等等，然后介绍了降维的一些基本概念，包括降维是什么、为什么要降维、降维可以解决维数灾难等，然后分析可以从什么样的角度来降维，接着整理了这些算法的具体流程。主要目录如下:

1. 降维基本概念
2. 从什么角度出发降维
3. 降维算法
- 3.1 主成分分析PCA
- 3.2 多维缩放(MDS)
- 3.3 线性判别分析(LDA)
- 3.4 等度量映射(Isomap)
- 3.5 局部线性嵌入(LLE)
- 3.6 t-SNE
- 3.7 Deep Autoencoder Networks
4. 小结
5.代码附录

图1 不同降维算法对比

这里autoencoder是否去中心化个人觉得还是有点疑问，在处理图像数据的时候，会对输入图片做一个变到0均值的预处理，但是这个操作是针对一张样本内减均值[1]，这里的去中心化指的是针对某一维数据减均值，并不是一个概念。下面开始具体谈谈降维相关的内容。

1.降维基本概念

而为什么可以降维，这是因为数据有冗余，要么是一些没有用的信息，要么是一些重复表达的信息，例如一张512*512的图只有中心100*100的区域内有非0值，剩下的区域就是没有用的信息，又或者一张图是成中心对称的，那么对称的部分信息就重复了。正确降维后的数据一般保留了原始数据的大部分的重要信息，它完全可以替代输入去做一些其他的工作，从而很大程度上可以减少计算量。例如降到二维或者三维来可视化。

2. 从什么角度出发来降维

一般来说可以从两个角度来考虑做数据降维，一种是直接提取特征子集做特征抽取，例如从512*512图中只取中心部分，一种是通过线性/非线性的方式将原来高维空间变换到一个新的空间，这里主要讨论后面一种。后面一种的角度一般有两种思路来实现[2]，一种是基于从高维空间映射到低维空间的projection方法，其中代表算法就是PCA，而其他的LDA、Autoencoder也算是这种，主要目的就是学习或者算出一个矩阵变换W，用这个矩阵与高维数据相乘得到低维数据。另一种是基于流形学习的方法，流形学习的目的是找到高维空间样本的低维描述，它假设在高维空间中数据会呈现一种有规律的低维流形排列，但是这种规律排列不能直接通过高维空间的欧式距离来衡量，如下左图所示，某两点实际上的距离应该是下右图展开后的距离。如果能够有方法将高维空间中流形描述出来，那么在降维的过程中就能够保留这种空间关系，为了解决这个问题，流形学习假设高维空间的局部区域仍然具有欧式空间的性质，即它们的距离可以通过欧式距离算出(Isomap)，或者某点坐标能够由临近的节点线性组合算出(LLE)，从而可以获得高维空间的一种关系，而这种关系能够在低维空间中保留下来，从而基于这种关系表示来进行降维，因此流形学习可以用来压缩数据、可视化、获取有效的距离矩阵等。

图2 流形学习

3. 几种降维方法流程

3.1 主成分分析PCA

这个式子实际上就是表示了线性变换矩阵W在PCA算法中的作用是让原始协方差矩阵C对角化。又由于线性代数中对角化是通过求解特征值与对应的特征向量得到，因此可以推出PCA算法流程(流程主要摘自周志华老师的《机器学习》一书，其中加入了目标和假设用于对比后面的算法。周老师书中是基于拉格朗日乘子法推导出来，本质上而言与[3]都是一样的，这里很推荐这篇讲PCA数学原理的博客[3])。

此外，PCA还有很多变种kernel PCA, probabilistic PCA等等，本文暂时只考虑最简单的PCA版本。

3.2 多维缩放(MDS)

3.3 线性判别分析(LDA)

图3 LDA进行投影(图来源[4])

个人觉得这里的优化目标实际上体现了一个假设，即假设优化目标上下的表达式都是对角矩阵，W的变换使得Sd 与Sw 都变成了对角矩阵。

3.4 等度量映射(Isomap)

目标:降维的同时保证高维数据的流形不变
假设:高维空间的局部区域上某两点距离可以由欧式距离算出
1.由KNN先构造A的一部分，即求出相邻的点并取它们的欧式距离填入Aij，其他的位置全部初始化为无穷大
2.根据最短路径算法(Dijkstra算法)找到距离比较近的点之间的路径并填入距离
3.将距离矩阵A作为MDS的输入，得到输出

3.5 局部线性嵌入(LLE)

基于上面的假设，首先想办法来求解这个权重，假设每个样本点由周围K个样本求出来，那么一个样本的线性组合权重大小应该是1∗K，通过最小化reconstruct error重构误差来求解，然后目标函数对f求导得到解。

求出权重之后，代入低维空间的优化目标

来求解Z，这里将F按照 N∗K 排列起来，且加入了对Z的限制。这里用拉格朗日乘子法可以得到 MZ=λY 的形式，从而通过对M进行特征值分解求得Z。

输出:降维后矩阵Z
目标:降维的同时保证高维数据的流形不变
假设:高维空间的局部区域上某一点是相邻K个点的线性组合，低维空间各维正交
1.由KNN先构造A的一部分，即求出K个相邻的点，然后求出矩阵F和M
2.对M进行特征值分解
3.取前d个非0最小的特征值对应的特征向量构成Z(这里因为最小化目标，所以取小的特征值)

3.6 t-SNE

同时将低维空间两个点的相互关系或者说相似程度也用联合概率来表示，假设在低维空间中两点间欧式距离服从一个自由度的学生t分布，那么在低维空间中两个点的距离概率在所有的两个点距离概率之中的比重作为它们的联合概率。

需要注意的是，这个算法将低维数据作为变量进行迭代，所以如果需要加入插入新的数据，是没有办法直接对新数据进行操作，而是要把新数据加到原始数据中再重新算一遍，因此T-sne主要的功能还是可视化。

3.7 DeepAutoencoder Networks

图4 Autoencoder网络结构图

然而在实际的实现网络过程中，整个网络实际上层数只是图4中的一半，即4层网络，2000-1000-500-30的全连接结构。因为权重参数实际上在encoder和decoder中是相同的，enocoder过程是上一层的节点值乘以权重得到这一层的节点值，而decoder是这一层节点值与权重矩阵的转置相乘得到上一层的节点值。下图[7]更加清晰的展示了每一层实际的结构，包括一次前向传播和后向传播，因此可以拿最顶层的值作为网络的降维输出来进行其他的分析，例如可视化，或者作为压缩特征使用。

图5 Autoencoder层间结构

4.小结

本文主要重点放在算法流程是什么，每一步具体做了什么，有的地方可能理论阐述还不够清晰。但是有意思的是除了t-sne和autoencoder之外，其他的几种降维算法都是基于构造某个矩阵，然后对矩阵进行特征值分解，得到相关的ZZ或者WW。Laplacian Eigenmaps拉普拉斯特征映射没有完整研究，但是看算法最后也是选择前d个最小非零特征值，这个很有意思，就是数学功底不好，暂时想不通为什么基于特征值的效果这么好。而比较一层的autoencoder和PCA，假设autoencoder的目标函数是最小化均方误差，虽然autoencoder没有PCA那么强的约束(要求每一维正交)，但是autoencoder也许可以学到，因为本身基于最大化协方差的迹与最小均方差估计是等价的。几种方法总是让人感觉有着某些潜在的关联，不知道是不是能够提取出一种统一的模型能够把降维这件事情给解决掉。