基于最小连通邻域图的ISOMAP算法

噪音的干扰和邻域大小的不合适会在ISOMAP算法的邻域图中引入“短路”边,使其不能正确表达数据的邻域结构,从而使该算法具有较差的鲁棒性和拓扑稳定性。为此,根据最小连通邻域图能有效避免“短路”边的特点,提出了一种能有效删除“短路”边因而更具鲁棒性和拓扑稳定性的ISOMAP算法——基于最小连通邻域图的ISOMAP（MCNG-ISOMAP）算法。该算法能在一定程度上避免邻域大小难以有效选取的问题,同时还能在不依赖于邻域大小的情况下发现数据真正的固有维数。

ISOMAP based on minimal connected neighborhood graph

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 dimensionality of the data independent of the neighborhood size unlike ISOMAP. Finally, the feasibility of MCNG-ISOMAP is verified by experimental results very well.