第4期 谢朝霞，等：基于LE的多姿态人耳识别 ·323 具体算法分3步： 1)邻域选择：计算每个样本点X,的邻域点陬 距离最近的K个邻域点或固定半径ε的球状邻 域： 2计算重构权值矩阵W,:在X,的邻域中，计算 能最好地重构每个X,的权值矩阵W使重构误差 Ew)=∑x·∑，wgx最小其中，权值矩 阵W要满足2个约束条件：1)每一个数据点X,都 只能由它的邻近点来表示，若X,不是近邻点，则W, 为零矩阵；2)权值矩阵W的每一行的和为1这样， 求解最优权值就转化为重构误差EW)在约束条件 09 下的最小二乘问题： 0.5 3计算d维嵌入值Y,:根据权值矩阵W,重构 0 每个数据点的低维嵌入向量Y,使得重构误差 中(Y)最小： (a)S-Curve曲线 Φy=￥-∑w,Y (1) 1.5 为了保证式(1)能得到惟一解，低维嵌入Y,需 满足2个约束条件：1) ∑Y,为零矩阵： 0.5 2￥￥=1 LLE的优点在于：1)待定参数少，只有K和d -0. 2)具有整体最优解，不需要迭代，避免了局部极值 问题：3)嵌入向量的求解归结为求解稀疏矩阵的特 征向量，计算复杂度较低，容易执行」 图1给出了LE在人工合成数据上的低维嵌 20 入实例.在R空间中的S-Curve曲面上，随机选取 2000个数据点，邻域大小K=37,低维嵌入维数d= 2,采用LLE获取该数据集的最佳2维嵌入，结果如 2s-40-030010152025 图1(b)所示 2.2参数的选择 (b)二维嵌入结果 LLE算法中待定参数只有K和d然而这2个 图1LLE低维嵌入 Fig 1 Low dmensional embedding using LLE 参数的选择却对后续操作有着至关重要的影响。 221K的选择 直接影响低维嵌入映射的好坏 选择合理的K值，是LLE算法的关键问题之 222d的选择 一，K值过大1，可能会导致不能正确表示其局部 和K一样，d的选择是LE算法的另一个关键 几何关系；相反，K值过小，将会导致将连续流形分 问题.从直观角度考虑，K取值越大，说明对每个数 割为不相交的子流形 据点的描述信息越丰富，所需的自由变量的数目也 图2分别给出图1(a)中S-Cuve曲面在低维嵌 越多，参数d的取值也应增大.但是对于有限样本容 入维数相同时，即d=2,不同K值得到的低维嵌入 量，数据点在高维空间通常呈现出高度稀疏性，d取 映射 值过大显然不合理.因此，合理选择d值，是一个值 对比图1、图2可以看出，选取K=37图1)所 得考虑的问题 得到的2维嵌入结果显然要优于K取值分别为5、 图3分别给出图1(a)中S-Cuve曲面在邻域大 15、25和40时图2)的嵌入结果.这表明K取值不 小相同时，即K=37,不同d得到的低维嵌入结果 同，得到的低维嵌入结果也不同.K取值的合理与否 由于当d>3时，低维嵌入映射呈现在维数大于 1994-2008 China Academic Journal Electronic Publishing House.All rights reserved.htp://www.cnki.net具体算法分 3步 : 1)邻域选择 :计算每个样本点 Xi 的邻域点 (取 距离最近的 K个邻域点或固定半径 ε的球状邻 域 ) ; 2)计算重构权值矩阵 W ij:在 Xi 的邻域中 ,计算 能最好地重构每个 Xi 的权值矩阵 W ij ,使重构误差 E (W ) = ∑i Xi - ∑j W ijXj 2 最小. 其中 ,权值矩 阵 W ij要满足 2个约束条件 : 1)每一个数据点 Xi 都 只能由它的邻近点来表示 ,若 Xj不是近邻点 ,则 W ij 为零矩阵; 2)权值矩阵 W ij的每一行的和为 1. 这样 , 求解最优权值就转化为重构误差 E (W )在约束条件 下的最小二乘问题; 3)计算 d维嵌入值 Yi:根据权值矩阵 W ij ,重构 每个数据点的低维嵌入向量 Yi , 使得重构误差 Φ ( Y)最小 : Φ ( Y) = ∑i Yi - ∑j W ij Yj 2 . (1) 为了保证式 (1)能得到惟一解 ,低维嵌入 Yi 需 满 足 2 个 约 束 条 件 : 1 ) ∑i Yi 为 零 矩 阵; 2) 1 N ∑ i Yi Y T i = I. LLE的优点在于 : 1)待定参数少 ,只有 K和 d; 2)具有整体最优解 ,不需要迭代 ,避免了局部极值 问题; 3)嵌入向量的求解归结为求解稀疏矩阵的特 征向量 ,计算复杂度较低 ,容易执行. 图 1给出了 LLE在人工合成数据上的低维嵌 入实例. 在 R 3 空间中的 S2Curve曲面上 ,随机选取 2 000个数据点 ,邻域大小 K = 37,低维嵌入维数 d = 2,采用 LLE获取该数据集的最佳 2维嵌入 ,结果如 图 1 ( b)所示. 2. 2 参数的选择 LLE算法中待定参数只有 K和 d,然而这 2个 参数的选择却对后续操作有着至关重要的影响. 2. 2. 1 K的选择 选择合理的 K值 , 是 LLE算法的关键问题之 一. K值过大 [ 18 ] ,可能会导致不能正确表示其局部 几何关系 ;相反 , K值过小 ,将会导致将连续流形分 割为不相交的子流形. 图 2分别给出图 1 ( a)中 S2Curve曲面在低维嵌 入维数相同时 ,即 d = 2,不同 K值得到的低维嵌入 映射. 对比图 1、图 2可以看出 ,选取 K = 37 (图 1)所 得到的 2维嵌入结果显然要优于 K取值分别为 5、 15、25和 40时 (图 2)的嵌入结果. 这表明 K取值不 同 ,得到的低维嵌入结果也不同. K取值的合理与否 ( a) S2Curve曲线 ( b)二维嵌入结果 图 1 LLE低维嵌入 Fig. 1 Low dimensional embedding using LLE 直接影响低维嵌入映射的好坏. 2. 2. 2 d的选择 和 K一样 , d的选择是 LLE算法的另一个关键 问题. 从直观角度考虑 , K取值越大 ,说明对每个数 据点的描述信息越丰富 ,所需的自由变量的数目也 越多 ,参数 d的取值也应增大. 但是对于有限样本容 量 ,数据点在高维空间通常呈现出高度稀疏性 , d取 值过大显然不合理. 因此 ,合理选择 d值 ,是一个值 得考虑的问题. 图 3分别给出图 1 ( a)中 S2Curve曲面在邻域大 小相同时 ,即 K = 37,不同 d得到的低维嵌入结果. 由于当 d > 3时 ,低维嵌入映射呈现在维数大于 第 4期 谢朝霞 ,等 :基于 LLE的多姿态人耳识别 · 323 · © 1994-2008 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net