基于Stacking策略的稳定性分类器组合模型研究

吴挡平,张忠林,曹婷婷

(兰州交通大学 电子与信息工程学院,兰州 730070)

1 引 言

分类是数据挖掘和机器学习的基本问题,对于如何提高分类器的分类性能是当下主要的研究目的之一.传统的分类器的学习系统是由给定的训练样本集,使用已有的学习器(如支持向量机、决策树等)进行训练产生一个模型,再用训练好的模型来预测新的测试样例,后根据模型的预测结果来对学习器的分类性能进行分析[1].然而随着数据量的不断增加和数据的多元化,传统的分类算法已经无法满足对现有数据的处理以及实际问题的解决.对单个学习器的组合学习,使得在分类问题中显示出了强大的优越,从而使得组合分类算法在分类问题中得到了极大的关注.

现最流行的组合分类算法Boosting[2]和Bagging[3]方法.Bagging中使用的重采样技术使得每个弱分类器的分类性能是独立的,因此这些弱分类器可以并行的构造.随机森林[4]就是最典型的代表,它是由Breiman于2001年提出的一种基于决策树的集成算法.Bagging方法的分类性能在于其基分类器的稳定性,它对于不稳定性的分类算法分类效果较好(决策树[5]、神经网络等),但是对于稳定的分类器集成效果就不是很理想.文献[6]元慧等人提出了一种基于特征选择的SVM Bagging集成方法,采用不同的特征选择方法构建子学习器,以增加不同子学习器间的差异性,与Bagging不同,Boosting方法中基分类器的训练集取决前一个基分类器的分类性能,对前一个分类器分错的样例按较大的概率出现在下一个基分类器的训练集中,虽然提高了组合分类算法的泛化性能,但有可能会出现过分偏向于一些很难分的样例,从而有时会导致算法的性能降低(其中C5.0就是采用Boosting方式的组合算法).He等人[7]针对Boosting很难应用在KNN上和对噪声较敏感的问题,提出了基于组合模型的BK-NN算法,通过距离度量计算的优化以及重置数据集的多样性,提高了泛化性能.文献[8]提出了基于图模型的自适应K近邻算法,为了改进KNN算法性能将Boosting技术映射到基于图的方法中.

针对Bagging[10]和Boosting[11]两种组合算法在分类任务中对稳定性的分类器集成效果并不理想且改善效果均十分有限的问题,本文利用Stacking[9]策略的两层式叠加框架,结合特征降维技术,提出了一种基于Stacking策略的稳定性分类器组合模型.

本文首先利用一种过滤式的特征选择算法对数据集进行预处理,消除一些冗余特征以简化组合分类模型；然后在基于Stacking算法的多分类器组合方法上,将SVM、KNN、GLM和LDA四种稳定性学习算法作为初级分类器进行组合学习,次级分类器采用逻辑回归算法,实验部分主要对本文的组合算法与单个算法以及其他几种集成算法的对比分析,结果表明基于Stacking策略的稳定性分类器组合模型能够获得更好的分类精度.

2 多分类器组合方法

2.1 Stacking策略

对于Stacking策略,作为一种异构分类器集合的技术.该方法被认为是实现集合中基分类器多样性的工具,以此提高组合分类的准确性.它采用两层框架的结构,如图1所示.具体的训练过程为：首先Stacking方法调用不同类型的分类器对数据集进行训练学习,然后将各分类器得到的训练结果组成一个新的训练实例作为元分类器的输入.最终元分类器的输出结果为最终的结果输出.Stacking是一种通用框架,可看作是许多集成方法的推广[12].

图1 Stacking算法框架Fig.1 Stacking algorithm framework

2.2 投票法

投票法是每个基分类器对样本的预测结果中,数量最多的类别就是最终的分类类别,相比平均后验概率法和stacking学习法,此方法保留了每个基分类器的预测结果,但却把每个基分类器对其他类的预测情况给忽略掉了,因此算法对基分类器的选择和数据集变化较敏感[13].

2.3 平均概率法

平均后验概率法是适用于基分类器或类别数过多的情况下的一种分类器集成策略.现假定有N个基分类器,K个类别,x为输入数据,其中第i个基分类器对应的分类结果为：

Ci(x)=[Pi1Pi2……PiK]

向量pin表示每个类别的后验概率.对所有的基分类器对每个类别的后验概率求平均,作为元分类器的输入为

[(P11+…+PN1)/N…(P1K+…+PNK)/N]

即这样数据从N*K维变为K维,但这种方法却掩盖了基分类器的预测结果,因此在类别数较少的数据集中其精度往往低于基于分类器输出方法[13].

3 基于Stacking策略的稳定性分类器组合模型

在组合模型中,对基分类器的选取这里我们有两种选择：

1)选取的基分类器是同一种类型的.(比如对单个的决策树学习器使用不同的参数训练得到多个决策树模型组合学习和对神经网络使用不同层数构造多个不同结构的训练模型组合学习)；

