·432· 智能系统学报 第3卷 1)首先计算每个点的mXk个最近邻构成该 LLE、ISOMAP及其许多改进算法都采用的标准测试 点的局部区域，然后以k为邻域大小估计x到局部 数据，包括Swiss roll surface、S-cuve、3 D clusters、To- 区域内.其他任意点之间的测地距离，然后根据估计 oidal Helix和Twin Peaks,.在每个数据集上均采样 的测地距离来选择最小的k个最近邻作为点x的邻 600个点构造实验数据. 域，并将每个点的邻域表达为中心化的行向量k 31性能分析 矩阵M; GHLE等5种方法在几种标准数据集上的 2)采用奇异值分解每个邻域矩阵M',将其正 运行结果如图3~7所示.图3中的实验数据是采用 交向量V的前d个分量作为其切空间： HLE的方法从Swiss roll surface.上采样一个数据规 3)求切空间的Hessian矩阵.当d=2时，根据 模为600个点的长方形但从其中心移去一个小的长 切空间中的点形成如下矩阵X=[1V,.1V,2 方形而形成的非凸数据集，这也是HLE实验中采 N.)2N.22)N.1.2)1,其中V.1 用的实验数据.不难发现在采样的这个数据集上 表示切空间中所有点的第一维的值，对d>2采用相 LLE和HLE不能够完美地将数据嵌入在二维空 同的方法创建1+d+d(d+1)2列的矩阵，然后用 间.ISOMAP将去除的区域强烈膨胀，并扭曲其余的 Gram-Schm idti正交化x'产生新的正交矩阵又，将其 数据点.而GA-HLLE和GHLE能够较完美地将 转置后取最后的d(d+l)/2列构成Hessian矩阵H'; 数据嵌入在二维空间，其中心移去的一个小长方形 少首先构造二次型H,=∑∑(H),H)山， 也能在嵌入的二维空间中正确体现，因此在这个数 对H进行特征分析，获取其d+1个最小特征值对 据集上GLHLLE能够解决ISOMAP等其他方法不 应的d+1维子空间，第1个特征值0对应于常函 能解决的问题.同时在剩余的4个数据集上，GL 数，接下来的d个特征向量就构成d维空间，对其选 HLE和GA-HLLE都胜过HLE和LLE,而G 择一个正交基，变换就可获得要恢复的参数空 HLLE和GA-HLLE的效果无明显区别.在有的数据 间w. 集如图5上它们的性能略差于SOMA P,而在另外 算法GL-HLLE中的1)利用局部估计的测地距 一些数据集如图3和图7上它们的性能则优于SO- 离确定每个点的邻域，余下的步骤与HLLE相同，因 MAP因此从整体性能上GL-HLLE和GA-HLLE是 此复杂的数学推导和更详细的算法描述见HLLE原 相对较好的方法，特别是它们都比LE好 文.GHLE增加了估计局部测地距离的时间 10 ON),N=X|,但与HLLE一样都只需要N个k 稀疏的特征问题计算，而ISOMAP需要一个NW 20 -50 密集的特征问题求解.如果N很大时，显然G 105-50 -40-200204060 HLE比ISOMAP有优越性，而从后面的实验结果 (a)原始数据 (b)LLE (c)ISOMAP 看，GL-HLLE的降维性能比HLLE、ISOMAP和LLE 0.10 0.05 0.05 都要好 0.05 y 3实验分析 -0.05 实验比较GL-HLLE与GA-HLLE、HLE、LLE -0.0500.05-0.0500.05 -0.0500.05 和SOMA方法的性能和时间复杂度.几种方法均采 (d)HLLE (e)GA-HILE (f)GL-HLLE 用Matlab编程实现，其中HLE、LLE和ISOMAP采 图3几种算法在数据集wiss roll surface.上的结果 用原作者提供的Matlab代码，GA-HLLE和G Fig 3 Embedding results of the compared app roaches HLLE由作者编程实现.实验中的参数设置为线性 on Swiss roll surface data 重构的邻域k=12,局部区域大小为5水，而估计 测地距离的邻域参数取6实验数据采用HLLE 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net1) 首先计算每个点的 m ×k个最近邻构成该 点的局部区域 ,然后以 kg 为邻域大小估计 x到局部 区域内. 其他任意点之间的测地距离 ,然后根据估计 的测地距离来选择最小的 k个最近邻作为点 x的邻 域 ,并将每个点的邻域表达为中心化的行向量 k ×n 矩阵 M i ; 2) 采用奇异值分解每个邻域矩阵 M i ,将其正 交向量 V的前 d个分量作为其切空间; 3) 求切空间的 Hessian矩阵. 当 d = 2时 ,根据 切空间中的点形成如下矩阵 X i = [ 1 V·, 1 V·, 2 (V·, 1 ) 2 (V·, 2 2 ) (V·, 1 ×V·, 2 ) ],其中 V·, 1 表示切空间中所有点的第一维的值 ,对 d > 2采用相 同的方法创建 1 + d + d ( d + 1) /2列的矩阵 ,然后用 Gram2Schm idt正交化 X i 产生新的正交矩阵 XŠ i ,将其 转置后取最后的 d ( d +1) /2列构成 Hessian矩阵 H i ; 4) 首先构造二次型 Hij = 6l 6r ( (H l ) r, i (H l ) r, j ), 对 H 进行特征分析 ,获取其 d + 1个最小特征值对 应的 d + 1维子空间 ,第 1个特征值 0对应于常函 数 ,接下来的 d个特征向量就构成 d维空间 ,对其选 择一个正交基 , 变换就可获得要恢复的参数空 间 W. 算法 GL2HLLE中的 1)利用局部估计的测地距 离确定每个点的邻域 ,余下的步骤与 HLLE相同 ,因 此复杂的数学推导和更详细的算法描述见 HLLE原 文 [ 4 ] . GL2HLLE增加了估计局部测地距离的时间 O (N ) , N = |X | ,但与 HLLE一样都只需要 N 个 k ×k 稀疏的特征问题计算 ,而 ISOMAP需要一个 N ×N 密集的特征问题求解. 如果 N 很大时 , 显然 GL2 HLLE比 ISOMAP有优越性 ,而从后面的实验结果 看 , GL2HLLE的降维性能比 HLLE、ISOMAP和 LLE 都要好. 3 实验分析 实验比较 GL2HLLE与 GA2HLLE、HLLE、LLE 和 ISOMA方法的性能和时间复杂度. 几种方法均采 用 Matlab编程实现 ,其中 HLLE、LLE和 ISOMAP采 用原作者 提 供 的 Matlab 代 码 , GA2HLLE 和 GL2 HLLE由作者编程实现. 实验中的参数设置为线性 重构的邻域 k = 12,局部区域大小为 5 ×k, 而估计 测地距离的邻域参数取 6. 实验数据采用 HLLE、 LLE、ISOMAP及其许多改进算法都采用的标准测试 数据 ,包括 Swiss roll surface、S2curve、3D clusters、To2 roidal Helix和 Twin Peaks,在每个数据集上均采样 600个点构造实验数据. 3. 1 性能分析 GL2HLLE等 5种方法在几种标准数据集上的 运行结果如图 3～7所示. 图 3中的实验数据是采用 HLLE的方法从 Swiss roll surface上采样一个数据规 模为 600个点的长方形但从其中心移去一个小的长 方形而形成的非凸数据集 ,这也是 HLLE实验中采 用的实验数据 [ 4 ] . 不难发现在采样的这个数据集上 LLE和 HLLE不能够完美地将数据嵌入在二维空 间. ISOMAP将去除的区域强烈膨胀 ,并扭曲其余的 数据点. 而 GA2HLLE和 GL2HLLE能够较完美地将 数据嵌入在二维空间 ,其中心移去的一个小长方形 也能在嵌入的二维空间中正确体现 ,因此在这个数 据集上 GL2HLLE能够解决 ISOMAP等其他方法不 能解决的问题. 同时在剩余的 4 个数据集上 , GL2 HLLE和 GA2HLLE 都胜过 HLLE 和 LLE, 而 GL2 HLLE和 GA2HLLE的效果无明显区别. 在有的数据 集如图 5上它们的性能略差于 ISOMAP,而在另外 一些数据集如图 3和图 7上它们的性能则优于 ISO2 MAP. 因此从整体性能上 GL2HLLE和 GA2HLLE是 相对较好的方法 ,特别是它们都比 HLLE好. 图 3几种算法在数据集 Swiss roll surface上的结果 Fig. 3 Embedding results of the compared app roaches on Swiss roll surface data ·432· 智 能 系 统 学 报 第 3卷