特征稀疏性

特征稀疏性研究可以从特征提取和特征选择出发。特征提取是指通过某种变换，将原始高维数据映射到低维空间的方法。线性变换方法包括：非负矩阵分解（Non－negative MatrixFactorization，NMF）［68］、主成分分析（Principle Component Analysis，PCA）［69］、局部保留投影（Locality Preserving Projection，LPP）［70］和线性判别分析（Linear Discriminant A－nalysis，LDA）［71］等方法。线性变换方法不能保持局部信息和没有显式考虑数据所在的流形结构，进而不能很好地解释降维前后数据之间的联系。为了保持不同数据的结构信息，一般采用非线性降维技术，其中流形学习（Manifold Learning）［72］和核学习（Kernel Learning）［6，7，73－75］，是当前研究热点。

特征选择是指从原始高维数据中选择若干特征组成新的低维数据的方法。按照评价体系，特征选择方法可分为筛选式（filters）、封装式（wrappers）、嵌入式（embedded）三类。（1）相对于封装式和嵌入式，筛选式不需要计算模型，而是直接计算特征子集的某种度量，常使用的度量准则有：方差（Variance Score）、拉普拉斯得分（Laplacian Score）和互信息（Mutual Information）等，基于不同评价准则，很多过滤方法被提出并且应用于实际问题中，比如：F－值（F－score）方法［76］、t－检验（t－test）方法、最大相关最小冗余法（mRMR）、信息增益法（Information Gain）和拉普拉斯得分方法（Laplacian Score）等。通常，筛选式的特征选择过程在分类或者聚类任务之前，一般会有两个步骤，第一步：根据预定义的评价准则将所有的特征进行排序，第二步：选择排序在最前的特征。筛选式的特征选择相对简单高效，但是它没有考虑选择的特征子集在分类或者聚类算法上的性能表现。其优点是计算资源占用小，而缺点是可能无法选择最有用的特征子集。（2）封装式通过建立在子集上的一个模型来计算子集的得分，一般可采用基于该子集的后续学习器（根据实际需要，例如，拟合器、分类器、聚类器等）的性能作为模型。其优点是得到的特征子集更符合后续学习器的需要，缺点是计算耗时过长、且易发生过拟合［77］。（3）嵌入式是近几年提出的一种结合学习器评价特征子集的特征选择模型，具有封装式特征选择模型的精度，同时具有筛选式特征选择模式的效率。比如采用了不同范数的SVM模型，这些模型可以在进行特征选择的同时进行分类或者回归［78］。标准SVM一般称为l2－norm SVM。这一模型不具有特征稀疏性，所以对于具有高维样本数据特性的分类问题，标准SVM并不能取得较好的分类精度。鉴于此，使用不同范数以期具有特征稀疏性的SVM新模型和算法陆续提出，其对于具有高维样本数据特性的分类问题可以达到比较好的分类精度，结果也更具有可解释性。

目前，稀疏SVM模型包括两类，第一类是能够同时实现分类与通常意义下的特征选择的稀疏SVM，这类模型使用能够导致稀疏解的范数代替标准SVM中的l2－norm，包括l1－norm SVM［79］、l0－norm SVM［81］与lp－norm SVM（0＜p＜1）［40］以及混合模型，如l2－l1－norm SVM［81］，l2－l0－norm SVM［81］，l2－lp－normSVM［82］等。l1－norm SVM可以转化为线性规划，易于求解。l0－norm SVM则是非多项式可解（NP）问题，通过逐步线性近似（Succsessive Linear Approximation，SLA）将其转化为一系列线性规划求解［83］。lp－norm SVM是非凸、非光滑的优化问题，其目前的求解方法与求解l0－norm SVM类似，也是通过逐步线性近似将其转化为一系列线性规划求解。混合模型中，除了l2－l1－norm是凸二次规划，l2－l0－norm SVM，l2－lp－norm SVM目前均通过CCCP（Convex－Concave Programming）［84］近似转化为一系列凸二次规划求解。

第二类是能够同时实现分类与成组特征选择的带有组范数（group－norm）正则项的稀疏SVM模型，即用group－norm代替标准SVM中的l2－norm得到的模型。成组特征选择与通常意义下的特征选择不同之处在于，成组特征选择要实现同一组特征同时被选择或同时不被选择。在成组特征选择问题中，特征的分组通常是已知的，特征的分组有两种情形，一是每个特征只能在一个组内，二是一个特征可能同时存在于多个组内，如生物信息学中的癌症基因选择问题中，一个基因往往同时在多个生物通路中行使功能（这个基因同时存在于不同的组内）。带有组范数正则项的稀疏SVM模型比较少，目前仅有研究第一种分组情况的l∞－norm SVM［85］，其最终可以转化成线性规划求解。此外，这类模型是以特征选择为目的提出的，并未使用核技巧，在处理非线性问题中具有局限性。对于大规模实际问题，其很难保证实用性。目前，由于处理方式的限制，凡带有p范数（0＜p＜1）正则项的稀疏支持向量机所有模型在目前的求解过程中，都会增加2n个约束，当特征数目n比较大时，计算机很难处理或根本不能处理。如文本分类或基因选择问题中，特征的数目通常会数以万计，一般的PC根本没有办法处理，这极大限制了稀疏支持向量机在实际问题中的应用。而l∞SVM在同时解决分类与成组特征选择时只考虑了最简单的第一种特征分组情况，对于实际问题中比较常见的第二种特征分组情况，l∞－norm SVM还不能解决。