邵 超，万春红，赵静玉

(河南财经政法大学计算机与信息工程学院，郑州 450002)

1 概述

近年来，人们陆续发现实际中的很多高维数据都分布在某个低维非线性流形上［1-2］，为此提出了多种能有效学习这种结构的流形学习算法如等距映射［3-4］(Isometric Mapping，ISOMAP)和局部线性嵌入［5-6］(Locally Linear Embedding，LLE)。现有的大多数流形学习算法能否成功应用还依赖于其邻域大小参数的选取是否合适，然而，目前该参数在实际中通常还难以高效选取，另外，数据中的噪音对邻域大小参数的合适性也会产生一定的影响［7］，从而限制了它们的实际应用［7-10］。

针对流形学习算法敏感于邻域大小参数的这一问题，目前大多数方法都基于残差来选取合适的邻域大小参数［3，11-12］，但这需要多次运行整个流形学习算法以计算相应的残差(尽管文献［11 -12］都只对其中具有极小重建误差或极小成本函数的少数几个邻域大小参数分别计算相应的残差);另外，残差只是维数约简过程中产生的误差，难以正确指导邻域大小参数的合适选取［13］。

通过对采用不同邻域大小参数得到的多个运行结果进行集成可以在一定程度上减轻流形学习算法对邻域大小参数的敏感程度［9］，但算法的时间复杂度会显著增加。通过识别和删除邻域图中可能出现的“短路”边也能在一定程度上避免邻域大小参数难以高效选取的问题，例如，文献［14］删除每一个数据点中具有最小重建权重的几个近邻点，文献［15］删除每一个数据点中具有最大图距离的几个近邻点，但它们又引入了一个同样难以选取的额外参数。……