Boosting学习笔记（Adboost、GBDT、Xgboost）

向右看齐 2022-04-16 02:27 165阅读 0赞

转载出处：[http://www.cnblogs.com/willnote/p/6801496.html][http_www.cnblogs.com_willnote_p_6801496.html]

## 前言 ##

本文为学习boosting时整理的笔记，全文主要包括以下几个部分：

*  对集成学习进行了简要的说明
 *  给出了一个Adboost的具体实例
 *  对Adboost的原理与学习过程进行了推导
 *  针对GBDT的学习过程进行了简要介绍
 *  针对Xgboost的损失函数进行了简要介绍
 *  给出了Adboost实例在代码上的简单实现

文中的内容是我在学习boosting时整理的资料与理解，如果有错误的地方请及时指出，谢谢。

## 集成学习 ##

集成学习通过构建并结合多个学习器来完成学习任务，有时也被称为多分类器系统、基于委员会的学习等。集成学习通过将多个学习器进行结合，常可获得比单一学习器显著优越的泛化性能。下面从两个方面对集成学习进行简要介绍。

*  分类  
    根据个体学习器的生成方式，目前的集成学习方法大致可以分为两大类，即个体学习器间存在强依赖关系、必须串行生成的序列化方法，以及个体学习器间不存在强依赖关系、可同时生成的并行化方法；前者的代表是Boosting，后者的代表是Bagging和随机森林。
 *  结合策略  
    对于基分类器最终的结合策略常见的方法有如下几种：
    
     *  平均法  
        对于数值形输出，最常见的结合策略即为平均法：
        
         
        
        H(x)=1T∑i=1Thi(x)H(x)=1T∑i=1Thi(x)
        
          
        其中hi(x)hi(x)为基学习器的输出结果，H(x)H(x)为最终学习器的结果，TT为基学习器的个数。
     *  加权平均法
        
         
        
        H(x)=∑i=1Twihi(x)H(x)=∑i=1Twihi(x)
        
          
        其中wiwi是个体学习器hihi的权重，通常要求wi⩾0,∑Ti=1wi=1wi⩾0,∑i=1Twi=1。显然，简单平均法是加权平均法令wi=1/Twi=1/T的特例。
     *  投票法  
        预测结果为得票最多的标记，若同时有多个标记获得相同的票数，则从中随机选取一个。
     *  学习法  
        当训练数据很多时，可以通过另一个学习器来对所有基学习器产生结果的结合方法进行学习，这时候个体学习器称为初级学习器，用于结合的学习器成为次级学习器或元学习器。

## Adaboost ##

### 思想 ###

AdaBoost是最著名的Boosting族算法。开始时，所有样本的权重相同，训练得到第一个基分类器。从第二轮开始，每轮开始前都先根据上一轮基分类器的分类效果调整每个样本的权重，上一轮分错的样本权重提高，分对的样本权重降低。之后根据新得到样本的权重指导本轮中的基分类器训练，即在考虑样本不同权重的情况下得到本轮错误率最低的基分类器。重复以上步骤直至训练到约定的轮数结束，每一轮训练得到一个基分类器。

可以想象到，远离边界（超平面）的样本点总是分类正确，而分类边界附近的样本点总是有大概率被弱分类器（基分类器）分错，所以权值会变高，即边界附近的样本点会在分类时得到更多的重视。

### 举例 ###

为了防止看到公式推导你(wo)就(zao)要(pao)跑(le)，我们先来通过例子让你明白AdaBoost的运作方式，这样从整体框架上有个印象，之后再进行公式的推导。例子所用的代码在文章最后给出。

首先对一些符号进行约定：

<table> 
 <thead> 
  <tr> 
   <th>符号</th> 
   <th>含义</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>D={(xi→,yi),&nbsp;i∈[1,m]}D={(xi→,yi),&nbsp;i∈[1,m]}</td> 
   <td>训练集，共m个样本</td> 
  </tr> 
  <tr> 
   <td>TT</td> 
   <td>训练轮数</td> 
  </tr> 
  <tr> 
   <td>Dt(x)Dt(x)</td> 
   <td>第tt轮时样本的权重分布</td> 
  </tr> 
  <tr> 
   <td>htht</td> 
   <td>第tt轮得到的基分类器</td> 
  </tr> 
  <tr> 
   <td>αtαt</td> 
   <td>第tt轮得到的基分类器的权重</td> 
  </tr> 
  <tr> 
   <td>ϵtϵt</td> 
   <td>第tt轮htht的错误率</td> 
  </tr> 
  <tr> 
   <td>PA(D)PA(D)</td> 
   <td>强分类器AA在数据集DD上的最终准确率</td> 
  </tr> 
 </tbody> 
</table>

接下来，给定下边的数据集DD，我们用AdaBoost算法来学习得到一个强分类器

数据集DD共有10条数据，根据x的输入得到的y可以分类两类，即y=1与y=-1。我们每一轮使用最简单的决策树桩来构建基分类器，即每轮设定一个阈值θθ，只要x<θx<θ，就判定为正类(y=1)，x>θx>θ就判定为负类(y=-1)。

第一轮

*  D1(x)D1(x)  
    因为是第一轮，故所有样本的权重相同：
    
     
    
    D1(x⃗ )=\{110,110,110,110,110,110,110,110,110,110\}D1(x→)=\{110,110,110,110,110,110,110,110,110,110\}
 *  θθ  
    因为是离散数据，所以θθ可以依次取0.5，1.5，2.5，...，8.5来对x进行分类，这里可以有两种分类方法：
    
     *  x<θx<θ时分为正类，x>θx>θ时分为负类，分类错误率对应ϵ1tϵt1
     *  x>θx>θ时分为正类，x<θx<θ时分为负类，分类错误率对应ϵ2tϵt2
    
    最终要选择一个令ϵ1ϵ1取得最小值的θθ与分类方法，这9个值在两种分类方法下，此层h1h1的错误率ϵ1→ϵ1→分别为：
    
     
    
    ϵ11→=\{0.5∗110,0.4∗110,0.3∗110,0.4∗110,0.5∗110,0.6∗110,0.5∗110,0.4∗110,0.3∗110\}ϵ21→=\{0.5∗110,0.6∗110,0.7∗110,0.6∗110,0.5∗110,0.4∗110,0.5∗110,0.6∗110,0.7∗110\}ϵ11→=\{0.5∗110,0.4∗110,0.3∗110,0.4∗110,0.5∗110,0.6∗110,0.5∗110,0.4∗110,0.3∗110\}ϵ12→=\{0.5∗110,0.6∗110,0.7∗110,0.6∗110,0.5∗110,0.4∗110,0.5∗110,0.6∗110,0.7∗110\}
    
      
    可以看到ϵ11→ϵ11→中的0.3∗1100.3∗110为最小值。对应的，我们取θθ为2.5（θθ为8.5亦可），使用第一种分类方法。则x为0，1，2的样本分为正类，都分对了；而之后的样本都被分为负类，分错了3个，所以总错误率为3∗1103∗110。故此轮弱分类器的阈值θθ取2.5，分类方法取第一种。
 *  α1α1  
    第一层基分类器h1h1的权重α1α1的计算推到方法后面的推导部分再细说，此处只要知道通过如下的公式来计算即可：
    
     
    
    α1=12log1−ϵ1ϵ1=0.4236α1=12log1−ϵ1ϵ1=0.4236
 *  H(x),PA(D)H(x),PA(D)  
    根据如下公式计算H(x)H(x)，此时TT为1：
    
     
    
    H(x)=∑t=1Tαtht(x)H(x)=\{0.424,0.424,0.424,−0.424,−0.424,−0.424,−0.424,−0.424,−0.424,−0.424\}sign(H(x))=\{1,1,1,−1,−1,−1,−1,−1,−1,−1\}H(x)=∑t=1Tαtht(x)H(x)=\{0.424,0.424,0.424,−0.424,−0.424,−0.424,−0.424,−0.424,−0.424,−0.424\}sign(H(x))=\{1,1,1,−1,−1,−1,−1,−1,−1,−1\}
    
      
    整个模型（现在只有一个基分类器）的准确率为：
    
    PA(D)=0.7PA(D)=0.7

至此第一轮的工作就结束了，可以看出被误分类样本的权值之和影响误差率，误差率影响基分类器在最终分类器中所占的权重。

第二轮

*  D2(x)D2(x)  
    第一轮训练完成后对D1(x)D1(x)进行更新得到D2(x)D2(x)，更新公式的推导过程也是等到后边的推到部分再说，此处还是只要知道通过下边的公式来计算更新即可：
    
     
    
    D2(x)=D1(x)e−α1y(x)h1(x)Z1D2(x)=D1(x)e−α1y(x)h1(x)Z1
    
     
    
    D2(x)=\{0.071,0.071,0.071,0.071,0.071,0.071,0.167,0.167,0.167,0.071\}D2(x)=\{0.071,0.071,0.071,0.071,0.071,0.071,0.167,0.167,0.167,0.071\}
    
      
    上一轮中x=6、7、8的点分错了，可以看到这三个点在D2D2中的权重变大了，而其余分类正确的点权重变小了。
 *  θθ  
    我们依然对θθ依次取0.5, 1.5, ... , 8.5来对x进行分类，注意我们刚才已经得到了D2(x)D2(x)，样本权重的分布不再是第一轮全部相等的110110了，如当θθ取0.5按第一种分类方法进行分类时，ϵ12ϵ21计算方法如下：
    
     
    
    ϵ12(θ=0.5)=0∗0.071+1∗0.071+1∗0.071+0∗0.071+0∗0.071+0∗0.071+1∗0.167+1∗0.167+1∗0.167+0∗0.071=0.643ϵ21(θ=0.5)=0∗0.071+1∗0.071+1∗0.071+0∗0.071+0∗0.071+0∗0.071+1∗0.167+1∗0.167+1∗0.167+0∗0.071=0.643
    
      
    对所有θθ与分类方法都按照如上的步骤进行计算，则可得到ϵ12→ϵ21→与ϵ22→ϵ22→分别为：
    
    ϵ12→=\{0.643,0.571,0.5,0.571,0.643,0.714,0.548,0.381,0.214\}ϵ22→=\{0.357,0.429,0.5,0.429,0.357,0.286,0.452,0.619,0.786\}ϵ21→=\{0.643,0.571,0.5,0.571,0.643,0.714,0.548,0.381,0.214\}ϵ22→=\{0.357,0.429,0.5,0.429,0.357,0.286,0.452,0.619,0.786\}
    
      
    可以看到ϵ12→ϵ21→中的0.214为最小值，故此轮弱分类器的阈值θθ取8.5，分类方法为第一种。
 *  α2α2  
    依然使用如下公式进行计算：
    
     
    
    α1=12log1−ϵ2ϵ2=0.6496α1=12log1−ϵ2ϵ2=0.6496
 *  H(x),PA(D)H(x),PA(D)  
    继续根据如下公式计算H(x)H(x)，此时TT为2：
    
     
    
    H(x)=∑t=1Tαtht(x)H(x)=\{1.073,1.073,1.073,0.226,0.226,0.226,0.226,0.226,0.226,−1.073\}sign(H(x))=\{1,1,1,1,1,1,1,1,1,−1\}H(x)=∑t=1Tαtht(x)H(x)=\{1.073,1.073,1.073,0.226,0.226,0.226,0.226,0.226,0.226,−1.073\}sign(H(x))=\{1,1,1,1,1,1,1,1,1,−1\}
    
      
    整个模型（现在有两个基分类器）的准确率仍然为：
    
    PA(D)=0.7PA(D)=0.7

至此第二轮的工作就结束了，下面我们继续使用上边的方式来看第三轮是否能将准确率提升。

第三轮

*  D3(x)D3(x)  
    使用D2(x)D2(x)更新得到D3(x)D3(x)如下：
    
     
    
    D3(x)=\{0.045,0.045,0.045,0.167,0.167,0.167,0.106,0.106,0.106,0.045\}D3(x)=\{0.045,0.045,0.045,0.167,0.167,0.167,0.106,0.106,0.106,0.045\}
    
      
    上一轮中x=3、4、5的点被分错，所以在D3D3中的权重变大，其余分类正确的点权重变小。
 *  θθ  
    继续使用之前的方法得到ϵ13→ϵ31→与ϵ23→ϵ32→分别为：
    
     
    
    ϵ13→=\{0.409,0.364,0.318,0.485,0.652,0.818,0.712,0.606,0.5\}ϵ23→=\{0.591,0.636,0.682,0.515,0.348,0.182,0.288,0.394,0.5\}ϵ31→=\{0.409,0.364,0.318,0.485,0.652,0.818,0.712,0.606,0.5\}ϵ32→=\{0.591,0.636,0.682,0.515,0.348,0.182,0.288,0.394,0.5\}
    
      
    可以看到ϵ23→ϵ32→中的0.182为最小值，故此轮弱分类器的阈值θθ取5.5，分类方法为第二种。
 *  α2α2  
    依然使用如下公式进行计算：
    
     
    
    α1=12log1−ϵ2ϵ2=0.752α1=12log1−ϵ2ϵ2=0.752
 *  H(x),PA(D)H(x),PA(D)  
    继续根据如下公式计算H(x)H(x)，此时TT为3：
    
     
    
    H(x)=∑t=1Tαtht(x)H(x)=\{0.321,0.321,0.321,−0.526,−0.526,−0.526,0.978,0.978,0.978,−0.321\}sign(H(x))=\{1,1,1,−1,−1,−1,1,1,1,−1\}H(x)=∑t=1Tαtht(x)H(x)=\{0.321,0.321,0.321,−0.526,−0.526,−0.526,0.978,0.978,0.978,−0.321\}sign(H(x))=\{1,1,1,−1,−1,−1,1,1,1,−1\}
    
      
    整个模型（现在有三个基分类器）的准确率为：
    
    PA(D)=1PA(D)=1

至此，我们只用了3个弱（基）分类器就在样本集DD上得到了100%的准确率，总结一下：

*  在第tt轮被分错的样本，在下一轮更新得到的Dt+1(x)Dt+1(x)中权值将被增大
 *  在第tt轮被分对的样本，在下一轮更新得到的Dt+1(x)Dt+1(x)中权值将被减小
 *  所使用的决策树桩总是选取让错误率ϵtϵt（所有被htht分类错误的样本在Dt(x)Dt(x)中对应的权值之和）最低的阈值来设计基本分类器
 *  最终Adboost得到的H(x)H(x)为：

sign(H(x))=sign(0.4236∗h1+0.6496∗h2+0.752∗h3)sign(H(x))=sign(0.4236∗h1+0.6496∗h2+0.752∗h3)

其他情况

上边的例子每一轮使用了最简单的决策树桩来得到基分类器，下面就几种常见的其他情况对基分类器的训练过程进行简单介绍，纯粹个人理解，如有错误之处请及时指出。

*  分类问题
    
     *  决策树桩  
        见上例
     *  决策树  
        每一个节点的选择过程都需要将Dt(x)Dt(x)考虑进去，即在定义损失函数的时候，考虑每一个样本被分错的代价（权重）
     *  逻辑回归  
        阈值θθ的选取需令本层ϵtϵt取得最小值
 *  回归问题
    
     *  按照Dt(x)Dt(x)的分布对原始数据集进行重新采样，利用采样后得到的新数据集再进行训练

推导

AdaBoost算法可以认为是一种模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的而分类学习方法。在对αtαt和DtDt进行推导前，我们先对加法模型和前向分步算法进行简要介绍。

*  加法模型  
    加法模型的定义如下：
    
     
    
    f(x)=∑Mm=1βmb(x;γm)f(x)=∑Mm=1βmb(x;γm)
    
      
    其中，b(x;γm)b(x;γm)为基函数，βmβm为基函数的系数，γmγm为基函数的参数。在给定训练数据及损失函数L(y,f(x))L(y,f(x))的条件下，学习加法模型f(x)f(x)成为经验风险极小化，即损失函数极小化的问题：
    
    minβm,γm∑i=1NL(yi,∑Mm=1βmb(x;γm))minβm,γm∑i=1NL(yi,∑Mm=1βmb(x;γm))
    
      
    这通常是一个极其复杂的优化问题，因为需要同时考虑所有基函数与其权重的选取来令目标最小化。
 *  前向分步算法  
    前向分步算法对加法模型的求解思路是：如果能够从前向后，每一步只学习一个基函数及其系数，逐步逼近优化目标，那么就可以简化优化的复杂度。即每步只需优化如下损失函数：
    
     
    
    minβ,γ∑Mm=1L(yi,βb(x;γ))minβ,γ∑Mm=1L(yi,βb(x;γ))
    
      
    这样，前向分步算法将同时求解所有步骤的βmβm、γmγm的优化问题简化为逐次求解各个βmβm、γmγm的优化问题。
 *  αtαt的推导过程  
    AdaBoost算法是前向分布加法算法的特例。这时，模型是由基本分类器组成的加法模型，损失函数是指数函数。即此时的基函数为基分类器。AdaBoost的最终分类器为：
    
     
    
    H(x)=∑t=1Tαtht(x)H(x)=∑t=1Tαtht(x)
    
      
    损失函数为：
    
    L(y,H(x))=e−yH(x)L(y,H(x))=e−yH(x)
    
      
    上式即被称为指数损失函数，其中y是样本的真实类别。假设在第t轮迭代时有：
    
    Ht(x)=Ht−1(x)+αtht(x)Ht(x)=Ht−1(x)+αtht(x)
    
      
    目标是使得到的αtαt和ht(x)ht(x)令L(y,H(x))L(y,H(x))最小，即：
    
    (αt,ht(x))=arg minαt,ht∑i=1Ne−yi(Ht−1(x)+αtht(x))=arg minαt,ht∑i=1Nw¯tie−yiαtht(x)ht(x)∗=arg minht(x)∑i=1Nw¯tiI(yi≠ht(x))(αt,ht(x))=arg minαt,ht∑i=1Ne−yi(Ht−1(x)+αtht(x))=arg minαt,ht∑i=1Nw¯tie−yiαtht(x)ht(x)∗=arg minht(x)∑i=1Nw¯tiI(yi≠ht(x))
    
      
    其中，w¯ti=e−yiHt−1(x)w¯ti=e−yiHt−1(x)。因为w¯tiw¯ti既不依赖于αtαt也不依赖于ht(x)ht(x)，所以与最小化无关。但它依赖于Ht−1(x)Ht−1(x)，会随着每一轮迭代而发生变化。第二个式子为令指数损失函数最小的ht(x)∗ht(x)∗，其中I(⋅)I(⋅)为指示函数，此ht(x)∗ht(x)∗使第m轮加权训练数据分类的误差率得到了最小值。接下来我们对上边的第一个式子的右边进行一下简单变形：
    
    ∑i=1Nw¯tieyiαtht(xi)=∑yi=ht(xi)w¯tie−αt+∑yi≠ht(xi)w¯tieαt=(eαt−e−αt)∑i=1Nw¯tiI(yi≠ht(xi))+e−α∑i=1Nw¯ti∑i=1Nw¯tieyiαtht(xi)=∑yi=ht(xi)w¯tie−αt+∑yi≠ht(xi)w¯tieαt=(eαt−e−αt)∑i=1Nw¯tiI(yi≠ht(xi))+e−α∑i=1Nw¯ti
    
      
    将上式对αtαt求导并令导数为0，即可解得：
    
    α∗t=12log1−etetαt∗=12log1−etet
    
      
    上式即之前例子中所用到的αtαt的更新公式，其中，etet为分类误差率：
    
    et=∑Ni=1w¯tiI(yi≠ht(xi))∑Ni=1w¯ti=∑i=1NwtiI(yi≠ht(xi))et=∑i=1Nw¯tiI(yi≠ht(xi))∑i=1Nw¯ti=∑i=1NwtiI(yi≠ht(xi))
    
      
    由此可知，当et⩽12et⩽12时，αt⩾0αt⩾0，并且αtαt随着etet的减小而增大，所以分类误差率越小的基分类器在最终分类器中的作用越大。
 *  DtDt的推导过程  
    接下来我们对DtDt的更新公式进行推导。由之前推导过程中所得到的下边两个式子：
    
     
    
    Ht(x)=Ht−1(x)+αtht(x)w¯ti=e−yiht(xi)Ht(x)=Ht−1(x)+αtht(x)w¯ti=e−yiht(xi)
    
      
    将第一个式子两边同乘−yi−yi，并作为ee的指数即可得到下一轮w¯t+1,iw¯t+1,i的更新公式：
    
    w¯t+1,i=w¯t,ie−yiαtht(x)w¯t+1,i=w¯t,ie−yiαtht(x)
    
      
    上式再在分母添加一个规范化因子即为例子中所用到的DtDt的更新公式。

总结

在训练过程中，每个新的模型都会基于前一个模型的表现结果进行调整，这也就是为什么AdaBoost是自适应（adaptive）的原因，即AdaBoost可以自动适应每个基学习器的准确率。

### GBDT ###

*  简介  
    GBDT即梯度提升树，提升方法依然采用的是加法模型与前向分布算法。以决策树为基函数的提升方法称为提升树。对分类问题决策树是二叉分类树，对回归问题决策树是二叉决策树。例如前文中的例子中所使用的决策树桩即为一个根节点直接连接两个叶节点的简单决策树。
 *  与Adboost的区别  
    GBDT与Adboost最主要的区别在于两者如何识别模型的问题。Adaboost用错分数据点来识别问题，通过调整错分数据点的权重来改进模型。GBDT通过负梯度来识别问题，通过计算负梯度来改进模型。
 *  学习过程  
    针对不同问题的提升树学习算法，其主要区别在于使用的损失函数不同。包括用平方误差损失函数的回归问题，是指数损失函数的分类问题，以及用一般损失函数的一般决策问题。对于分类问题，GBDT实质是把它转化为回归问题。在多分类问题中，假设有k个类别，那么每一轮迭代实质是构建了k棵树，对某个样本x的预测值为
    
     
    
    f1(x),f2(x),...,fk(x)f1(x),f2(x),...,fk(x)
    
      
    之后使用softmax可以得到属于每一个类别的概率，此时该样本的loss即可以用logitloss来表示，并对所有类别的f(x)都可以算出一个梯度，即可以计算出当前轮的残差，供下一轮迭代学习。下面主要对回归问题的提升树进行说明。
    
    依然采用前向分步算法，过程如下：
    
     
    
    f0(x)=0fm(x)=fm−1(x)+T(x;Θ),m=1,2,...,MfM(x)=∑m=1MT(x;Θm)f0(x)=0fm(x)=fm−1(x)+T(x;Θ),m=1,2,...,MfM(x)=∑m=1MT(x;Θm)
    
      
    第一个式子首先定义初始提升树f0(x)=0f0(x)=0；之后第m步的模型即为第二个式子，其中T(x;Θ)T(x;Θ)表示决策树，ΘΘ为决策树的参数；第三个式子表示GBDM的最终模型，其中M为树的个数。
    
    在前向分步算法的第m步，给定当前模型fm−1(x)fm−1(x)，需求解
    
     
    
    Θ^m=arg minΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm))Θ^m=arg minΘm∑i=1NL(yi,fm−1(xi)+T(xi;Θm))
    
      
    得到的Θ^mΘ^m即为第m颗树的参数。当采用平方误差作为损失函数时：
    
    L(y,f(x))=(y−f(x))2L(y,f(x))=(y−f(x))2
    
      
    带入上式中，则其损失函数变为：
    
    L(y,fm−1(x)+T(x;Θm))=\[y−fm−1(x)−T(x;Θm)\]2=\[r−T(x;Θm)\]2L(y,fm−1(x)+T(x;Θm))=\[y−fm−1(x)−T(x;Θm)\]2=\[r−T(x;Θm)\]2
    
      
    这里
    
    r=y−fm−1(x)r=y−fm−1(x)
    
      
    是当前模型拟合数据的残差。所以，对于回归问题的提升树算法来说，只需简单地拟合当前模型的残差。即每一轮产生的残差作为下一轮回归树的输入，下一轮的回归树的目的就是尽可能的拟合这个输入残差。
 *  举例  
    我们以简单的年龄预测为例，训练集共包括4个人：A,B,C,D，他们的年龄分别是14，16，24，26。每个人都有两个属性：每周的购物金额、每周的上网时间。数据集如下：
    
     *  A：购物金额<=1K，上网时间<=20h
     *  B：购物金额<=1K，上网时间>=20h
     *  C：购物金额>=1K，上网时间<=20h
     *  D：购物金额>=1K，上网时间>=20h
    
    我们的目的就是构建一个GBDT模型来预测年龄。简单起见，我们限定每棵树只有一个分支，如下图所示：![GBDT举例][GBDT]
    
     *  第一轮（树）  
        第一颗树节点属性的选取我们用最小化残差的方法。当选择每周购物金额作为划分属性时，两边叶子节点的残差和为：
        
         
        
        (14−14+162)2+(16−14+162)2+(24−24+262)2+(26−24+262)2=4(14−14+162)2+(16−14+162)2+(24−24+262)2+(26−24+262)2=4
        
          
        当选择上网时间作为划分属性时，得到的残差和为：
        
        (14−14+242)2+(24−14+242)2+(16−16+262)2+(16−16+262)2=100(14−14+242)2+(24−14+242)2+(16−16+262)2+(16−16+262)2=100
        
          
        通过比较上边两种方法，我们选择每周的购物金额作为划分属性，结果如上图左边的树。此时可以看到A、B被划分到了左节点。左节点的均值为(14+16)/2=15，则A的残差为14-15=-1，B的残差为16-15=1，同理可得C和D的残差分别为-1和1。这样当4个样本经过第一颗树后，分别产生的残差为（-1，1，-1，1），这个残差作为第二课树的输入，如上图右边第二颗树的根节点。
     *  第二轮（树）  
        第二颗树的目的是尽量去拟合由第一颗树产生的残差（-1，1，-1，1），特征选取的过程同第一棵树，不再复述。现在我们用每周的上网时间来作为划分的属性，则结果如上图第二颗树。A、C被划分到左节点，B、D被划分到右节点，两个节点的均值分别为-1和1。此时两个子节点的残差都为0，训练结束。
     *  结果  
        不考虑泛化性，我们简单地使用训练集进行测试。  
        A = 15 + (–1) = 14  
        B = 15 + 1 = 16  
        C = 25 + (–1) = 24  
        D = 25 + 1 = 26  
        全部预测正确，厉(fei)害(hua)了我的哥。
 *  总结
    
     *  GBDT每一轮训练时所关注的重点是本轮产生结果的残差，下一轮以本轮残差作为输入，尽量去拟合这个残差，使下一轮输出的残差不断变小。所以GBDT可以做到每一轮一定向损失函数减小的梯度方向变化，而传统的boosting算法只能是尽量向梯度方向减小，这是GBDT与传统boosting算法最大的区别，这也是为什么GBDT相比传统boosting算法可以用更少的树个数与深度达到更好的效果。
     *  和AdaBoost一样，Gradient Boosting也是重复选择一个表现一般的模型并且每次基于先前模型的表现进行调整。不同的是，AdaBoost是通过提升错分数据点的权重来定位模型的不足，而GBDT是通过算梯度来定位模型的不足。因此相比AdaBoost，GBDT可以使用更多种类的目标函数。
     *  抽象地说，模型的训练过程是对一任意可导目标函数的优化过程，通过反复地选择一个指向负梯度方向的函数，该算法可被看作在函数空间里对目标函数进行优化。
     *  回归问题  
        1) 用回归树去拟合残差，其实就是用回归树去拟合目标方程关于f（x）的梯度。  
        2) 回归的目标函数并不一定会用square loss。square loss的优点是便于理解和实现，缺点在于对于异常值它的鲁棒性较差，一个异常值造成的损失由于二次幂而被过分放大，会影响到最后得到模型在测试集上的表现。可以算则Absolute loss或者Huber loss代替。
     *  分类问题  
        1) 此时的目标函数常用log loss，如KL-散度或者交叉熵。  
        2) 除了损失函数的区别外，分类问题和回归问题的区别还在于当多分类问题时，每轮可能会训练多个分类器。
     *  由于决策树是非线性的，并且随着深度的加深，非线性越来越强，所以基于决策树的GBDT也是非线性的。

