Research On Neighborhood Selection And Incremental Algorithm In Manifold Learning

With the rapid development of information technology, the scale of dataset is still increasing in a geometrical rate. There has been a large number of high-dimensional data in the real world, which is high dimensional sparse. The feature of the data brings enormous challenge to modern data analysis and processing. Dimension reduction is one of tasks for the many high-dimensional data to analyze in preprocessing stage.However, because of the expansion of the dimension, traditional linear dimension reduction can not meet demand, and we need to find a new technology to reduce the dimension. Manifold learning is a new technology for nonlinear dimensionality reduction, which is to uncover the nature of dataset by analyzing the external characteristics of high-dimensional observed dataset. And it has become the key technology to preprocess high-dimensional massive dataset. In recent years, manifold learning algorithms based on different theories and methods have achieved good results, and can better find low-dimensional manifold structures of high-dimensional observed dataset.However, manifold learning algorithms still have some problems. One is how to adaptively build neighborhood relationship for different manifold structure. The other is we can not get explicit mapping function from the original sample space to low-dimensional embedding space, and it is difficult to calculate low-dimensional embedding of new data. So, we should pay attention to the important problems in theory and applications. In this paper, we study these two issues, specific contributions are as follows:(1) An orderly adaptive neighborhood selection algorithm is proposed because the traditional neighborhood selection algorithm has a defect that can not select neighbors adaptively based on the sample density and curvature. In this algorithm, data point starts with the smallest curvature point in the manifold, and breadth-first searching algorithm is used to expand manifold data with the existing reasonable neighborhood. For each point, we can adaptively construct neighborhood according to local linearity of data manifold. This method is applied to Isomap, and experimental results validate the accurate of the embedding results for different datasets.(2) Based on human cognitive, an incremental Hessian LLE (LIHLLE) algorithm is proposed, which to preserve local neighborhood relationship between the original space and the embedding space. New sample points were linearly reconstructed with existing embedding results of local neighborhood samples. The proposed algorithm can learn manifold in an incremental way. Simulation results in swiss roll with hole and frey_rawface database testify the efficiency and accuracy of the proposed algorithm.(3) Based on the idea of Isomap to preserve global distance, we propose the incremental Isomap algorithm (LI-Isomap) for preserving local distance. The algorithm ensures the constant radial distance of new data in the direction of each neighborhood and minimizes the difference of angle on new data in the neighborhood between the original space and the embedded space point, giving the objective function. We get the low-dimensional embedding of the new point by solving the optimization problem. Experiments on the-swiss roll and the frey_rawface datasets show that the algorithm is rational and efficient.In summary, this paper proposes adaptive neighborhood selection algorithm of different manifold structure to provide reference and technical support for most of the manifold learning algorithms. Besides, incremental manifold learning algorithms are proposed to expand the learning algorithm and enhance the learning ability of manifold learning algorithms.