局部切空间排列(LTSA)-高维数据的流形学习分析方法

2.4.6.1　基本思想

LTSA的基本思想是利用样本点所在空间领域的切空间来表示点的邻域，并对每一个点都建立邻域切空间，然后将这些局部切空间排列起来以建立流形的全局坐标。LTSA算法首先构建每个样本点的局部切空间，并且局部切空间可以由局部样本协方差矩阵的特征向量来表示，因此可以把构建局部切空间的问题转化为局部PCA分解问题，进而把局部坐标表示为每个样本点邻域在PCA主分量上的投影；然后从所有这些有交叠的局部坐标系统出发，采用线性排列技术构建全局唯一的低维坐标系统。

2.4.6.2　算法步骤

(1)选择近邻点

(2)计算局部切空间坐标

LTSA通过如下的优化函数计算一个d维仿射子空间来逼近XNi中的点:

以此构建局部坐标系:

(3)阵列全局坐标(www.xing528.com)

将式(2.25)写成矩阵表示形式:

因此可以将重构误差表示为:

通过映射，实现重构误差的极小化。

所以极小化重构误差的最优解可以通过计算矩阵SWWTST的第2个到第d＋1个最小特征值对应的特征向量V2，V3，…，Vd＋1来获得，即T＝[V2，V3，…，Vd＋1]。

2.4.6.3　算法分析

从LTSA的算法步骤中不难分析它的计算复杂度，选取邻域的计算复杂度为O(Dn2)，计算局部切空间坐标的计算复杂度为O(Dk2n)，排列全局坐标计算复杂度为O(dn2)，因此，LTSA算法只需要较少的计算量，执行速度快。LTSA除了能够有效恢复出等距流形的低维嵌入坐标，而且对数据集并没有凸性的假设，对于采样数据存在孔洞情况，LTSA也能对其进行正确投影。图2-5是采用LTSA对有孔洞数据进行低维投影的结果。然而，由LTSA算法获得的全局低维嵌入结果，无法保持数据集的某些全局几何信息。另外，LTSA算法对样本点的密度和曲率的变化比较敏感，样本点的密度和曲率的变化会导致样本点的邻域在局部切空间的投影产生较大偏差，使得局部切空间坐标无法很好地保持流形的局部几何信息，造成了全局低维嵌入结果的扭曲。

图2-5　LTSA对有孔S曲线数据的映射结果