流形学习理论与算法研究

随着信息技术的发展，人们需要处理的数据越来越复杂。这些数据的内在规律的复杂性往往超出人们的直接感知能力，人们必须借助机器学习方法来从数据中学习并发现内在规律。流形学习方法便是近年来出现的一个重要的机器学习领域，在探索非线性数据的内在规律等方面取得了令人瞩目的成果。 本文从学习结果应当有利于人们对数据集内部结构认知的思想出发，深入分析了非监督学习的特征提取任务和数据拓扑结构描述任务对流形学习模型与算法的要求，并讨论了现有主要流形学习理论和算法与这些要求的相容性。对于非监督特征提取任务，本文提出了流形学习理论与算法应当遵循的两个准则：“重构误差最小化”准则与“相似性保持”准则，以保证人们通过提取的特征，能够正确地理解数据集的内在性质。以这两个准则为标准，本文澄清了非监督特征提取任务中过拟合与欠拟合的概念，提出了对特征提取算法的评价标准，并深入地分析了现有多种主要流形学习理论和算法存在的问题，指出目前尚无满足此二准则的流形学习理论模型。对于数据拓扑结构描述任务，本文指出，为使人们能够正确且直观地认知数据集的拓扑结构，拓扑结构学习模型与算法应当具有较强的拓扑结构生成能力，且在其学习结果与数据集的拓扑结构之间建立起对应关系。根据此标准，本文分析并比较了现有的多种拓扑结构学习理论与算法，发现这些理论与算法无法很好地实现上述要求，从而在准确并直观地表达数据的拓扑结构方面存在缺憾。为解决当前流形学习理论与算法中存在的上述问题，本文开展了以下几个方面的研究： (一)本文基于非监督特征提取任务的“重构误差最小化”准则与“相似性保持”准则，提出了“相似性保持主曲线”的概念，证明了其存在性，研究了其微分性质并将其推广到高维情形。相似性保持主曲线理论的意义在于其在保持数据之间相似关系不变的条件下，取得对数据的最佳逼近，因此是特征提取任务的最优一维特征提取模型。相似性保持主曲线及其高维推广的理论完善了流形学习理论，可以做为特征提取任务下流形学习算法的理论目标，具有重要的理论意义。本文提出了相似性保持主曲线的一个学习算法。在仿真数据集与真实数据集上的试验结果表明了该学习算法的有效性，从而验证了相似性保持主曲线理论的合理性。 (二)本文针对现有嵌入流形学习方法在面临一些具有强非线性性质的数据集时出现欠拟合现象的问题，提出了一种新的嵌入算法——“全局拉普拉斯特征映射”算法。与LLE等局部方法相比，该算法在考虑数据集的局部信息的同时，还考虑了数据集的全局信息；而与ISOMap等全局方法相比，该算法以一种更加灵活的方式来处理数据的全局信息，从而避免了ISOMap方法拘泥于保持全局流形距离带来的局限。在一些具有强非线性性质的数据集上的实验结果表明，该算法获得了低于大多数甚至所有其他参测嵌入方法的重构误差。 (三)本文以使人们能够直观地认知数据集的拓扑结构为目的，提出了数据集的“主拓扑”与“拓扑图”的概念。数据的主拓扑概念表征数据最显著的拓扑特征，而拓扑图则是对主拓扑的简明表达。在数据集的拓扑图与主拓扑之间存在着拓扑结构的一一对应关系，这种关系使得人们能够通过拓扑图直观地了解数据的最显著的拓扑特征。本文提出了拓扑图学习的分割-组合学习策略。基于该策略，本文提出了拓扑图学习的增长聚类算法。该算法在仿真数据集以及现实应用中都取得了比较好的效果。