流形学习(manifold learning)是一类借鉴了拓扑流形概念的降维方法。在局部具有欧氏空间的性质,能用欧氏距离来进行距离计算。启发:若低维流形嵌入到高维空间中,则数据样本在高维空间的分布虽然看上去非常复杂,但在局部上仍具有欧氏空间的性质。因此,可以在局部建立降维映射关系,然后再设法将局部映射关系推广到全局。当维数被降至二维或三维时,可以进行可视化。
等度量映射
等度量映射(Isometric Mapping,Isomap)认为低维流形嵌入到高维空间之后,直接在高维空间中计算直线距离具有误导性,因为高维空间中直线距离在低维嵌入流形是不可达的。“测地线”(geodesic)距离,沿着流形曲面上的测地线,测地线距离是两点之间的本真距离。如下图所示,直接在高维空间中计算直线距离是不恰当的。
测地线距离可以用近邻距离来近似,对每个点基于欧氏距离找出其邻近点,然后就能建立一个近邻连接图,图中近邻点之间存在连接,非近邻点之间不存在连接,所以测地线距离转变为计算近邻连接图上两点之间的最短路径问题。基于近邻距离逼近能获得低维流形上测地线距离很好的近似。
在近邻连接图上计算两点间的最短路径,可采用著名的Dijkstra算法或Floyd算法,在得到任意两点的距离之后,就可通过MDS方法来获得样本点在低维空间中的坐标.Isomap仅是得到了训练样本在低维空间的坐标,对于新样本,如何将其映射到低维空间呢?训练一个回归学习器来对新样本的低维空间坐标进行预测.
构建近邻图的两种做法,一种是指定近邻点个数,例如欧氏距离最近的k个点为近邻点,得到的近邻图称为k近邻图;另一种是指定距离阈值 ,距离小于的点被认为是近邻点,这样得到的近邻图称为近邻图。两种方式均有不足,例如若近邻范围指定得较大,则距离很远的点可能被误认为近邻,这样就出现 “短路” 问题;近邻范围指定得较小,则圈中有些区域可能与其他区域不存在连接? 这样就出现 “断路” 问题。短路与断路都会给后续的最短路径计算造成误导。
局部线性嵌入
局部线性嵌入,Locally Linear Embedding,试图保持邻域内样本之间的线性关系。
假定样本点的坐标能通过它的领域样本的坐标通过线性组合而重构出来,即
LLE希望这种关系在低维空间中得以保持。