基于随机游走的流形学习与可视化

现有的全局流形学习算法都敏感于邻域大小这一难以高效选取的参数,它们都采用了基于欧氏距离的邻域图创建方法,从而使邻域图容易产生“短路”边。本文提出了一种基于随机游走模型的全局 流形学习算法(Random walk-based isometric mapping，RW-ISOMAP)。和欧氏距离相比,由随机游走模型得到的通勤时间距离是由给定两点间的所有通路以概率为权组合而成的,不但鲁棒性更高,而且还能在一定程度上度量具有非线性几何结构的数据之间的相似性。因此采用通勤时间距离来创建邻域图的RW-ISOMAP算法将不再敏感于邻域大小参数,从而可以更容易地选取邻域大小参数,同时还具有更高的鲁棒性。最后的实验结果证实了该算法的有效性。

Manifold Learning and Visualization Based on Random Walk

The existing global manifold learning algorithms are relatively sensitive to the neighborhood size, which is difficult to select efficiently. The reason is mainly because the neighborhood graph is constructed based on Euclidean distance, by which shortcut edges tend to be introduced into the neighborhood graph. To overcome this problem, a global manifold learning algorithm is proposed based on random walk, called the random walk-based isometric mapping (RW-ISOMAP). Compared with Euclidean distance, the commute time distance, achieved by the random walk on the neighborhood graph, can measure the similarity between the given data within the nonlinear geometric structure to a certain extent, thus it can provide robust results and is more suitable to construct the neighborhood graph. Consequently, by constructing the neighborhood graph based on the commute time distance, RW-ISOMAP is less sensitive to the neighborhood size and more robust than the existing global manifold learning algorithms. Finally, the experiment verifies the effectiveness of RW-ISOMAP.