非线性降维方法介绍

PCA，ICA，CCA，SVD，MDS都是线性的特征降维方法，对那些非线性结构的数据就无能为力，相应地，非线性降维技术则能产生较好的结果。ISOMAP，LLE是两种代表性的非线性降维方法。学者Roweis和Saul提出的LLE算法在将高维数据映射到低维坐标系的同时，保留了邻接点间的几何结构关系，发现了数据集中的非线性结构，并具有对平移、旋转等的不变性。学者Tenenbaum等人提出的ISOMAP方法在测地线距离和MDS算法的基础上，实现了数据集的非线性降维。

ISOMAP是一种代表性的流形学习方法，在对高维数据进行非线性降维的同时，还保持了数据间的内积不变。ISOMAP的理论框架是以MDS(Multi-Dimensional Scaling)方法为基础的，将MDS的输入距离参数换成了流形上的测地线距离，即:流形上两点之间的最短路径长度。完整的ISOMAP算法主要包括以下三个步骤:

步骤1　构造邻接图:计算原始高维欧氏空间R中任意两个样本点i，j之间的距离dR(i，j)，连接所有距离小于规定阈值的样本点，构成一个邻接图，并且，将连接样本点i，j之间边的权重赋值为dR(i，j)，邻接图就是一个无向加权图G；(www.xing528.com)

步骤2　计算测地线距离:在无向加权图G中，计算任意两点间的最短路径，并将最短路径上所有边的权重之和作为测地线距离d*(i，j)，得到测地线距离矩阵D*＝{d*(i，j)}；

步骤3　构造内嵌子空间:将测地线距离矩阵D*＝{d*(i，j)}作为MDS算法的输入，则输出结果即为保留了原始空间中几何特性和内积不变性的低维数据嵌入结构。