降维方法知多少？

1. 主分量分析

主分量分析又被称为主成分分析、Karhunen–Loève变换（Karhunen–Loève Transform，KLT）或霍特林变换。主分量分析是1901年由皮尔森（K.Pearson）首先提出，1933年由霍特林（H.Hotelling）奠定了其数学基础。主分量分析是一种把握事物主要性质的多元统计分析方法。它将原始变量变换为一小部分反映事物主要性质的变量（称之为主分量），从而将高维数据投影到了低维空间，并且保证投影后的低维数据在最小平方意义下最优地表征原有高维数据。主要步骤如下：（1）计算数据样本的协方差矩阵；（2）求解该协方差矩阵的特征向量，按照相应的特征值从大到小排序，选择排在前面的部分特征向量作为投影向量；（3）将原高维数据投影到投影向量张成的子空间中以达到降维的目的。上节我们花了一整篇文章详述PCA，这里就再不赘述。

2. 线性判别分析

与主分量分析类似，线性判别分析也要求解一组投影向量，并将高维数据投影到低维空间之中，从而达到降低维度的要求。线性判别分析是1936年由费舍尔（R.Fisher）首先提出的。与主分量分析不同的是，如果被告知待分析的数据样本来自于多个不同的类别，我们常常会期望在将高维数据投影到低维空间中后，各类的数据样本能够尽可能地分开且不重叠。因此，我们需要在数据降维的过程中考虑引入数据样本的类别信息。线性判别分析定义了费舍尔准则，使得在投影空间中，不同类数据之间区别将被最大化，各类别自身数据之 间的区别将达到最小化，从而显著提高了各类别之间的可分性。由于主分量分析与线性判别分析的动机不同，前者着眼于降维数据对原有高维数据保真度的优化，而后者更关心降维数据对不同类数据判别性的优化。因此对于相同的数据，它们求解出的投影方向（向量）也截然不同（见图1）。图1中，假设一组二维数据样本，分为两类（ClassⅠ与ClassⅡ），主分量分析试图求解一个投影方向（图中以实线表示），使得投影的数据能在最小平方意义下尽可能地表征原数据；而线性判别分析求解的投影方向，将使投影后的两类数据尽可能地分开（图中以虚线表示）。

图1 主分量分析和线性判别分析示意图

3. 典型相关分析

在多元数据分析中，经常需要发掘事物两组属性（变量）之间的关系，或者从事物的一类属性推知另一类属性。这就是由霍特林于1936年提出的典型相关分析。如人的身高与体重的关系、万维网图像与其文本描述的关系，汽车排量、发动机功率及重量与加速度、油耗可能存在的内在联系和两种语言间的关系等等。假如我们掌握了这种联系，那么在得知其中的一组属性的数据后，可据此预测出另一组属性的值。这涉及两组变量间的相关分析。然而，两组变量间的相关性受到观察样本间角度的影响，或者说与表示两组数据的坐标轴有 关。典型相关分析关注于如何建立两组多元变量间的线性关系，是主分量分析在两组变量上的推广。两组多元变量可被认为是同一事物的两个侧面，典型相关分析为每一组变量求解一个投影方向，从而使两组投影后变量之间的相关最大化（见图2）。图2中，假设用两组变量来描述同一组样本，如图中的X和Y。典型相关分析为两组变量各求解一个投影方向（图中的实线Wx表示为X求解的投影方向，虚线Wy表示为Y求解的投影方向），从而使得投影后得到的变量间相关性最大化（见右图）。右图中的横纵轴分别对应两个投影方向。

图2 典型相关分析示意图

近年发展起来的降维方法主要是：基于核的非线性降维、两维化和张量降维、流形学习与局部化降维以及半监督降维。

4. 基于核的非线性降维

在过去十多年中热门的机器学习方法支持向量机（Support Vector Machine，SVM）自20世纪末诞生以来，迅速在机器学习界流行开来，是继神经网络之后的又一轮热潮。核方法是支持向量机成功的关键支撑技术，主要思想是用核函数去替换内积，相当于用一个核诱导的非线性映射将原始数据映射到高维空间，然后在高维空间中进行线性操作。可从如下几个方面理解核方法的实质： （1）据Cover模式可分性定理可知，数据在高维空间中更容易线性可分； （2）由满足Mercer定理的核函数可诱导出从输入空间到高维特征空间的隐含的非线性映射；（3）高维空间中的内积可通过核函数在低维空间中直接计算， 从而计算量并没有随着维数升高而增加很多。图3给出了核方法的示意图。肖科尔考夫（B. Schölkopf）等人首先将核方法引入降维领域，提出了经典的核主分量分析（Kernel Principal Component Analysis，KPCA）。随后，研究人员将核方法应用到其它传统降维方法，分别提出了核费舍尔判别分析（Kernel Fisher Discriminant Analysis，KFDA）、核典型相关分析（Kernel CanonicalCorrelation Analysis，KCCA）及核独立分量分析（Kernel Independent Component Analysis，KICA）等。截至目前，几乎所有的线性降维方法都已经有了相对应的“核化版本”，核方法已经成为将一个线性降维方法非线性化的标准做法。与其它核学习算法一样，在基于核的降维算法中，核及核参数的选取是一个十分关键的问题。另外，提高基于核的降维算法在大规模数据上的运行效率也是人们关注的焦点之一。

