The Manifold Learning Theory And Its Application In Spatial Information Processing

As development of computer application involves more and more high dimensional data procession tasks, researchers are facing a huge chanllenge on how to compress the dimensionality of those high dimensional data effectively. Manifold learning is a popular dimensionality reduction method which accomplish its task by maintaining the topological structure of high dimensional data in the lower target data space. Locally linear embedding (LLE) is a widely-used manifold learning algorithm, in this paper we improve on the algorithm and put it to use in spatial data index.This paper intorduces the manifold learning method, illusstrate its applications and discuss one typical manifold learning method—the locally linear embedding algorithm. In practical applications, it occurs to us that most high dimensional data to be processed are sparsely sampled, while according to numerical experiments, the locally linear learning embedding algorithm fails to function in case of sparse source data. By anaylyzing the local linear hypotheses of the algorighm and its measures to keep the near neighbor property during implementation, we find a inconsistency between the algorithm's theoretical basis and its implementation procedures. The locally linear embedding algorithm keeps the source data's near neighbor property by forcing the denotation coordination unchanged and deriving it directly from the source data, while in fact the denotation coordination should be mucually-dicided by data inboth the source and the target data space, the locally linear embedding algorithm lost sight of the target data space's role in computing the denotation coordination, which leads to a deviation from the true value of the denotation coordination, such deviation becomes more and more serious as data becomes sparser. Thus, in case of sparse source data, the algorithm fails to function because it can no longer keep the near neighbor property of the data.To solve this problem , we propose a new method by optimizing the two majorized functions of the algorith together, in which the coordination is co-decided by data in both the source and the target data space—the Unified Locally Linear Embedding(ULLE) Algorithm.The improved algorithm truly realize the locally linear embedding's basic idea and can keep the topological structure of the source data in case of sparse data source, the method's validity is demonstrated through experiments on artificial S curve and on two groups of face images.Spatial information application is a hot research subject for the moment, but since spatial data is a kind of high dimensional and highly complex data source and is always accompanied with noises, how to organize n query and process the spatical data effectively is a very important problem, and spatial data index is a key technique in accomplishing effective data searching. Basing on our analysis and understanding of spatial data, we combine unified locally linear embedding algorithm with R-tree to realize spatial data indexing...