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

摘要： 现有的等距映射算法对邻域参数的选择较为敏感，而且对噪声干扰缺乏足够的鲁棒性。基于平均最短路径与邻域参数的变化关系与平均最短路径梯度提出了一种构建最优邻域图的方法，基于该方法构建的邻域图几乎没有短路边;可以根据每个数据点的不同特性采用可变的邻域参数;对数据点间的测地距有更好的逼近。实验表明：算法不仅对均匀采样、无噪声干扰的数据集有更好的降维性能，而且对噪声干扰的数据集有较强的鲁棒性与拓扑稳定性。

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