一种更具拓扑稳定性的ISOMAP算法  

A More Topologically Stable ISOMAP Algorithm

作　　者：邵超[1] 黄厚宽[1] 赵连伟[1] 

机构地区：[1]北京交通大学计算机与信息技术学院

出　　处：《软件学报》2007年第4期869-877,共9页Journal of Software

基　　金：SupportedbytheNationalNaturalScienceFoundationofChinaunderGrantNo.60443003(国家自然科学基金);theNationalGrandFundamentalResearch973ProgramofChinaunderGrantNos.2007CB307100;2007CB307106(国家重点基础研究发展规划(973));theFoundationofBeijingJiaotongUniversityofChinaunderGrantNo.2003SZ003(北京交通大学基金)

摘　　要：ISOMAP算法能否被成功运用,很大程度上依赖于邻域大小的选取是否合适.然而,如何有效地选取合适的邻域大小,目前还是一个尚未解决的难题.根据“短路”边会途经相对的低密度区域这一特点,能够有效删除邻域图中可能存在的“短路”边,提出了P-ISOMAP(pruned-ISOMAP)算法,这极大地削弱了ISOMAP算法对邻域大小的依赖程度,从而使其更具拓扑稳定性.由于避免了邻域大小难以有效选取的问题,P-ISOMAP算法能够更容易地对数据进行可视化.实验结果很好地验证了该算法的有效性.The success of ISOMAP depends greatly on being able to choose a suitable neighborhood size, however, it is still an open problem how to do this effectively. Based on the fact that ＂short circuit＂ edges pass the area with the relatively lower local densities, this paper presents a new variant of ISOMAP, i.e. P-ISOMAP （pruned-ISOMAP）, which can prune effectively ＂short circuit＂ edges existed possibly in the neighborhood graph and thus is much less sensitive to the neighborhood size and more topologically stable than ISOMAP. Consequently, P-ISOMAP can be applied to data visualization more easily than ISOMAP because the open problem described above can be avoided to the utmost extent. The effectivity of P-ISOMAP is verified by the experimental results very well.

关 键 词：ISOMAP P—ISOMAP(pruned—ISOMAP) 邻域大小 拓扑稳定性 残差 核密度估计 局部密度 

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