1.3.1　特征降维

真实世界中的很多数据是高维的，即数据包含很多属性或特征。尽管高维数据比低维数据拥有更多的信息量，但在实际应用中对高维数据进行直接操作非常困难。首先，“维数灾难”[15,16]会导致分类学习所需的有标记样本计算量随着维数的增加呈指数级增长，部分算法在极高维空间中甚至无法工作；其次，人们在低维空间中形成的一些直觉在高维空间中可能会失效。例如，对于二维空间中的单位圆和单位正方形，两者的面积相差不多；对于三维空间中的单位球和单位立方体，两者的体积也差不多；然而随着维数的增加，在高维空间中超球的体积相对于超立方体的体积会迅速变小。

为了解决高维数据所面临的问题，一种有效的方法是对其进行降维。笼统地说，降维是指为高维数据获取一个能忠实反映原始数据固有特性的低维表示。降维有特征选择和特征提取两种方式[17−19]。

特征选择的基本原则是选择类别相关的特征而排除冗余的特征。它是根据某种准则从一组数量为D的特征中选择出数量为d（D>d）的一组最优特征的过程。特征选择通过降低原始数据的相关性和冗余性，在一定程度上解决了“维数灾难”问题。特征选择主要分3类[20−23]：①过滤法，设计一个评分函数对每个特征评分，按分数高低将特征排序，并将排名靠前的特征作为特征子集；②封装法，把学习机作为一个黑箱并通过验证样本的正确率来衡量特征子集的性能，一般采用向前或向后搜索的方法生成候选特征子集；③嵌入式方法，该方法是一种结合学习机评价特征子集的特征选择模型，具有封装法的精度和过滤法的效率。近年来，众多学者从事特征选择研究，并取得了一些成果。Kira和Rendell提出的Relief[24]算法根据特征值在同类实例中及相近不同类实例中的区分能力来评价特征的相关度；Nakariyakui和Casasent提出的分支跳跃法[25]通过对解决方案树中某些节点不必要评价函数的计算来提高搜索速度；Brodley提出的FSSEM算法[26]根据最大化的期望值来选择特征子集；Whiteson等人提出的FS-NEAT算法[27]通过特征集合搜索和拓扑网络学习解决特征选择问题。

特征提取是指原始特征空间根据某种准则变换得到低维投影空间的过程。与特征选择相比，特征提取的降维效率更高[28]。特征提取可分为线性方法和非线性方法两类。经过几十年的发展，研究人员提出了多种线性特征提取方法：非负矩阵分解（Non-negative Matrix Factorization，NMF）[29]通过将原始特征空间低秩近似来保证降维后的特征非负；因子分析（Factor Analysis）[30]通过降低原始特征空间的相关性实现降维；奇异值分解（Singular Value Decomposition，SVD）[31]通过考察奇异值的贡献率实现降维；主成分分析（Principal Component Analysis，PCA）[32]通过对原始特征空间方差的研究得到一组正交的主成分；独立成分分析（Independent Component Analysis，ICA）[33]利用原始特征空间的二阶和高阶统计信息，进一步提高了PCA的降维效率；线性判别分析（Linear Discriminant Analysis，LDA）[34]通过最大化类间离散度和类内离散度的广义Rayleigh熵实现特征变换。线性特征提取方法不能保持原始特征空间的局部信息，没有充分考虑数据的流形结构。鉴于此，近年来出现了众多非线性特征提取方法：核主成分分析（Kernel Principal Component Analysis，KPCA）[35]和核Fisher线性判别分析（Kernel Linear Fisher Discriminant Analysis，KLFDA）[36,37]分别在PCA和LDA的基础上引入核方法，将PCA和LDA的适用范围从线性空间推广到非线性空间；多维缩放（Multi-dimensional Scaling，MDS）[38]通过保持数据点间的相似性实现降维；ISOMAP（Isometric Mapping）的主要思想是利用数据间的测地线距离代替欧氏距离，然后利用MDS来求解；局部线性嵌入（Locally Linear Embedding，LLE）[39]利用稀疏矩阵算法实现降维；拉普拉斯特征映射（Laplacian Eigenmap，LE）[40]利用谱技术实现降维。此外，近年来还出现了一系列基于流形学习的算法，如局部切空间排列（Local Tangent Space Alighment，LTSA）[41]、海森特征谱（Hessian Eigenmap，HE）[42]、保局投影（Locally Preserving Projection，LPP）[43]、近邻保持映射（Neighborhood Preserving Projection，NPP）[44]等。这些算法本质上都是非线性降维方法，并没有利用样本的类别信息。鉴于此，研究人员提出了有监督非线性降维方法，如判别近邻嵌入（Discriminant Neighborhood Embedding，DNE）[45]、最大边缘投影（Maximum Margin Projection，MMP）[46]等。DNE算法基于不同类别拥有不同低维流形这一假设，为每个类别分别建立流形结构，然后通过最大化不同类别间近邻样本距离、最小化相同类别近邻样本距离得到最终的子空间。MMP则是一种半监督学习方法，其考虑到现实中获得样本的标记比较困难，所以对于获得的样本，如果有标记则尽量区分不同的流形结构，如果没有标记则尽量发现其所在的流形结构。MMP将LPP和DNE结合，通过求解广义特征值问题得到子空间。流形学习在数据可视化领域得到了广泛应用。然而，由于流形学习隐式地将数据从高维空间向低维空间映射，所以其不足之处在于无法得到新样本在低维子空间的分布。流形学习在描述邻域结构时还存在邻域选择、邻域权重设置等问题。

上述降维方法无法解释各变量对数据表示和分类的影响。鉴于此，研究人员提出了基于稀疏表示的特征提取方法。稀疏表示由傅里叶变换和小波变换等传统的信号表示扩展而来，目前在模式识别、计算机视觉、信号处理等领域得到成功的应用。迄今为止，基于稀疏表示的降维方法的典型代表有[47]稀疏主成分分析（Sparse PCA，SPCA）、稀疏线性判别分析（Sparse LDA，SLDA）、稀疏表示分类器（Sparse Representation-based Classification，SRC）、稀疏保持投影（Sparsity Preserving Projection，SPP）等。SPCA没有考虑样本的类别信息，因此不利于后续的分类任务。SLDA可以用于解决二分类问题，但对于多分类问题，并不能像LDA那样进行直接扩展。SRC在流形稀疏表示的框架下保持数据的局部属性，该方法被成功地应用于人脸识别。SPP将稀疏表示的稀疏性作为一种自然鉴别信息引入特征提取中，并在人脸数据集上证明了其有效性。然而，稀疏表示在寻找子空间的过程中会牺牲类内的同一性，因为它对单个样本分别获取它们的稀疏表示，因此缺乏对数据全局性的约束，无法准确地描述数据的全局结构。当数据包含大量噪声或有损坏时，会使算法的性能明显下降。