硕士学位论文 过求解M?(I?W)T(I?W)的特征值得到，M为m?m的矩阵。

LLE能够有效地将高维数据在低维空间中可视化。下面是一个应用LLE降维的例子，图2.3中，左图所示是在三维空间中Gaussian数据集的数据，右图是Gaussian数据集在LLE上的低维嵌入。从图中可以看出，LLE的降维结果是比较满意的，它能够很好地保持数据点之间的邻域关系。

图2.3 Gaussian数据集在LLE上的低维嵌入

ISOMAP是以保持全局测地距离不变的思想来降维，而LLE是通过局部线性拟合来获得内在的全局非线性结构。LLE的一大优点是无需计算成对的距离矩阵，通过稀疏矩阵的特征分解来得到嵌入向量，很大程度上减少了计算量。另外，LLE中每个点的近邻权值在平移、旋转和放缩变换下是保持不变的。

LLE也有一定的不足之处。首先，该算法强调高维空间近邻数据间的序应在低维嵌入空间中保持一致，进而对近邻数据间权值的求取可采用闭式求解法，但针对新数据如何应用这一权值矩阵还没有一般性的解决方法。其次，对于等距的流形，如果流形所对应的低维空间的子集不是凸集时，LLE不能很好地恢复出同它等距的低维嵌入，即不能得到正确的嵌入结果。最后，因为LLE能够保持局部邻域点的几何性质，对于有噪声、样本间关联较弱或者密度稀疏的数据集，相距较远的点之间的关联会减弱。因而在映射过程中，很可能将相距较远的点映射到邻近点的位置，从而很难发现数据的内蕴结构。

2.4拉普拉斯特征映射

拉普拉斯特征映射（Laplacian Eigenmaps，LE）[21]的降维目标非常直观，它将高维空间流形中相距很近的点投影至低维空间，其流形映像也应该相距较近。其基本思想是利用图的拉普拉斯概念，寻找保持局部邻域信息的最优低维表示。LE在保持无向图的局部近邻关系下能保持局部结构，在低维空间中重新把无向图描绘出来。

假设在高维空间Rn中有数据集X?[x1,x2,,xm]，寻找低维空间Rd（d<

15

人脸识别中基于流形学习的特征提取方法研究 中的一组数据Y?[y1,y2,表示Rn上的嵌入流形。

,ym]，yi是高维数据xi的低维表示，且xi?M?Rn，M

LE算法的实现步骤如下：

（1）构造邻域图。如果数据点xi和xj是邻接的，则图中节点i与节点j之间存在一条边。采用?邻域法或k邻域法来确定xi?Rn的近邻。其中，?邻域法表达直观，但?的大小不易确定。k邻域法易于实现，但缺乏几何意义的理解。

（2）选择权值矩阵。若选择热核方法，数据点xi和xj在邻域关系图中相

xi?xj2连接，那么Wij?et，否则Wij=0。若选择简单方法，数据点xi和xj在邻域

图中相连接，那么Wij=1，否则Wij=0。

（3）计算特征映射。假定所构造的是连通图，否则在每个连通分支上对其计算特征映射。计算如下广义特征值和特征向量：

LY??DY （2.4）

其中，D为对角矩阵，Dii??Wij，L=D-W为拉普拉斯矩阵。求出λ和Y，

j选择d个最小非零特征值?1,?2,便是高维数据的低维表示。

,?d，y1,y2,,yd是特征值对应的特征向量，Y

LE算法的实质是将高维空间中的数据点降维到低维空间后，使得近邻的点仍然保持近邻关系。出于这样的算法思路，可定义在适当的约束条件下最小化如下目标函数：

?i,jyi?yjWij （2.5）

2此目标函数保证了xi和xj近邻则yi与yj也近邻，同时惩罚 xi和xj近邻而yi与yj远离。针对Y?[y1,y2,,ym]，这里的yi对应邻域关系图中的第i个顶点

的低维嵌入。因此，目标函数最小化问题可以表述为如下的矩阵形式：