2)选取的基分类器不是一个类型的,或者说是异质的(比如对于一个分类问题.在同一个训练集在采用支持向量机,逻辑回归模型和K近邻算法几种不同的基分类器组合学习得到最终的分类模型).本文采用第二种选择方法,基于Stacking学习法的两层结构框架,对几种不同的稳定性分类器组合学习.具体的为GLM、LDA、KNN和SVM作为第一层的分类器,也就是基分类器,广义线性模型(GLM)也可以说是逻辑回归作为第二层的元分类器.针对这四种常见的、在组合模型中一般不采用的稳定性分类器的特点,提出了将这4种算法进行组合学习,从而进一步提高分类器的分类性能.下面主要介绍了这4种算法和结合的数据降维机制.

3.1 分类算法

3.1.1 K邻近算法

K邻近算法(K-Nearest Neighbor),是一种较传统的稳定性分类器,也是一种懒惰的学习算法,其基本思想是对预测样例点最邻近的K个样例点与预测样例点进行计算,从而判别出新样例点的类别,达到对新样例的分类和预测.它是一种基于距离和样本实例的无参方法.虽然说KNN算法简单有效,但是随着样本的分布不均匀增大时时,算法的分类误差也会增大[14].

3.1.2 支持向量机

支持向量机(SVM)是一种经典的稳定性分类器.它是基于统计学习理论(Vapnik-Chervonenkis ,VC)和结构风险最小化理论(Structural Risk Minimization,SRM)发现训练子集中的最小化经验风险和最大化决策边缘来控制算法的分类能力.SVM在解决二分类问题具有很好的泛化能力以及在解决非线性的高维的数据集来说具有一定的优势.因此在分类、识别和检索等应用很广泛[15].

3.1.3 线性判别分析

线性判别式分析(LDA)是一种传统的稳定性分类算法.它的核心思想是通过将高维的样本集投影到一个矢量空间,使得样本在新的子空间中有最大的类间 距离和最小的类内距离[16].即类间的耦合度低,类内的聚合度高,这样才能使得分类效果最佳.

假设一个Pn空间有m个样本分别为：x1,x2,…,xm,即每个x是一个n行的矩阵,其中ni表示属于i类的样本个数,假设有j个类,则可得类i的样本均值为：

(1)

可得总体样本均值为：

(2)

类间离散度矩阵计算法如公式(3)所示：

(3)

类内离散度矩阵计算如公式(4)所示：

(4)

其中ui表示类i的样本均值；u表示总体的样本均值；xk表示第k个样本.

3.1.4 广义线性模型

广义线性模型(GLM)在处理二分类问题上应用最广泛的是Logistic回归模型.适用于输入变量与输出变量间为线性关系,它将样例的属性特征整合为线性组合来当作输入变量,其使用logistic函数将输入变量 映射到(0,1)区间上,则可知y=1的概率简单定义为：

(5)

其中x是n维特征向量,g(x)=B0+B1X1+....+BnXn是logistic函数,如图2所示.

图2 logistic函数图Fig.2 Graph of logistic function

则y=0概率为：

p(y=0/x)=1-p(y=1/x)

(6)

经过logit变换后,

(7)

可以看出使用广义线性模型是将非线性回归形式问转化为一个线性回归形式求解.建模学习二分类问题并根据AIC评分准则来选择最优的模型.

3.2 CFS-GA特征选择算法

利用遗传算法进行特征选择时,通常以学习算法的分类精度和选择的特征子集大小作为适应度函数.虽然这种方法在某种程度上是依据GA具有的全局搜索能力找到最优解,但是当数据量较大时它的性能不是很好且复杂度较大.考虑将适应度函数设置成一种过滤型的算法.因此本文应用了CFS-GA特征选择算法对数据进行降维,以简化模型和提高模型的分类精度.该算法中,遗传算法GA将样例的特征子集看作染色体 对其进行二进制编码；利用CFS启发值作为GA的适应度 函数对个体进行评价；CFS值越大的个体遗传到下一代的概率越大.结合GA的全局搜索特性,该算法可保证所得特征子集是全局最优的[17].

CFS是一种过滤式的特征选择算法,其评估方法如下：

(8)

假如有变量X,其可能的取值有n种,每一种取到的概率为Pi,那么X的熵就定义为：

(9)

假设用属性T来划分属性X,计算属性T给X带来的熵值为：

(10)

其中属性T有k个取值,所以特征T给X属性带来的信息增益为：IG(T)=H(X)-H(X|T).信息增益越大,X与T的相关性就越大.

3.3 主成分分析(PCA)

PCA是一种数据降维技术.它的目标是将原始变量重新组合成新的相关性小的综合变量的表示,并使新的变量尽可能多的表达原始的变量信息,所得的相关性较小的综合变量称为主成分.假设将原始变量X1,X2,…,XK通过线性转换变成一组相互无关的变量PC1,PC2,…,PCn,在这种变换中,保持原始变量X1,X2,…,XK的总方差之和不变,则PC1具有最大方差,PC2作为次方差,以此类推,从而得到一组不相关的变量,得到对数据的降维目的.如第一主成分PC1为：

