Contents
  1. 1. Ada算法
  2. 2. AdaBoost算法解释
  3. 3. 提升树
    1. 3.1. 提升树模型
    2. 3.2. 提升树的算法

对于分类问题来说,给定一个训练样本集,求比较粗糙的分类规则(弱分类器)要比精确的分类规则(强分类器)容易得多。提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称基本分类器),然后组合这些弱分类器,构成一个强分类器。
大多数的提升方法都是改变训练数据集的概率分布(训练数据的权值分布),针对不同的训练数据分布调用弱学习算法学习一系列弱分类器。

需要解决的两个问题:1. 在每一轮如何改变训练数据权值或者概率分布;2.如何将这些弱分类器组合成一个强分类器。
AdaBoost做法:1.提高那些被前一轮弱分类器错误分类样本权值,降低那些被正确分类样本的权值。2.加权多数表决。

Ada算法

  1. 初始化训练数据的权值分布
    D1=(w11,,w1i,,w1N)w1i=1N
  2. 对m =1,2,…M
    (a)使用具有权值分布D_m的训练数据集学习,得到基本分类器Gm(X):X{1,1}
    (b)计算Gm(X)在训练数据集上的分类误差率
    em=P(Gm(xi)yi)=Ni=1wmi(Gm(xi)yi)
    (c)计算Gm(X)的系数
    αm=12log1emem

    这里的对数是自然对数
    (d) 更新训练数据集的权值分布
    Dm+1=(wm+1,1,,wm+1,i,,wm+1,N)
    wm+1,i=wmiZmexp(αmyiGm(xi))
    Zm是规范化因子,使得Dm+1成为一个概率分布
  3. 构建基本分类器的线性组合

AdaBoost算法解释

可以认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习方法为前向分布算法时的二类学习方法。

提升树

提升树是以分类树或回归树为基本分类器的提升方法,提升树被认为是统计学习中性能最好的方法之一。

提升树模型

提升方法采用加法模型(基函数的线性组合)与前向分布算法。以决策树为基函数的提升方法称为提升树。提升树模型可以表示为决策树的加法模型:
fm(x)=m=1M=T(x;Θm)

提升树的算法

提升树采用前向分布算法,首先确定初始提升树,然后通过经验风险极小化确定下一棵决策树的参数Θm
由于树的线性组合可以很好的拟合训练数据,即时数据中的输入与输出之间的关系很复杂也是如此,所以提升树是一个高功能的学习算法。

不同提升树的算法主要区别在使用的损失函数的不同。包括用平方误差损失函数的回归问题,用指数损失函数的分类问题以及一般损失函数的一般决策问题。

对于二类分类问题,提升树算法只需将AdaBoost中基本分类器限制为二类分类树即可。

Contents
  1. 1. Ada算法
  2. 2. AdaBoost算法解释
  3. 3. 提升树
    1. 3.1. 提升树模型
    2. 3.2. 提升树的算法