论文摘要
随着科学的进步,信息技术得到了快速发展及广泛应用,如医学图像处理、计算生物学、全球气候模型等,高维数据应运而生。高维数据难以被现有的机器学习和数据挖掘算法进行有效地处理。降维算法是处理这些高维数据的一个非常重要的工具和方法。而流形学习作为一种高维数据降维的技术手段,在非线性降维方面取得了广泛的应用。其中主成分分析(PCA)是一种假设全局能够线性化表示而提出的流形学习算法。在数据规模越来越大的今天,数据处理速度越来越成为人们关注的重点。但是我们又不想在牺牲算法准确性的基础上降低时间复杂度,因为那样会使得降维或分类后的数据无法如实反映原有数据的信息。本文主要主要工作如下：1.对降维算法做了总体的概述,重点介绍了两种算法—ISOMAP和LLE,并且指出了ISOMAP在求近邻点时将欧氏距离改为测地距离以后,算法所耗费的时间大量增加的缺点；简要比较了在不同近邻点数的情况下LLE降维效果的不同,并且对各向异性算法做了简单的介绍。2.对主成分分析(PCA)算法进行了深入的研究与改进,对PCA的特点进行了详细地分析,在数据集规模比较大尤其是行数和列数都在三千以上的情况下,我们指出了PCA算法中最耗时的步骤,展示了三种随机矩阵与贪婪算法在PCA降维过程中减少矩阵分解时间的重要作用,提出了在精确度要求不大的情况下(偏差小于5%),在偏差可估的情况下进一步加快算法的方法。并且我们用实验对比了两种降维模式和标准PCA的计算时间和用特征向量衡量的低维嵌入偏差。