0 引言

随着科学研究的不断进步，数据挖掘领域需处理的对象越来越复杂，其数据维度也在急剧增加，在图像识别、文本分类、生物信息学、基因微阵列分析等大规模数据挖掘应用中出现了一个被称为高维小样本学习的研究热点。

高维小样本数据，是指具备数据维数特别高，样本绝对数量很少或样本数远小于数据维数特征的数据(也有文献称为”Large p small n”数据^[1]，p代表特征数，n代表样本数)。

高维小样本数据上的分类问题是机器学习中的难点，针对不同的应用领域衍生出了高维小样本、高维稀疏、高维不平衡等多个研究热点。较高的维数是获得问题准确描述的有力保障，而难以避免地会含有大量冗余、不相关和噪声特征，由于高维小样本数据的这些特点，容易引发“维数灾难”(Curse of Dimensionality)，即随着维数增高，计算复杂度显著增高而分类器的性能急剧下降；又因为其样本数量很少，传统的分类学习方法效能严重下降，容易出现过拟合(Over Fitting)，无法进行有效的分类或识别；近年来，高维小样本导致的特征选择模型的不稳定性也引起了重视。为了消除或减轻维数灾难，同时提升分类器的泛化能力，降维成为重要途径。

在不同应用领域的高维小样本降维研究中，特征抽取与特征选择是两类非常重要的技术。特征抽取主要是是将高维数据映射到特定的低维空间，而特征选择可以看作从初始特征空间搜索出一个最优特征子集的过程。

从算法原理上分析，特征抽取是一种基于变换的方法，原数据中的不相关和冗余的特征均在降维中产生作用，影响了分类性能，且新的低维特征空间中特征失去原有的物理解释，对某些高维小样本数据分类问题(如癌症基因分析)而言，很难接受。特征选择并不改变原特征空间，只是选择一些分辨力好的特征，组成一个新的低维空间，可以保留原始特征空间大部分性质，对于高维小样本而言，特征选择可以去除不相关特征和冗余特征，在一定程度上将噪声数据对分类器性能的影响降到最低，且选择的特征可解释性较好。

特征选择已成为高维小样本数据分类问题中的关键性步骤，一直是机器学习和数据挖掘研究的热点之一，新的算法也不断地被提出，本文对当前已进行的研究进行综述，尝试从原理上分析这些算法的区别与联系，总结各自的优点与不足，并对未来高维小样本特征选择的研究进行展望。

1 高维小样本中的特征选择

为了便于比较和分析，本文按照评价函数的不同将高维小样本特征选择方法分为Filter(筛选法)、Wrapper(封装法)、Embedded(嵌入式)以及Ensemble(集成法)四类，在实际高维小样本分类应用中，Embedded方法因其适合处理小样本问题而受到了诸多研究人员的关注，本文也将针对该类方法作重点分析。

1.1 Filter(筛选法)

Filter(筛选法)通过分析特征子集内部的特点来衡量特征的分类能力，与后面的采用何种分类器无关，这类方法通常需要评价特征相关性的评分函数和阈值判别法来选择出得分最高的特征子集。通过文献调研，根据选择特征子集方式的不同，可以继续划分为基于特征排序(Feature Ranking)和基于特征空间搜索(Space Search)两类。

基于特征排序的方法，其主要思想^[2]是：

1) 使用评分函数(Scoring Function)对每个特征进行评分，并将所有特征按照得分的降序排列；

2) 对每个特征得分进行显著性检验(如p-value等)；

3) 通过预先设置的阈值选择排序前列的具有显著统计学意义的特征；

4) 验证选择的最优特征子集, 通常使用ROC(Receiver Operating Characteristic)曲线、分类正确率、组相关系数、稳定性等。

基于特征排序方法的核心就是评分函数，表 1列举了高维小样本分类应用中出现的基于度量样本群分布之间的差异、基于信息论、基于相关性标准等三类热门评分函数。

基于特征空间搜索法主要是采用一种优化策略从整个特征集合中选出包含最多信息并且达到最小冗余的特征子集。在特定领域，如致病基因的准确发现有一些研究，如基于关联规则(Correlation-based Feature Selection, CFS)、最大相关最小冗余(Maximum Relevance Minimum Redundancy, MRMR)等，表 2给出了上述基于特征空间搜索法的几类主流方法。

基于特征排序的方法多为单变量方法，每次考虑单个特征的影响，选择与类标签最相关的特征，对高维小样本来说具有较低的计算复杂度，但在某些应用领域如基因微阵列数据中，因忽略了特征间的相互关系，直接应用分类精度较为一般；而基于特征空间搜索为多变量的方法，这类算法不但需要考虑特征子集与类标签的相关性，还需要考虑特征子集之间的相关性，通常分类正确率较高，但在高维条件下寻找最优子集过程的计算复杂度较高。

