随着信息时代的到来,科研工作者在研究过程中不可避免地会遇到大量的高维数据,如全球气候模型、人类基因分布、文本聚类中的词频等,所以经常会面临高维数据降维的问题。数据降维的目的是要找出隐藏在高维数据中的低维结构。为了更精确地刻画图像和其他感知刺激的变化,采取数学方法是非常必要的。流形学习是近年来出现在机器学习领域的一种重要方法,在探索非线性数据降维方面取得了令人瞩目的成果。近年来,已经发展了许多有效的基于流形学习的非线性数据降维方法。主要包括等距映射(Isomap)、局部线性嵌入(LLE)以及它的变换形式Hessian LLE、拉普拉斯特征映射(Laplacian Eigenmaps)和局部切空间排列(LTSA)等。LLE是典型的基于流形学习的非线性数据降维方法,已经广泛应用于数据的降维、聚类及可视化等领域。对于流形上的样本点,LLE利用其近邻点的线性组合进行线性逼近,求得局部重建权值矩阵,然后根据重建权值矩阵构造重建误差并使其达到最小,从而求得样本的低维嵌入。然而,不同近邻个数的选取会产生不同的重构误差,不同的重构误差势必会严重地影响数据低维表示,从而使LLE算法的降维效果相对的不稳定;此外,LLE算法假设样本点在高维空间的分布是均匀的,它没有很好的考虑数据点间的密度信息。值得指出的是,高维观测空间的数据密度对其维数的确定具有很重要的影响作用,对于数据密度变化较大的流形,LLE很可能会将在高维空间中相隔较远的点映射到低维空间中相邻近的位置,从而导致嵌入结果有着比较明显的扭曲。这些都是LLE算法面临的问题。本文从高维数据的结构特性出发,全面地分析和总结了现有的数据降维方法,着重研究了LLE算法并对其进行了修正改进。具体来讲,本文的主要工作包括:⑴全面总结了现有的数据降维方法,对具有代表性的方法进行了系统分类和详细的阐述,并从算法的时间复杂度和优缺点两方面对这些算法进行了深入的分析和比较。⑵在LLE算法中,不同近邻个数的选取会产生不同的重构误差,从而产生不同的降维效果。本文利用聚类中心含有大量的信息这一特点,定义了近似重构系数,并提出了改进的LLE方法。⑶LLE算法假设样本在高维空间的分布是均匀的,对于密度不均匀或密度变化较大的数据集,LLE很难正确降维。本文分析了LLE算法的不足,提出了基于密度的LLE算法——DLLE算法。