《浅谈流形学习及其算法》由会员分享，可在线阅读，更多相关《浅谈流形学习及其算法（12页珍藏版）》请在金锄头文库上搜索。
1、 浅谈流形学习及其算法 郝晨辉摘 要：流形学习是借助几何学中子流形的概念，利用流形的结果和性质来挖掘嵌入在高维空间中的数据集的真实的低维结构。本文在介绍流形学习具体算法的基础上，通过MATLAB分析了不同算法的特点，对不同算法之间的关系进行了比较。基于此分析，我们对现有流行学习的缺点及局限提出了优化方法及改进方法。关键词：流形学习；算法；映射；数据集：TP301.6 ：A ：1671-2064（2018）01-0219-041 引言对于如今的机器学习来说，面临着所需处理的数据量、数据特征递增的趋势，但是有效的数据特征相对较少，为了减轻不必要的时间消耗，在处理数据之前都要对数据的特征进行稀疏化，
2、一种方法是直接对数据的维数进行降维，来达到重要特征提取的目的。另一种是对数据的特征进行稀疏化，把没用的特征信息都设置为零，从而达到特征稀疏的目的。本文主要从降维这个角度来进行探讨。早期主要的降维方法是线性降维算法主成分分析法PCA6，其主要过程是研究一个线性降维映射，将高维空间中的样本点集投影到低维空间中。PCA6通过最大化数据点集之间的协方差矩阵来选取数据点集分布的最主要的特征，从而达到降维的目的。这种算法适用于处理的数据集呈现线性分布。但是针对分布呈现复杂的非线性分布，PCA很难达到较好的降维效果。非线性分布的高维样本点集，其所在的非线性空间可以看成是嵌入在高维空间的低维非线性子空间。在机
3、器学习中通常采用kernel函数的方法来进行处理，称之为kernel PCA7。这种算法存在的问题是很难选择一个合适的kernel函数，如果kernel选择的不合适反而会对学习过程造成很大的影响，增加学习的时间消耗，且最终的降维效果也不会很好。针对复杂的非线性分布的数据点集，虽然全局结构无法获得，但我们可以看出数据点集的很小的局部邻域结构还是呈现出线性分布结构。对于这种局部呈现出线性结构而全局呈现出非线性结构的数据点，我们将其假设成分布在某个流形上，其降维过程称为流形学习。流形学习是一类借鉴拓扑流形概念的降维方法。“流形”是在局部与欧氏空间同胚的空间，直观上来说“流形”的局部邻域可以近似的看成
4、是欧氏空间结构。根据流形的这个性质所设计出的流形学习算法都是从流形的局部结构出发通过保持流形的局部线性结构来对高维样本点集进行降维。当然流形的全局结构也是从局部结构出发来获取全局的结构。流形学习算法，大致可以分为两大类，都是在假设流形的局部邻域为线性空间基础上进行的。一类是保持全局结构的非线性降维算法，如Isomap2：Isomap又称为等距映射算法，目的是保持降维前后任意两点之间的真实的距离结构。在流形上，任意两点之间的真实的距离不是两点之间的欧氏距离，而是两点之间的测地线距离。所以Isomap旨在保持任意两点之间的测地线距离。另一类是保局部结构的降维算法，如LLE1，LEP3，LPP9，L
5、TSA5，HLLE4等。LLE算法旨在保持样本点局部邻域的线性组合结构，通过假设高维样本点的局部邻域是线性结构，然后计算每个样本点与其邻域点之间的线性相关系数，由此在低维空间中邻域点之间还保持相同的线性相关性。LEP算法旨在保持局部样本点之间的结构，降维的主要思想是距离较近的点降维后还是距离较近，在算法设计中通过建立样本点集之间的局部邻域图结构，任意两点之间的边赋予相应的权重，通过权重来体现局部邻域点之间的距离关系。LPP继承了LEP算法的思想，给出保持局部结构的线性降维算法。LTSA算法也是将流形的局部邻域假设成线性空间，然后在局部邻域上利用PCA进行降维。2 基本知识介绍流形学习算法的共有
6、的前提假设是，所要降维的高维样本点集分布在某个非线性流形F上，此流形是嵌入在高维欧氏空间中的一个子流形。流形学习的目的是从高维空间中挖掘出子流形F的真实的低维表示结构。为了算法的需求，我们假设高维样本点集表示为x1，x2，xNFRD，其中N表示样本点集的个数，D表示高维样本点集的维数。对应的低維样本点集表示为y1，y2，yNYRd，其中d表示低维样本点集的维数。基于此目的，我们给出流形学习的形式化定义。流形学习的目的是挖掘高维样本点集产生的机制，表示为映射f，具体的表示形式如下：f：YFRD。在降维过程中，流形的全局或局部几何结构得到保持。3 算法描述3.1 等距映射Isomap2又称等距映射
7、算法，其目的是保持降维前后所有样本点集之间的全局距离结构。Isomap借助MDS8来挖掘高维样本点集之间真实的内在结构。MDS8是保持降维后高维样本点集之间的欧氏距离结构。而Isomap旨在保持样本点集之间真实的距离结构。在流形上，两点之间真实的距离不是欧氏距离，而是两点之间的测地线距离。在此算法中，通过构造样本点之间的局部图结构，然后任意两点之间的测地线距离通过寻找两点之间的最短路径来获得。算法步骤如下：（1）确定原空间每个点的邻域点（找样本点的近邻点方法有两种：1）是规定k的值即取距离样本点最近的k个近邻点。2）是规定一个球的半径E，以样本点为球心，找出这个球覆盖的样本点。）（2）估算测地
8、线距离（高维空间中较近点之间的测地线距离用欧式距离代替，较远点距离用测地线距离，最短路径逼近，计算公式为dG（i，j）=mindG（i，k）+dG（k，j），其中dG（i，j）表示点i与点j之间的欧氏距离），从而构造所有数据点之间的距离矩阵D。（3）用MDS在低维欧式空间找到点间距符合第一步中距离的点y1，y2，yNRd。MDS算法：输入主对角线元素为零的距离矩阵D。endprint（2）计算B矩阵的谱分解（3）通过求出形成矩阵（4），我们取矩阵X的前d个列向量所组成的矩阵XNd作为低维输出。其中H是半正定矩阵，D是非负对称矩阵，B是格拉姆矩阵此种算法的优点是：1）具有估计低维空间维数的作用，
9、不用给定低维空间的维数。2）整体等距映射到低维空间，无需考虑局部坐标之间的相容性。3）很好的识别了非线性流形结构。3.2 局部线性嵌入映射LLE1又称局部线性嵌入映射，此算法假设样本点所在的子流形的局部邻域是线性结构。与Isomap算法不同，LLE算法旨在保持样本点集的局部邻域的线性结构，其基本思想可以简单的表示如下：流形上任意数据点pM，都可以用其K-邻域内的K个邻近点近似线性表示，然后在低维欧式空间中重构一组低维样本点表示y1，y2，yN，使得这些低维样本点集的局部邻域点之间也满足原始数据点之间的线性组合关系。算法步骤如下：（1）找每个样本点x1，x2，xN的近邻点（方法同Isomap）。
10、（2）计算高维邻域点之间的局部权值矩阵Wij，其中xij为xi的k个近邻点。满足代价函数并满足约束条件。定义一个误差函数，如下：误差函数值越小，说明局部权值矩阵重建的越好，说明xi越接近其近邻点的线性组合的点。（3）在低维空间重构一组样本点y1，y2，yN，使得其保持高维邻域点之间的线性相关关系。此种算法的优点是：1）算法中建立的权值矩阵是一个稀疏矩阵，计算量较小；2）算法具有整体最优解（低维欧式空间所对应的所有数据点表示），不需要迭代，减少了计算的复杂性。3.3 拉普拉斯特征映射拉普拉斯特征映射（LEM）3借助Laplace矩阵的性质来对高维样本点集进行降维。其与LLE算法思想基本相似，保持
11、高维样本点集的局部几何结构。LEM的目的就是寻找原始数据流形在低维欧式空间的对应表示，LEP算法有着很直观的降维目标，即在高维空间中离得很近的点投影到低维空间中的像也应该离得很近，这能够保持局部几何结构不变。基于此，LEM算法所要优化的目标函数为。其中Y表示低维数据点集的矩阵表示形式，矩阵L=D-W是拉普拉斯矩阵。限制条件YTY=I保证优化问题有非奇异解，并且保证映射后的数据点不会被“压缩”到一个小于m维的子空间中。基于这样的算法思想，我们给出LEP算法的基本步骤。算法步骤：（1）根据K-邻域法选择每一点处的k个近邻点集。（2）将每个样本点的k个近邻点连接成邻接图。（3）构造数据点集上的权值矩
12、阵W，W的每个分量表示相应两点之间的权重。（4）计算拉普拉斯矩阵L的特征向量与特征值。使用最小的d个非零特征值对应的特征向量作为降维后的输出结果，其中d表示低维空间的维数。此种算法的优点是：通过求解稀疏矩阵的特征值可以求出整体最优解。4 算法实践及分析分别选取两类数据集对各类流形学习算法的降维效果进行对比分析。一类数据集为仿真数据集，我们分别选取两组仿真数据集：Swiss Roll和Punctured Sphere。另一类数据集为真实世界中的数据集，USPS手写体识别数据集。首先对仿真数据集进行实验分析，然后对USPS数据集进行分析。4.1 仿真数据集Swiss Roll以及Punctured
13、 Sphere为两组三维数据点集，其每一个数据点都是由一个三维向量进行表示。在本实验中，我们分别采取800个Swiss Roll数据点以及1000个Puncture Sphere数据点进行实验。所有这些数据点所在的非线性流形是嵌入在三維空间中的二维流形。我们分别采用三种流形学习算法对这两组数据集进行降维，将其降维到二维空间中。这三类算法分别为等距映射（Isomap）、局部线性嵌入（LLE）、拉普拉斯特征映射（LEP）。由于这三类算法都受局部邻域因子K值的影响，所以在实验阶段，我们分别选取不同的K值，然后来分析在不同的K值下三类算法的降维效果。4.1.1 实验过程首先给出Swiss Roll数据
14、集的实验过程。此数据集包含800个三维数据点，我们分别选取邻域因子K=8，12，16。其对应的降维结果如下图1所示，其中图中第一行表示K=8时三个算法的降维结果，第二行表示K=12时的降维结果，第三行表示K=16时的降维结果。Puncture Sphere数据集是一组采样与二维球面上的三维数据点集。我们采取1000个数据点，与Swiss Roll相同，我们分别选取K=8，12，16。其相应的降维结果如图2所示。4.1.2 实验结果由Swiss Roll图可知，Isomap降维的效果明显好于其他两种算法。LLE和LEP这两种方法降维后的图形较为相似，这是由于两种算法都是假设样本点所在的子流形的局
15、部邻域是线性结构。但我们并不能从LLE和LE两种方法降维后的图形辨认出原始流形，之所以瑞士卷降维后呈现这样的图形是因为这两种算法只是保持了流形的局部结构，对于全局结构没有得到很好的保持，所以降维后的结果只是在局部邻域中效果比较好，从算法来看，这两种算法对流形的全局结构并没有做约束。当K值增大到16时，这两种局部线性嵌入方法降维后的准确度降低，降维的效果变得不好。这是因为K是局部邻域的大小，当K增大时，局部邻域范围就会变大，所以表面上局部邻域已经不呈现出线性结构，但潜在的原因是降维过程中并没有考虑到局部邻域的曲率结构，所以会出现这些结果。针对Puncture Sphere数据集，LEP算法的降维
16、效果明显好于其余两个算法。且随着K值的增加，LEP的降维效果并没有明显的降低。从算法本身分析其结果我们可以看出，LLE算法目的是要保持降维前后数据点邻域的线性结构，而针对Puncture Sphere数据集，其是采样与球面的数据集，所以每个数据点的局部邻域的线性结构非常的弱。而针对Isomap算法，其是为了保持样本点集降维前后的全局结构，所以从降维结果可以看出，虽然在全局上，降维后的流形依然保持球面的整体结构，但是每个数据点的局部邻域结构在降维过程中并没有得到很好的保持。endprint4.2 真实世界数据集对流形学习的算法做进一步实验，用局部线性嵌入（LLE）、主成分分析（PCA）以及拉普拉斯特征映射（LE