### xgboost ###

*  简介  
    xgboost 的全称是eXtreme Gradient Boosting，由华盛顿大学的陈天奇博士提出，在Kaggle的希格斯子信号识别竞赛中使用，因其出众的效率与较高的预测准确度而引起了广泛的关注。
 *  与Adboost的区别  
    GBDT算法只利用了一阶的导数信息，xgboost对损失函数做了二阶的泰勒展开，并在目标函数之外加入了正则项对整体求最优解，用以权衡目标函数的下降和模型的复杂程度，避免过拟合。所以不考虑细节方面，两者最大的不同就是目标函数的定义，接下来就着重从xgboost的目标函数定义上来进行介绍。
 *  目标函数  
    xgboost的目标函数定义如下：
    
    Obj(t)=∑i=1nl(yi,y^(t)i)+∑i=1tΩ(fi)=∑i=1nl(yi,y^(t−1)i+ft(xi))+Ω(ft)+constantObj(t)=∑i=1nl(yi,y^i(t))+∑i=1tΩ(fi)=∑i=1nl(yi,y^i(t−1)+ft(xi))+Ω(ft)+constant
    
      
    其中，t表示第t轮，ftft表示第t轮所生成的树模型，Ω(fi)Ω(fi)表示正则项，constant=∑t−1i=1Ω(fi)constant=∑i=1t−1Ω(fi)。接下来是xgboost的重点，我们使用泰勒展开
    
    f(x+△x)≃f(x)+f′(x)△x+12f′′(x)△x2f(x+△x)≃f(x)+f′(x)△x+12f″(x)△x2
    
      
    来定义一个近似的目标函数如下：
    
    Obj(t)≃∑i=1n\[l(yi,y^(t−1)i)+gift(xi)+12hif2t(xi)\]+Ω(ft)+constantgi=∂y^(t−1)l(yi,y^t−1),hi=∂2y^(t−1)l(yi,y^t−1)Obj(t)≃∑i=1n\[l(yi,y^i(t−1))+gift(xi)+12hift2(xi)\]+Ω(ft)+constantgi=∂y^(t−1)l(yi,y^t−1),hi=∂y^(t−1)2l(yi,y^t−1)
    
      
    因为l(yi,y^(t−1)i)l(yi,y^i(t−1))的值由之前的过程决定，所以本轮不变，constantconstant也不影响本轮的训练，所以将这两者其去掉，得到：
    
    Obj(t)≃∑i=1n\[gift(xi)+12hif2t(xi)\]+Ω(ft)Obj(t)≃∑i=1n\[gift(xi)+12hift2(xi)\]+Ω(ft)
    
      
    现在的目标函数有一个非常明显的特点，它只依赖于每个数据点在误差函数上的一阶导数和二阶导数。接下来，我们对ftft的定义做一下细化，将树拆分成结构部分qq和叶子权重部分ww：
    
    ft(x)=wq(x)ft(x)=wq(x)
    
      
    当我们给定了如上定义之后，就可以对树的复杂度Ω(ft)Ω(ft)进行定义了：
    
    Ω(ft)=γT+12λ∑j=1Tw2jΩ(ft)=γT+12λ∑j=1Twj2
    
      
    其中，第一部分中的T为叶子的个数，第二部分为ww的L2模平方。我们来看下图的示例：  
    ![w、q解释][w_q]  
    可以看到叶子的权重ww就是GBDT例子中叶子结点的值，而qq就是将某个样本点映射到某个叶子结点的函数。有了上边的两个式子后，继续对目标函数进行如下改写：
    
    Obj(t)≃∑i=1n\[gift(xi)+12hif2t(xi)\]+Ω(ft)=∑i=1n\[giwq(xi)+12hiw2q(xi)\]+γT+12λ∑j=1Tw2j=∑j=1T\[(∑i⊂Ijgi)wj+12(∑i⊂Ijhi+λ)w2j\]+γTObj(t)≃∑i=1n\[gift(xi)+12hift2(xi)\]+Ω(ft)=∑i=1n\[giwq(xi)+12hiwq2(xi)\]+γT+12λ∑j=1Twj2=∑j=1T\[(∑i⊂Ijgi)wj+12(∑i⊂Ijhi+λ)wj2\]+γT
    
      
    其中，IjIj为每个叶子节点上的样本集合Ij=\{i|q(xi=j\}Ij=\{i|q(xi=j\}。现在这个目标函数包含了T个相互独立的单变量二次函数，我们定义：
    
    Gi=∑i⊂Ijgi, Hj=∑i⊂IjhiGi=∑i⊂Ijgi, Hj=∑i⊂Ijhi
    
      
    那么我们就得到了最终的目标函数样子：
    
    Obj(t)=\[Gjwj+12(Hj+λ)w2j\]+γTObj(t)=\[Gjwj+12(Hj+λ)wj2\]+γT
    
      
    现在我们假设qq已知，通过将上式对ww求导并令其等于0，就可以求出令Obj(t)Obj(t)最小的ww：
    
    w∗j=−GjHj+λwj∗=−GjHj+λ
    
      
    剩下的工作就很简单了，通过改变树的结构来找到最小的w∗jwj∗，而对应的结构就是我们所需要的结果。不过枚举所有树的结构不太可行，所以常用的是贪心法，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的增益可以由如下公式计算：
    
    Gain=12\[G2LHL+λ+G2RHR+λ−G2L+GRHL+HR+λ\]−γGain=12\[GL2HL+λ+GR2HR+λ−GL2+GRHL+HR+λ\]−γ
    
      
    观察这个目标函数会发现如下三点：
    
     *  这个公式形式上跟ID3算法（采用entropy计算增益） 、CART算法（采用gini指数计算增益） 是一致的，都是用分裂后的某种值减去分裂前的某种值，从而得到增益
     *  引入分割不一定会使情况变好，因为最后有一个新叶子的惩罚项。所以这也体现了预减枝的思想，即当引入的分割所带来的增益小于一个阈值时，就剪掉这个分割
     *  上式中还有一个系数λλ，是正则项里ww的L2模平方的系数，对ww做了平滑，也起到了防止过拟合的作用，这个是传统GBDT里不具备的特性
 *  总结  
    xgboost与传统的GBDT相比，对代价函数进行了二阶泰勒展开，同时用到了一阶与二阶导数，而GBDT在优化时只用到一阶导数的信息，个人认为类似牛顿法与梯度下降的区别。另一方面，xgboost在损失函数里加入的正则项可用于控制模型的复杂度。正则项里包含了树的叶子节点个数、每个叶子节点上输出score的L2模的平方和。从Bias-variance tradeoff角度来讲，正则项降低了模型的variance，使学习出来的模型更加简单，防止过拟合，这也是xgboost优于传统GBDT的一个特性。

### 代码 ###

针对上文Adboost中使用决策树桩作为基分类器的例子写了一个简单实现，类Adboost中的方法\_\_get\_decision\_stump()为决策树桩，大家可以另写一个其他算法的实现进行替换，之后对train()方法重写以完成自己想要的训练步骤与每轮的打印信息，其他部分参照代码注释。

import math
    
    class Adboost(object):
        def __init__(self, x_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
                           y_list = [1, 1, 1, -1, -1, -1, 1, 1, 1, -1]):
            """initialization
            initializing parameters of the Adboost
    
            input
            x_list : training data set
            y_list : labels of the x_list
            """
            self.x_list = x_list
            self.y_list = y_list
            self.sample_count = len(self.y_list)
            self.dt_list = [0.1] * self.sample_count  #the distribution of sample weights in the current round
            self.dt_next_list = []  #the distribution of sample weights in the next round
            self.ht_list = []  #results of the base classifier in the current round
            self.alpha = 0.0  #the weight of the self.ht_list
            self.Ht_list = [0.0] * self.sample_count  #results of the Adboost  in the current round
            self.Ht_sign_list = []  #sign(self.Ht_list)
            self.acc = 0.0  #the accuracy rate of the Adboost in the current round
    
        def __get_decision_stump(self):
            """base classifier(decision stump)
            obtain the decision stump by minimizing the classification error of current round with the self.dt_list
    
            output
            error_list  :  the error of each theta value and method
            method_flag :  method flag
            error_min   :  the minimum error of the error_list
            theta_min   :  the value of theta of the corresponding error_min
    
            error_min is necessary for return to compute other parameters, the rest are not
            """
    
            def __get_ht_list(theta):
                ht_list = []
                for x in self.x_list:
                    if x < theta:
                        ht_list.append(1)
                    else:
                        ht_list.append(-1)
                return ht_list
    
            theta_list = [x + 0.5 for x in self.x_list[:-1]]
            error_list = [[], []]
            error_min = 99999
            for theta in theta_list:
                ht_list_1 = __get_ht_list(theta) #method 1
                ht_list_2 = [-ht for ht in ht_list_1] #method 2
                for method, ht_list in enumerate([ht_list_1, ht_list_2]):
                    error = 0
                    for loc, y_ in enumerate(ht_list):
                        if y_ != self.y_list[loc]:
                            error += self.dt_list[loc]
                    error_list[method].append(error)
                    if error < error_min:
                        error_min = error
                        theta_min = theta
                        method_flag = method + 1
                        self.ht_list = ht_list
            return error_list, method_flag, error_min, theta_min 
    
        def __get_alpha(self, error):
            self.alpha = 0.5 * math.log((1-error)/(error))
            
        def __get_dt_next(self):
            for loc, dt in enumerate(self.dt_list):
                z = math.e**(-self.alpha * self.y_list[loc] * self.ht_list[loc])
                self.dt_next_list.append(dt * z)
            self.dt_next_list = [dt / sum(self.dt_next_list) for dt in self.dt_next_list]
            
        def __get_acc_rate(self):
            error = 0
            for loc, _ in enumerate(self.x_list):
                self.Ht_list[loc] += self.alpha * self.ht_list[loc]
            self.Ht_sign_list = [int(math.pow(-1, (Ht > 0) * 1 + 1)) for Ht in self.Ht_list]
            self.acc = map(cmp, self.Ht_sign_list, self.y_list).count(0) / (self.sample_count + 0.0)
    
        def train(self, T = 3):
            for t in range(T):
                error_list, method, error, theta = self.__get_decision_stump()
                self.__get_alpha(error)
                self.__get_dt_next()
                self.__get_acc_rate()
    
                print '--------------Round %s--------------' % (t+1)
                print 'error list : %s\n\t\t\t %s' % ([round(e, 3) for e in error_list[0]],\
                                                      [round(e, 3) for e in error_list[1]])
                print 'theta : %s' % theta
                print 'method : %s' % method
                print 'error : %s' % round(error, 4)
                print 'alpha : %s' % round(self.alpha, 4)
                print 'ht_list : %s' % self.ht_list
                print 'dt_list : %s' % [round(dt, 3) for dt in self.dt_list]
                print 'dt_next_list : %s' % [round(dt, 3) for dt in self.dt_next_list]
                print 'Ht_list : %s' % [round(Ht, 3) for Ht in self.Ht_list]
                print 'Ht_sign_list : %s' % self.Ht_sign_list
                print 'accuracy rate : %s' % self.acc
                print '------------------------------------\n'
                self.dt_list = self.dt_next_list
                self.dt_next_list = []
    
                if self.acc == 1.0:
                    break
    
    if __name__ == "__main__":
        adb = Adboost()
        adb.train(5)
    ----------------------------------------Output----------------------------------------
    
    --------------Round 1--------------
    error list : [0.5, 0.4, 0.3, 0.4, 0.5, 0.6, 0.5, 0.4, 0.3]
                 [0.5, 0.6, 0.7, 0.6, 0.5, 0.4, 0.5, 0.6, 0.7]
    theta : 2.5
    method : 1
    error : 0.3
    alpha : 0.4236
    ht_list : [1, 1, 1, -1, -1, -1, -1, -1, -1, -1]
    dt_list : [0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1, 0.1]
    dt_next_list : [0.071, 0.071, 0.071, 0.071, 0.071, 0.071, 0.167, 0.167, 0.167, 0.071]
    Ht_list : [0.424, 0.424, 0.424, -0.424, -0.424, -0.424, -0.424, -0.424, -0.424, -0.424]
    Ht_sign_list : [1, 1, 1, -1, -1, -1, -1, -1, -1, -1]
    accuracy rate : 0.7
    ------------------------------------
    
    --------------Round 2--------------
    error list : [0.643, 0.571, 0.5, 0.571, 0.643, 0.714, 0.548, 0.381, 0.214]
                 [0.357, 0.429, 0.5, 0.429, 0.357, 0.286, 0.452, 0.619, 0.786]
    theta : 8.5
    method : 1
    error : 0.2143
    alpha : 0.6496
    ht_list : [1, 1, 1, 1, 1, 1, 1, 1, 1, -1]
    dt_list : [0.071, 0.071, 0.071, 0.071, 0.071, 0.071, 0.167, 0.167, 0.167, 0.071]
    dt_next_list : [0.045, 0.045, 0.045, 0.167, 0.167, 0.167, 0.106, 0.106, 0.106, 0.045]
    Ht_list : [1.073, 1.073, 1.073, 0.226, 0.226, 0.226, 0.226, 0.226, 0.226, -1.073]
    Ht_sign_list : [1, 1, 1, 1, 1, 1, 1, 1, 1, -1]
    accuracy rate : 0.7
    ------------------------------------
    
    --------------Round 3--------------
    error list : [0.409, 0.364, 0.318, 0.485, 0.652, 0.818, 0.712, 0.606, 0.5]
                 [0.591, 0.636, 0.682, 0.515, 0.348, 0.182, 0.288, 0.394, 0.5]
    theta : 5.5
    method : 2
    error : 0.1818
    alpha : 0.752
    ht_list : [-1, -1, -1, -1, -1, -1, 1, 1, 1, 1]
    dt_list : [0.045, 0.045, 0.045, 0.167, 0.167, 0.167, 0.106, 0.106, 0.106, 0.045]
    dt_next_list : [0.125, 0.125, 0.125, 0.102, 0.102, 0.102, 0.065, 0.065, 0.065, 0.125]
    Ht_list : [0.321, 0.321, 0.321, -0.526, -0.526, -0.526, 0.978, 0.978, 0.978, -0.321]
    Ht_sign_list : [1, 1, 1, -1, -1, -1, 1, 1, 1, -1]
    accuracy rate : 1.0
    ------------------------------------

### 参考 ###

1.  统计学习方法. 李航. P137-P153
2.  机器学习. 周志华. P171-P191
3.  [梯度提升树GBDT原理][GBDT 1]
4.  [xgboost原理][xgboost]
5.  [GBDT（MART） 迭代决策树入门教程 | 简介][GBDT_MART_ _ _]
6.  [为什么xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度？][xgboost_gbdt]
7.  [GBDT如何应用于二分类问题？具体如何使用logitloss？][GBDT_logitloss]
8.  [当我们在谈论GBDT：Gradient Boosting 用于分类与回归][GBDT_Gradient Boosting]
9.  [机器学习算法中GBDT与Adaboost的区别与联系是什么？][GBDT_Adaboost]
10. [XGBoost 与 Boosted Tree][XGBoost _ Boosted Tree]
11. [机器学习算法中GBDT和XGBOOST的区别有哪些？][GBDT_XGBOOST]

[http_www.cnblogs.com_willnote_p_6801496.html]: http://www.cnblogs.com/willnote/p/6801496.html
[GBDT]: https://raw.githubusercontent.com/shuxunsohu/markdown_pic/master/GBDT.png
[w_q]: /images/20220416/3db4b2e0364e4403a5edf600875ecb3f.png
[GBDT 1]: http://blog.csdn.net/a819825294/article/details/51188740
[xgboost]: http://blog.csdn.net/a819825294/article/details/51206410
[GBDT_MART_ _ _]: http://blog.csdn.net/w28971023/article/details/8240756
[xgboost_gbdt]: https://www.zhihu.com/question/45487317/answer/99654929
[GBDT_logitloss]: https://www.zhihu.com/question/55379008
[GBDT_Gradient Boosting]: https://zhuanlan.zhihu.com/p/25257856?refer=data-miner
[GBDT_Adaboost]: https://www.zhihu.com/question/54626685?from=profile_question_card
[XGBoost _ Boosted Tree]: http://www.52cs.org/?p=429
[GBDT_XGBOOST]: https://www.zhihu.com/question/41354392