• Article
  • | |
  • Metrics
  • |
  • Reference [20]
  • |
  • Related [20]
  • |
  • Cited by
  • | |
  • Comments
    Abstract:

    Feature extraction of data lying on disconnected manifold is an open problem in the field of manifold learning, and decomposition-composition (D-C) algorithm is the most effective method so far to deal with this problem. However, the biggest limitation of D-C method is edge problem, that is when the nearest data points of different clusters are located in the inner part instead of the edge part of the corresponding cluster, D-C method always behaves poorly. To tackle this key issue, a method, called transition curve method, is presented in this paper. The main idea of the method is to make all clusters on the underlying manifold connect more effectively by constructing smooth transition curves which connect the nearest edge points of different clusters, and in this way the global shape of the data can be preserved better in the low-dimensional space. Experimental results on a series of synthetic and image data sets verify that the transition curve method performs evidently better than D-C method. Particularlly, the edge problem is alleviated. In this way, the application scope of D-C method is expanded remarkably.

    Reference
    [1] Tenenbaum JB, de Silva V, Langford JC. A global geometric framework for nonlinear dimensionality reduction. Science, 2000, 290(5500):2319?2323. [doi: 10.1126/science.290.5500.2319]
    [2] Roweis ST, Saul LK. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000,290(5500):2323?2326. [doi: 10.1126/science.290.5500.2323]
    [3] Belkin M, Niyogi P. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 2003,15(6): 1373?1396. [doi: 10.1162/089976603321780317]
    [4] Zhang ZY, Zha HY. Principal manifolds and nonlinear dimension reduction via local tangent space alignment. Technical Report, CSE-02-019, Pennsylvania: Pennsylvania State University, 2002.
    [5] Bachmann CM, Ainsworth TL, Fusina RA. Exploiting manifold geometry in hyperspectral imagery. IEEE Trans. on Geoscience and Remote Sensing, 2005,43(3):441?454. [doi: 10.1109/TGRS.2004.842292]
    [6] Lee JG, Zhang CS. Classification of gene-expression data: The manifold-based metric learning way. Pattern Recognition, 2006, 39(1):2450?2463. [doi: 10.1016/j.patcog.2006.05.026]
    [7] Venna J, Kaski S. Local multidimensional scaling. Neural Networks, 2006,19(6-7):889?899. [doi: 10.1016/j.neunet.2006.05.014]
    [8] Yang L. Sammon’s nonlinear mapping using geodesic distances. In: Kittler J, Petrou M, Nixon M, eds. Proc. of the 17th Int’l Conf. on Pattern Recognition (ICPR 2004). Washington: IEEE Computer Society Press, 2004. 303?306.
    [9] Yang L. Building k-edge-connected neighborhood graph for distance-based data projection. Pattern Recognition Letters, 2005, 26(13):2015?2021. [doi: 10.1016/j.patrec.2005.03.021]
    [10] Yang L. Building k edge-disjoint spanning trees of minimum total length for isometric data embedding. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2005,27(10):1680?1683. [doi: 10.1109/TPAMI.2005.192]
    [11] Yang L. Building k-connected neighborhood graphs for isometric data embedding. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2006,28(5):827?831. [doi: 10.1109/TPAMI.2006.89]
    [12] Yang L. Tetrahedron mapping of points from N-space to three-space. In: Kasturi R, Laurendeau D, Suen C, eds. Proc. of the 16th Int’l Conf. on Pattern Recognition (ICPR 2002). Washington: IEEE Computer Society Press, 2002. 343?346.
    [13] Yang L. k-edge connected neighborhood graph for geodesic distance estimation and nonlinear data projection. In: Kittler J, Petrou M, Nixon M, eds. Proc. of the 17th Int’l Conf. on Pattern Recognition (ICPR 2004). Washington: IEEE Computer Society Press, 2004. 196?199.
    [14] Yang L. Distance-Preserving mapping of patterns to 3-space. Pattern Recognition Letters, 2004,25(1):119?128. [doi: 10.1016/j.patrec.2003.09.009]
    [15] Yang L. Distance-Preserving projection of high dimensional data. Pattern Recognition Letters, 2004,25(2):259?266. [doi: 10.1016/ j.patrec.2003.10.010]
    [16] Yang L. Distance-Preserving projection of high dimensional data for nonlinear dimensionality reduction. IEEE Trans. on Pattern Analysis and Machine Intelligence, 2004,26(9):1243?1246. [doi: 10.1109/TPAMI.2004.66]
    [17] Meng DY, Leung Y, Fung T, Xu ZB. Nonlinear dimensionality reduction of data lying on the multicluster manifold. IEEE Trans. on Systems, Man and Cybernetics?Part B: Cybernetics, 2008,38(4):1111?1122. [doi: 10.1109/TSMCB.2008.925663]
    [18] Vardi Y, Zhang CH. The multivariate L1-median and associated data depth. Proc. of the National Academy of Sciences, 2000,97(4): 1423?1426.
    [19] Knuth DE. The Art of Computer Programming, Vol.3: Sorting and Searching. 2nd ed., Reading: Addison-Wesley, 1973. 144?148.
    [20] Cormen TH, Leiserson CE, Rivest RL, Stein C. Introduction to Algorithms. 2nd ed., Cambridge: MIT Press, 2002. 614?618.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

古楠楠,孟德宇,徐宗本.针对非连通流形数据降维的过渡曲线方法.软件学报,2010,21(8):1898-1907

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:September 10,2008
  • Revised:April 29,2009
You are the first2035312Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063