第5期 文贵华，等：局部测地距离估计的Hessian局部线性嵌入 ·431 了很多弯曲的曲面，从而容易导致短路问题如图1 ②利用所有t迭代计算所有的d(x,x)= 所示，HLE采用欧氏距离确定点x的5邻域就导 mind d (x.x),d (x.x)+d (xx) 致短路问题，其邻域为虚线园内的点，点的类别分别 这样计算测地距离的时间复杂度近似为 为{square,square,square,circle,circle},这显然发 Ox3),复杂度太高.从图1可以看出，用测地距 生了短路现象，因为类别为square的点并不是点x 离确定x点的邻域，不必要计算x到所有点的测地 在流形上的最近邻，由此确定的邻域扭曲了数据真 距离，只需要计算x附近的点就可以了.具体方法是 实的邻域结构，进而产生不正确的低维嵌入，尤其对 首先确定局部区域大小L,然后以x为中心，选择其 稀疏或含噪音的数据集更是如此.相反，用测地距离 L个最近邻点构成该点的局部区域，进而在此局部 确定的邻域则为虚曲线内的点，点的类别为{circle,. 区域内估计x到其他L个点之间的测地距离.最后 circle,circle,circle,.circle},这是正确的结果.因此 根据估计的测地距离来选择最小的k个最近邻作为 只要测地距离的估计是正确的，那么确定的邻域就 点x的邻域，由此形成的邻域可显著减少短路边，如 能导致正确的低维嵌入 图2所示，其中k=12,L=mXk=512,而用于计 算测地距离的邻域大小k=6图2(a)的样本是从 Swiss roll surface随机采样600个点，但叠加了均值 为0和方差为Q3的高斯噪音后的含噪音数据集 图2(b)是利用Euclidean距离确定的邻域图，其中 明显出现了短路边，它们将靠得很近的2个不同曲 面连接了起来，而图2(c)是用局部估计的测地距离 确定的邻域，其中没有任何短路边出现，这说明了利 用局部估计的测地距离改进HLLE将取得更好的嵌 入结果.将据此改进的HLE记为GHLE,以区 别于利用全局估计的测地距离改进的HLLE,记为 图1欧氏距离和测地距离确定的不同邻域 GA-HLLE为保持算法的清晰性，给出完整的G Fig 1 Different neighborhoods using Euclidean distance HLE算法如下： and geodesic distance 10 以前采用ISOMA P计算测地距离的方法计算输 入数据之间的测地距离，并用之确定每个数据点的 01050-5 2010010 x-20100-10 邻域，然后用HLE方法计算每个点的低维嵌 入1，ISOMA P计算测地距离主要包括2步： (a)噪音数据集 (b)Euclidean (c)局部估计 1)根据观察数据x和邻域大小k构造邻域权重 图2利用Euclidean距离和局部估计的 图G=少，E.V对应于X中的观察数据，E为连接 测地距离确定的不同邻域图 2点的边的集合，(x,)∈E若x,是x的k最近邻， Fig 2 D ifferent neighborhood graph susing Euclidean x,与y之间的距离为殴氏距离dG(x, distance and bcally estmated geodesic distance 2)通过求G上任意两点之间的最短距离来估 算法CL-HLEE算法(X,kk,dm): 计流形上所有点对之间的测地距离d(x,x) /*输入中X是高维观察数据，k是用于确定切 ①初始化 空间的局部邻域大小，d是低维参数空间的维数，而 dE(x,,ifx,)∈E k是用于估计测地距离的邻域大小，m确定局部区 de (x.x) else 域的参数.输出是低维参数空间W*/ 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net了很多弯曲的曲面 ,从而容易导致短路问题. 如图 1 所示 , HLLE采用欧氏距离确定点 x的 52邻域就导 致短路问题 ,其邻域为虚线园内的点 ,点的类别分别 为 { square, square, square, circle, circle} ,这显然发 生了短路现象 ,因为类别为 square的点并不是点 x 在流形上的最近邻 ,由此确定的邻域扭曲了数据真 实的邻域结构 ,进而产生不正确的低维嵌入 ,尤其对 稀疏或含噪音的数据集更是如此. 相反 ,用测地距离 确定的邻域则为虚曲线内的点 ,点的类别为 { circle, circle, circle, circle, circle} ,这是正确的结果. 因此 只要测地距离的估计是正确的 ,那么确定的邻域就 能导致正确的低维嵌入. 图 1 欧氏距离和测地距离确定的不同邻域 Fig. 1 D ifferent neighborhoods using Euclidean distance and geodesic distance 以前采用 ISOMAP计算测地距离的方法计算输 入数据之间的测地距离 ,并用之确定每个数据点的 邻域 , 然后用 HLLE 方法计算每个 点的低 维嵌 入 [ 15 ] , ISOMAP计算测地距离主要包括 2步 : 1)根据观察数据 x和邻域大小 k构造邻域权重 图 G = (V, E). V 对应于 X中的观察数据 , E为连接 2点的边的集合 , ( xi , xj ) ∈E若 xi 是 xj的 k最近邻 , xi 与 xj之间的距离为殴氏距离 dG ( xi , xj ). 2)通过求 G上任意两点之间的最短距离来估 计流形上所有点对之间的测地距离 dG ( xi , xj ). ①初始化 dG ( xi , xj ) = dE ( xi , xj ) , if( xi , xj ) ∈ E, ∞, else. ②利用所有 t, 迭代计算所有的 dG ( xi , xj ) = m in{ dG ( xi , xj ) , dG ( xi , xt ) + dG ( xt , xj ) }. 这样 计 算 测 地 距 离 的 时 间 复 杂 度 近 似 为 O ( | x | 3 ) ,复杂度太高. 从图 1可以看出 ,用测地距 离确定 x点的邻域 ,不必要计算 x到所有点的测地 距离 ,只需要计算 x附近的点就可以了. 具体方法是 首先确定局部区域大小 L,然后以 x为中心 ,选择其 L个最近邻点构成该点的局部区域 ,进而在此局部 区域内估计 x到其他 L 个点之间的测地距离. 最后 根据估计的测地距离来选择最小的 k个最近邻作为 点 x的邻域 ,由此形成的邻域可显著减少短路边 ,如 图 2所示 ,其中 k = 12, L =m ×k = 5 ×12,而用于计 算测地距离的邻域大小 kg = 6. 图 2 ( a)的样本是从 Swiss roll surface随机采样 600个点 ,但叠加了均值 为 0和方差为 0. 3的高斯噪音后的含噪音数据集 , 图 2 ( b)是利用 Euclidean距离确定的邻域图 ,其中 明显出现了短路边 ,它们将靠得很近的 2个不同曲 面连接了起来 ,而图 2 ( c)是用局部估计的测地距离 确定的邻域 ,其中没有任何短路边出现 ,这说明了利 用局部估计的测地距离改进 HLLE将取得更好的嵌 入结果. 将据此改进的 HLLE记为 GL2HLLE,以区 别于利用全局估计的测地距离改进的 HLLE,记为 GA2HLLE. 为保持算法的清晰性 ,给出完整的 GL2 HLLE算法如下 : ( a)噪音数据集 ( b) Euclidean ( c)局部估计 图 2利用 Euclidean距离和局部估计的 测地距离确定的不同邻域图 Fig. 2 D ifferent neighborhood graph susing Euclidean distance and locally estimated geodesic distance 算 法 GL2HLEE算法 (X, k, kg , d, m ) : /3 输入中 X是高维观察数据 , k是用于确定切 空间的局部邻域大小 , d是低维参数空间的维数 ,而 kg 是用于估计测地距离的邻域大小 , m 确定局部区 域的参数. 输出是低维参数空间 W 3 / 第 5期 文贵华 ,等 :局部测地距离估计的 Hessian局部线性嵌入 ·431·