第3卷第5期 智能系统学报 Vol 3 Na 5 2008年10月 CAA I Transactions on Intelligent Systems 0ct2008 局部测地距离估计的Hessian局部线性嵌入 文贵华，江丽君2，文军 (1华南理工大学计算机科学与工程学院，广东广州510641；2华南理工大学电子材料科学与工程系，广东广州 510641,3湖北民族学院理学院，湖北恩施445000) 摘要：为处理极度弯曲的数据流形，提出了基于局部测地距离估计的Hessian局部线性嵌入算法，算法采用Hessian局 部线性嵌入(HLLE)的概念框架，采用局部估计的测地距离而不是欧氏距离来确定每个点的邻域，从而减少数据流形弯 曲对邻域选择的影响.算法可认为是全局和局部方法的综合，在性能上不仅比HLE显著提高，有更强的鲁棒性，而且时 间增加不明显.标准数据集上的实验结果验证了所提方法的有效性. 关键词：流形学习；Hessian变换；局部线性嵌入；测地距离 中图分类号：1P391文献标识码：A文章编号：1673-4785(2008)050429-07 Usng locally estinated geodesic distances to i prove Hessian local linear em beddng WEN Gui-hua',JNG Li-jun,WEN Jun' (1.SchoolofComputer Science and Engineering.South China University of Technolgy,Guangzhou 510641,China,2 Deparment of Electronic Material Science and Engineering.South China University of Technology,Gunaghou 510641,China;3.School ofMathe- matical Science,Hubei Insitute for Natonalities,Enshi 445000.China) Abstract:To deal with highly curved data manifolds,the Hessian locally linear embedding(HLLE)algorithm was modified based on a bcally estmated geodesic distance It used the general conceptual framework of HLLE to guar- antee correct setting of local isometry to an open connected subset It empbys the bcally estmated geodesic dis- tance instead of the Euclidean distance to detem ine the neighborhood of any point,so that it reduces the disbrting influence of curvature of the data manifold on detem ining the neighborhood This approach can be regarded as the integration of a bcalmethod and a glbalmethod,so that it has better peromance and stability than HILLE,with only a slight increase in computational tie Experments conducted on benchmark data sets verified etficoncy of the proposed app roach Keywords:maniold leaming Hessian transfomation;bcally linear embedding geodesic distance 很多高维数据如遥感、气候等常常分布于较低 多改进算法.LE在降维嵌入过程中保持局部的几 维的流形上，自从国际著名期刊《Science》在2000 何结构不变，并能避免局部极小，最终获得一个全 年发表2种最有代表性的方法OMAP和LLE2)局的低维嵌入系统，效果也很好.目前发展的改进算 以来，寻找描述这样低维流形的参数空间就成为最 法包括利用拉普拉斯(Lap lac ian)B1、赫森(Hessian) 近的研究热点.ISOMAP在降维过程中通过计算点 变换改进的算法HE,、利用数据分类信息改进 对之间的测地距离，并采用MDS方法来获取全局最 的监督LLEI、增量式LLE6、利用Fisher改进的 优的几何结构，获得了较好的效果，目前已发展了很 LE)、以及利用PCA改进的鲁棒性LLE⑧等.性能 上，HLLE是对LE的较大改进，它在某些情况下超 收稿日期：2007-11-25 基金项目：广东省科技攻关资助项目(2007B030803006):湖北省科 越了ISOMAP的能力.ISOMA P的基本假设是全局 技攻关资助项目(2005A4101C17), 通信作者：文贵华.Emai止crghwen@(scut edu cn 等距映射和凸的参数空间，这在很多情况下难以满 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3卷第 5期 智 能 系 统 学 报 Vol. 3 №. 5 2008年 10月 CAA I Transactions on Intelligent System s Oct. 2008 局部测地距离估计的 Hessian局部线性嵌入 文贵华 1 , 江丽君 2 , 文 军 3 (1. 华南理工大学 计算机科学与工程学院 , 广东 广州 510641; 2. 华南理工大学 电子材料科学与工程系 ,广东 广州 510641; 3. 湖北民族学院 理学院 ,湖北 恩施 445000) 摘 要 :为处理极度弯曲的数据流形 ,提出了基于局部测地距离估计的 Hessian局部线性嵌入算法. 算法采用 Hessian局 部线性嵌入 (HLLE)的概念框架 ,采用局部估计的测地距离而不是欧氏距离来确定每个点的邻域 ,从而减少数据流形弯 曲对邻域选择的影响. 算法可认为是全局和局部方法的综合 ,在性能上不仅比 HLLE显著提高 ,有更强的鲁棒性 ,而且时 间增加不明显. 标准数据集上的实验结果验证了所提方法的有效性. 关键词 :流形学习 ; Hessian变换 ;局部线性嵌入 ; 测地距离 中图分类号 : TP391 文献标识码 : A 文章编号 : 167324785 (2008) 0520429207 Using locally estimated geodesic distances to improve Hessian local linear embedding W EN Gui2hua 1 , J IANG L i2jun 2 , W EN Jun 3 ( 1. School of Computer Science and Engineering, South China University of Technology, Guangzhou 510641, China; 2. Department of Electronic Material Science and Engineering, South China University of Technology, Gunagzhou 510641, China; 3. School ofMathe2 matical Science, Hubei Insitute for Nationalities, Enshi 445000, China) Abstract: To dealwith highly curved data manifolds, the Hessian locally linear embedding (HLLE) algorithm was modified based on a locally estimated geodesic distance. It used the general concep tual framework of HLLE to guar2 antee correct setting of local isometry to an open connected subset. It emp loys the locally estimated geodesic dis2 tance instead of the Euclidean distance to determ ine the neighborhood of any point, so that it reduces the distorting influence of curvature of the data manifold on determ ining the neighborhood. This app roach can be regarded as the integration of a local method and a global method, so that it has better performance and stability than HLLE, with only a slight increase in computational time. Experiments conducted on benchmark data sets verified etficioncy of the p roposed app roach. Keywords:manifold learning; Hessian transformation; locally linear embedding; geodesic distance 收稿日期 : 2007211225. 基金项目 :广东省科技攻关资助项目 ( 2007B030803006) ; 湖北省科 技攻关资助项目 (2005AA101C17) 1 通信作者 :文贵华. E2mail: crghwen@ scut. edu. cn. 很多高维数据如遥感、气候等常常分布于较低 维的流形上 ,自从国际著名期刊《Science》在 2000 年发表 2种最有代表性的方法 ISOMAP [ 1 ]和 LLE [ 2 ] 以来 ,寻找描述这样低维流形的参数空间就成为最 近的研究热点. ISOMAP在降维过程中通过计算点 对之间的测地距离 ,并采用 MDS方法来获取全局最 优的几何结构 ,获得了较好的效果 ,目前已发展了很 多改进算法. LLE在降维嵌入过程中保持局部的几 何结构不变 , 并能避免局部极小 ,最终获得一个全 局的低维嵌入系统 ,效果也很好. 目前发展的改进算 法包括利用拉普拉斯 (Lap lacian) [ 3 ]、赫森 (Hessian) 变换改进的算法 HLLE [ 4 ]、利用数据分类信息改进 的监督 LLE [ 5 ]、增量式 LLE [ 6 ]、利用 Fisher改进的 LLE [ 7 ]、以及利用 PCA改进的鲁棒性 LLE [ 8 ]等. 性能 上 , HLLE是对 LLE的较大改进 ,它在某些情况下超 越了 ISOMAP的能力. ISOMAP的基本假设是全局 等距映射和凸的参数空间 ,这在很多情况下难以满