1.2 Wrapper(封装法)

Wrapper方法是一种与分类模型结合的特征选择方法，使用某个分类模型封装成黑盒，根据这个分类器在特征子集上的结果好坏来评价所选择的特征，并采取某些优化的搜索策略对子集进行调整，最终获得近似的最优子集。N个特征的数据集，可能的特征子集数为2^N个，发现最优特征子集已经被证明是NP-Hard，因此高维小样本特征选择中Wrapper研究热点并不局限于采用何种分类模型作为评价准则(通常使用遗传算法(Genetic Algorithm, GA)^[23]、支持向量机(Support Vector Machine, SVM)^[24]、K最近邻(K-Nearest Neighbor, KNN)^[25]构建分类模型)，特征子集搜索策略成为研究热点。

根据文献[26]，Wrapper方法可以被粗略划分为顺序搜索与启发式搜索两类(有文献将其分类为确定性与随机性^[22])：

1) 顺序搜索算法。

顺序搜索算法从一个空的特征子集开始，通过不断增加(或删除)特征直到特征子集能使评价函数得到最好表现，现实中会引入一些停止搜索的标准加速特征子集的选择，确保评价函数持续增加并达到最好表现时，所选择特征子集具有最少数目。图 1给出了常规顺序搜索算法的发展脉络。

顺序搜索策略不断增加(或删除)单个特征，避免了完全搜索计算复杂度过高的问题，但选择出的特征子集很难避免所选特征之间的高度相关性^[27]；自适应的顺序浮动选择方法(Adaptive Sequential Floating Forward Selection, ASFFS)^[28]引入了参数r用于指定加入特征的数量，并使用参数o去除属性；同时，为了提升时间性能，Nakariyakul等^[29]提出一种新的特征选择方法——“增L去R”，每次从候选特征集中添加(或删除)L个特征，考虑入选(或删除)的L个特征之间相关性，然后删除(或添加)与类标签最不相关(或最相关)的R个特征，有效提升了算法的时间性能。

2) 启发式搜索算法。

启发式搜索算法所开始搜索的初始特征子集是从完整的特征候选集中随机生成，通过启发式规则逐步接近最优解，这种方法在搜索时具有很强的不确定性，但随着算法的运行，使用这种策略获得的特征子集的质量也能满足需要。在高维小样本特征选择中常用的启发式搜索方法有GA和粒子群优化(Particle Swarm Optimization, PSO)算法^[30]等，通过设定迭代次数的阈值，从而降低需要搜索的特征子集的数量，通过调整GA的参数和遗传算子，还可以获得更多的应用。Cordón等^[31]使用进化遗传算法的方法对图像识别领域中的特征选择问题进行了尝试。

因为顺序搜索算法的特点，无法从已抛弃的特征中进行二次选择，也无法抛弃已选择的特征，容易陷入被称为嵌套影响(Nesting Effect)的局部最优情况，启发式搜索算法可以有效解决这些问题，并且有文献表明，采用并行设计启发式搜索算法的计算复杂度比顺序选择算法显著降低^[32]。

1.3 Embedded(嵌入式)

Embedded(嵌入式)方法的出现主要是为了解决Wrapper(封装法)在处理不同数据集时，分类模型需要重构代价高等问题。如果严格区分，它与Wrapper的不同在于，Embedded将特征选择与分类模型的学习过程结合，即在分类器的训练过程中包含了特征选择功能，由于其高效的时空性能及较好的分类精度，逐渐成为高维小样本特征选择的热点方向，其中，有两类方法成为非常热门的研究对象：一是以SVM为基础的模型；二是以套索算法Lasso(Least Absolute absolute Shrinkage shrinkage and Selection selection Operator)为代表的正则化组稀疏模型。

由于SVM可以根据有限的样本在模型的复杂性和学习能力之间寻求最佳平衡，弱化了对数据正态分布的要求，同时对维数灾难不敏感，可以有效剔除冗余特征，具有较好的泛化性能，因而被广泛用于处理高维小样本特征选择。

