马发民+张林+王锦彪

摘 要：机器学习是近几年研究的热点，维数约简算法是机器学习的必要手段，本文从维数约简算法的定义讲起，介绍了几种典型的数据降维算法，其中包括线性降维和非线性降维，流形学习是非线性降维的代表算法。并且介绍了每个算法的构造过程及其特点，在此基础上分析了所有维数约简算法的执行效率时间和空间复杂度，并且给出了每个算法的特点和算法的核心思想，最后在此基础上给予总结，为后面研究者提供参考和借鉴。

关键词：机器学习；维数约简；数据降维；线性降维；非线性降维

中图分类号：TP301 文献标识码：A

Abstract：Machine learning，mainly realized through dimensionality reduction，has become a hot topic for research in recent years.This paper first presents the definition of the dimensionality reduction algorithm，and then introduces several typical data dimensionality reduction algorithms including linear dimensionality reduction and non-linear dimensionality reduction（manifold learning is the typical algorithm of non-linear dimensionality reduction）.Besides，the paper elaborates on the construction process and characteristics of each algorithm，then analyzes the execution efficiency time and space complexity of all dimensionality reduction algorithms and provides the features and key point of each algorithm.Most importantly，the final conclusion offers references to future researchers.

Keywords：machine learning；dimensionality reduction；data dimensionality reduction；linear dimensionality reduction；

non-linear dimensionality reduction；manifold learning

1 引言（Introduction）

機器学习是近几年比较火的一个研究方向，不论在模式识别还是图像处理方面都要用到机器学习的理论，机器学习中有个重要的方面研究就是如何把大数据量内容降低成有限的维数，从而提高机器学习的速度，这里面用到一个关键的算法就是维数约简算法，它的原理就是通过线性和非线性的方法，将高维数据降低到可以解的低维数据从而提高机器学习的速度。接下来文章将从维数约简数学定义说起，紧接着介绍常用的几种维数约简算法，并且给出这些算法的优缺点，最后给出总结为后续做研究的人提供指引和方向。

2 维数约简数学定义（Mathematical definition of

dimensionality reduction）

定义1：给定个数据点，

，。

构造映射，其中

，即

我们把叫作低维表示方法。

假如映射F是线性的那么这种降维叫作线性降维，同理若F是非线性的则这种降维叫作非线性降维。……