·430· 智能系统学报 第3卷 足.而LLE只要求局部等距映射和开的连通参数 距离，方法是假定当两点非常近时，测地距离等于欧 空间，因而应用范围更宽.但是LE需要保持邻域 氏距离，而对较远的点对之间的测地距离则根据近 的线性化，当数据流形比较弯曲时，难以满足，不可 邻点之间测地距离的累加实现.当观察数据集足够 避免地面临短路问题，因此需要邻域优化.目前有3 密集且内在的参数空间是凸的，则SOMAP能够成 类与邻域相关的工作，第1类是构造连通的邻域 功地获得参数空间.ISOMAP面临的问题是，在很多 图9-)：第2类采用新的测度来选择邻域点1-51，例 情况下参数空间并不是凸的，此时它得不到正确的 如监督LE利用分类信息构造新的测度)]，但需要 结果 分类信息，替代策略是采用自动聚类确定分类信 HLLE采用局部线性方法实现流形学习.它只 息)同时图代数还可以用来定义新的测度并优化 要求局部等距映射的子集是开的且连通，而不必是 邻域14-s1,以及利用测地距离确定邻域1,11等：第3 凸的.其理论依据来源于流形切空间上的Hessian 类是研究邻域的大小问题，包括如何选择合适的邻 变换.假定流形MCR”是光滑的，其任意点m∈M 域大小61，以及适用于非均匀分布流形的邻域大小 都有切空间TM),在此空间引入欧氏空间的内积 自适应确定算法1.本文的工作属于第2类，采用 就可以建立局部坐标系统，且有原点O∈TmM).设 局部估计的测地距离来确定邻域，以减少流形弯曲 Nm是m∈M的邻域，对任意m'∈Nm都有惟一的 对邻域选择的影响.此前华南理工大学曾采用测地 最近点v'∈T.M)使得映射m'→v是光滑的，因此 距离来确定HLE的邻域Is1,Claudio Varini采用测 Nm具有局部坐标系统，记为(n,m.设 地距离来确定LE的邻域)，但它们都需要计算 F:M→R在m附近是C2光滑的，G:U→R,UCR是 所有点对之间的测地距离，然后用于确定邻域，增加 零点O的一个邻域.令g(x)=f(m),因m'x是 的时间复杂度太高，接近OW).为此本文改变策 光滑的，g是C光滑的，则f的Hessian变换为 略，只估计每个点与其局部区域内的点之间的测地 距离，并用之确定HLE的邻域，不仅增加的时间不 m,=是是§ Cx:C g(x)Ix-0 明显，而且效果仍然很好.最后的实验表明此改进算 二次型HD=m)d定义了fM一 法在降维性能上比ISOMA P、HLLE和LLE都有效， 更适合于处理弯曲的数据流形 R在M上的平均弯曲率，其中‖·I2是Frobenius 范数.可以证明若参数空间⊙CR是开的连通子 1 Hessian局部线性嵌入 集，则H(f)有一个(d+1)维的零空间(null pace), 假定有一个参数空间⊙CR和一个光滑映射 参数空间能够通过计算此零空间的一个合适的基坐 中：⊙→R",其中嵌入空间R”满足n>d,则称M= 标来发现，这就是HLE的核心.由此可以发现：1) 中©)为流形.流形学习的目的是根据观察数据确 框架上HLLE与LE和LE一致，不同的是用Hes 定参数空间⊙CR ISOMAP采用等距嵌入(isomet- sian变换取代了LE的Lap lacian算子，而LLE是LE ric embedding)和等角嵌入(conomal embedding) 理论框架下的一种经验实现；2)HLE需要对每个 来实现流形学习.其基本假设是：1)等距，即测地距 数据点计算n次偏导数，当观察数据的维非常高 离在等距嵌入映射下是不变的，流形上任意点之间 时，计算量不小：3)每个点的切空间要求其邻域是 的测地距离在等距嵌入变换下获得的欧氏空间中仍 线性的，当邻域高度弯曲时，极易面临短路威胁，这 然保持G(x以=Ia-B‖，x∈M,y∈M,a∈O,B∈O; 是HLLE需要克服的另一个主要问题 2凸性，即参数空间⊙CR是凸的.对任意a,B∈⊙， 线段{(1-)a+B11∈0,1)仍然属于⊙ 2改进算法 SOMA P算法利用等距嵌入的这种不变性，在 HLLE对极度弯曲的数据流形难以得到正确的 没有任何关于观察数据测度知识的基础上构造测地 结果，原因是被当作线性化的局部区域实际上包含 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net足. 而 HLLE只要求局部等距映射和开的连通参数 空间 ,因而应用范围更宽. 但是 HLLE需要保持邻域 的线性化 ,当数据流形比较弯曲时 ,难以满足 ,不可 避免地面临短路问题 ,因此需要邻域优化. 目前有 3 类与邻域相关的工作 ,第 1 类是构造连通的邻域 图 [ 9210 ] ;第 2类采用新的测度来选择邻域点 [ 11215 ] ,例 如监督 LLE利用分类信息构造新的测度 [ 5 ] ,但需要 分类信息 ,替代策略是采用自动聚类确定分类信 息 [ 13 ] . 同时图代数还可以用来定义新的测度并优化 邻域 [ 14215 ] ,以及利用测地距离确定邻域 [ 11, 18 ]等 ;第 3 类是研究邻域的大小问题 ,包括如何选择合适的邻 域大小 [ 16 ] ,以及适用于非均匀分布流形的邻域大小 自适应确定算法 [ 17 ] . 本文的工作属于第 2类 ,采用 局部估计的测地距离来确定邻域 ,以减少流形弯曲 对邻域选择的影响. 此前华南理工大学曾采用测地 距离来确定 HLLE的邻域 [ 18 ] , Claudio Varini采用测 地距离来确定 LLE的邻域 [ 11 ] , 但它们都需要计算 所有点对之间的测地距离 ,然后用于确定邻域 ,增加 的时间复杂度太高 ,接近 O (N 3 ). 为此本文改变策 略 ,只估计每个点与其局部区域内的点之间的测地 距离 ,并用之确定 HLLE的邻域 ,不仅增加的时间不 明显 ,而且效果仍然很好. 最后的实验表明此改进算 法在降维性能上比 ISOMAP、HLLE和 LLE都有效 , 更适合于处理弯曲的数据流形. 1 Hessian局部线性嵌入 假定有一个参数空间 Θ < R d 和一个光滑映射 φ:Θ →R n ,其中嵌入空间 R n 满足 n > d,则称 M = φ(Θ)为流形. 流形学习的目的是根据观察数据确 定参数空间 Θ< R d . ISOMAP采用等距嵌入 ( isomet2 ric embedding) 和等角嵌入 ( conformal embedding) 来实现流形学习. 其基本假设是 : 1)等距 ,即测地距 离在等距嵌入映射下是不变的 ,流形上任意点之间 的测地距离在等距嵌入变换下获得的欧氏空间中仍 然保持 G ( x, y) =‖α-β‖, x∈M, y∈M,α∈Θ,β∈Θ; 2)凸性,即参数空间Θ< R d 是凸的. 对任意 α,β∈Θ, 线段 { (1 - t)α+βt | t∈(0, 1) }仍然属于 Θ. ISOMAP算法利用等距嵌入的这种不变性 ,在 没有任何关于观察数据测度知识的基础上构造测地 距离 ,方法是假定当两点非常近时 ,测地距离等于欧 氏距离 ,而对较远的点对之间的测地距离则根据近 邻点之间测地距离的累加实现. 当观察数据集足够 密集且内在的参数空间是凸的 ,则 ISOMAP能够成 功地获得参数空间. ISOMAP面临的问题是 ,在很多 情况下参数空间并不是凸的 ,此时它得不到正确的 结果. HLLE采用局部线性方法实现流形学习. 它只 要求局部等距映射的子集是开的且连通 ,而不必是 凸的. 其理论依据来源于流形切空间上的 Hessian 变换. 假定流形 M < R n 是光滑的 ,其任意点 m ∈M 都有切空间 Tm (M ) ,在此空间引入欧氏空间的内积 就可以建立局部坐标系统 ,且有原点 O∈Tm (M ). 设 Nm 是 m ∈M 的邻域 , 对任意 m ′∈Nm 都有惟一的 最近点 v′∈Tm (M )使得映射 m ′→v′是光滑的 ,因此 Nm 具有局部坐标系统 ,记为 x1 ( tan, m ) , …, x ( tan, m ) d . 设 F:M →R在 m 附近是 C 2 光滑的 , G: U→R, U < R d 是 零点 O 的一个邻域. 令 g ( x) = f (m ′) ,因 m ′→x是 光滑的 , g是 C 2 光滑的 ,则 f的 Hessian变换为 (H tan f (m ) ) i, j = 5 5xi 5 5xj g ( x) | x =0 . 二次型 H ( f) = M∫‖H tan f (m ) ‖ 2 F dm 定义了 f:M → R在 M 上的平均弯曲率 ,其中 ‖·‖ 2 F 是 Frobenius 范数. 可以证明若参数空间 Θ < R d 是开的连通子 集 ,则 H ( f)有一个 ( d + 1)维的零空间 ( null space) , 参数空间能够通过计算此零空间的一个合适的基坐 标来发现 ,这就是 HLLE的核心. 由此可以发现 : 1) 框架上 HLLE与 LE和 LLE一致 ,不同的是用 Hes2 sian变换取代了 LE的 Lap lacian算子 ,而 LLE是 LE 理论框架下的一种经验实现 ; 2) HLLE需要对每个 数据点计算 n ×n次偏导数 ,当观察数据的维非常高 时 ,计算量不小; 3)每个点的切空间要求其邻域是 线性的 ,当邻域高度弯曲时 ,极易面临短路威胁 ,这 是 HLLE需要克服的另一个主要问题. 2 改进算法 HLLE对极度弯曲的数据流形难以得到正确的 结果 ,原因是被当作线性化的局部区域实际上包含 ·430· 智 能 系 统 学 报 第 3卷