Robust Modification And Supervised Extension Of Locally Linear Embedding Algorithm

In this paper, we investigate and extend the Locally Linear Embedding (LLE) algorithm. Locally Linear Embedding is a novel and efficient unsupervised nonlinear dimensionality reduction technique proposed recently. It can preserve the locally geometric structure and relationships of the high-dimensional data perfectly when they are mapped into a low-dimensional space. Its main attractive characteristics are simple to implement, few free parameters to be set and a non-iterative solution avoiding the convergence to a local minimum. Despite these appealing properties, there still exist some aspects to deal with, such as: the algorithm's robust extension against outliers; its extension to combine with the label information to supervise the performance of classification in pattern classification. According to such situation, our research emphasizes on the following three aspects:1. The original Locally Linear Embedding algorithm is introduced in detail and its executive details are complementedThe basic ideas and main processes of the LLE algorithm are introduced in detail. We also deduce and demonstrate its corresponding executive details. Moreover, we survey some intrinsic researches and extensions of the algorithm.2. Neighborhood-based Robust Locally Linear Embedding algorithm is proposed to make LLE more robust against outliersWe explore and demonstrate that LLE is not robust against outliers. Then, based on the neighborhood relations among the data point and its neighboring points, we obtain the neighborhood value of each data point to detect the outliers and then a simple but effective method is proposed to reduce the undesirable effect of outliers on the embedding result.3. Orthogonal Centroid Locally linear Embedding algorithm is proposed for pattern classificationBased on the practical requirement and characteristic of the pattern classification work, we propose a supervised variant of LLE, Orthogonal Centroid Locally Linear Embedding algorithm, to guide the implement of dimensionality reduction. This new algorithm uses the class membership information to map overlapping high-dimensional data into disjoint clusters in the embedded space. Experiments show the efficacy of this variant algorithm and very promising classification results are yielded.