基于小世界模型的流形学习算法

Manifold learning algorithm based on the small world model

等距特征映射(ISOMAP)不仅计算复杂度很高,而且缺乏对新样本的学习能力。基于标志点的ISOMAP(L-ISOMAP)通过只保持一些标志点之间的测地线距离有效地降低了复杂度,然而标志点集的随机选择常常会导致较差的嵌入结果。为此,提出了一种基于小世界模型的流形学习算法。根据小世界模型的原理,该算法仅仅保持每个样本点与其k个最近邻和一些随机选择的远点之间的测地线距离,采用最速梯度下降法优化来得到数据的低维表示。理论分析表明,该算法的计算复杂度远远低于ISOMAP的复杂度。利用应力函数和剩余方差对3个算法进行了比较。实验结果表明,从该算法得到的结果与从ISOMAP得到的结果相近,且优于从L-ISOMAP得到的结果。同时,该算法可以实现对新样本的学习,对噪声也不太敏感。

Isometric Feature Mapping （ISOMAP） not only has high complexity but also can not learn new samples. L-ISOMAP has lower complexity by only preserving the geodesic distances between some landmark points. However, landmark point set randomly selected often leads to worse embedding results. A manifold learning algorithm based on the small world model was proposed, which only preserve the geodesic distances between each point and its k nearest neighbors as well as some distant points randomly chosen according to the small world model. The deepest gradient descent method was used to optimize the iterative process to obtain the low dimensional representation of data. The theoretic analysis demonstrates that the complexity of the proposed algorithm is far below one of ISOMAP. The stress function and the residual variance were used to compare the three methods. The experiments show that the results from the new method are close to those from ISOMAP and are superior to those from L-ISOMAP. Moreover, the algorithm can treat new data and is also not sensitive to noise.