图3 核方法示意图

5. 两维化和张量降维 传统模式表示采用的是向量模式，即一个模式样本被表示为n维空间中的一个点。当模式样本被表示成向量时，则易于采用统计学中的一些方法对其进行后续处理。然而，实际的模式样本往往都是两维模式（比如人脸图像）。传统方法首先把此类两维模式转换成对应的向量模式，然后再按照类似一维模式的方法进行后续处理。但这样至少会带来如下不足：（1）原有矩阵模式的空间或结构信息可能会遭到破坏；（2）由于图像转换成相应的 向量后，维数通常会很大，导致计算时间的开销和存储开销会随着维数的升高而显著增加。近年来，基于两维化或张量的模式表示方法在模式识别、机器学习、计算机视觉等领域流行起来。相对于传统操作于向量模式的一维化方法，该方法操作于两维矩阵模式或更高阶张量，不再把图像拉伸成向量。刘（K. Liu）等人首先提出了直接对二维（two Dimension， 2D）矩阵图像而非其对应的一维（one Dimension， 1D）转化向量来提取特征的思想。其后续研究则分别从不同角度提出和进一步完善了这种直接对二维矩阵图像进行特征提取的方法，并发展出两维主分量分析（twoDimensional Principal Component Analysis，2DPCA）、两维线性判别分析（two-Dimensional Linear Discriminant Analysis，2DLDA）和两维典型相关分析（two-Dimensional Canonical Correlation Analysis，2DCCA）等。与核方法类似，两维化和张量方法也已成为推广原始降维算法的一种标准技术。两维化和张量降维方法的优点是计算效率高，另外，很多诸如人脸识别等实验结果显示在有些数据集上二维方法要明显优于一维方法。然而，尽管存在一些相关研究，目前仍很难解释为什么这种看似简单的二维表示方法会有效果以及什么时候会有效果等关键问题。

6. 流形学习与局部化降维 自2000年《科学》（Science）发表了两篇经典的等度规映射（ISOmetric MAPping，ISOMAP）和局部线性嵌入（Locally LinearEmbedding， LLE）算法以来，流形学习已成了目前机器学习领域一个新的研究热点。从降维的角度来看，流形学习是除了核方法之外实现非线性降维的另一类重要手段。流形学习的一个基本假设是样本分布在一个潜在的流形之上，所以尽管输入空间的维数很高，但流形的内在维度一般不是很高。如图4所示，左图是三维空间中的一个S曲面流形，其内在维度是二维。中间图是对流形进行采样而来，右图是经流形学习算法局部线性嵌入把流形展在二维平面所得到的结果。在等度规映射和局部线性嵌入之后，出现了一系列流形学习算法，主要包括拉普拉斯特征映射（Laplacian Eigenmaps，LE）、最大方差延展（Maximum Variance Unfolding，MVU）和局部正切空间对齐（Local TangentSpace Alignment， LTSA）等。相比传统线性降维算法，流形学习尽管能有效处理非线性问题，但多数流形算法存在计算效率低下、不能推广到Out-of-sample等问题。后续算法针对上述问题分别做出了许多改进，其中有代表性的是何（X.He）等人所提出的局部保持投影（Local Preserving Projection，LPP）。它实际上是拉普拉斯特征映射的线性化版本。在局部保持投影之外，出现了很多局部化的降维算法，这些方法中都利用了局部保持的思想，即在高维空间中相邻的样本在投影后的低维空间中也应该相邻，一般是通过k近邻（K-NearestNeighbor，k-NN）或ε邻域来度量近邻关系并用一个图来刻画，因而上述方法又可归为一类基于图的降维。之后，人们又将在支持向量机中关键的类间隔（Margin）思想引入其中，相应地发展出了近邻判别分析的降维算法（所谓类间隔是指类间的最小距离，直觉上，最大化该间隔能保证有好的判别性能）。与局部保持投影等无监督方法不同，近邻判别分析不仅综合了类别信息，而且通过同时构建类内及类间k近邻关系图定义出优化目标，进而优化该目标，以获得具有良好判别能力的数据降维。最近，严（S.Yan）等人提出的图嵌入的一般降维框架成为了一个典型的范例，它将上述多数降维方法纳入到该框架之中。在基于图的嵌入降维方法中，图的构建和参数的选取是其非常关键的步骤。

