一种快速的Isomap算法  

A Fast Isomap Algorithm

作　　者：屈太国[1] 蔡自兴[1] 

机构地区：[1]中南大学信息科学与工程学院,湖南长沙410083

出　　处：《信息与控制》2014年第4期476-482,489,共8页Information and Control

基　　金：国家自然科学基金资助项目(90820302;60805027);教育部博士点基金资助项目(200805330005)

摘　　要：针对Isomap采用Floyd-Warshall算法求最短路径时运算速度慢的问题,考虑到邻域图的稀疏性,提出了Isomap的改进算法.通过采用基于Fibonacci堆的Dijkstra算法,减少了求最短路径的时间,从而提高了Isomap的速度.在多个数据集上的实验结果表明,改进后的算法较原Isomap算法的运算速度快.For the slow operational speed problem of the Isomap algorithm in which the Floyd-Warshall algorithm is applied to finding shortest paths, an improved Isomap algorithm is proposed based on the sparseness of the adjacency graph. In the improved algorithm, the runtime for shortest paths is reduced by using Dijkstra＇ s algorithm based on a Fibonacci heap, thus speeding up the Isomap operation. The experimental results on several data sets show that the improved version of Isomap is faster than the original one.

关 键 词：流形学习 ISOMAP FIBONACCI 堆 最短路径 DIJKSTRA 算法 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]