文献类型：期刊文献

中文题名：基于最小连通邻域图的ISOMAP算法

英文题名：ISOMAP based on minimal connected neighborhood graph

作者：邵超[1];万春红[1];陈广宇[1]

第一作者：邵超

机构：[1]河南财经学院信息学院

第一机构：河南财经政法大学计算机与信息工程学院

年份：2007

卷号：27

期号：10

起止页码：2570-2574

中文期刊名：计算机应用

外文期刊名：Journal of Computer Applications

收录：CSTPCD;;北大核心:【北大核心2004】；CSCD:【CSCD2011_2012】；

语种：中文

中文关键词：等距映射;MCNG-ISOMAP;最小连通邻域图;成本;“短路”边

外文关键词：ISOmetric MAPping （ISOMAP）; MCNG-ISOMAP; minimal connected neighborhood graph; cost; ＂shortcut＂ edge

摘要：噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入"短路"边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免"短路"边的特点,提出了一种能有效删除"短路"边因而更具鲁棒性和拓扑稳定性的ISOMAP算法——基于最小连通邻域图的ISOMAP(MCNG-ISOMAP)算法。该算法能在一定程度上避免邻域大小难以有效选取的问题,同时还能在不依赖于邻域大小的情况下发现数据真正的固有维数。
It is well known that ISOMAP is poorly robust and topologically unstable, mainly because ＂shortcut＂ edges may emerge in the neighborhood graph due to the noise or the unsuitable neighborhood size. The emergence of ＂shortcut＂ edges can make the corresponding neighborhood graph represent the neighborhood structure of the data falsely, and thus ISOMAP cannot be applied successfully. Therefore, this paper presented a more robust and more topologically stable ISOMAP algorithm, i.e. MCNG-ISOMAP （Minimal Connected Neighborhood Graph-based ISOMAP）, which can prune effectively ＂shortcut＂ edges, existed possibly in the neighborhood graph, based on that the minimal connected neighborhood graph can avoid ＂shortcut＂ edges effectively. MCNG-ISOMAP is much less sensitive to the neighborhood size and thus can be applied to data visualization more easily than ISOMAP. In addition, MCNG-ISOMAP can also find the true intrinsic dimensionahty of the data independent of the neighborhood size unlike ISOMAP. Finally, the feasibility of MCNG-ISOMAP is verified by experimental results very well.