图4 流形学习示意图

7. 半监督降维

根据是否利用了监督信息，可把降维分成监督降维和无监督降维两大类。前者是指降维中利用了样本的类别信息，适用于样本有标记情形；后者是指降维中不需利用样本的类别信息，样本没有标记时也可用。值得注意的是，由于数据采集技术和存储技术的发展，获取无标记样本已变得非常容易。而有标记样本的获取由于需要相关领域的专家对样本进行标记，因而相对比较困难而且代价昂贵。在许多实际应用中，通常既会有大量的无标记样本，又会有少量的有标记样本。由此引出一个很自然的问题，即当获取的样本中既有标记样本，又有无标记样本时，如何进行降维？此时，传统的监督降维方法只能作用于少量的标记样本，难以利用大量的无标记样本，从而造成浪费。另一方面，传统的无监督降维方法没有利用宝贵的监督信息，限制了其后分类性能。

由此，半监督学习作为一种新兴的能同时利用标记和无标记样本的学习方法，正在机器学习及相关领域中流行起来。在降维领域也开始出现一些基于半监督思想的降维算法，比如半监督概率主分量分析、基于流形正则化的半监督判别分析、半监督局部费舍尔判别分析以及基于谱分析的半监督特征选择等。上述方法的共同点是，它们都通过在传统降维方法中引入无标记样本，来达到能同时利用标记和无标记样本降维的目的，从而最大程度地服务于其后的分类任务。由于在这些方法中，监督信息是通过标记样本以标号的形式来提供的，所以有时又称其为基于标号的半监督降维。在很多实际应用中，监督信息除了通过标记样本以标号形式给出外，还可有其它形式，比如部分样本的嵌入结果（又称流形上的坐标）以及样本间的成对约束（Pairwise Constraint，即两个样本是否属于同一类别作为监督信息）等。

总结和展望

本文简略地回顾了应用于机器学习和数据挖掘等相关领域的降维方法，介绍了主分量分析、线性判别分析和典型相关分析等经典降维算法，对当前降维研究中基于核的非线性降维、两维化和张量降维、流形学习和局部化降维以及半监督降维进行了介绍和分析。降维方法的发展经历了一个从线性到非线性，从无监督、监督到半监督的过程。我们认为，这与降维方法所要处理的数据有相当大的关联，如数据变得越来越复杂，无标记的数据量越来越大，而标记数据却有限。

展望未来降维方法的发展，它与数据的复杂性的特点分不开。很多数据处理中突出的特点是数据量非常大，甚至达到海量，研制面向海量数据的高效降维算法十分重要。为此可将数值分析和最优化领域中已有的快速算法结合到降维中来。在很多实际应用中所获得的数据还呈现出结构复杂、异构和多模态等特点，如何结合领域知识以便更好地处理这些复杂数据实现有效降维，是一个重要的研究课题。

现在大多数降维算法与后续的学习任务相分离。在对降维算法进行评价时， 又用降维后数据在学习器上的精度来衡量。由此导致两个既有趣又值得深入思考的问题：一是除了通过降维后数据在后续学习器上的精度来评价降维方法之外，是否还有其它方式？二是既然降维是由后续学习器来评价的，为何不把其纳入至降维过程中（类似特征选择中的封装法或嵌入式法）以便进一步提高性能呢？

与机器学习中其它研究方向类似，降维方法的研究主要来自统计学和数学领域，与其它领域特别是认知科学、神经科学的交叉并不多。在很多应用场合， 机器实际上仍远未达到人或其它一些动物的水平，非常典型的例子就是计算机视觉中的识别问题。例如，人能在复杂多变的环境中快速找到感兴趣的人或物，并能对其行为做出快速预知和判断。如果把人眼看作一个摄像机，那么在一段时间内记录下的“视频”（很多帧图像的序列）就是一个包含很多信息的高维数据集合。人是如何实现对此高维数据的快速特征抽取和降维的呢？我们认为，将降维的研究领域与认知科学、神经科学等领域进行交叉，是一个值得关注的方向。

参考文献：张道强 陈松灿，高维数据降维方法，南京航空航天大学，中国计算机学会通讯，第5卷 第8期 2009年8月

免责声明：本文系网络转载。版权归原作者所有。如涉及版权，请联系删除！