argmintr(YTLY) （2.6）

Y其中L是半正定的拉普拉斯矩阵。其约束条件如下：

YTDY?I （2.7）

以上的优化问题可以转化为下式：

T argmintr(YLY) （2.8） TYDY?I利用拉格拉日乘子解上面的优化问题得到式（2.4）推广的特征值问题。 根据目标函数，可以得出结论：目标函数的最小化等同于求解广义特征值

16

硕士学位论文 问题的最小特征值与之对应的特征向量问题。

图2.4中，左图是Toroidal Helix数据集，右图是Toroida

l Helix数据集在LE上的低维嵌入。直观地显示了LE将一个三维空间中的环形螺旋状曲线投影到二维空间，不难发现此三维环形螺旋状曲线实质就是一个一维流形。

图2.4 Toroidal Helix数据集在LE上的低维嵌入

与保持距离不变的思想不同，LE是基于局部几何结构保持不变来获得高维观测空间同低维结构在局部意义下的对应，从而使得高维空间中的近邻关系在低维空间中仍然得到保持。从算法可以看出，LE计算量较小，无需迭代计算。同时，它的权值设置简单，只需直接设置权值，不需计算线性方程组。由于LE仅确保流形上近邻的点在映射到低维空间时的近邻关系，而对于流形上较远的点投影后有可能将距离放大。因此，LE不适合恢复出同流形等距的低维结构。然而，热核参数的选取对嵌入结果影响较大，如何更有效的选取参数也是一个进一步研究的问题。此外，LE对于噪声和错位点比较敏感。

2.5流形学习方法的比较

如前所述，流形学习方法可以分为全局方法和局部方法。基于全局的流形学习方法（如ISOMAP），在降维时不仅将流形上邻近的点映射到低维空间中保持近邻关系，而且将流形上非近邻点映射到低维空间中保持疏远关系；基于局部的流形学习方法（如LLE、LE）仅仅将流形上邻近的点映射到低维空间中保持近邻关系，对远离点没有做要求。其共同特性是：首先根据原始输入数据构造流形的局部邻域结构，然后使用这些局部邻域结构将原始输入数据映射到一个低维空间，以此寻找数据的内蕴结构。

流形学习的优点在于：它们都是非线性的降维方法，以便寻找流形的内在几何结构，能够发现现实数据的本质内涵；它们都是非参数方法，无需对流形做过多先验假设；它们的求解都很简单，转化为求解特征值来得到数据的低维嵌入，不需要进行迭代，同时避免了局部极值问题的出现。

17

人脸识别中基于流形学习的特征提取方法研究 流形学习仍存在一些不足之处[39]。第一，增量学习问题。流形学习缺少从高维空间到低维嵌入空间的非线性映射关系，对新样本的处理具有局限性，不能直接应用到新样本的降维上，从而降低了算法的泛化性能。当新的样本出现时，需重新构造权值矩阵，同时计算相应矩阵的特征向量获得低维嵌入结果，因而很难适应动态的样本更新变化，缺乏增量学习的能力。第二，邻域点选取问题。由于算法本身的稳定性与邻域选择有关，一个适合的邻域是得到准确低维嵌入的前提条件。尽管较小的邻域更能体现邻域间的线性结构，但是必须保证邻域间有足够的交叠，这样流形上的样本点才能得到紧密的联系，否则流形的结构很难得到保持。第三，分类问题。现有的流形学习方法都是无监督的，并且算法是基于重构的，对于分类判别分析问题来说，低维嵌入结果不一定是最佳的。

2.6小结

本章中，首先介绍了流形学习的一些相关概念，然后较为详细的介绍了三种经典的流形学习方法：等距映射（ISOMAP）、局部线性嵌入（LLE）、拉普拉斯特征映射（LE），从算法的思想、算法流程以及它们各自的特点和缺点方面进行了阐述。最后对它们进行了比较，为后面章节的展开做好了铺垫。

18