高维数据流形的低维嵌入及嵌入维数研究  

Study on the Low-Dimensional Embedding and the Embedding Dimensionality of Manifold of High-Dimensional Data

作　　者：赵连伟[1] 罗四维[1] 赵艳敞 刘蕴辉[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044 [2]Faculty of Information Technology,University of Technology,Sydney,Australia

出　　处：《软件学报》2005年第8期1423-1430,共8页Journal of Software

基　　金：No.60373029国家自然科学基金~~

摘　　要：发现高维数据空间流形中有意义的低维嵌入是一个经典难题.Isomap是提出的一种有效的基于流形理论的非线性降维方法,它不仅能够揭示高维观察数据的内在结构,还能够发现潜在的低维参数空间.Isomap的理论基础是假设在高维数据空间和低维参数空间存在等距映射,但并没有进行证明.首先给出了高维数据的连续流形和低维参数空间之间的等距映射存在性证明,然后区分了嵌入空间维数、高维数据空间的固有维数和流形维数,并证明存在环状流形高维数据空间的参数空间维数小于嵌入空间维数.最后提出一种环状流形的发现算法,判断高维数据空间是否存在环状流形,进而估计其固有维数及潜在空间维数.在多姿态三维对象的实验中证明了算法的有效性,并得到正确的低维参数空间.Finding meaningful low-dimensional embedded in a high-dimensional space is a classical problem.Isomap is a nonlinear dimensionality reduction method proposed and based on the theory of manifold. It not only can reveal the meaningful low-dimensional structure hidden in the high-dimensional observation data, but can recover the underlying parameter of data lying on a low-dimensional submanifold. Based on the hypothesis that there is an isometric mapping between the data space and the parameter space, Isomap works, but this hypothesis has not been proved. In this paper, the existence of isometric mapping between the manifold in the high-dimensional data space and the parameter space is proved. By distinguishing the intrinsic dimensionality of high-dimensional data space from the manifold dimensionality, and it is proved that the intrinsic dimensionality is the upper bound of the manifold dimensionality in the high-dimensional space in which there is a toroidal manifold. Finally an algorithm is proposed to find the underlying toroidal manifold and judge whether there exists one. The results of experiments on the multi-pose three-dimensional object show that the method is effective.

关 键 词：ISOMAP 环状流形 等距映射 嵌入维数 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]