选择性集成算法综述

选择性集成算法综述

1选择性集成算法集成学习，获取训练样本的各种分类器（称为基分类器），然后以不同的方式组合这些分类器，以解决相同的学习任务。集成学习过程可分为两大阶段,一是构造基分类器,二是对这些基分类器的预测结果进行组合。相对于单个分类器,集成学习有效地提高了分类器的泛化能力。选择性集成(EnsemblePruning)是在集成学习的基分类器构造和分类器组合之间又增加了一个阶段,即分类器选择阶段。选择性集成具有两个方面的优越性:(1)提高泛化能力:通过剔除对集成分类器的预测能力具有负面影响的基分类器,进一步提高预测性能;(2)降低预测阶段的开销:去掉冗余基分类器以减少集成分类器的存储空间、降低预测运算量、加快预测速度。本文对选择性集成算法的分类进行了介绍,并根据选择策略将已有的选择性集成算法分为四类,最后从预测精度、分类器选择时间、目标集成分类器大小三个方面对各类典型算法进行了比较分析。文章的结构如下:第2节介绍选择性集成算法分类以及典型的选择性集成算法;第3节对实验结果进行比较分析;最后总结全文,并展望了未来这一方向的研究重点。2选择性集成方法根据不同的分类标准,可将选择性集成算法分为不同的几类。主要的分类方法有如下三种:(1)根据基分类器的选择时机的不同,可分为静态法和动态法。静态法是利用一个校验样本集来计算最佳的基分类器集合,该基分类器集合将持续用于对新样本的预测。动态法是在预测新样本类别时才进行分类器选择,选择的依据是新样本的属性特征以及基分类器在训练时的表现,每个新样本所选的基分类器集合可能互不相同。目前选择性集成方法的研究多集中在静态方法上。(2)根据选择过程中对集成分类器的度量标准的不同,可分为基于预测精度的方法和基于多样性的方法。预测精度度量包括基分类器的预测准确度及其变体,而多样性度量的目的则是发现和利用分类器之间的互补性,从而间接地提升集成预测性能。(3)根据算法采用的选择策略,可将选择性集成方法分为四类:迭代优化法、排名法、分簇法、模式挖掘法。下面对第三种划分进行详细介绍。2.1选择性集成算法给定一个度量准则(例如集成分类器在校验样本集上的预测精度),选择性集成的目的是找到一个基分类器集合,使得该度量的值最优。分类器的选择过程是一个组合优化问题,如采用穷举法则存在组合爆炸问题,因此研究者们将选择性集成问题转换为逐步求优问题,以便在较短的时间内获得问题的近似最优解。迭代优化方法涵盖了一大批选择性集成算法,这类方法的核心是问题的映射,即如何将分类器选择问题表示为相应的优化问题。迭代优化法需要引入某一优化处理过程,例如GASEN算法利用遗传算法来进化一组与分类器对应的权重向量,目标是使得集成分类器对校验样本集的预测精度最优。EPRL算法利用强化学习的方法获得一个最优的决策函数,同时将该函数作为启发式来指导搜索过程的进行。SDP算法利用数学变换将选择性集成转化为二次整数规划问题,并利用整数规划法求得近似最优的基分类器集合。受限于优化方法的特性,这些选择性集成算法的收敛速度均较慢。爬山法也将选择性集成看作是一个逐步求优的搜索过程,不过它每一次搜索都是建立在对前一次搜索评估的基础之上,因此它的搜索空间可以迅速减小,速度大为提高。爬山法根据搜索的方向分为前向选择(ForwardSelection,简称FS)和向后消除(BackwardElimination)两种。爬山法的关键在于评估标准的确定。由于爬山法思想简单,速度较快,因此得到了广泛的关注。2.2基于集体性和排次性的选择性集成算法排名法采用特定函数对所有基分类器进行评估并排序,然后按照该次序选择基分类器。排名法的最大优势在于分类器选择速度快,该类方法涵盖的选择性集成算法较多,其中方向排序(OrientedOrder,简称OO)、边界距离最小化(MarginDistanceMinimization,简称MDSQ)这两种算法在预测性能和选择速度方面均位居列。其他基于排名法的选择性集成算法还有Kappa算法、基于Boosting的选择性集成法等。排名法的关键是采用何种标准对各基分类器进行评估,即所使用的排序标准。早期的算法大都是基于预测性能以及源于信息论的各种统计量,但是实验证明:个体基分类器预测性能好并不能保证集成分类器也具有较好的预测性能,因此目前许多基于排名的算法都是通过分析分类器之间的相关性,使得所选的基分类器具有互补性,从而避免它们的优势互相抵消。排名法的另一个重要问题是如何确定最终获得的目标集成分类器的大小。最简单的方法是预设目标集成分类器的大小或基分类器数目占总数的百分比;另一种方法是设定基于精度或其他度量的阈值,只有达到该阈值的基分类器才能入选。为了避免主观性,需要针对具体问题利用实验分析设定相关参数的预定值。2.3分间器选择方法分簇法(CPF)一般包含两个阶段:首先根据某个聚类算法将相似的基分类器分在一个簇,然后在每个簇内部进行分类器选择。该类方法的目的是利用簇来保持基分类器的多样性,并利用簇内选择来剔除冗余分类器。分簇法首先需要对基分类器进行分簇,可以采用传统的聚类分析算法,例如分层聚类法、k-means以及确定性退火(DeterministicAnnealing)等;然后进行簇内的分类器选择,这一阶段可以使用其他的选择性集成方法,如排名法。簇内分类器选择和单独的选择性集成的主要区别是:由于已经利用分簇保持了分类器的多样性,所以簇内的选择不必考虑基分类器的多样性,从而可以采用较为积极的选择方法,尽量减少每个簇内的冗余分类器数目。基于分簇的方法还需要考虑的问题有:(1)确定簇的数目,这与具体问题密切相关,通常需要对实际问题进行分析获得;(2)确定分簇时使用的距离度量,通常可使用欧氏距离、多样性度量等。2.4选择选择性集成的基本单位这类方法是将各基分类器对校验样本集的预测结果表示为事务数据库的形式,即每个基分类器被看作是事务中的一个项;然后通过对事务数据库进行模式挖掘从而获得若干模式的集合,该集合即被用作选择性集成的基本单位,从而获得速度和预测性能两方面的优势。这类方法的关键是模式挖掘算法的设计。PMEP是本类最具代表性的算法,该算法采用多数投票法确定候选基分类器,并利用著名的FP-Tree数据结构进行模式挖掘和预测结果保存,获得了很好的预测性能。模式挖掘法将事务处理的技术用于选择性集成,是一种全新的选择策略,目前这一方向的研究刚刚展开,在事务数据库的生成、模式挖掘方法上有较大的研究空间。3算法对比的算法下面我们从预测性能、选择时间、集成分类器大小三个方面对典型的选择性集成算法进行对比。参与对比的算法包括GASEN、FS、OO、MDSQ、CPF、PMEP、Select-Best(SelB)和Bagging。实验中,我们使用了UCI机器学习数据库中20个来自不同领域的数据集。3.1svm-pcr扩增能力实验采用十次交叉验证的方法。为了充分验证各算法的性能,实验采用了四种异构的基分类器,所生成基分类器中有40个BPNN神经网络,20个C4.5决策树,20个简单贝叶斯,20个SVM支持向量机。3.2选择性集成算法的预测性能从表1可以看出,SelB的结果表明选择单个最优基分类器极有可能出现过适应问题。Bagging的结果说明在绝大多数情况下集成学习的性能优于单个分类器,同时也可能表明基分类器相关性强或是性能较差会对集成分类器的预测性能有较大影响。其他六种选择性集成算法的实验结果再次验证了选择性集成能够提高集成分类器的泛化能力。GASEN算法的性能相对不佳,我们认为其主要原因在于GASEN终止条件的确定相对困难,从而难以达到全局最优。CPF利用分簇思想引入了多样性的考虑,其存在的问题是即使性能较差的基分类器,由于其差异性较高,也可能被选入到目标集成分类器。FS算法以预测精度作为度量标准进行贪婪式选择,OO算法以基分类器签名向量与参考向量间的角度进行排序,它们均获得较好的预测性能。MDSQ和PMEP是最近提出的新算法,这两种算法均综合考虑了基分类器的预测精度和多样性,并获得了优异的性能。3.3.算法的速度比较从表2的左半部分可以看出,OO算法的分类器选择时间最短,时间均值也最优。GASEN和FS由于在每次迭代中都需要重新合并分类器的预测结果,因此它们的速度最慢,其中GASEN采用了遗传算法,搜索空间很大,是最耗时的算法。OO和MDSQ都是基于排名的算法,不必考虑预测结果的合并,选择速度相对于基分类器的数目是线性变化的,因此它们的速度最快。CPF和PMEP的选择速度明显优于GASEN和FS,比OO和MDSQ稍差。3.4cpf算法的特点从表2右半部分中可以看出,GASEN、FS和PMEP的目标集成分类器均很小,其基分类器均不到原始基分类器的1/10,这是由于上述算法中都有灵活的中止条件来适应数据集的特点。CPF算法获得的目标集成分类器最大,约为原始基分类器数目的30%,主要原因是CPF算法在进行簇内分类器剪除时,由于无法辨别预测性能最优的若干基分类器之间的差别,而将它们全部保留。OO和MDSQ算法选择的基分类器数目约占初始的20%,由于它们属于排名法,本身没有一个很好的确定目标集成分类器大小的方法,因此这两种算法的结果集成分类器较大。3.5选择性集成的实验结果我们的实验结果表明,对于大多数分类问题,选择性集成的预测准确度都优于Bagging,而且选择性集成可以大幅度删除对预测能力没有贡献的基分类器,使得预测阶段的性能大大提高。因此,表1和表2的实验结果充分验证了选择性集成的优势。结合表1和表2的结果,我们从算法类别、算法实现难易、预测性能、分类器选择速度、目标集成分类器大小等方面对上述算法进行综合比较,结果如表3所示。比较结果表明,在实际应用中,为了提高预测精度,选择性集成算法是一个很好的选择,对于预测时间要求不高的领域,可优选MDSQ算法,如果对预测时间要求较高,则可优选PMEP算法。4关于选择性集成的研究重点本文从分类器选择策略的角度将目前已有的选择性集成算法分为四类:迭代优化法、排名法、分簇法、模式挖掘法,最后通过实验对这些典型算法的预测精度、分类器选择时间、目标集成分类器大小进行比较。结果表明,MDSQ和PMEP算法的精度最佳,分类器选择时间也较少。由于PMEP的目标集成分类器比较小,更适合于对预测实时性要求高的应用领域。目前,选择性集成还存在许多问题等待研究与探讨,我们总结了如下四个研究重点:(1)在选择性集成算法的研究方面,将多样性和预