基于特征选择的SVM选择性集成学习方法

文/扈晓君 康宁

1 引言

支持向量机（SVM）是一种基于统计学习方法中结构风险最小化以及VC维理论基础上的机器学习方法[1]。SVM在解决过拟合和小样本学习分类方面具有良好的性能，SVM的一个主要特点是它可以克服机器学习领域的维数灾难问题。

在近些年来的机器学习领域中，集成学习也成为了研究热点之一。基本原则是使用多个单独的分类器通过投票的方式来综合分析判断。其中的基分类器类型又可以分为两类：异质类型和同质类型。其中生成同质类型分类器的方法主要有：Bagging(bootstrap aggregating)算法[2]和Boosting算法[3]。Bagging是一种可以并行执行的方法，其产生的训练子集通过有放回的数据抽样产生，最后将由训练数据产生的各个基分类器进行集成组合。而Boosting方法构成最终分类器的方式，则是给各个分类器赋予不同的权重来集合完成。

之前为了进一步提高SVM的泛化能力，部分研究已将集成学习技术集成到SVM中。然而由于集成学习是由多个基分类器进行合成，因而训练速度相比单分类器要慢，而且其中包含的基分类器规模越大，其计算复杂度和运行需要的资源也就越多。本文通过从集成学习的输入变量中提取特征子集来处理数据，获得较大差异化的训练子集，根据预测精度对所获得的基分类器进行选择组合。既可以让训练集和基分类器的差异增加，又可以让基分类器数量在一定程度上减少。

2 基于特征选取的选择性集成学习

一般的集成学习方法比较适合于不稳定的分类器，但SVM同其他分类器相比则属于比较稳定的算法。为了产生不稳定的差异化结果，可以通过在输入数据中构造特征子集的方式进行前期的数据处理，之后根据训练精度，通过排序获得部分选取的基分类器以形成最终的分类器集合。

2.1 SVM及选择性集成

支持向量机（SVM）通过确定分类的最优决策边界来使得类之间的间距最大化。SVM决策超平面可以表示为：

SVM的决策函数：

以下是引入核函数后SVM的超平面方程，以此解决非线性问题：

其中ai是为求得带约束的最优化问题而得到的拉格朗日因子。在引入核函数后，SVM分类模型为：

集成学习一般是应用多个基分类器，对其结合加权或简单投票的方式来分类。多项研究表明，集成学习框架同泛化能力不稳定的分类器进行结合会有比较好的作用。而对于选择性集成来说，有训练集T，验证集V，分类器h，其基本工作原理有：首先，初始化分类器集合S为空集，定义最终得到的分类器数量n；其次，通过迭代计算在T上得到子集ST，并使用ST分别获得hi，并将其放入S中；最后，在V上对S中的hi进行评估，按照一定的评估准则构成新的集合S*集成分类器。

2.2 特征以及数据集的选取

Bagging算法主要通过随机有放回抽样方法形成子数据集，然后生成差异化的子训练集。然后将通过这些训练子集获得的子分类器组合成集成分类器集合。本文也主要采用了此种方式选取数据。

在本文中，使用Bagging中的bootstrap方法用于选择训练数据，以便生成的基分类器在泛化能力方面产生较大的差异。同时，在特征集规模为F的样本数据集S中，随机的选择规模为f的子特征集，f

2.3 子分类器的选择

算法需要通过一定的评估标准，从之前的基分类器集合C中获得满足条件的子分类器形成新的子分类器集合C*。本文将使用基分类器的预测精度作为度量和选取标准。其中主要的过程是从集合C中按照基分类器的泛化能力大小来选择新的基分类器子集。

在分类器集合C中，通过验证集V对q个分类器进行测试，|V|代表验证集的样本数量，分类器ht的错误率：

从得到的分类器中依据各个分类器错误率的大小选取符合要求的基分类器进行组合。部分研究表明，对于分类器数量的选取上，当集合C中的分类器较少[4]时，选取40%左右会比较理想，而当集合中分类器较多[5]时，选取15%～30%的成员较好。确定所选择的规模大小之后，集合C*的成员由C中的分类器按精度排序并等间隔的选取构成，之后C*中的多个基分类器用简单投票法对数据进行分类。在样本集X中，h(x)i表示一组子分类器，kj表示第j类的标记。每类的得票数目如下：

该样本的为得票最多的那一类：

在二分类问题中，可以设置基分类器的数目为奇数个，以避免出现投票数一样多的问题。

2.4 执行步骤

有样本数据集合S：{(x1,y1),…(xn,yn)}，xi∈X，yi∈{+1，-1}，i=1,2,3…n，S=R∪V，S划分为训练集R和验证集V，h是子学习器，T为循环次数。R用于训练最初的基分类器集合，V用于在初始集中选取符合要求的基分类器。

步骤1.初始基分类器集合E=∅；

步骤2.迭代次数t=1…T，然后进行以下循环：

步骤2.1.为产生数据集Rt，在R上使用bootstrap算法进行抽样选取；

步骤2.2.在Rt上得到规模为M的特征集合F，再随机选取规模为m=|M/2|的特征集合f。Rt在f上投影得到子数据集Rt*；

步骤2.3.以Rt*作为训练集获得分类器ht，并放入集合E中；

步骤3.得到t个基分类器的集合E；

步骤4.通过V对E中的各个基分类器进行泛化评估，并对评估的分类器从大到小排序；

步骤5.将错误率大于0.5的基分类器去除，之后从E中剩余的分类器中选出一定的ht作为最终组合。

以上过程在2个方面得到了改善：首先，随机选取基分类器后再次对数据样本的特征集进行了随机选取，以此加大样本间的差异，进一步使得SVM的稳定性降低；其次，为了缩小基分类器最终的规模，在原集合中依据错误率再次对其中的基分类器进行了筛选。

3 实验及分析

3.1 实验数据

实验数据选取了4组来自UCI的数据集，并随机划分出各自相应的训练集、验证集和测试集。SVM在遇到多分类问题时，可以使用一对一[6]或者一对多的方式将问题转换为二分类问题。文中为便于处理非线性问题使用了高斯核函数，设置其参数σ为0.2，C为2。同时用一般的Bagging算法作为对比项，以往的验证表明其抽取的样本子集约包含63.2%的原数据。试验中的循环次数T为1000，基分类器的规模均设为291。实验所用数据的相关信息如表1所示。

3.2 实验结果及分析

表1

表2

实验所使用的是4个UCI数据集，实验前已对其中的缺失数据和无效数据予以剔除，并使用一般的Bagging算法作为参照，对比后的准确率如表2所示。

实验迭代次数均设为1000，本文算法与传统的Bagging算法相比较在4个数据集的结果上均有所提升，获得了相对于传统的Bagging算法较好的泛化性能和效果。

4 结语

本文将SVM和集成学习框架进行结合，其中通过对训练数据的子集和特征集进行选取使基分类器的泛化能力和结果产生较大的差异和不通，间接的将SVM分类器从稳定变为不稳定的状态，以便于更加适合当前的集成学习理论。通过在数据集上比较，本SVM集成分类效果要好于传统的Bagging集成算法。由于SVM可以通过调整不同的核参数来得到不同泛化能力的分类器，因而对于文中的算法还可以通过调参方式使得基分类器之间产生差异，这也是一个可以进一步研究和学习的方面。