MVU算法：高维数据的流形学习分析方法

2.4.2.1　基本思想

Weinberger和Saul提出的最大差异展开算法(MVU)，也称为半正定嵌入算法(Semi-definite Embedding，SDE)。它的基本思想是:假设样本点中每个点都与其k近邻点组成近邻图，在不破坏点与点之间的近邻关系的基础上，如果能够找到一种映射使得非近邻点之间的距离映射到低维空间后最大，那么样本点在低维空间的嵌入就能通过这种映射关系得到。

2.4.2.2　算法步骤

(1)建立近邻图

每一个数据点都与其k近邻点连接并且所有存在近邻关系的数据点都互相连接。如果数据点是稠密采样的，那么通过这种方式建立的近邻图比较忠实地保留数据点的流形结构。

(2)半正定规划近邻图的Gram矩阵

在保持近邻图中所有边的欧氏距离、低维坐标中心化和内积矩阵半正定三个约束条件下，建立目标函数，使得Gram矩阵的迹达到最大，并通过半定规划输出Gram矩阵，实现高维数据全局结构的“伸展”。这种“伸展”不是直接得到原始数据伸展后的输出，而是通过半正定规划，找到在近邻图中不连接的任意两个点之间距离和最大的内积矩阵。(www.xing528.com)

(3)谱分解

对Gram矩阵采用MDS方法映射，得到输入数据在低维空间的映射结果。

2.4.2.3　算法分析

MVU算法在保持降维前后近邻间的距离和角度不变，同时使得非近邻点在低维嵌入空间的距离尽可能远的条件下展开高维数据流形学习。虽然MVU也是一种全局特性保持方法，但该算法不需要度量高维观测数据间的测地距离，因此对非凸数据集也有理想的降维效果。

MVU算法的主要缺点有:①算法的时间复杂度高。算法在求解半定规划所需要的时间复杂度是样本个数的三次方，即O(k3n3)；算法在对Gram矩阵进行广义特征值分解的计算复杂度为O(n3)，因此算法总的时间复杂度近似为O(n3＋k3n3)。MVU算法高额的时间复杂度使MVU算法很难在大规模数据集上获得广泛的应用。②算法对噪声较为敏感。因为算法在半定规划求解Gram矩阵时采用了严格的局部等距约束，使得受噪声污染的数据集很难获得满意的低维嵌入结果。