Abstract: Euclidean distance is normally used to measure the similarity between samples in Localiy Linear Embedding algorithm（LLE）, But for some high dimensional data with low-dimensional manifold structure, Euclidean distance does not measure the relative position of two points in a manifold. A Local Linear Embedding algorithm based on Geodesic Rank-order Distance（GRDLLE） is proposed. Firstly, the algorithm approximates the geodesic distance between any two sample points by using the shortest path length to find the shortest path algorithm（Dijkstra algorithm）. Then the Rank-order distance is calculated for the similarity measurement of the LLE algorithm. GRDLLE, other improved LLE manifold learning algorithms and 2DPCA algorithm are compared on ORL and Yale data sets. The face recognition rate of data is improved after dimension-reduction using GRDLLE algorithm. The results show that the GRDLLE algorithm has good dimensional reduction effect.

Key words: locally linear embedding, manifold learning, dimensionality reduction, GRDLLE algorithm

摘要： 局部线性嵌入算法（LLE）中常用欧氏距离来度量样本间相似度，而对于具有低维流形结构的高维数据，欧氏距离不能衡量流形上两点间相对位置关系。提出基于Geodesic Rank-order距离的局部线性嵌入算法（简称GRDLLE）。应用最短路径算法（Dijkstra算法）找到最短路径长度来近似计算任意两个样本间的测地线距离，计算Rank-order距离用于LLE算法的相似性度量。将GRDLLE算法、其他改进LLE的流形学习算法及2DPCA算法在ORL与Yale数据集上进行对比实验，对数据用GRDLLE算法进行降维后人脸识别率有所提高，结果表明GRDLLE算法具有很好的降维效果。

关键词: 局部线性嵌入, 流形学习, 降维, GRDLLE算法