Guyon等^[33]采用基于递归特征的后项搜索剔除思想(Recursive Feature Elimination, RFE)，提出SVM-RFE方法，该方法将SVM超平面的每个维度对应高维小样本数据集里的每个特征，从而每个维度权重的绝对值可以用来度量对应数据特征的重要性，即通过权重对特征进行降序排序。从排序后的特征集合开始，每次删除排名靠后的一个特征，迭代直到该特征集合为空，一般来说最先被删除的多为噪声或冗余特征，最后被删除的特征一般具有较强的区分能力，由于该方法在处理高维小样本数据方面的优势及贪婪算法带来的计算复杂度，围绕该方法研究人员提出了许多改良方法，其中有按比例删除特征的^[34-35]，采用前向序列思想的^[36-37]，采用模糊聚类的^[38]，基于Relief的^[39]以及采用了粒子群算法的^[40]，图 2给出了部分基于SVM-RFE的算法分类。

除基于SVM的方法之外，正则化稀疏模型可以将大量冗余或噪声特征去除，同时保留与类标变量最相关的特征，选择的特征子集具有很好的可解释性，也获得了许多研究人员的关注。其代表算法有1996年Tibshirani^[41]提出的Lasso，其基本思想是在最小二乘估计中加入系数的绝对值作为惩罚项，使系数的绝对值之和小于等于某一个阈值来最小化残差平方，能产生趋于0的回归系数，使得与目标关系弱的预测变量(特征)系数被惩罚为0，从而具备特征选择功能。表 3给出了Lasso在高维小样本数据应用中的优势和不足。

为了解决Lasso的有偏估计问题，自适应Lasso、松弛Lasso、SCAD(Smoothly Clipped Absolute Deviation)模型、MCP(Minimax Concave Penalty)等模型^[42-43]相继被提出。

由于缺少高效的求解算法，Lasso在高维小样本特征选择研究中没有广泛流行，最小角回归(Least Angle Regression, LAR)算法^[44]的出现有力促进了Lasso在高维小样本数据中的应用，后续研究人员从降低计算复杂度及避免过拟合等角度对Lasso进行了改进，如采用迭代思想的GSIL(Gene Selection based on Iterative Lasso)，采用序贯思想的SLasso(Sequential Lasso)以及采用有监督组Lasso(Supervised Group Lasso, SGLasso)等。表 4给出了部分针对Lasso缺点的改进方法及其基本思想。

1.4 Ensemble(集成法)

集成学习是使用一系列特征选择方法进行学习，并使用某种规则把各个学习结果进行整合从而获得比单个特征选择方法更好学习效果的高维小样本特征选择方法。在某些高维小样本特征选择问题研究中，学者多采用这类方法提升特征选择算法的稳定性，如Li等^[52]提出一种新的特征选择方法，采用重抽样技术把数据扰动，生成几个不同的训练集和测试集，反复调用递归决策树，并把分类错误率作为评价指标来选择特征；Dutkowski等^[53]将不同特征选择算法用于基因选择，并通过优化策略来整合各个算法得到的结果，形成最终的特征子集；Saeys等^[54]、Abeel等^[55]将Bagging思想用于集成特征选择，Saeys采用融合多个特征选择算法结果的方式来完成特征子集的集成，而Abeel则通过样本重取样技术生成多个特征子集，并在若干高维小样本数据集上与SVM-RFE方法进行对比，取得较好效果。

1.5 特征选择方法总结

高维小样本特征选择难点在于在有限的样本空间内尽量剔除冗余特征及噪声数据、尽量选择分辨能力更好的特征、保证算法的稳定性，同时还需要避免过拟合及综合考虑时空性能。表 5给出了四类特征选择方法在高维小样本应用中的优缺点对比。

在实际应用中，SVM和以Lasso为代表的正则化方法是比较常见的方法，特别是SVM方法由于其产生的分类器结构简单，用到的样本信息很少，受到了更多的关注，在一些文献中也有将两者结合共同进行特征选择的研究^[25]。在近期的文献中，已较少见到Filter和Wrapper单独作为高维小样本的特征选择模型，常见的多将其应用于两阶段的特征选择，如使用计算复杂度较低的Filter方法去除冗余与噪声特征，选择与类标签相关度较好的特征构成新的特征集合，再用Wrapper方法(如SVM、GA、随机森林)在新的特征集合上去选择分辨力非常强的特征子集，可以实现很好的降维效果^[56-58]，而集成法则更多用于需要算法具备较好稳定性的应用中，对原本就稳定的特征选择方法，集成后效果并不明显。

2 挑战与研究展望 2.1 面临的挑战

1) 数据不一致，各算法很难直接比较。

高维小样本特征选择多源自数据驱动，以基因微阵列数据为例，各研究人员使用的数据来源不尽相同，甚至有同名数据集但内容不相同的情况^[59]，这使得后续研究人员很难在统一的数据标准下重现目标算法来进行结果的比较。

2) 分类正确率是否仍然是唯一重要指标。