PC1=a1X1+a2X2+…+akXk

(11)

3.4 利用Stacking策略的稳定性分类器组合模型实现

每个基分类器间的训练是相互独立的,利用特征选择算法FCS-GA对数据集降维,然后分别在每个基分类器上训练模型,得到的模型经过Logistic回归模型检验分析,得出各个模型的拟合度检验p值,选择最优的组合模型分类.Stacking组合算法框架如图3所示.

图3 Stacking策略的分类算法组合模型框架Fig.3 Stacking strategy classification algorithm combination model structure

本文利用Stacking策略的分类算法组合模型训练过程如下：

Step1.利用CFS-GA算法对数据集D进行特征选择,去除一些冗余特征和与类别不相关的特征.得到新的数据集D′；

Step2.将数据集D′切分为训练集和测试集,在训练集上利用交叉验证法训练n个基分类器,得到n个模型,作为第二层元分类器的输入样本mod；

D={(xi,yi),i=1,…,m}

mod={fi(x),j=1,…,N}

mod=(mod1,…,modn)

Step3.利用数据预处理技术主成分分析法(PCA)对输入样本集models进行降维处理；

Step4.使用处理后的样本集训练元分类器,通过交叉验证法选择合适的参数,得到最终的分类结果.

Step5.在测试集上测试组合分类模型.

4 实验分析

本文在PC机(CPU为2.5GHz ,内存为4.0GB)上,基于weka平台的特征选择算法和R语言中的caret软件包进行实验.算法实验数据直接来源于UCI数据库,数据的描述如表1所示.

4.1 实验1

本文利用PCA降维技术处理组合模型的输入样本,即提取与观测变量相关性大的特征进行组合学习.这里以UCI数据集中的皮马印第安人糖尿病数据集为例,首先对组合模型的基分类器性能进行详细分析(这里使用箱线图可视化技术来比较基分类器的性能)如图4所示；然后利用散点图分析法来对比基分类器间的相关性如图5所示.从而为模型的选择提供了一个可靠的方案.

表1 实验数据集Table 1 Experimental data sets

图4 基分类器的分类性能对比Fig.4 Comparison of classification performance of base classifiers

在一定程度上分类器的选择是分类器组合模型的关键之一.基分类器的精度过高或者过低都会影响组合模型的分类性能.从图4可以看出所选的基分类器间的分类精度相差不大.没有表现特好或者特差的分类器,这在一定程度上保证了组合模型的性能不会是因为基分类器的差异性而导致的分类性能降低的问题.

图5 基分类器间的相关性分析Fig.5 Correlation analysis among base classifiers

从图5基分类器间的相关性分析图可以看出GLM和LDA间的相关性较大,其他几个分类器的相关性较小,PCA处理是依据相关性大小来提取主成分,将相关性较大的因素删除,提取相关性较小的因素.因此PCA在数据集Diabetes上的主成分提取数为3(训练得到的基分类器数是4个).表2描述了FCS-GA特征选择算法和PCA提取的主成分数的结果.其中FCA-GA算法是基于weka平台进行实验.

表2 特征处理的结果Table 2 Result of feature processing

4.2 实验2

实验1给出了基分类器与特征选择算法的关系,实验采用表1的公共数据集,在R语言环境下编程.与单个的分类算法(CART、KNN、SVM、LDA、GLM)和集成算法(AdaBoost、C50、Bagging、RF)以及文献[10]和文献[11]的算法进行分类精度的对比,实验结果如表3所示.

表3 分类器间的分类精度对比Table 3 Comparison of classifier in classification accuracy

从测试结果来看,Ionosphere数据集上预测最佳结果达到约 98%的分类准确率.整体上本文的稳定性分类器组合模型在泛化性能上都要优于单个的稳定性分类器和其他几种集成算法,取得了较好的分类效果.选取四种较简单的分类器组合学习,不管是在算法的分类精度上还是在算法的复杂度上都要优于现有的一些集成算法,进一步可以总结出本文提出的基于Stacking策略的稳定性分类器组合模型为二分类问题在分类性能上提出了一个可行的参考方案.

5 结束语

Stacking方法最为一种组合学习方法,相比于Boosting和Bagging组合方法来说,理论的研究较少,由于它在算法上的灵活性和可扩展性较强,因此在各种算法的集成大赛中较受欢迎.大部分研究者主要是通过扰动样本和选取不稳定分类算法来提高组合算法的泛化性能,一般不建议采取稳定性的算法作为基分类器.因此出现了以决策树、神经网络等分类精度高的不稳定性分类算法为基分类器的大量组合算法的研究,而相对于一些稳定性分类算法的组合就相对来说较少且改善效果有限,而且分类效果一般在二分类的问题上就表现不是很好.

因此本文提出用Stacking方法来提高一些在模型的组合中不常采用作为基分类器、比较稳定的、简单速度快的分类算法进行组合学习,结果验证它在二分类问题上取得了较好分类效果.下一步的工作是在本文算法的基础上拓展到多分类任务中,能够在多分类认为中达到较好的表现.