论文部分内容阅读
随着大数据时代的到来,海量信息给我们的生活带来更多机遇的同时也带来了新的挑战。海量数据通常具有很高的维度,使得很多传统的数据分析方法无法直接对这些数据进行处理,这就是著名的"维数灾难",是21世纪数据分析面临的巨大挑战。数据降维作为解决"维数灾难"的重要工具,一直是机器学习、人工智能以及数据挖掘等领域的研究热点。然而传统线性降维算法的全局线性假设己经不能适应海量高维数据日益复杂的非线性结构,因此非线性降维方法成为了新的研究热点,其中流形学习的发展最为引人关注。以等距特征映射(Isometric Feature Mapping,ISOMAP)和局部线性嵌入(Locally Linear Embedding,LLE)为代表的流形学习算法以其简单直观的几何特性和完善的理论已经被成功地应用到不同的领域。但是目前基于流形学习的降维算法的研究中依然存在一些问题,例如计算复杂度问题、参数选择问题以及鲁棒性问题。以此为出发点,本论文围绕流形学习算法,特别是地标等距特征映射(Landmark-ISOMAP,L-ISOMAP)算法中存在的一些问题,进行了深入的探讨和研究,针对每一类问题提出了相应的解决方法,并且在人造标准数据集和真实数据集上对所提方法的有效性和可行性进行了验证。本文的主要工作和贡献如下:1.针对L-ISOMAP算法中的landmark点选择问题,提出了两种自适应的landmark点选择方法。第一种方法先采取贪婪策略得到邻域图的一个子覆盖,产生landmark候选点,然后从中挑选出互不相邻的点作为landmark点。第二种方法基于图论中的图顶点染色思想,采用Welsh-Powell算法对邻域图的顶点染色,然后利用Welsh-Powell染色定理选择其中的一个颜色划分中的点作为landmark点。在标准测试数据集和真实数据集上的仿真实验表明L-ISOMAP采用这两种方法所选取的landmark点都可以得到理想的低维嵌入结果。通过比较,第一种方法在计算准确性上要优于第二种方法;但是当遇到大规模数据集的时候,第二种方法具有更高的计算效率。在实际应用中,可以根据应用的场景和需求选取合适的方法。2.针对L-ISOMAP算法的鲁棒性问题,提出了两种消除"短路边"的方法。第一种方法基于计算最短路径时采用的Dijkstra算法的贪婪特性定义"边流量",通过选取"测试路径",实现对"边流量"的快速计算并且以此作为判断一条边是否为"短路边"的重要依据;第二种方法基于"短路边"的定义和流形的局部线性性质,以概率统计中的多维核密度估计函数为工具,分别计算流形上点的局部密度和边的区域密度,并且以此作为判断"短路边"的依据。通过大量在不同数据集上的仿真实验,验证了本文所提的两种方法可以准确地找出邻域图中的"短路边"并且将其从邻域图中删除,大大提高了 L-ISOMAP算法的鲁棒性。3.针对因特网流量矩阵数据的高维特性,利用改进的L-ISOMAP算法对因特网流量矩阵进行降维,分析流量矩阵的低维流形结构。首先对真实的网络流量数据进行流量矩阵建模,然后利用改进的L-ISOMAP算法对其进行降维,通过分析低维嵌入产生的"残差"曲线,证实了高维因特网流量矩阵的确具有低维特性。最后将流量矩阵数据投影到三维和二维空间中,分析了不同流量矩阵数据的低维非线性结构,为从全网络的视角分析因特网数据流量特征提供了一种新的思路和解决方案。