传统特征选择方法有很多评价指标，在高维小样本环境中，有相当一部分文献在作算法对比分析时，仅仅进行了分类精度的度量，较少涉及算法稳定性、结果可解释性等度量。

除此之外，面对不平衡高维小样本数据，特别是在一些代价敏感学习问题中，降低决策风险、减小平均误分类代价和提高分类可靠性显得尤为重要，分类正确率是否依然作为特征选择唯一的重要的评判标准还应具体问题具体对待。

3) 复杂且超高维数据带来巨大压力。

目前主流的特征选择方法SVM及Lasso等在处理连续型数据时具有较好的优势，随着大数据技术的不断发展，数十万维且混合了离散和连续型数值的数据集将有可能成为高维小样本领域最常见的对象，个别数据甚至可能超过千万维，复杂且超高维数据的到来给未来特征选择方法不但在时间和空间复杂度方面提出了巨大挑战，更在算法本身的设计方面提出了新的要求。

4) 缺少国内可信数据源。

目前学界使用的大多为国外机构提供的分析数据，缺少国内公开的权威数据源，特别是基因微阵列数据及人像识别等领域，据此分析的结果得出的结论(如哪些基因对疾病诊断有帮助)很难在实践中得到验证，各算法得出的最终结果的可解释性受到一定影响。

5) 缺少对特征选择结果的解释分析。

大多数文献采取与其他文献中算法进行量化的对比分析来说明自己算法的优势，很少有文献针对特征选择的最终结果，即最终选择的特征集合的物理属性进行深入分析，仅通过文献的阅读很难了解这些被选择出的属性是否可以用于指导实践，特征选择结果的可解释性无从考证。

2.2 未来研究展望

随着大数据时代的不断演变，高维数据的价值越来越凸显，高维小样本特征选择主要面临计算复杂度、时间复杂度和复杂数据类型等问题，结合文献调研及趋势分析，本文认为面向高维小样本的特征选择方法还可以在以下几个方面取得新的进展：

1) 增量式学习算法(Incremental Learning)。

在未来超高维小样本数据面前，常规的集中式特征选择方法可能很难满足时空性能的需求，甚至无法得到令人满意的特征选择结果，增量式学习为超高维小样本数据的特征选择问题提供了一种思路，增量式不仅指数量的逐渐递增，更多的是指特征数量的逐渐递增。目前，已有工作开展了相关研究，形成了被称为“Online Feature Selection”的研究热点。

2) 非连续型数据的处理。

当前高维小样本特征选择所面对的数据对象很大一部分是连续型数据，特别是基因微阵列数据都是细胞内mRNA的相对或绝对数量来表示的连续型数据，相应的，大多数文献都选择了SVM或Lasso等可以直接处理连续型数据的特征选择方法，就本文所调研范围，少有文献去深入分析高维小样本连续型数据的离散化问题。因此，对非连续型数据的特征选择及与连续型数据特征选择方法进行深度对比分析具有一定研究价值。

3) 算法的稳定性(Stability)与可伸缩性(Scalability)。

Lasso等正则化的稀疏模型存在特征选择的不一致性，即模型稀疏化后的不稳定性，同样的问题也可能出现在其他几类主流的特征选择方法中，由于高维小样本数据的特殊性，今后的研究可能不单纯只进行分类正确率及时空性能的比较，还需要考虑算法本身的稳定性，这样选择的结果才更加容易被接受；同时，随着数据维数的急剧增加，算法的可伸缩性也是一个重要的指标，随着数据量和维数的增加，算法的性能不可出现显著下降。

4) 传统统计学算法焕发新生。

正则化方法产生于1955年，Lasso也是20年前的方法，这些传统的方法在高维小样本等新的应用环境里重新获得了发展，这也提示传统的统计学中的变量选择方法是否值得去重新梳理，特别是一些线性计算，空间复杂度低的方法，挖掘和改进使之与当前高维小样本应用能够结合，从而丰富高维小样本的特征选择方法。

5) 多阶段的混合式特征选择。

在高维小样本的应用中，通常伴有高维不平衡、高维稀疏等现象，没有一种通用的方法可以应对所有的高维小样本分类应用问题，采用混合的多阶段的特征选择方法，可以有效去除不相关及冗余特征，如使用重抽样技术扩大样本规模，使用Filter去除不相关属性，再使用Embedded等方法去除冗余属性等。

6) 可信数据源的构建。

随着政府开放数据带来的利好，国内会有更多专业机构参与国内数据的采集整理工作，如果能根据权威公开数据构建高维小样本数据开放共享平台，让更多研究人员参与其中，可以更好地发挥数据本身的价值。