Journal of Frontiers of Computer Science and Technology ›› 2017, Vol. 11 ›› Issue (7): 1092-1101.DOI: 10.3778/j.issn.1673-9418.1608047

Previous Articles     Next Articles

Global Adaptive Isometric Mapping Algorithm for Visualization

WANG Xiyang, CHENG Chunling+, CHEN Xingguo   

  1. School of Computer, Nanjing University of Posts and Telecommunications, Nanjing 210003, China
  • Online:2017-07-01 Published:2017-07-07

面向可视化的全局自适应等距映射算法

王曦杨程春玲+,陈兴国   

  1. 南京邮电大学 计算机学院,南京 210003

Abstract: The Isomap (isometric mapping) and its variant algorithm are much influenced by static parameters and the nearest neighbor judgment logic. As a result, there are problems such as computational waste, numerical sensitivity or unstable data topology. In the practical application of interactive data visualization, it is very difficult to fulfill the requirement of real-time interaction and accurate visualization. Therefore, this paper makes an improvement on the original computing framework of isometric mapping, and proposes a global adaptive algorithm called GA-Isomap (global adaptive-Isomap). In the aspect of neighborhood construction, this paper proposes an incremental construction method and region selection method, by means of the new designed method of local density calculation and the       region division. In the aspect of low-dimensional embedding, this paper proposes a mapping calculation method based on two-layer graph, which takes the framework graph of landmarks and the relative position relationship into consideration. Compared with original Isomap, L-Isomap, Isomap with dynamic neighbor and Isomap with NC, simulation results show that the GA-Isomap algorithm can effectively balance the data topology stability and operational efficiency in visualization.

Key words: isometric mapping, data visualization, topological stability, data manifold

摘要: 等距映射(isometric mapping,Isomap)及其衍生的维度约简算法受静态近邻值、地标比重值或近邻判断逻辑的影响,存在计算浪费、数值敏感或数据拓扑不稳定的情况,在数据可视化分析的实际应用中很难满足交互实时性和视图准确性的需求。为此,对等距映射的原始计算框架进行改进,提出了具有全局自适应性的GA-Isomap(global adaptive-Isomap)算法。邻域图构建方面,设计了数据局部密度值计算和区域划分方法,提出了渐进式的邻域图构造方法和区域地标点选取方法;降维映射方面,引入地标框架图并利用相对位置关系,提出了基于双层图的映射计算方式。仿真结果表明,与Isomap、L-Isomap、Isomap with dynamic neighbor和Isomap with NC算法相比,该算法在进行数据可视化映射时能有效兼顾数据拓扑稳定性和运行效率。

关键词: 等距映射, 数据可视化, 拓扑稳定, 数据流形