文章汇总了七种降维算法，探讨其基本概念、流程及应用，适合机器学习初学者阅读。
原文标题：机器学习降维算法汇总！
原文作者：数据派THU
冷月清谈：
怜星夜思：
2、不同降维算法的选择标准有哪些？
3、降维后数据如何评估效果？
原文内容
来源：算法进阶本文约7500字，建议阅读10分钟
本文给出了七种算法的一个信息表，归纳了关于每个算法的参数、算法主要目的等，并介绍了降维的一些基本概念。
-
3.1 主成分分析PCA
-
3.2 多维缩放(MDS)
-
3.3 线性判别分析(LDA)
-
3.4 等度量映射(Isomap)
-
3.5 局部线性嵌入(LLE)
-
3.6 t-SNE
-
3.7 Deep Autoencoder Networks
,Z 表示降维输出矩阵大小低维数d乘以N，
,线性映射是
,高维空间中两两之间的距离矩阵为A，Sw,Sb分别是LDA的类内散度矩阵和类间散度矩阵，k表示流形学习中一个点与k个点是邻近关系,F表示高维空间中一个点由周围几个点的线性组合矩阵,
。−表示不确定。P 是高维空间中两点距离占所有距离比重的概率矩阵，Q 低维空间中两点距离占所有距离比重的概率矩阵。
表示全连接神经网络的层数，
表示每一层的节点个数。
来代表个数为D的向量
所包含的有用信息，其中d<D。假设对一张512*512大小的图片，用svm来做分类，最直接的做法是将图按照行或者列展开变成长度为512*512的输入向量，跟svm的参数相乘。假如能够将512*512的向量在保留有用信息的情况下降维到100，那么存储输入和参数的空间会减少很多，计算向量乘法的时间也会减少很多。所以降维能够有效的减少计算时间。而高维空间的数据很有可能出现分布稀疏的情况，即100个样本在100维空间分布肯定是非常稀疏的，每增加一维所需的样本个数呈指数级增长，这种在高维空间中样本稀疏的问题被称为维数灾难。降维可以缓解这种问题。
PCA由Karl Pearson在1901年发明，是一种线性降维方法，高维空间(维数为D)的某个点
通过与矩阵W相乘映射到低维空间(维数为d，d<D)中的某个点
，其中W的大小是D∗d，i对应的是第i个样本点。从而可以得到N个从D维空间映射到d维空间的点，PCA的目标是让映射得到的点尽可能的分开，即让N个的方差尽可能大。假如D维空间中的数据每一维均值为0，即
，那么两边乘上
得到的降维后的数据每一维均值也是0，考虑一个矩阵
，这个矩阵是这组D维数据的协方差矩阵，可以看出对角线上的值是D维中的某一维内的方差，非对角线元素是D维中两维之间的协方差。
那么针对降维后d维数据的协方差矩阵
，如果希望降维后的点尽可能分开，那么就希望B对角线上值即每一维的方差尽可能大，方差大说明这些维上数据具有非常好的区分性，同时希望d的每一维都是正交的，它们正交就会使得两个维是无关的，那么它们就不会包含重叠的信息，这样就能最好的表现数据，每一维都具有足够的区分性，同时还具有不同的信息。这种情况下B非对角线上值全部为0。又由于可以推导得出：
这个式子实际上就是表示了线性变换矩阵W在PCA算法中的作用是让原始协方差矩阵C对角化。又由于线性代数中对角化是通过求解特征值与对应的特征向量得到，因此可以推出PCA算法流程(流程主要摘自周志华老师的《机器学习》一书，其中加入了目标和假设用于对比后面的算法。周老师书中是基于拉格朗日乘子法推导出来，本质上而言与[3]都是一样的，这里很推荐这篇讲PCA数学原理的博客[3])。
-
输入：N个D维向量
，降维到d维
-
输出:投影矩阵
，其中每一个
都是D维列向量
-
目标:投影降维后数据尽可能分开，
(这里的迹是因为上面提到的B的非对角线元素都是0，而对角线上的元素恰好都是每一维的方差)
-
假设:降维后数据每一维方差尽可能大，并且每一维都正交
-
1.将输入的每一维均值都变为0，去中心化
-
2.计算输入的协方差矩阵
-
3.对协方差矩阵C做特征值分解
-
4.取最大的前d个特征值对应的特征向量
此外，PCA还有很多变种kernel PCA, probabilistic PCA等等，本文暂时只考虑最简单的PCA版本。
3.2 多维缩放(MDS)
MDS的目标是在降维的过程中将数据的dissimilarity(差异性)保持下来，也可以理解降维让高维空间中的距离关系与低维空间中距离关系保持不变。这里的距离用矩阵表示，N个样本的两两距离用矩阵A的每一项
表示，并且假设在低维空间中的距离是欧式距离。而降维后的数据表示为，那么就有
。右边的三项统一用内积矩阵E来表示
。去中心化之后，E的每一行每一列之和都是0，从而可以推导得出
其中
单位矩阵I减去全1矩阵的
，i⋅ 与⋅j 是指某列或者某列总和，从而建立了距离矩阵A与内积矩阵E之间的关系。因而在知道A情况下就能够求解出E，进而通过对E做特征值分解，令
，其中 Λ 是对角矩阵，每一项都是E的特征值λ1≥…≥λd，那么在所有特征值下的数据就能表示成
，当选取d个最大特征值就能让在d维空间的距离矩阵近似高维空间D的距离矩阵，从MDS流程如下[2]:
-
输入:距离矩阵
，上标表示矩阵大小，原始数据是D维，降维到d维
-
输出:降维后矩阵
-
目标:降维的同时保证数据之间的相对关系不变
-
假设:已知N个样本的距离矩阵
-
1.算出$a{i\cdot}、a{\cdot j}、a_{\cdot \cdot}$
-
2.计算内积矩阵E
-
3.对E做特征值分解
-
4.取d个最大特征值构成
，对应的特征向量按序排列构成
3.3 线性判别分析(LDA)
LDA最开始是作为解决二分类问题由Fisher在1936年提出，由于计算过程实际上对数据做了降维处理，因此也可用作监督线性降维。它通过将高维空间数据投影到低维空间，在低维空间中确定每个样本所属的类，这里考虑K个类的情况。它的目标是将样本能尽可能正确的分成K类，体现为同类样本投影点尽可能近，不同类样本点尽可能远，这点跟PCA就不一样，PCA是希望所有样本在某一个维数上尽可能分开，LDA的低维投影可能会重叠，但是PCA就不希望投影点重叠。它采用的降维思路跟PCA是一样的，都是通过矩阵乘法来进行线性降维，投影点是
。假设按下图中的方向来投影，投影中心对应的原来高维点分别是μ1，μ2。由于希望属于不同类的样本尽可能离的远，那么就希望投影过后的投影中心点离的尽可能远，即目标是
，但是仅仅有中心离的远还不够，例如下图中垂直于x1轴投影，两个中心离的足够远，但是·有样本在投影空间重叠，因此还需要额外的优化目标，即同类样本投影点尽可能近。那么同类样本的类间协方差就应该尽可能小，同类样本的协方差矩阵如下。
其中μ1=(u1,…,uN),W=(w1,…,wd)，
表示样本属于第1类的集合，中间的矩阵
是属于第的样本协方差矩阵，将K个类的原始数据协方差矩阵加起来称为类内散度矩阵，
。而上面两个类的中心距离是中心直接相减，K个类投影中心距离需要先计算出全部样本的中心
(
表示属于第k类的样本个数)，通过类间散度矩阵来衡量，即
。整合一下，LDA算法的优化目标是最大化下面的costfunction:
二分类情况下，W的大小是D∗1，即J(W)本身是个标量，针对K类的情况，W的大小是D∗d−1，优化的目标是对上下的矩阵求它的迹。这里可以发现在LDA中没有对数据去中心化，如果要去中心化每个类的中心就会重叠了，所以这个算法没有去中心化。然后J(W)对W求导，这个式子就表明了W的解是
的d-1个最大特征值对应的特征向量组成的矩阵。那么就可以通过W来对X进行降维。
-
输入:N个D维向量
，数据能够被分成d个类
-
输出:投影矩阵$W=(w1, …, w{d-1})，其中每一个，其中每一个w_i$都是D维列向量
-
目标:投影降维后同一类的样本之间协方差尽可能小，不同类之间中心距离尽可能远
-
假设:优化目标是最大化
-
1.求出类内散度矩阵Sw 和类间散度矩阵Sb
-
2.对做奇异值分解
，求得
-
3.对矩阵
做特征分解
-
4.取最大的前d-1个特征值对应的特征向量$w1,…,w{d-1}$
个人觉得这里的优化目标实际上体现了一个假设，即假设优化目标上下的表达式都是对角矩阵，W的变换使得Sd 与Sw 都变成了对角矩阵。
3.4 等度量映射(Isomap)
上面提到的MDS只是对数据降维，它需要已知高维空间中的距离关系，它并不能反应出高维数据本身潜在的流形，但是可以结合流形学习的基本思想和MDS来进行降维[5]。也就是高维空间的局部空间的距离可以用欧式距离算出，针对MDS的距离矩阵A，某两个相邻的点之间距离
也就是它们的欧式距离，距离比较近的点则通过最短路径算法来确定，而离的比较远的两点之间Aij = ∞，把矩阵A确定下来，那么这里就涉及到判断什么样的点相邻，Isomap是通过KNN来确定相邻的点，整体算法流程如下:
-
输入:N个D维向量，一个点有K个近邻点，映射到d维
-
输出:降维后矩阵
-
目标:降维的同时保证高维数据的流形不变
-
假设:高维空间的局部区域上某两点距离可以由欧式距离算出
-
1.由KNN先构造A的一部分，即求出相邻的点并取它们的欧式距离填入Aij，其他的位置全部初始化为无穷大
-
2.根据最短路径算法(Dijkstra算法)找到距离比较近的点之间的路径并填入距离
-
3.将距离矩阵A作为MDS的输入，得到输出
3.5 局部线性嵌入(LLE)
如之前提到过的，流形学习的局部区域具有欧式空间的性质，那么在LLE中就假设某个点 xi 坐标可以由它周围的一些点的坐标线性组合求出，即
(其中 Xi 表示 xi 的邻域上点的集合)，这也是在高维空间的一种表示。由于这种关系在低维空间中也被保留，因此
，两个式子里面权重取值是一样的。
基于上面的假设，首先想办法来求解这个权重，假设每个样本点由周围K个样本求出来，那么一个样本的线性组合权重大小应该是1∗K，通过最小化reconstruct error重构误差来求解，然后目标函数对f求导得到解。
求出权重之后，代入低维空间的优化目标：
来求解Z，这里将F按照 N∗K 排列起来，且加入了对Z的限制。这里用拉格朗日乘子法可以得到 MZ=λY 的形式，从而通过对M进行特征值分解求得Z。
-
输入:N个D维向量，一个点有K个近邻点，映射到d维
-
输出:降维后矩阵Z
-
目标:降维的同时保证高维数据的流形不变
-
假设:高维空间的局部区域上某一点是相邻K个点的线性组合，低维空间各维正交
-
1.由KNN先构造A的一部分，即求出K个相邻的点，然后求出矩阵F和M
-
2.对M进行特征值分解
-
3.取前d个非0最小的特征值对应的特征向量构成Z(这里因为最小化目标，所以取小的特征值)
3.6 t-SNE
t-SNE也是一种将高维数据降维到二维或者三维空间的方法，它是2008年由Maaten提出[6]，基于2002年Hinton提出的随机近邻嵌入(StochasticNeighbor Embedding, SNE)方法的改进。主要的思想是假设高维空间中的任意两个点，xj 的取值服从以 xi 为中心方差为 σi 的高斯分布，同样 xi 服从以 xj 为中心方差为σj 的高斯分布,这样 xj 与 xi 相似的条件概率就为
即 xj 在 xi 高斯分布下的概率占全部样本在 xi 高斯分布下概率的多少，说明了从 xi 角度来看两者的相似程度。接着令 pij =(pi|j+pj|i)/2n用这个概率来作为两个点相似度在全部样本两两相似度的联合概率 pij 。公式如下，论文没有解释σ是标量还是矢量，但是因为在后续的求解中 pij 不是直接由下面这个联合概率公式求出，而是通过前面的条件概率来求，前面的式子针对每一个样本i都会计算一个σi，具体给定一个确定值
，其中
。接着通过二分查找来确定 xi 对应的σi，使得代入上面的两个式子后等于Prep的值，因此这里的σ应该是个矢量。不太可能所有样本都共用一个高斯分布参数。
同时将低维空间两个点的相互关系或者说相似程度也用联合概率来表示，假设在低维空间中两点间欧式距离服从一个自由度的学生t分布，那么在低维空间中两个点的距离概率在所有的两个点距离概率之中的比重作为它们的联合概率。
假如在高维空间的 xi,xj 与对应在低维空间中的 zi,zj 算出来的相似性值 pij,qij 相等，那么就说明低维空间的点能够正确的反应高维空间中的相对位置关系。所以tsne的目的就是找到一组降维表示能够最小化pij 和qij 之间的差值。因此，tsne采用了KullbackLeibler divergence即KL散度来构建目标函数
，KL散度能够用来衡量两个概率分布的差别。它通过梯度下降的方法来求输入数据对应的低维表达 zi，即用目标函数对 zi 求导，把 zi 作为可优化变量，求得每次对 zi 的梯度为
，然后更新迭代 zi ，在实际更新的过程中则像神经网络的更新一样加入了momentum项为了加速优化，大概的算法流程如下:
-
输入:N个D维向量，映射到二维或者三维，定值Perp，迭代次数T，学习率η，momentum项系数α(t)
-
输出:降维后数据表示z1,…,zN
-
目标:降维到二维或者三维可视化(重点是可视化)
-
假设:在高维空间中，一个点 xj 的取值服从以另外一个点 xi 为中心的高斯分布。在低维空间中，两个点之间的欧式距离服从自由度为1的t分布
-
1.先由二分查找确定 xi 的σi
-
2.计算成对的$P{j|i}，得到，得到p{ij} = (p{j|i}+p{i|j})/2$
-
3.初始化z1,…,zN
-
4.计算qij
-
5.计算梯度 ∂J/∂zi
-
6.更新
-
7.重复4~6至收敛或者完成迭代次数T
需要注意的是，这个算法将低维数据作为变量进行迭代，所以如果需要加入插入新的数据，是没有办法直接对新数据进行操作，而是要把新数据加到原始数据中再重新算一遍，因此T-sne主要的功能还是可视化。
3.7 DeepAutoencoder Networks
Autoencoder是神经网络的一种，它是一种无监督算法，可以用来降维也能用来从数据中自动学习某种特征，这个神经网络的原理是输入一组值，经过网络之后能够获得一组输出，这组输出的值尽可能的跟输入的值大小一致。网络由全连接层组成，每层每个节点都跟上一层的所有节点连接。Autoencoder的结构如下图4所示，encoder网络是正常的神经网络前向传播z=W x+b，decoder网络的传播参数是跟它成对称结构的层参数的转置，经过这个网络的值为
，最后传播到跟网络的输入层个数相等的层时，得到一组值x′，网络希望这两个值相等x′=x，这个值与真实输入 x 值通过交叉熵或者均方误差得到重构误差的costfunction，再通过最小化这个cost和梯度下降的方法使网络学到正确的参数。因此可以通过这个网络先经过”encoder”网络将高维数据投影到低维空间，再经过”decoder”网络反向将低维数据还原到高维空间。
图5 Autoencoder层间结构
06年的时候Hinton在science上发了一篇文章讲如何用深度学习中的autoencoder网络来做降维[8]，主要是提出了先通过多层RBM来预训练权重参数，用来解决autoencoder降维后的质量依赖初始化网络权重的问题，即主要目的是提出一种有效的初始化权重的方式。上面的表达式中没有加入非线性变换，真实网络中每一层跟权重做矩阵乘法之后还需要加上非线性变换。此外，autoencoder的模型中可以加入sparsity的性质[9]，即针对N个D维输入，某一层的某一个节点输出值之和
趋近于0，即
，其中l代表是哪一层，i代表是第几个输入。也能加对权重有要求的正则项。
-
输入:N个D维向量x1,…,xN，网络结构即每层节点数，迭代次数T，学习率η
-
输出:降维后数据表示z1,…,zN
-
目标:网络能够学习到数据内部的一些性质或者结构，从而能够重构输入数据
-
假设:神经网络就是特牛逼，就是能学到特征，科科
-
1.设置层数和每一层节点数
-
2.初始化权重参数
-
3.前向传播计算下一层的节点值z=W x+b
-
4.反向传播计算上一层反向节点值
-
5.计算每一层对输入和对这层参数W的梯度，利用反向传播将error传递到整个网络
-
6.将分别对 W 和
的梯度求和然后更新W
-
7.重复3~6至收敛或者完成迭代次数T
