基于GASEN技术的选择性BagBoosting Trees集成学习研究，本文主要内容关键词为：选择性论文,技术论文,GASEN论文,BagBoosting论文,Trees论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
引言
著名统计学家C.R.Rao曾多次指出，统计的未来在于数据挖掘。作为数据挖掘技术在统计学中的一个新的研究热点，机器学习中的集成学习日益得到统计学界广泛的关注。早在1997年，国际机器学习界的权威T.G.Dietterich就将集成学习列为机器学习四大研究方向之首（注：机器学习的研究主要分为四个大方向：通过集成学习方法提高学习精度、扩大学习规模、强化学习和学习复杂的随机模型。）[1]。现在已经有很多集成学习算法，比如：Bagging[2]算法、Boosting[3]算法、Arcing[4]算法、Random Forest[5]法、GASEN[6]算法等等。
集成学习的思路是通过对原始数据集进行自助法重采样(bootstrap)，生成多个基学习器（注：集成学习器中的每一个构成部分我们可以将其称为基学习器。基学习器可以为神经网络、决策树等学习器。本文所用的基学习器是指决策树中的一种——分类回归树(CART)。），把这些基学习器集成起来，通过对多个基学习器的学习结果进行某种组合来决定最终的分类或回归结果，以取得比单个基学习器更好的性能。如果把单个基学习器比作一个决策者，集成学习的方法就相当于多个决策者共同进行一项决策。
在本文中，笔者提出了一种新的选择性集成学习算法，并将其命名为SE-BagBoosting Trees算法。该算法综合了Bagging算法和Boosting算法的优点，其基本思想是在原始数据的每一个自助数据集中利用Boosting方法构建比简单Bagging方法更好的分类回归树，再利用GASEN算法对这些分类回归树进行有选择的参与集成，以达到从一些优秀的基学习器中选择更优秀的基学习器进行集成的目的。实验数据分析结果表明，该算法与其他集成算法相比，具有更小的模型推广误差，且算法运行结果较稳定。
一、相关理论与算法简介
（一）Bootstrap技术简介
Bootstrap方法是一种只依赖于给定的观测信息，而不需要其它假设和增加新的观测的统计推断方法，其系统地提出和完整的介绍应归功于美国统计学家Efron[7]。Bootstrap方法处理的就是实际中可能发生的，只能获得少量样本的统计估计，以此模拟大样本进行统计量估计。它是以原始数据为基础的模拟抽样统计推断方法，通过重采样来扩充样本容量，从而得到样本序列统计量值的经验分布。可用于研究一组数据的某统计量的分布特征，特别适用于那些难以用常规方法导出对参数的区间估计、假设检验等问题，小样本序列的统计指标如均值、方差等统计指标都可以用Bootstrap方法得到。
Bootstrap方法的基本原理很简单。考虑来自一个完全不确定分布P的长度为n的随机采样序列
（二）分类回归树算法简介
分类回归树(CART)[8]是机器学习中的一种分类和回归算法。在分类回归树下面有两个关键的思想。一是关于递归地划分自变量空间的想法；二是用验证数据进行剪枝。
很明显，这个递归划分过程不可能无限进行下去，否则最终每一个矩形中仅包含一条样本记录，这就是“过拟合”现象。所以在CART形成过程中第二个关键的思想是用独立的验证数据集（测试数据集）对根据训练集生长的树进行剪枝，即确定在什么时候停止递归划分过程。通常CART采取的策略是增长一棵较大的树
，仅当达到最小节点大小（比如5）时才停止分裂过程。然后利用代价复杂性准则来修剪这棵较大的树，从而将一些噪声和干扰数据排除，获得最优树。
（三）Boosting和Bagging集成学习算法简介
长久以来，人们一直在研究弱学习算法与强学习算法等价性的问题。如果两者等价，那么在学习概念时，只要找到一个比随机猜测略好的弱学习算法，就可以将其提升为强学习算法，而不必直接去找通常情况下很难获得的强学习算法。
Boosting（注：Boosting方法常被人称为“提升法”或“助推法”。）就是一种用来提高学习算法准确度的方法，这种方法通过构造一个预测函数序列，以一定的方式将它们组合成一个预测函数，达到把一弱学习算法提升为强学习算法的目的。当Boosting用于分类问题时，具体实施过程为；首先给每一个训练样例赋予相同的权重，然后训练第一个基本分类器并用它来对训练集进行测试，对于那些分类错误的测试样例提高其权重（实际算法中是降低分类正确的样例的权重），然后用调整后的带权训练集训练第二个基本分类器，重复这个过程直到最后得到一个足够好的学习器。应用于分类问题的Boosting类算法有很多种，其中最常用的一种是AdaBoost算法。
当其用于回归分析时，并不需要构造一个拟合精度高、预测能力好的回归算法，只要一个效果只比随机猜测略好的粗糙算法即可，称之为基础算法。通过不断地调用这个基础算法就可以获得一个拟合和预测误差都相当好的组合回归模型。Boosting算法可以应用于任何基础回归算法，无论是线性回归、神经网络，还是SVM方法，都可以有效地提高精度。因此，Boosting可以被视为一种通用的增强基础算法性能的回归分析算法。应用于回归问题的Boosting类算法也有很多种，其中最常用是基于平方误差损失函数的
-Boosting算法。
Bagging算法是Bootstrap Aggregating的缩写，又被称为“自助聚集”，是Breiman提出的与Boosting相似的技术。Bagging技术的主要思想是给定一弱学习算法和一训练集
。让该学习算法训练多轮，每轮的训练集由从初始的训练集中随机取出的n个训练例组成，初始训练例在某轮训练集中可以出现多次或根本不出现。对每个训练集构建一个学习器
，称为基学习器，最后组合所有的(i=1，…，M)，得到最终的预测模型H。最终的预测模型H对分类问题采用投票方式，分类结果是所有基学习器“投票”类别出现最多的那一类；对于回归问题，取所有基学习器预测结果的简单平均值。
（四）选择性集成学习算法简介
集成学习算法通常是对所有的个体学习器进行组合，但Zhou等人[6]提出了“选择性集成(Selective Ensemble)”算法，并从理论上证明了在执行分类或回归任务时，当训练出多个学习器之后，从中选择一部分进行集成，比使用所有学习器进行集成更好。
假设已经独立训练出M个基学习器
，要求从中选择的一个子集S，使得由S中的基学习器组成的集成具有最好的推广性能。有很多方法可以实现基学习器的选择。例如，可以生成的所有子集（除了空集外，一共
个），计算所有这些子集对应的基学习器集成在测试集上的推广误差，然后选择推广误差最小的那个集合。当M不大时，这种方法很容易实现并且能够得到最优解，但是当M较大时（如M＞30），该方法的复杂度太大；还可以使用贪婪算法，最初集合中仅包含在测试集上推广误差最小的那个基学习器，然后每次加入一个基学习器，使得与集合对应的集成在测试集上的误差不断降低，直到加入任何基学习器都不能降低组合集成的误差为止。贪婪算法的计算复杂度较小，但是通常贪婪算法不能得到最优解，很多时候贪婪算法得到的解甚至与最优解相差较大；目前最常用的选择性集成学习算法是Zhou等人[6]提出的基于遗传算法的选择性集成—GASEN算法。该算法令基学习器集成的规模（集成中基学习器的个数）为M，即每个遗传个体的编码长度为M，若编码的某位为1，则表示与其对应的基学习器参与集成；为0，则表示不参与集成。然后利用遗传算法在选择、杂交和变异等遗传算子的作用下通过对编码群体的进化来获取对现实问题的较优解。
二、SE-BagSoosting Trees算法简介及实现步骤
以往研究表明，Bagging算法主要减小方差，而Boosting算法主要减小偏差。那么可以给我们一个启发，能否设计一种算法，它既具有Boosting算法减小偏差的优点，也同时具有Bagging算法减小方差的优点。实际上，在2004年，Marcel Dettling提出了一种综合了Boosting算法和Bagging算法各自优点的组合算法—BagBoosting算法[9]，其基本思想是Boosting的对象一基学习器，不再是一棵CART，而是由Bagging算法自助聚合后的一批CART，通过对这一批CART进行“提升”。在本文中，笔者提出了另一种思路，即先利用Boosting方法对每一个自助数据集上形成的单棵CART进行“提升”，再利用GASEN方法将这些“提升”后的CART进行有选择的集成。简言之，就是在每一个自助数据集中利用Boosting方法去构建比简单Bagging方法更好的CART，再从中选择一批更优秀的CART进行集成。笔者将这种算法称之为SE-BagBoosting Trees算法。
本文提出的SE-BagBoosting Trees算法既可以用于回归问题也可以用于分类问题的研究，如果利用AdaBoost技术对CART进行提升，则是应用于分类问题；如果采用的是-Boosting对CART进行提升，则是应用于回归问题。限于篇幅，这里仅介绍该算法应用于回归问题的情况，分类问题的研究过程也类似。
该算法首先将原始数据集拆分为训练集和测试集两个部分。通过对训练集进行自助法重抽样可生成M个自助数据集，然后在每一个自助数据集上利用-Boosting算法分别构建基学习器—
(i=1，2，…，M)，再利用GASEN算法从中选择出较优秀的m棵CART进行集成。因为这里指的是回归问题，对于第n条记录，最终输出结果为组合这m棵CART预测的简单平均值，即：
。
三、实验设计
（一）实验数据说明
本节回归案例所使用数据集为3个模拟函数数据集和3个实际数据集。三个模拟函数数据集分别为Friedman#1、Friedman#2、Friedman#3。他们都是合成数据集[10]，经常被用于回归案例的研究与分析，作为评价回归模型性能的典型数据集。详见表1。
表1 模拟函数数据集基本信息概要
3个实际数据集分别为Boston Housing、Ozone、Algae。其中Boston Housing、Ozone均来自加州大学厄文分校(UCI)的机器学习库中，也是经常被用于评价回归模型性能的典型数据集。Algae是一个关于海藻繁殖数据集。共包含340个水样，删除两条包含过多缺失数据的水样后分为训练集和测试集（注：原始数据可以从http://www.liacc.up.pt/%7Eltorgo/DataMiningWithR／处获取。）。表2列出了这3个实际数据集的信息概要。
表2 实际数据集基本信息概要
数据集
训练集 测试集 预测变量 因变量
Boston Housing406 100
11
1
Ozone 264 669
1
Algae 270 68
11
1
（二）研究目的
通过运用CART、Boosting Tree、Bagging Trees、Random Forest、SE-BagBoosting Trees等算法对以上数据进行分析处理，从而比较各算法对于这些数据集处理效果的好坏。
（三）实验分析过程及结果
通过R语言编程，笔者选择了CART、Boosting Tree、Bagging Trees、Random Forest、SE-BagBoosting Trees等算法对以上数据进行分析处理，对于如Bagging Trees等集成学习算法，为克服一次结果的随机性，笔者采取了重复以上学习过程50次，取50次的平均结果作为最终的预测输出的方式。它们的预测精度（注：事实上，评价模型的效果和预测精度的指标有很多，比如AIC、SC、拟合优度等等，但在机器学习中，由于要拆分为训练集和测试集两个部分，所以笔者采用1-NMSE作为模型的评价标准，它的值越大说明预测精度越高。这也是统计学家Luis Torgo常采用的一个评价模型在测试集上的预测精度的指标。）比较见表3。
由表3可知，SE-BagBoosting Trees算法与其它算法相比，预测精度有一定的提高，尤其是要优于简单的Bagging Trees和Boosting Trees算法，且算法较稳定，在训练集和测试集上的预测精度相差不大。而且它与Random Forest算法相比，预测效果差别不大，同时在某些数据集上的运行效果要优于Random Forest算法，且SE-BagBoosting Trees算法集成所需要的树学习器的个数远远小于Random Forest算法构建时所需要的树学习器个数，所以说，SE-BagBoosting Trees算法运行时间要短于Random Forest算法，这一点在大数据集上尤能体现出来，即SE-BagBoosting Trees算法运行效率得到了较大的提高。
四、结束语
本文提出的SE-BagBoosting Trees算法可以看作是一类算法建模文化，它是一种综合了Boosting和Bagging算法各自特点的选择性集成学习算法。它利用Boosting技术在每一个自动数据集上构建一棵较优秀的树，然后再利用GASEN算法进行选择性集成。从实践运行来看，它对一些数据的处理要优于简单的Bagging和Boosting算法。
表3 SE-BagBoosting Trees及其它算法在各数据集上的预测效果比较
