论文部分内容阅读
科学的进步,特别是信息产业的发展,把我们带入了一个崭新的信息时代。在信息时代的科学研究过程中,不可避免的会遇到大量的高维数据,如全球气候模型、图像分类系统、文本聚类和基因序列的建模等。在实际应用中,用高维数据来表示的观测点可以模拟成可能带有噪音的低维非线性流形上的样本点或者逼近这些样本点。因此,数据降维尤其是非线性降维成为数据挖掘的一个重要手段,进行降维的目的是为了从高维空间中找出隐藏的低维结构。 过去几年来,非线性降维在包括数据挖掘、机器学习、图像分析和计算机视觉等许多研究领域都吸引了广泛的关注。最近,已经发展出一些有效的算法来进行非线性降维。这些算法包括等距映射(Isomap)、局部线性嵌入(LLE)以及它的变换形式:海赛局部线性嵌入(HLLE)和局部切空间排列(LTSA)等。所有的这些算法都有一个共同的特征:找出每个数据点周围的局部性质以及采用这些所收集到的局部性质信息将流形非线性的映射到一个低维的空间中。然而,这些算法的实现在收集邻域的局部信息以及采用这些收集的局部信息构造全局的嵌入上都是不同的。比如,Isomap利用每个邻域的邻域点之间的联系和欧氏距离在数据点上构造出一个图,并根据图距离来估计出所有数据点之间的测地距离。构造出的全局低维坐标需要保持估计的测地距离。LLE找出每个点同它的邻域点之间的一个线性组合关系,并且由此决定保持这种线性组合结构的低维嵌入。LTSA将每个点的邻域点投影到它在流形上的局部切空间上,然后排列所有的局部坐标来决定低维的全局坐标。显然的,局部几何结构的恢复效率决定了这些算法的效率。 LLE是流形学习方面经典的局部非线性方法,它有参数少、计算快、易求全局最优解等优点,并在图像分类、图像识别、谱重建、数据可视化等方面都有着广泛的应用。但是,LLE可能会将相隔较远的点映射到低维空间中邻近点的位置,从而导致嵌入结果有着比较明显的扭曲。这其中的一个重要原因是,LLE采用的单个重构权并不能完全的反映出流形的局部几何性质。此外,用以求解重构权的有约束的最小二乘问题的最优解也许不是唯一的,而且LLE采用正则化方法求解涉及到正则因子γ的选取,难以保证所求的解是最优解。这些都是LLE所面临的问题。 有一些共同的因素影响着流形学习方法的效果。流形学习方法首先面临的是邻域选取的问题,需要选取出一个合适的邻域以获取局部的线性信息,邻域选取的结果直接影响着最终的嵌入结果。很显然的,邻域越小可以认为邻域的线性结构越明显,但是我们