Research On The Manifold Based Locally Dimensionality Reduction Algorithms

Dimensionality reduction algorithms have been applied widely in images, audio, andvideo analysis fields. More and more researchers take more attention to these fields in recentyears. Manifold learning algorithms are divided into linear and nonlinear algorithms indimensionality reduction field. Principal Component Analysis (PCA) is a classical algorithmin linear dimensionality reduction field. And its characteristic is to learn a mapping matrix byanalyzing the existing samples. Then the algorithm maps the samples from high dimensionalspace to low dimensional space. Low complexity is one of the advantages of linear algorithms.But it doesn’t have a good effect on nonlinear distributed data. It means that we will losesome important features using linear algorithms in dimensionality reduction procedure. ISOMapping, Locally Linear Embedding and Laplacian Mapping are classical algorithms innonlinear dimensionality reduction fields. And their characteristic is to reduce the datadimensionalities by nonlinear mapping method. We divide nonlinear algorithms into globaland local algorithms. ISO Mapping is a classical global algorithm which tries to preserve theglobal structure of data distribution in dimensionality reduction procedure. An advantage ofISO Mapping is to preserve the global structure. But it has high complexity and it is notsuitable for real-time application. Locally Linear Embedding and Laplacian Mapping areclassical local algorithms, which only preserve the local structure in dimensionality reductionprocedure. The data in low dimensional space has some deformation, but it is suitable forreal-time application because of the low complexity. This paper introduces and analyzes someclassical algorithms firstly. Subsequently, we point out the existing problems and researchfocuses. Then we begin the research as follows:Firstly, aiming at the problem of similarity measurement, we present two Mahalanobisdistance metric algorithms based manifold learning algorithms. Both algorithms useMahalanobis distance metric in the procedure of searching neighbourhoods and recognizingnew samples. Two algorithms get the coefficient matrix based Mahalanobis distance metricby analyzing the existing samples firstly. Subsequently, algorithms search neighbourhoods ofeach sample. Then we can nonlinearly map the samples from high dimensionality space tolow dimensionality space. We can also use Mahalanobis distance metric to determine theneighbourhoods and the categories of new samples. Secondly, aiming at the problem of finding intrinsic structure of high dimensional data,we present adaptive neighbourhoods based locally linear embedding (ANLLE) algorithm.K-nearest neighbor (KNN) algorithm is usually used to search the neighbourhoods of eachsample in manifold learning based dimensionality reduction algorithms. But how to get thevalue of K? We normally use the method of trial and error. But it costs much time sometimes.For the reasons above, we propose ANLLE algorithm, which gives every sample a differentthreshold automatically. We regard a sample s2as a neighbourhood of sample s1if thedistance from s1to s2is smaller than the threshold of s1. Otherwise s2is not theneighbourhood of s1. ANLLE algorithm not only solves the problem of choosing K value, butalso gives every sample a different K value according to the distribution of the samples.ANLLE is more reasonable comparing with classical algorithms.Thirdly, aiming at the problem of transforming an image to an image vector in theprocedure of dimensionality reduction algorithm. We present a linear two-dimensionaldimensionality reduction algorithm, Modified Modular Principal Component Analysis, whichis an improved algorithm of Modular Principal Component Analysis (MPCA). The algorithmchanges the method of computing images mean and the method of recognizing new samples.We also prove that Two-Dimensional Principal Component Analysis algorithm is a specialcase of Modified Modular Principal Component Analysis algorithm.Finally, aiming at the problem of transforming an image to an image vector in theprocedure of dimensionality reduction. We present a nonlinear two-dimensionaldimensionality reduction algorithm named Two-Dimensional Locally Linear Embedding.Through theoretical analysis, we acquire that2dPCA is a special case of line-based PCAalgorithm and Locally Linear Embedding algorithm can be regarded as a nonlinear expansionof PCA. Based on these reasons, we propose line-based (or column-based) Locally LinearEmbedding algorithm named Two-Dimensional Locally Linear Embedding.