关键词: 邻域图, 平均最短路径, 平均最短路径梯度, 测地距, 等距映射

Abstract: The recent isometric mapping algorithms are sensitive to selecting an appropriate neighborhood size，and present insufficient noise tolerance.Based on the relationship of the average shortest distance with the neighborhood size and the average shortest distance gradient，this paper proposes a new method for constructing the optimal neighbor graph from a data set，which has few short-circuit edges，and better approximates the geodesic distances between the data points.Furthermore，for different points the neighborhood sizes are adaptive variant with the local characteristics of the data points.Experimental results show that the proposed method yields better performances for symmetrically sampling data points free of noise than the recent methods.It is also shown that the topologically stability and degree of noise tolerance can be significantly improved.

Key words: the neighborhood graphs, average shortest distance, average shortest distant gradient, geodesic distance, isometric mapping