高维数据流形学习分析方法中的局部样条嵌入

2.4.8.1　算法思想

Xiang等人在兼容映射的概念框架下提出了局部样条嵌入算法(LSE)。LSE算法的基本思想是对于嵌入在高维输入空间的低维流形，寻找一组由局部坐标映射与全局排列映射复合而成的兼容映射。在兼容映射的概念框架下，LSE算法首先通过主分量分析计算每个样本点局部邻域在切空间上的投影以获得该邻域所有样本的局部坐标，从而保持流形的局部几何结构信息；然后采用Sobolev空间的一组样条函数把每个样本点的局部坐标映射成全局唯一的低维坐标。与LTSA算法相似，LSE也是源于“局部拟合，全局排列”的思想，在局部拟合时，它们都是利用每个样本的局部切空间来捕获流形的局部几何，样本点在切空间的投影可用来表示样本点的局部坐标。然而它们的主要区别在于全局排列，LTSA算法是利用仿射变换来进行全局排列，而LSE算法是利用样条函数来获得全局唯一的低维坐标。

2.4.8.2　算法步骤

(1)选择近邻点

(2)局部切空间投影

但是由于样条函数未知，因此式(2.36)的求解是不确定的。要使式(2.36)能求解，所有的样条函数不仅要满足上式要求，而且其重构误差需要由Yi表示。已经有研究者证明Sobolev空间的样条函数能满足上式的求解。Sobolev空间的样条函数可表示如下:

为了实现低维映射空间内的投影能尽量保持流形的局部几何结构信息，可以通过最下化的正则化重构误差实现，如下:(www.xing528.com)

其中，正则化参数λ控制样条函数的光滑程度，如果λ足够小，式(2.40)中的第一项可以被忽略，故有:

另外，为了防止低维映射结果出现退化，添加一个约束条件YYT＝I消除旋转自由度，可以得到约束目标函数如下:

由以上目标函数可知，全局低维嵌入是由M的第二个到第d＋1个最小特征值对应的特征向量组成。

2.4.8.3　算法分析

LSE算法可以恢复出等距流形的低维嵌入坐标，且对数据集没有凸性的假设，例如对有孔洞的流形，仍可以恢复出它的低维本征结构。LSE算法中步骤一的计算复杂度为O(Dn2)，步骤二的计算复杂度为O(Dk2n)，步骤三的计算复杂度为O(dn2)，LSE算法大约80%的计算时间用于步骤一，总体上LSE算法的计算复杂度与LTSA算法相当。由于LSE算法采用非线性样条函数排列全局坐标，因此相对于LTSA而言，LSE算法能够实现更小的重构误差。LSE算法的主要缺点在于:①由于在计算低维嵌入坐标时加入了单位方差的约束，所以LSE算法无法保持数据的全局尺度信息；②不能学习具有较大曲率的低维流形结构；③如何选择合适的样条函数也是一个值得思考的问题。

另外，必须指出的是，与LTSA方法和HLLE方法类似，LSE算法在选择近邻点后，也是通过对邻域的切空间进行建模，但是在最后的求解过程中，其全局低维嵌入又比较类似LLE算法。正因为采用局部邻域切空间建模，LSE方法对数据并没有凸分布的要求。但是最后的求解却需要消除低维映射的旋转自由度，以防止映射结果的而退化。