http://www.ma-xy.com
目录
第一章 决策树和集成学习 1
1.1 决策树 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.1 引言 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 基本理论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.3 MATLAB 应用实例 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 集成学习 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.1
引言
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2.2 Boosting 起源 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2.3 AdaBoost 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2.4 加法模型 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.2.5 GBDT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.2.6 XGboost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.2.7 应用示例-XGboost . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
1.2.8 应用示例-LightGBM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1
http://www.ma-xy.com
第一章 决策树和集成学习
1.1 决策树
1.1.1 引言
为了引出决策树，考虑下面一些分类/回归问题。首先考虑单变量分类/回归问题，数据类型
如表 (1.1) 所示
表 1.1: 决策树单变量引例数据
data x(肤色) y(地区)
1 黄 亚洲
2 白 欧洲
3 白 欧洲
4 黄 亚洲
我们的目标是根据个体的肤色 x 来判断其所属的地区 y。可以从数据中总结出：如果这个人
的肤色是黄色，那么这个人是亚洲人；如果这个人的肤色是白色，那么这个人是欧洲人。我们将
这个规则绘制成树，如图 (1.1) 所示
图 1.1: 单变量决策树
分类/回归问题的本质是求 y = f(x)，不过，这里的 f 是一个特征函数 f ≜ I
x∈R
i
，其中，R
i
表示 x 的一个区域，当 x 在某个区域 R
i
内时，y 取特定值，如图 (1.2) 所示
1
http://www.ma-xy.com
1.1 决策树 第一章 决策树和集成学习
图 1.2: 单变量决策树区域图
将上述的离散型 x 变为连续型，则决策树区域可以是图 (1.3) 的情况
图 1.3: 连续型单变量决策树区域图
这里的目标是确定参数 θ。参数 θ 决定了区域 R
i
从而决定了特征函数 I
θ
。
上面考虑的是单一变量的分类问题。下面考虑两个变量的分类/回归问题。数据类型如表
(1.2) 所示
表 1.2: 决策树两变量引例数据
data x
1
(眼色) x
2
(身高) y(地区)
1 黑 中 亚洲
2 黄 高 欧洲
3 黑 中 亚洲
4 黄 高 欧洲
根据上面表 (1.2) 的数据，可以给出地区 y 的决策树，如图 (1.4) 所示
图 1.4: 两变量决策树
决策树的区域如图 (1.5) 所示
http://www.ma-xy.com 2 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.1 决策树
图 1.5: 两变量决策树区域图
继续考虑连续型的变量 x
1
, x
2
，连续型变量的分类区域是图 (1.6) 的形式
图 1.6: 连续型两变量决策树区域图
我们的目标是：确定划分区域，即确定图 (1.6) 中的 θ = (θ
1
, θ
2
)，θ
1
= (θ
11
, θ
12
, θ
13
, θ
14
)，
θ
2
= (θ
21
, θ
22
, θ
23
)。值得一提的是，虽然决策树的本质目标是求解区域参数 θ，但这并不是决策
树的唯一目标。在建立决策树时，要先确定节点变量 x
j
，然后再确定该节点对应的参数 θ
j
。
将上述方法推广到多变量分类问题。设数据为 D，共有 p 个属性变量 x
j
, j = 1, 2, . . . , p，变
量可以是连续型、二分类、多分类和有序的。并且，设属性 x
j
的水平数为 c
j
(例如：属性“性别”
的水平为“男”“女”，则其水平数为 2)，设变量 x
j
的参数为 θ
j
；设标签为 y，标签的水平数为
c
y
(这决定了是二分类问题还是多分类问题/回归问题)；设共有 n 个样本。我们在数据 D 上建立
决策树，将决策树模型记为 T
D
。在 T
D
中用 □ 表示属性 x
j
，称为根节点；用 表示终止的分
类，称为叶节点。在建立决策树 T 时，应该考虑如下问题：
1. 如何确定当前节点 x
j
, j = 1, 2, . . . , p？一种方法是计算 x
j
与 y 的相关性，x
j
与上层节点的
相关性，将相关性高的放在当前节点。不过要注意共线性。
2. 如何判断该节点 x
j
的划分点 (分割点)θ
j
？
3. 如何判断该节点 x
j
是否需要继续划分 (是否有子节点)？这是设定终止条件，可以依据当前
节点下的样本数量、树深度以及当前节点下的分类正确率来判断是否终止。
4. x
j
可在一棵树中出现多次，能否简化？
5. 如何添加一些外来参数 ϵ，使得树 T 更加灵活可调节？
6. 如何评价树？如何评价不同的树？
http://www.ma-xy.com 3 http://www.ma-xy.com
http://www.ma-xy.com
1.1 决策树 第一章 决策树和集成学习
1.1.2 基本理论
树的生成：节点及分割点的选取
下面来看看 ID3、ID4.5 和 CART 等树是如何解决上面的问题 (即如何生成树)。值得一提
的是，对于树中叶节点上的百分数，其为条件概率，例如
p(y = 1|x
1
= 1, x
2
= 2) = 0.97
考虑是否有必要令 x
1
, x
2
相互独立。下面来解决如何选择属性 x
j
以及如何寻找属性 x
j
的划分
点/分割点 θ
j
。
选择划分属性 (节点) 及分割点 θ 的目的是为了尽可能的区分标签，例如：
p(y = 1|x
j
< θ
1
) = 0.79
p(y = 1|x
j
< θ
2
) = 0.83
一般情况下，我们更愿意选择 θ
2
作为 x
j
的分割点。接下来考虑，如何确定当前属性 x
j
，以及如
何确定该属性是否需要继续划分 (不满足终止条件)？在确定当前属性 x
j
时，可以使用这样一种
方法：在所有属性中，将当前节点的上一层节点属性去掉，记为 {x
j
}
−
。然后对 {x
j
}
−
中的每一
个属性 x
j
的每一种分割点 θ
j
计算标签的区分度：条件概率 p(y =?|··· , x
j
< θ
j
) =?。最终，选
择条件概率最大的属性 x
j
及其对应分割点 θ
j
¬
。这种方法本质上是一种枚举法，理论上是可行
的，但并不一定实用。
上面提到的标签区分度是条件概率 (本质上就是一个概率，是样本的子样本下的一个概率)，
其实还有许多不同的样本区分度度量标准，例如：1. 信息熵；2. 信息增益 (ID3)；3. 增益率 (C4.5)；
4. 基尼指数 (CART)。
(1) 熵是信息论中的概念，用于度量系统离散程度，熵越大，系统离散程度越大。给出整个样本 D
的熵的定义
Ent(D) = −
c
y
k=1
p
k
log
2
p
k
其中：p
k
为属于 k 类的概率，可以用样本的极大似然估计之，Ent 越小，划分程度越高。上面
的问题就是选择 θ，使样本尽可能区分开。因此，可以将熵的概念用于 θ
j
的确定，求 θ
j
使子样
本的熵尽可能低。这里说的子样本是样本的子集，比如：样本中 x
1
= 1, x
2
= 2 的子样本。记子
样本集为 D
v
，x
j
的划分点为 θ
j1
, θ
j2
，则有
Ent(D
v
) = −
c
k=1
p(y = k|··· , θ
j1
< x
j
< θ
j2
) log
2
p(y = k|··· , θ
j1
< x
j
< θ
j2
)
称上式为在 x
j
给定后 θ
j
= (θ
j1
, θ
j2
) 带来的总体 D
v
的条件熵 (因为是基于条件分布的)。与前
面所说的条件概率相似，当 p(y = 1|···) = 0.5，p(y = 0|···) = 0.5 时，D
v
最难分开。我们应
该选择 θ
j
使 D
v
的 Ent 尽可能小，即 p(y = k|···) 尽可能大。
¬
注：可以想象的是，T 是 θ 的函数，目标是求最佳的 θ，使 T “最佳”。
http://www.ma-xy.com 4 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.1 决策树
(2) 但不得不考虑的一个问题是样本量的偏倚，样本数量越多，影响越大。定义信息增益
(information gain) 为
Gain(D)
θ
j
= Ent(D) −
num
θ
j
v =1
|D
v
|
|D|
Ent(D
v
)
此 Gain 为 ID3 算法选择属性 x
j
和分割点 θ
j
的策略。
(3) 虽然上面的 Gain 解决了样本量的偏倚，但应该注意到会有表 (1.3) 这种情况
表 1.3: 子样本的特殊情况
D
v
x
j
y
1 1 0
2 2 1
3 3 0
4 4 1
5 5 0
如果 x
j
的分割点 θ
j
= (1, 2, 3, 4, 5)，则每个 p(y = ·|· < x
j
< ·) 仅含有一个样本，这会导
致其不具有推广能力。为此，Quinlan 于 1993 年设置了 C4.5(商用版本为 C5.0) 的增益率 (gain
ratio)
Gain_ratio(D)
θ
j
=
Gain(D)
θ
j
IV
θ
j
其中：
IV
θ
= −
num
θ
j
v =1
|D
v
|
|D|
log
2
|D
v
|
|D|
(4) 基尼指数。另外，Breiman 在 1984 年开发的 CART 树是通过基尼指数来进行选择。Gini
定义为
Gini(D) = 1 −
c
y
c=1
p
2
(y = k)
Gini 反映了从数据集 D 中随机抽取两个样本，其标签不同的概率。对于子样本，Gini(D
v
) 定义
为
Gini(D
v
)
θ
j
= 1 −
c
y
k=1
p
2
(y = k|··· , θ
j,i
< x
j
< θ
j,i+1
)
进一步考虑样本量的影响，有
Gini_index(D)
θ
j
=
num
θ
j
v =1
|D
v
|
|D|
Gini(D
v
)
http://www.ma-xy.com 5 http://www.ma-xy.com
http://www.ma-xy.com
1.1 决策树 第一章 决策树和集成学习
于是，我们要选择 θ
j
使得 Gini_index(D)
θ
j
尽可能小，有
θ
∗
j
= arg min
θ
j
∈Θ
Gini_index(D)
θ
j
树的修剪
决策树已经建好了吗？并没有，前面所做的工作只是介绍了树的生长方式：如何选择节点 x
j
以及分割点 θ
j
。这些工作可以生成一棵枝繁叶茂的树，但并不一定是一棵“漂亮”的树。在经过
一系列的生长后，到了用 x
j
划分的时候，发现 x
j
下的子样本仅有几个。出现这种情况的原因
是：¬属性节点太多；样本量太少。这种树会导致过拟合现象，为此，有必要考虑一下“园丁”
的工作：修剪树枝 (去掉一些节点属性)。根据上述情况产生的原因¬和，我们可以规定：
1. 属性达到一定的数目后就不再生长，即当树的根节点达到一定数目时就不再生长。设定数
目阈值为 ϵ
1
；
2. 子样本数目小于一定数目时就不再生长。设定子样本最小数目为 ϵ
2
；
其中：ϵ
1
, ϵ
2
就是我们前面所说的外来参数。它们是人为添加的，用于控制树 T 的生长。但这种方
法是人为设置的，有很强的主观性，有可能导致该出现的枝未出现。一般书上称这种工作为“预
剪枝”，其实，这并不能称为剪枝，而应该称为抑制生长。
对“应该出现的分枝未出现”，也可以有相应的改进策略，我们让所有的枝都生长出来，看
枝的“价值”如何，然后将价值低的枝减掉。一般书上称此策略为“后剪枝策略”。那么，问题
来了：枝是什么？如何评价枝的价值？如何剪枝？
C4.5 使用的是悲观剪枝法，CART 使用的是代价复杂度剪枝法。下面来介绍这两种剪枝方
法。我们称树 T 的一部分为树枝，如图 (1.7) 所示
图 1.7: 决策树树枝示意图
设节点 t 下的树枝为 T
t
，节点 t(注意，这里的节点为叶节点，如果我们将某一根节点下的
叶节点剪枝，则该根节点变为叶节点) 的错误率为 e
t
，样本数 N
t
，错误样本数 E
t
。错误率，即
新来样本在子节点处被判错的概率。如果所有子节点下的加权错误率大于父节点，则去掉这些子
(叶) 节点。
C4.5 是从底层开始逐层向上修剪，关键问题是误差的估计以及修剪标准的设置。考虑如下
图 (1.8) 的决策树
http://www.ma-xy.com 6 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.1 决策树
图 1.8: C4.5 决策树
其中：各节点下的数字比例 ? :? 表示：前一个数字为该节点 t 下的样本数 N
t
，后一个数字为错
判样本数 E
t
。例如：在 (叶) 节点 x
7
处终止，有 6 个子样本，其中 4 个为 1，2 个为 0。但现在
终止了，也就说明对于一个新来样本，在该处会被判为 1。节点 t ≜ x
7
的错误率为 ˆe
t
=
E
t
N
t
=
2
6
。
ˆe
t
的本质是一个样本估计量。然后来说明 C4.5 中“悲观”所在。其实，悲观是指在置信水平 α
下，错误率 e
t
的估计上限
ˆe
t
=
E
t
N
t
+ Z
α
2
E
t
N
t
(1 −
E
t
N
t
)
N
t
注：这里有
E
t
N
t
− e
t
E t
N
t
(1−
E
t
N
t
)
N
t
·
∼ N (0, 1)
当子节点 (x
5
, x
6
, x
7
) 的加权错误率超过父节点 x
3
的错误率，则去掉子叶节点 x
5
, x
6
, x
7
，根节点
x
3
变为叶节点。
当然，还可以通过其它手段来体现悲观。考虑如图 (1.9) 两个树枝 T
L
, T
R
(T
L
剪掉下层叶节
点变为 T
R
)
图 1.9: 用于悲观剪枝法的两个树枝
上图 (1.9) 中的叶节点处的数值比表示为真假样本比例。定义树枝的悲观度为
e
g
(T
t
) =
k
i=1
(E
t
i
+ Ω
t
i
)
k
i=1
N
t
i
=
E(T
t
) + Ω(T
t
)
N
t
http://www.ma-xy.com 7 http://www.ma-xy.com
http://www.ma-xy.com
1.1 决策树 第一章 决策树和集成学习
其中：t
i
为叶节点，E
t
i
为叶节点
t
i
下的错误样本，
N
t
i
为叶节点 t
i
下的总样本，Ω
t
i
为叶节
点 t
i
的惩罚，k 为枝 T
t
的叶节点数，T
L
的叶节点数为 7，T
R
的叶节点数为 4；设每个叶节点
t
i
, i = 1, 2, . . . , k 的惩罚为 0.5，则有
e
g
(T
L
) =
4 + 7 × 0.5
24
= 0.3125
e
g
(T
R
) =
6 + 4 × 0.5
24
= 0.3533
上面介绍了 C4.5 的悲观剪枝法，下面来介绍 CART 的代价复杂性剪枝法。C4.5 的悲观剪
枝法对枝的价值是通过下面的错判误差来衡量的，且由于是由下层逐层向上计算，枝也仅包含 2
层。而 CART 对枝价值的评价不仅仅包含 2 层，而是更多层。我们记 CART 的枝的价值为 R，
R 价值同样是由错误率与复杂性度量的，与 C4.5 不同的是，其错误率是在测试集上计算的。定
义枝
T
的价值
/
代价复杂度为
R
α
(T ) = R (T ) + α(|T | − 1)
其中：R(T ) 为 T 在测试集上的误差，|T | 表示枝 T 的子节点数目 (去掉父节点的)，α 为复杂度
系数，表示每增加一个子节点带来的复杂度。CART 的修剪步骤为：
Step1. 对于最大的树 T
1
，令 α = 0，计算复杂度，不断增加 α，直到有一个子枝可以被剪掉，此
时得到子树 T
2
。这里介绍剪掉内部节点 t 的分枝的方法：当 α ⩾
R(t)−R(T
t
)
|T
t
−1|
时，内部节点 {t} 的
代价复杂度小于等于子树 T
t
，则可以剪掉内部节点 t 的分枝。
Step2. 重复步骤 1，直到剩下最后一个根节点。最终得到的子树序列为 {T
1
, T
2
, . . . , T
k
} 及它们
的代价复杂度 R
α
(T
1
), R
α
(T
2
), . . . , R
α
(T
k
)。
Step3. 确定最终修剪结果 T
opt
R(T
opt
) ⩽ min
k
R(T
k
) + mSE(R(T
k
))
其中：m 为放大因子，SE(R(T
k
)) 为子树 T
k
在测试集上的预测误差的标准误
SE(R(T
k
)) =
R(T
k
)(1 − R(T
k
))
N
t
这里，我们详细说明一下 Step1。如图 (1.10) 所示
图 1.10: CART 剪枝示意图
http://www.ma-xy.com 8 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.1 决策树
计算完全树 T
1
的代价复杂度 R
α
(T
1
), α = 0；令 α = α + 1，判断 T
1
中是否有子枝可以被剪，
比如：针对图 (1.10) 中的节点 t 和枝 T
t
而言，对 R
α
(t) 的复杂度和 R
α
(T
t
) 的复杂度进行计算
R
α
(t) = R(t) + α
R
α
(T
t
) = R(T
t
) + α(|T | − 1)
其中：R(t) 是将测试集带入到树 T 中，只计算到 t 节点时的错误率；R(T
t
) 是将测试集带入到树
T 中，计算到最后，T
t
的错误率。当 α ⩾
R(t)−R(T
t
)
|T
t
−1|
时，剪掉 T
t
枝。
下面介绍 ID3、C4.5、CART、CHAID 和 QUEST 树的应用范围。(1)C4.5 可以用于建立多
叉分类树，要求输入变量是分类型/连续型，输出变量是分类型，以信息率为建树准则，以悲观
误差估计为剪枝策略，不用测试集。(2)CART 只能建立二叉树，要求输入变量是分类型/连续型，
输出变量为分类型/连续型，Gini 系数作为建树准则，以代价复杂性作为剪枝准则，需要测试集。
(3)CHAID 称为卡方自动交互诊断器，由 Kass 于 1980 年提出，可以建立多叉树，输入和输出变
量可以是连续型/分类型，它以卡方统计显著检验作为建树准则，以相关性限定策略作为剪枝策
略。(4)QUEST 是由 Loh 和 Shih 于 1997 年提出，可建立二叉树，要求输入变量是分类型/连续
型，输出变量为分类型，它以统计方法为基础进行建树。
树的评估
在前面的 CART 的剪枝策略中，我们构建了 {T
1
, T
2
, . . . , T
k
} 棵树，然后选择了 T
opt
，这种
剪枝的本质是用 CART 策略生成不同的树，然后从中选择最好的。并且，对于同一个数据集 D，
我们可以建立不同的树，那么如何评价这些树对于我们的问题/D 的好坏呢？很自然想到，如果
新来一批样本 (测试集)，哪棵树的误差小，那棵树就是好的。这里，我们是用误差作为树优良的
评判标准，同样，还有提升度，收益率等评判标准。先来泛化误差的计算。为了体现泛化，我们有
必要构造不同的数据集 D
1
, D
2
, . . . , D
k
，并在这些数据集上测试模型。下面介绍几种可行的，通
过 D 来构造 {D
k
} 的方法：
(1) 保持法：使用训练集和检验集 (非测试集)，在检验集上计算平均准确率，如果计算总准
确率，最好使不同模型的检验集样本数目相同。但是这种方法受样本量的限制。
(2) 随机 (二次) 采样：从 D 中随机抽取样本，设每次采样数目为 n
1
, n
2
, . . . , n
k
(共有 k 次采
样，形成 k 个样本)，用 i 作为标记，acc
i
是第 i 次抽样的准确率
acc
i
=
E
i
n
i
则总采样准确率为
acc
sub
=
k
i=1
acc
i
n
i
平均准确率为
acc
avg
=
acc
sub
k
i=1
n
i
http://www.ma-xy.com 9 http://www.ma-xy.com
http://www.ma-xy.com
1.1 决策树 第一章 决策树和集成学习
问：随机采样是真的从 D 中再生成子样本，但其子样本已经参与过建树的过程 (检验集中的
样本则没有参与建树过程)，这样的话能用其充当新样本吗？其实，建树过程只用了该样本的部
分信息，有些信息在修剪的过程中被剪掉了。
(3)k 折交叉验证：在 k 折交叉验证中，我们将样本集分为 k 个子集，先用第一个子集作为
检验集，剩下的子集作为训练集进行训练，得到误差 e
1
，然后用第二个子集作为检验集，剩下的
子集作为训练集进行训练，得到误差 e
2
，如此反复，直到第 k 个子集作为检验集，得到 e
k
。最
终的误差为 e =
i
e
i
。
(4)bootstrap 技术 (自助法)：自助法是估计一个统计量均值、方差和分布的一种有效的方法。
并且这种方法是有放回抽样。设有 n 个训练样本，设定有放回法采样 k 次，每次采样量为 α
i
，α
i
可以相同，也可以不同。用 i 作为次数标记，acc
i
为第 i 次有放回采样的准确率，则 bootstrap
方法的准确率为
acc
boot
=
1
k
k
i=1
α
i
n
E
i
α
i
+ (1 −
α
i
n
)acc
i
上面介绍了用于模型评价的泛化误差的计算，对于分类模型的评价，还可以采用混淆矩阵、
ROC 曲线、提升度和收益率等。
1.1.3 MATLAB 应用实例
MATLAB 中使用 tctree 函数来实现决策树的创建，其调用格式为 tree = tctree(x,y,Name,Value)；
使用 cvloss 来实现决策树剪枝，其调用格式为
[ , , bestlevel] = cvloss(tree,’subtrees’,’all’,’treesize’,’min’)
cptree = prune(tree,’Level’,’bestlevel’)
用 resubloss 来计算重带入误差，用 kfoldloss 来计算交叉验证误差，用 predict 来进行预测。
下面给出一个简单的 MATLAB 应用实例
1 t ree = f i t c t r e e ( means ( : , 1 : 2 ) , sp e cies , ’ PredictorNames ’ ,{ ’ s l ’ , ’sw ’ }) ;%创 建 决 策 树
2 [ grpname , node ] = p redi c t ( t ree , [ x , y ] ) ;
3 %绘 制 混 淆 矩 阵
4 tar ge to ut pu t = y ’ ;
5 output = predi c t (model_tree_Y1 , X_tree_test ) ; output = output ’ ;
6 t ar ge toutput = f u l l ( ind2vec ( t ar ge to ut pu t+1)) ;
7 output = f u l l ( ind2vec ( output+1)) ;
8 plo t conf u sion ( targetoutput , output ) ;
9 c l e a r output
10 g s s c a t te r (x , y , grpname , ’ grb ’ , ’ sod ’ )
11 view ( tree , ’ model ’ , ’ graph ’ )%绘 制 决 策 树
12 dtResabErr = r e s u bloss ( t r e e ) ;%重 带 入 误 差
13 crt = c r o s s v a l ( tree , ’ CVPartitin ’ , ’ cp ’ ) ;
14 dtCVErr = k f o l d l o s s ( crt ) ;%k 折 交 叉 验 证 误 差
15 re subco st = resubloss ( tr ee , ’ sub t ree s ’ , ’ a l l ’ ) ;
16 [ cost , s eco st , ntermnodes , b e s t l e v e l ] = c v l o s s ( tree , ’ su btre es ’ , ’ a l l ’ )%计 算 最 优 l e v e l
17 pl o t ( ntermnodes , cost , ’b−’ , ntermnodes , re subcost , ’ r−−’ )
18 f i g u r e ( g cf )
19 xlabel ( ’Number of terminal nodes ’ )
http://www.ma-xy.com 10 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
20 ylabel ( ’ co st m i s c l a s i f i c a t i o n e r r o r ’ )
21 legend ( ’ Cross−r a l i d a t i o n ’ , ’ Res ubs tit ati on ’ )
22 [ mincost , minloc ] = min( cos t )
23 c u t of f = mincost + secost ( minloc )
24 hold on
25 pl o t ( [ 0 , 2 0 ] , [ c u t o f f c u t o f f ] , ’ k : ’ )
26 pl o t ( ntermnodes ( b e s t l e v e l +1) , co st ( b e s t l e v e l +1) , ’ no ’ )
27 legend ( ’ Cross−r a l i d a t i o n ’ , ’ Res ubs tit ati on ’ , ’Min+1 st e r . e r r ’ , ’ Best c l o i c e ’ )
28 hold o f f
29 pt = prune ( t ree , ’ l e v e l ’ , ’ b est l e v e l ’ )%决 策 树 剪 枝
30 view ( pt , ’mode ’ , ’ graph ’ )
31 co s t ( be s t l e v e l +1)
32 %查 看 树
33 % t reet ype = type ( tree )
34 % var6 = cutvar ( t ree , 6 ) % 该 节 点 是 什 么 变 量
35 % type6 = cuttype ( t ree , 6 ) % 变 量 是 什 么 类 型
36
1.2 集成学习
1.2.1 引言
常用的集成学习有两种：Boosting(提升方法) 和 Bagging(打包方法)13。Boosting 族是一种
可将弱分类器提升为强分类器的学习方法，有 Adaboost 等；Bagging 是一种基于 bootsrtap 方
法的集成建模方法，有 RandomForest(随机森林) 等。这里，我们先来介绍两种集成学习方法的
不同之处，之后，再详细介绍 boosting 方法。Bagging 对训练集进行随机抽样，并且各轮训练相
互独立，最终的预测函数没有权重，易于并行训练；而 boosting 方法的各轮训练并不相互独立，
当前训练与前一轮训练的误差密切相关，并且 boosting 方法的预测函数有权重，只能顺序生成。
在大多数数据集上，boosting 的准确率要比 bagging 更高。
Boost 方法被放在了机器学习部分的最后，在前面的机器学习部分，我们介绍了许许多多的
分类/回归 (预测) 方法，这些方法都可以作为 Boost 方法的简单分类器。Boost 方法和组合预测
的思想类似，对于同一个分类/回归数据，我们用不同的模型 (弱分类器) 进行分类，然后将这些
模型的结果综合 (评价)，形成最终的分类结果。我们前面提到过，基本的 MLP(多层感知器) 就
是线性回归的组合策略。下面，我们要考虑的问题是：如何选择单一的分类模型？模型参数如何
调整？如何组合分类结果？
如何将多个分类器的分类结果组合，或者更详细的说，对于具体的某一样本 x
k
，我们有 M
个分类器的结果 y
k
1
= 1, y
k
2
= 3, y
k
3
= 1, . . . , y
k
M
= 1，那么，这个样本 x
k
的类别最终应判为哪
一类呢？我们自然想到，用 M 个分类结果的众数来作为最终的判别结果，如果对回归预测而言，
就用 M 个回归模型预测的均值作为最终预测结果，这种思想被称为 committee(委员会)。
我们有必要先研究一下这个组合估计的均值和方差大小，并与单一分类器得到的均值方差进
行比较。当然，后面介绍的 Boost 方法也要讨论估计量的性质。boosting 方法是 committee 方
法的变体，boosting 方法有 3 种基本的结构：
http://www.ma-xy.com 11 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
1. 通过过滤推举：用一个弱学习算法的不同版本过滤训练样本，有些样本在训练过程中会被
抛弃，有些则保留，这个方法要求样本量大，但它需要的存储空间较小。
2. 通过子抽样提升：这种方法用到一个固定大小的训练样本，训练中这些样本以一定的概率
(权重) 被重新抽取。
3. 通过加权推举：这种方法也用到一个固定大小的训练样本，但他决定弱学习算法能接收加
权后的样本。
Committee
无论对于分类问题还是回归问题，仍假设我们得到的样本集为 S = {x
k
, y
k
}
m
k=1
, x
k
= (x
k
1
, x
k
2
,
. . . , x
k
n
)，S ⊂ R
n
，y
k
∈ R 或者 {1, 2, . . . , c}。为了描述方便，这里我们考虑回归问题，我们要在
样本集上建立 M 个回归模型，然后将这些模型的结果综合，给出最终的预测/估计。假设第 i 个
模型的回归估计值为 y
i
= (y
1
i
, y
2
i
, . . . y
m
i
)，M 个回归模型的估计做平均，有
y(x) =
1
M
M
i=1
y
i
(x)
下面来分析这个估计量 y(x) 的均值和方差。设第 i 个模型 y
i
(x) 的误差为 ε
i
(x)，有离差平
方和
E
x
[(y − y
i
(x))
2
] = E
x
[ε
i
(x)
2
]
其中：y 为样本真实输出，y
i
(x) 为估计。于是，各模型独立预测时的平均误差为
E
arg
=
1
M
M
i=1
E
x
[ε
i
(x)
2
]
类似的，Commttee 方法的期望误差/平均误差为
E
com
= E
x
[(y(x) − y)
2
]
= E
1
M
M
i=1
y
i
(x) − y
2
= E
x
1
M
M
i=1
ε
i
(x)
2
如果我们假设
E
x
[ε
i
(x)] = 0
E
x
[ε
i
(x)ε
j
(x)] = 0
则有
E
com
=
1
M
E
arg
http://www.ma-xy.com 12 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
这个结果表明：对一个模型而言，可以通过模型的 M 个版本求平均 (组合) 的方式，使误差
减小 M 倍。但是，这个结果依赖于前面的假设，即由单个模型产生的误差是不相关的，但在实
际中，误差间往往高度相关。幸运的是，我们仍能证明组合策略的一大特点是
E
com
⩽ E
arg
即组合分类/预测模型的期望不会超过单一模型的期望。
1.2.2 Boosting 起源
Boosting 方法是一种非常强大的方法，它将多个弱分类器进行组合，产生新的强分类器，强
分类器比任何一个弱分类器都要好。Boosting 方法几乎可以应用到前面介绍的各种分类方法当
中 (应该也可以应用到聚类方法)。Boosting 打破了原样本的分布，这一点是至关重要的。下面，
我们将要描述：1.PAC 和 Boosting 猜想及证实以及 Boosting 最初的设计；2.Adaboost 训练误
差及泛化误差；3. 几种重要的 Adaboost 理论分析模型，并由此引出一些 AdaBoost 的改进；4.
介绍 AdaBoost 从二分类到多分类即回归问题的推广。
在可能近似正确 (Probably approximately Correct, PAC) 学习框架中，X 是样本空间，C
是目标种类集，C 中的每一个元素 c 对应着 X 上的某一个子集，D 是样本空间 X 的固定但未
知的分布函数，训练集 S = {x
k
}
m
k=1
是从分布 D 中独立随机抽取的样本集。
现在，假设有一个分类器 f (x)，分类器 f (x) 在样本 x 上的错误率为 e(f ) = P
x∈D
[c(x) =
f(x)]，PAC 学习模型弱化对分类器 f(x) 的要求，不要求 f (x) 输出其错误率，只要错误率在一
个很小的常数 ε 内，不要求 f (x) 对任何随机抽取的训练样本都能成功，只要失败的概率在一个
很小的 δ 内即可。
定义 PAC 的强学习概念：考虑一个 n 分类问题，C = {1, 2, . . . , n}，有一训练集 S，∀c ∈ C、
S 上的任意样本分布 D、0 < ε <
1
2
、0 < δ <
1
2
，如果存在
1
ε
,
1
δ
, n 和 size(c) 的多项式复杂度的
算法 A，能够以 1 − δ 的概率输出假设 f ，且 f 的错误率 e(f ) ⩽ ε，则称类 c 是 PAC 强可学习
的，称算法 A 是一个强学习算法。
如果只需要存在某对 ε, δ，使得以上结论成立，则类 c 是 PAC 弱可学习的，称算法 A 为弱
学习算法。
1989 年，Kearns 和 Valiant 在研究 PAC 时提出4：弱可学习是否等价于强可学习？如果等
价，那么任意给定一个仅比随机猜测好的弱学习算法 (准确率 > 0.5)，可以通过加强提升到一
个任意准确率的强学习算法，并可以通过构建一个多项式级的算法来实现这一加强 (提升) 过程，
这使得我们不必直接去寻找难以构建的强学习算法。Schapiro 通过构造性方法证明：一个类是弱
可学习的，当且仅当它是强可学习的。其构造过程如下：¬首先依分布 D 产生训练集 S 的一个
子集 EX
1
，调用算法 weaklearn 得到分类器 f
1
，只要分类器 f
1
是一个弱分类器；接着，构
造样本集 EX
2
，其一半是被 f
1
正确分类的样本，一半是错误分类的样本，训练得到分类器 f
2
；
®最后，选择 f
1
, f
2
分类结果不同的样本构成 EX
3
，调用 weaklearn 训练得到分类器 f
3
；®对新
样本，由 f
1
, f
2
, f
3
投票决定。可以证明，若 f
1
, f
2
, f
3
在任意分布下的错误率 α5 均小于
1
2
，则
f = sgn(f
1
+ f
2
+ f
3
) 在任意分布下的错误率 g(α) ⩽ 3α
2
− 2α
3
。这意味着上述算法可以得到一
http://www.ma-xy.com 13 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
个更低错误率的分类器 f，并且，如果继续深入上述算法，最终分类器 f 的错误率可以任意低。
强学习算法如 (1) 所示
算法 1 强学习算法 Learn
1: 初始化：训练样本集 EX，弱学习算法 weaklearn，weaklearn 的错误率上界 ε，置信度 δ。
2: 如果 ε ⩾ (1/2 − r)，返回 weaklearn(EX)；
3: α = g
−1
(ε)；
4: f
1
= learn(α, δ/k, EX
1
)；
5: f
2
= learn(α, δ/k, EX
2
)；
6: f
3
= learn(α, δ/k, EX
3
)；
注意到，上述强学习算法要求弱学习算法 weaklearn 的误差率 ε 满足一定要求，并且，在构
建 f
1
, f
2
, f
3
时，误差置信度是 1 −δ/k，最终分类器 f 的置信度为 (1 −δ/k)
k
> 1 −δ。算法每次
递归的性能增益与最大错误率 ε 称多项式关系，所以递归层数是多项式复杂性的，至此，证明了
弱学习算法可以被提升到以 1 −δ 概率输出错误率小于任意 ε 的假设 (即强学习算法)。上述过程
打破了分类器在已有样本上的优势，重新采样使接下来的分类器聚焦于难分类的样本。然而，由
于算法要求我们提前预知弱分类器的错误率上界 ε，因此，在实际中上述算法很难应用。
1.2.3 AdaBoost 算法
1995 年 Freund13提出 Adaboost 算法。Freund 和 Schapire 发现，在线分配问题与 Boosting
问题之间存在着很强的相似性，引入在线分配算法的设计思想，有助于设计出更实用的 boosting
算法。我们将加权投票的相关研究成果与在线分配问题结合，并在 Boosting 问题框架下进行对
应推广，得到了著名的 Adaboost 算法。Adaboost 算法不再要求预先知道弱学习算法 weaklearn
的任何先验知识，在实践中取得了巨大的成功。
AdaBoost 的主要步骤为：首先给出弱分类器和样本集 S = {x
k
, y
k
}
m
k=1
，每个样本都赋予一
个权重 w
k
, k = 1, 2, . . . , m，设初始权重 w
k
0
=
1
m
；然后，我们用弱学习算法迭代 M 次，每次运
行结束后，都按照分类结果的准确性更新样本权重，对于分类失败的训练样本赋予较大的权重，
下次迭代训练时，有较大机会挑选到失败的样本。我们在每一个 i(i = 1, 2, . . . , M) 都得到了一个
分类器 f
i
(i = 1, 2, . . . , M)，将这 M 个分类器按照一定权重组合，结果准确率高的分类器赋予大
的权重，最终形成的强分类器 F 。AdaBoost 算法步骤如下：
Step1. 初始化。S = {x
k
, y
k
}
m
k=1
，弱分类器 f 可以选择 SVM 或 BP 或决策树等，M ，i := 0，
w
k
0
=
1
m
。
Step2. 对 i = 0, 1, . . . , M − 1 训练第 i 个分类器 f
i
：
¬对 x
i
进行训练，得到分类器 f
i
(x)。分类器的目标是最小化加权误差
J
i
=
m
k=1
w
k
i
I
f
i
(x
k
)=y
k
其中：I 是特征函数，f
i
表示第 i 次的分类器，x
k
为第 k 个样本。
http://www.ma-xy.com 14 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
计算 ϵ
i
, α
i
ϵ
i
=
J
i
m
k=1
w
k
i
=
m
k=1
w
k
i
m
k=1
w
k
i
I
f
i
(x
k
)=y
k
α
i
=
1
2
ln
1 − ϵ
i
ϵ
i
ϵ
i
是加权错误率且
m
k=1
w
k
i
= 1。
®更新样本的权重 w
k
i+1
w
k
i+1
= w
k
i
exp{α
i
I
f
i
(x
k
)=y
k
}
被分错的样本 k 的权重 w
k
会变大，分对的样本的权重保持不变 (exp(0) = 1)。
Step3. 终止条件。如果不终止，则置 i := i + 1，返回 Step2；终止后，输出最终的组合分类模型
F (x) =
M
i=1
α
i
f
i
(x)
AdaBoost 的误差分析
(1) 训练误差。我们先来看 AdaBoost 的训练误差，在 AdaBoost 提出之初，Freund 就分析
了 AdaBoost 的训练误差。Freund 等在 1995 年的原文中首次证明：若 Adaboost 每一轮迭代中
生成的子分类器错误率分别为 ε
1
, ε
2
, . . . , ε
M
，则组合分类器 F =
M
i=1
α
i
f
i
的训练错误率 ε 有
上界：ε ⩽ 2
M
M
i=1
ε
i
(1 − ε
i
)。
随后，Schapire 等又给出另一种更简单的误差界推导方法，得到
ε =
1
m
m
k=1
[F (x
k
) = y
k
] ⩽
1
m
m
k=1
exp
−y
k
M
i=1
α
i
f
i
(x
k
)
=
M
i=1
z
i
其中：z
i
是第 i 轮迭代的样本归一化因子
z
i
=
m
k=1
w
k
i
exp(−α
i
y
k
f
i
(x
k
))
w
k
i
是样本 x
k
在第 i 次迭代中的样本权重。
上面给出了 AdaBoost 的训练误差界，但是这种误差界过于宽松，在实际训练中，AdaBoost 的
表现要比这个误差界好很多。虽然过于宽泛，但该过程可以用来指导我们寻找单一分类器 f
i
(x)。
我们只要找到 f
i
(x) 及 α
i
使
M
i=1
z
i
最小，即可得到高精度的强分类器 F 。然而，min
M
i=1
z
i
的全局最小化，每加入一个新的子分类器，都可能需要修改已有的子分类器，这样做的话训练复
杂度会很高。为了避免这个复杂的优化问题，AdaBoost 使用贪心策略，不修改已有子分类器的
形式，以线性加权方式加入新的子分类器，只要最小化当前代的样本归一化因子 z
i
，使
M
i=1
z
i
尽可能小。对训练误差进一步分析，可以得到下面的推论
推论 令 r
i
=
1
2
− ε
i
，如果存在 r > 0，对 ∀i 有 r
i
> r，则
1
m
m
k=1
I
F (x
k
)=y
k
⩽ exp(−2M r
2
)
http://www.ma-xy.com 15 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
上述推论表明：AdaBoost 的训练误差是以指数速度下降的，并且不需要知道下界 r。这正
是 Freund 和 Schapire 设计 AdaBoost 时所考虑的，AdaBoost 与 Boost 方法不同，它能适应弱
分类器各自的训练误差率。
(2) 泛化误差率。在 AdaBoost 提出之初，作者曾对算法的泛化能力进行过初步分析，得到
泛化误差估计与迭代次数和子/弱分类器的复杂度有关。为了使最终得到的组合/集成分类器具有
更好的泛化能力，应该按照所掌握的先验知识尽可能选择形式简单的子分类器，同时应当限制迭
代次数 M ，当 M 很大时，可能出现过拟合现象。然而，许多实验表明，AdaBoost 在迭代次数
很高时，并不会出现过拟合，如图 (1.11) 所示
图 1.11: Adaboost 误差率示意图
并且从图 (1.11) 右图可以看到，在训练误差达到 0 以后的一段时间内，AdaBoost 的测试
误差仍在下降，这是 AdaBoost 很“迷人”的地方。为了回答 AdaBoost 的泛化能力从何而来，
AdaBoost 的作者 Schapire 将统计学习中分类间隔分析的相关理论引入到 AdaBoost 的分析当
中：
定义 F =
i
α
i
f
i
(x) 的分类间隔为
margin
+
(x, y) = y
i
α
i
f
i
(x)
i
|α
i
| ∈ [−1, 1]
分类间隔的符号为正，则表示分类正确，反之为错误分类，其取值反应了分类结果的可信程度。
定理 设 D 是定义在 X × {−1, 1} 上的分布函数，训练样本集 S 依分布 D 独立随机采
样。若子分类器可行空间 f ∈ H 有限，C = {f : x →
f∈H
α
h
f(x)|α
h
⩾ 0,
h
α
h
= 1}，对
θ > 0, δ > 0，每一个 f ∈ C 以 1 − δ 的概率满足如下错误率限界8
P
D
(margin
+
(x, y) ⩽ 0) ⩽ P
s
(margin
+
(x, y) ⩽ θ) + O
1
√
m
log m log |H|
θ
2
+ log
1
δ
1
2
其中：P
s
是训练集的分类间隔分布，m 为样本数，子分类器 f 的可行空间大小是 |H|(通常以
VC 维度量)。
注意，上面的定理给出的泛化误差界 P
D
是非常松弛的，并且不具有渐进性，只有当训练集
中的样本数目很大时才有意义，而当样本量很小时，这一误差界并不准确。如何寻找一个更紧致
的泛化误差界以指导算法的设计仍然是一个困难的工作。
http://www.ma-xy.com 16 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
1996.Freund 在12中提出了 AdaBoost.M1 和 AdaBoost.M2 两种算法。AdaBoost.M1 即是
我们常见的 Discrate AdaBoost，而 AdaBoost.M2 是 M1 的泛化形式。该文的一个结论是：当
弱分类器使用简单分类方法时，boosting 的效果统一比 bagging 要好；当弱分类器使用 C4.5 时，
boosting 比 bagging 要好。1998.Schapire R E 和 Singer Y9提出更具一般性的 AdaBoost 形式，
提出自信率以改善 AdaBoost 的性能，并提出了解决多分类问题的 AdaBoost.MH(Real Boost)
和 AdaBoost.MR。事实上，Discrete 到 Real 的转变体现了古典集合到模糊集合的转变。
1.2.4
加法模型
Friedman2等从统计学角度出发，在非参数回归的基础上，给出了加法模型的前向顺序算法。
尽管这样解释受到了质疑，被认为不能有效解释 AdaBoost 的泛化能力，但在此理论基础上衍生
出了许多重要的 AdaBoost 算法，后面要介绍的 GBDT 就是其中一种，此外还有 LogitBoost、
fradient-boost-tree 以及用于解决概率回归的 ProbitBoost。
考虑二分类问题，并设置 y
k
∈ {−1, 1}。上面我们一共有 M 个弱分类器，并且最终的分类
器 (强分类器) 是 M 个弱分类器的组合。现在，我们将最终的强分类器写为7
F
M
(x) =
1
2
M
i=1
α
i
f
i
(x)
上式可以表示为
F
M
(x) = F
M−1
(x) +
1
2
α
M
f
M
(x)
这里将 F
M
(x) 作为直接的分类器，建立整体分类模型，设置模型的损失函数为
E =
m
k=1
e
−y
k
F
M
(x
k
)
当 F
M
(x
k
) = y
k
时，e
−y
k
F
M
(x
k
)
= e
−1
；当 F
M
(x
k
) = −y
k
时，e
−y
k
F
M
(x
k
)
= e
1
。
我们的目标是求参数 α = (α
1
, α
2
, . . . , α
M
) 以及 f
i
(x) 中的参数 θ，使 E 最小。这是一个非
常复杂的优化问题，并不易于求解 (这个地方好像与神经网络有关，以后再看)。下面，介绍前向
分步算法：每次只求一个 α
i
, f
i
(x)，其余 α
−i
, f
−i
(x) 保持不变。由此，可以将 E 进行拆分：固
定一组，待求一组。不失为一般性，我们假设求 α
M
, f
M
，于是 E 拆分为
E =
m
k=1
exp
−y
k
F
M−1
(x
k
) +
1
2
α
M
f
M
(x
k
)
=
m
k=1
exp
−y
k
F
M−1
(x
k
) −
1
2
y
k
α
M
f
M
(x
k
)
=
m
k=1
w
k
M
exp
−
1
2
y
k
α
M
f
M
(x
k
)
其中：w
k
M
= exp{−y
k
F
M−1
(x
k
)}，且
w
k
M
= 1，M > 1。
http://www.ma-xy.com 17 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
求最值，要将 E 对 α
M
和 f
M
求导。在此之前，将被 f
M
(x) 正确分类的样本集合记为 T
M
，
剩下误分类样本记为 M
M
，于是可以将上式拆分为
E = e
−
α
M
2
k∈T
M
w
k
M
+ e
α
M
2
k∈M
M
w
k
M
(1.1)
= e
−
α
M
2
m
k
=1
w
k
M
+
e
α
M
2
−
e
−
α
M
2
m
k=1
w
k
M
I
f
M
(x
k
)=y
k
其中：f
M
(x
k
) 是第 M 个分类器对第 k 个样本 x
k
的分类结果，y
k
为第 k 个样本的真实类别。现
在，我们再将 E 对 α
M
和 f
M
求导：
(1) 关于 f
M
的求导。注意到 w
k
M
是常量，因此
∂E
∂f
M
(θ)
=
e
α
M
2
− e
−
α
M
2
∂
∂f
M
(θ)
m
k=1
I
f
M
(x
k
)=y
k
上式与单一模型 J
M
=
m
k=1
w
k
M
I
f
M
(x
k
)=y
k
(这是第 M 个模型) 关于 f 求导是等价的。
(2) 关于 α
M
求导。注意，这里用 (1.1) 式比较方便，有
∂E
∂α
M
= −
1
2
e
−
α
M
2
k∈T
M
w
k
M
+
1
2
e
α
M
2
k∈M
M
w
k
M
令上式等于 0，有
α
M
= ln
k∈T
M
w
k
M
k∈M
M
w
k
M
我们令
ϵ
M
=
k∈M
M
w
k
M
m
k=1
w
k
M
=
m
k=1
w
k
M
I
f
M
(x
k
)=y
k
m
k=1
w
k
M
=
1 −
k∈T
M
w
k
M
m
k=1
w
k
M
上式用到了
m
k=1
w
k
M
=
k∈T
M
+
k∈M
M
将 ϵ
M
带入到 α
M
，我们有
α
M
= ln
1 − ϵ
M
ϵ
M
上面给出了
E
对
α
M
和
f
M
求导。根据
E
的计算公式
(
1.1)
，我们看到，在解出
α
M
和
f
M
(x) 之后，样本权重由下式更新
w
k
M+1
= w
k
M
exp
−
1
2
y
k
α
M
f
M
(x
k
)
http://www.ma-xy.com 18 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
由于
y
k
f
M
(x
k
) = 1 − 2I
f
M
(x
k
)=y
k
我们有
w
k
M+1
= w
k
M
exp
−
α
M
2
exp
α
M
I
f
M
(x
k
)=y
k
由于 exp(−
α
M
2
) 与 k 无关，对所有样本都有一个这样的因子，因此，我们可以将其忽略。这样，
我们就得到了样本权重的更新公式。
此外，对于 α
M
的选取，我们还有如下结论。我们选择 α
M
使指数误差函数最小，简写为
E =
k
w
k
e
−y
k
f
M
(x
k
)α
M
假设 f
M
(x
k
) 已有，记为 f
k
，且 y
k
∈ {−1, 1}，则
E =
k
w
k
e
−y
k
f
k
α
M
我们有
k
w
k
e
−y
k
f
k
α
M
⩽
k
1 − y
k
f
k
2
w
k
e
α
M
+
k
1 + y
k
f
k
2
w
k
e
−α
M
=
1 + ϵ
M
2
e
α
M
+
1 − ϵ
M
2
e
−α
M
令上式等于 0，我们可以找到最小的上界
α
′
M
=
1
2
ln
1 − ϵ
M
1 + ϵ
M
注意：这里只适用二分类情况 y
k
∈ {−1, 1}，但是它可以推广到多分类以及回归问题。上面，
我们将 boosting 方法转换成可加模型的指数误差优化模型，如果我们使用不同的目标函数，这
种转换可以引出一大类与 Adaboost 相似的算法。我们称这种多模型相加的模型为可加模型，称
这种逐步一次计算一个模型及参数的优化方法为前向分步算法或前向顺序算法。
1.2.5 GBDT
根据上面的加法模型，如果设置不同的弱分类器 f 和不同的损失函数，我们可以得到许多不
同的
boost
方法。我们以决策树作为弱分类器，构建的加法模型为提升树模型
(boost tree)
。将
整体分类函数记为
F
M
(
x
) =
M
i=1
f(x; θ
i
)
其中：f(x; θ
i
) 是第 i 个决策树，共有 M 个，θ
i
为决策树参数。我们可以将 F
M
进行拆分
F
M
(x) = F
M−1
(x) + f(x; θ
M
)
http://www.ma-xy.com 19 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
我们通过经验风险最小化来确定决策树参数 θ
M
ˆ
θ
M
= arg min
θ
M
m
k=1
L(y
k
, F
M
(x
k
))
其中：L 为损失函数。在加法模型中，我们使用的是指数损失函数，选用不同的损失函数，可以
得到不同的提升树。对于回归问题，我们可以采用
1
2
(y
k
− F
M
(x
k
))
2
或者 |y
k
− F
M
(x
k
)| 作为损
失函数；对于分类问题，我们使用指数损失，当然，我们还可以选择更一般的损失函数。关于损
失函数的种类，我们在前面的神经网络部分有详细的介绍。
加法模型中，我们使用指数损失处理了二分类问题，现在，我们来处理回归问题。在前向模
型中，给定当前模型 F
i−1
(x)，需要求解
ˆ
θ
i
= arg min
θ
i
m
k=1
L(y
k
, f(x
k
; θ
i
))
我们使用离差平方和作为损失函数
L(y
k
, f(x
k
)) = (y
k
− f(x
k
))
2
于是有
min
θ
i
J(θ
i
) =
m
k=1
(y
k
− F
i−1
(x
k
) − f(x
k
; θ
i
))
2
=
m
k=1
(r
k
i−1
− f(x
k
; θ
i
))
2
其中：r
k
i−1
= y
k
− F
i−1
(x
k
) 为第 i − 1 次的误差。也就是说，上述过程是用第 i 个模型 f
i
来拟
合模型的第 i − 1 次的残差 r
i−1
。所以，对回归问题而言，AdaBoost 只需要简单得拟合前模型
F
i−1
的误差
r
i−1
即可。
上面仍然是在介绍加法模型，下面来具体的介绍 GBDT(梯度提升模型)。在上面的加法模
型中，当损失函数 L 是平方损失或者指数损失时，每一步优化是简单的，但对于一般的损失函
数 L 而言则不是易于处理的，比如绝对损失和 Huber 损失等。为此，Freidman 提出 Gradient
Boosting5，GBDT 的核心在于：每一个子分类器 f
i
(x) ≜ f(x; θ
i
) 学习的是之前所有分类器的累
加之和的残差。每一次迭代减少上一模型的残差，并且在残差减少的梯度方向上建立新的组合模
型。在此之前，我们先来看一个引例。
考虑一般的线性回归模型
ˆy = f (x; θ
1
) = w
T
x + b
我们用 f 对 y 进行估计后，二者之间会有一个误差 ϵ ∈ R
m
(m 个样本)。如果我们想要改进 f ，
一个可行的方法是缩小它的残差，那么，我们可以对 y, f(x) 的残差进行估计，把估计的残差在
加入到 f 中，即
ˆy = f + ˆε
http://www.ma-xy.com 20 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
为了便于处理，我们仍然用 f 对 ε 进行估计
ˆε = f(x; θ
2
)
于是有
ˆy = f (x; θ
1
) + f(x; θ
2
)
用上式对 y 进行估计后，必然会有新的残差，我们仍然对新的残差进行估计，然后把估计的残差
加入到上一个模型当中，如此反复下去
ˆy = f
1
ˆy = f
1
+ f
2
.
.
.
ˆ
y
=
f
1
+
f
2
+
·
+
f
M
将上述方法规范化，写成加法模型的形式
F
i
(x) = F
i−1
(x) + α
i
f
i
(x; θ
i
)
F
M
=
M
i=1
α
i
f
i
(x)
并设置目标
{θ
i
, α
i
}
M
i=1
= arg min
θ,α
J(θ, α) =
m
k=1
L(y
k
, F
M
(x
k
))
上述优化问题较复杂，我们采用前面介绍的分步前向算法，有
(θ
i
, α
i
) = arg min
m
k=1
L(y
k
, F
i−1
(x
k
) + α
i
f
i
(x
k
; θ
i
))
现在的问题是，如何求解新加入的 f
i
和 α
i
？可以观察到 F
i
(x) = F
i−1
(x) + α
i
f
i
(x; θ
i
) 和优化模
型中的更新方程 x
i
= x
i−1
+ α
i
∆x
i
很相似，如果将 f
i
(x; θ
i
) 视为 ∆F
i
(x)，则有
F
i
= F
i−1
+ α
i
∆F
i
那么，我们能否将 f
i
视为目标 J 的梯度方向呢？我们在函数空间上形式的 对 F 求导，有
g
i
(x) = −
∂E
[
L
(
y, F
(
x
))]
∂F (x)
F (x)=F
i−1
(x)
g
i
(x) 即为 F 的负梯度方向 (这里的 g
i
就等价于前面的残差 r
i
)。为了更新 F ，接下来我们只要
求出步长 α
i
即可
α
i
= arg min
α
m
k=1
L(y
k
, F
i−1
(x
k
) + αf
i
(x
k
; θ
i
))
http://www.ma-xy.com 21 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
于是有下面的算法 (2)
算法 2 GBDT
1: F
0
(x) = f
0
(x)。
2: for i = 1, 2, . . . , M do
3: // 计算梯度 g
i
4: for k = 1, 2, . . . , m do
5: g
i
(x
k
) = −
∂E[L(y,F (x
k
))]
∂F (x
k
)
F (x
k
)=F
m−1
(x
k
)
6: end for
7: 计算步长 α
i
。α
i
= arg min E[L(y, F
i−1
(x) + α
i
g
i
(x))]
8: 计算更新量。f
i
(x) = α
i
g
i
(x)
9: 更新函数。F
i
(x) = F
i−1
(x) + f
i
(x) = F
i−1
(x) + α
i
g
i
(x)
10: end for
11: 输出。F = F
M
(x) = f
0
+
M
i=1
α
i
f
i
(x)
上面介绍了一般形式的 GBDT 算法，下面，我们给出一些损失函数 L 下的 GBDT 算法。
L_2 - TreeBoost
考虑二分类问题 y
k
∈ {−1, 1}，使用决策树作为子分类器，使用 negative binomial log-
likelihood 作为损失函数 (在加法模型中，我们使用了指数损失)，log 损失函数定义为
L(y, F ) = log(1 + e
−2yF
)
现在，我们用上面介绍的 GBDT 算法来求解上述问题：
Step1. 求第一个分类器
F
0
= f
0
= arg min J(F ) =
m
k=1
L(y
k
, F )
J(F ) 关于 F 求导，有
∂
∂F
m
k=1
L(y
k
, F )
=
m
k=1
e
−2y
k
F
− 2y
k
1 + e
−2y
k
F
=
k:y
k
=1
−2e
2F
1 + e
−2F
+
k:y
k
=−1
2e
2F
1 + e
2F
令上式为 0，有
F
0
(x) =
1
2
log
1 + ¯y
1 − ¯y
http://www.ma-xy.com 22 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
Step2. 对 g
i
(x) 进行求解
g
i
(x
k
) = −
∂L(y
k
, F )
∂F
F =F
i−1
=
−2y
k
e
−2y
k
F
1 + e
−2y
k
F
F
=
F
i−1
=
−2y
k
e
−2y
k
F
i−1
(x
k
)
1 + e
−2y
k
F
i−1
(x
k
)
=
2y
k
1 + e
2y
k
F
i−1
(x
k
)
Step3. 用决策树 f
i
对 g
i
(x) 进行估计，求解 θ
i
。
Step4. 用一个牛顿法求步长 α
i
α
i
= arg min
α
m
k=1
log(1 + exp{−2y
k
(F
i−1
(x
k
) + αf(x
k
; θ
i
))})
我们仍然使用决策树作为基本分类器，仍然要划分一个根节点
α
li
= arg min
α
x
k
∈R
li
log(1 + exp{−2y
k
(F
i−1
(x
k
) + αf
li
)})
或者
r
li
= α
li
h
li
= arg min
r
x
k
∈R
li
log(1 + exp{−2y
k
(F
i−1
(x
k
) + r)}) (1.2)
F
i
(x) = F
i−1
(x) + r
li
I(x ∈ R
li
)
我们可以使用 a single Newton-Raphson step 来求式 (1.2)
r
li
=
x
k
∈R
li
g
k
x
k
∈R
li
|g
k
|(2 − |g
k
|)
综上，有算法 (3)
http://www.ma-xy.com 23 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
算法 3 L2-TreeBoost
1: F
0
(x) =
1
2
log
1+¯y
1−¯y
。
2: for i = 1, 2, . . . , M do
3: // 计算梯度 g
i
4: for k = 1, 2, . . . , m do
5: g
k
= −
2y
k
1+e
2y
k
F
i−1
(x
k
)
6: end for
7: {R
li
}
L
l=1
= L_terminal_mode_tree({x
k
, g
k
}
m
k=1
)
8: r
li
=
∑
x
k
∈R
li
g
k
∑
x
k
∈R
li
|g
k
|(2−|g
k
|)
l = 1, 2, . . . , L
9: F
i
(x) = F
i−1
(x) + r
li
I(x ∈ R
li
)；
10: end for
设
p
+
(x) =
ˆ
P (y = 1|x) = 1/(1 + exp{−2F
M
(x)})
p
−
(x) =
ˆ
P (y = −1|x) = 1/(1 + exp{2F
M
(x)})
则最终的分类估计为
ˆy(x) = 2I(c(−1, 1)p
+
> c(1, −1)p
−
(x)) − 1
其中：c(ˆy, y) is the cost associated with predicting ˆy when the truth is y。例如 c(ˆy, y) = 1。
最小二乘损失：L2-Boost
设置损失函数为平方损失 L(y, F ) =
1
2
(y − F )
2
，我们有算法 (4)
算法 4 L2-Boost
1: F
0
(x) = ¯y。
2: for i = 1, 2, . . . , M do
3: // 计算梯度 g
i
4: for k = 1, 2, . . . , m do
5: g
k
i
= y
k
− F
i−1
(x
k
)
6: end for
7: 求参数 θ
i
和步长 α
i
。(θ
i
, α
i
) = arg min
α,θ
m
k=1
[g
k
− αf(x
k
; θ)]
2
8: F
i
(x) = F
i−1
(x) + α
i
f
i
(x; θ
i
)；
9: end for
http://www.ma-xy.com 24 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
绝对值损失：LAD-TreeBoost
设置损失函数为绝对值损失 L(y, F ) = |y − F |。
(1) 我们先来求解负梯度方向
g
k
i
= g
i
(x
k
) = −
∂L(y
k
, F (x
k
))
∂F (x
k
)
F (x)=F
i−1
(x
k
)
= sign[y
k
− F
i
−
1
(x
k
)]
(2) 用 f
i
去拟合 g
i
，求得 θ
i
，然后求步长 α
i
α
i
= arg min
α
m
k=1
L(y
k
, F
i−1
(x
k
) + αf(x
k
; θ
i
))
= arg min
α
m
k=1
|y
k
− F
i−1
(x
k
) − αf(x
k
; θ
i
)|
= arg min
α
m
k=1
|f(x
k
; θ
i
| ·
y
k
− F
i−1
(x
k
)
f(x
k
; θ
i
)
− α
= median
w
y
k
− F
i−1
(x
k
)
f(x
k
; θ
i
)
m
k=1
, w
k
= |f (x
k
; θ
i
)|
其中：median
w
是权重 w
i
的中值，f
i
(x
k
, ; θ
i
) 是一个 L 个末端节点的决策树。关于上面的计算，
我们把参数 P = {α
i
, θ
i
} 分割成 L 个子集 P
1
, P
2
, . . . , P
L
，梯度是相对分段的。
α
li
= median
w
y
k
− F
i−1
(x
k
)
f(x
k
; θ
i
)
x
k
∈ R
li
w
k
= |f
i
(x
k
; θ
i
)| (1.3)
L 为决策树叶节点数，R
li
是 x 的空间。由于 {f(x
k
; θ
i
)|x
k
∈ R
li
} 的值是全部相等的 f (x
k
; θ
i
) =
f
li
I(x
k
∈ R
li
)，因此，对于式 (1.3) 我们有
α
li
=
1
f
li
median{y
k
− F
i−1
(x
k
)|x
k
∈ R
li
}
并且，GBDT 的更新公式变为
F
i
(x) = F
i−1
(x) + median{y
k
− F
i−1
(x
k
)|x
k
∈ R
li
}I(x ∈ R
li
)
上面给出了基于绝对误损失的梯度提升树，下面，我们给出
LAD-TreeBoost
算法的伪代码
(5)
算法 5 LAD-TreeBoost
1: F
0
(x) = median{y
k
}
m
k=1
。
2: for i = 1, 2, . . . , M do
3: 计算梯度 g
k
= sign(y
k
− F
i−1
(x
k
))
4: {R
li
}
L
l=1
= L_terminal_node_tree({x
k
, g
k
}
m
k=1
)
5: r
li
= median
x∈R
li
(y
k
− F
i−1
(x
k
)), l = 1, 2, . . . , L 。
6: F
i
(x) = F
i−1
(x) + r
li
I(x ∈ R
li
)
7: end for
http://www.ma-xy.com 25 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
Huber 损失
下面，我们将损失设定为 Huber 损失，该损失是 Huber 于 1964 年提出，其形式为
L(y, F ) =
1
2
(y − F )
2
|y − F | ⩽ δ
δ(|y − F | −
δ
2
) |y − F | > δ
(1)L 关于 F 求导，有
g
k
= −
∂L(y
k
, F (x
k
))
∂F (x
k
)
F (x)=F
i−1
(x
k
)
=
y
k
− F
i−1
(x
k
) |y − F | ⩽ δ
δsign(y
k
− F
i−1
(x
k
)) |y − F | > δ
(2) 步长 α
i
为
α
i
= arg min
α
m
k=1
L(y
k
, F
i−1
(x
k
) + αf(x
k
; θ
i
))
转折点 δ 依赖于迭代次数 i，详细的说，δ
i
是 {|y
k
− F i − 1(x
k
)|}
m
k=1
的 α 分位数。
我们选用决策树作为基本分类器 (子分类器)，使用分割策略在每个 R
li
中查找 α
i
α
li
= arg min
α
x
k
∈R
li
L(y
k
, F
i
−
1
(x
k
) + αf
li
)
最终的更新公式为
F
i
(x) = F
i−1
(x) + r
li
I(x ∈ R
li
)
其中：r
li
= α
li
f
li
= arg min
r
x
k
∈R
li
L(y
k
, F
i−1
(x
k
) + r)。Huber1964 年给出 r
li
的简单一步估
计
˜r
li
= median
x
k
∈R
li
{r
i−1
(x
k
)}
这里 {r
i−1
}
M
i=1
are the current redsiduals r
l
i−1
(x
k
) = y
k
− F
i−1
(x
k
)，最终 r
li
的近似为
r
li
= ˜r
li
+
1
N
li
x
k
∈R
li
sign(r
i−1
(x
k
) − ˜r
li
) · min(δ
i
, |r
i−1
(x
k
| − ˜r
li
)
其中：N
li
是第 l 个节点的样本数。下面，给出 Huber M-TreeBoost 算法 (6)
http://www.ma-xy.com 26 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
算法 6 Huber M-TreeBoost
1: F
0
(x) = median{y
k
}
m
k=1
。
2: for i = 1, 2, . . . , M do
3: r
i−1
(x
k
) = y
k
− F
i−1
(x
k
), k = 1, 2, . . . , m；
4: δ
i
= quantile
α
{|r
i−1
(x
k
)|}
m
k=1
；
5:
g
k
=
r
i−1
(x
k
) |r
i−1
(x
k
)| ⩽ δ
i
δ
i
sign(r
i−1
(x
k
)) |r
i−1
(x
k
)| > δ
i
6: {R
li
}
L
l=1
= L_terminal_node_tree({x
k
, g
k
}
m
k=1
)
7: ˜r
li
= median
x
k
∈R
li
{r
i−1
(x
k
)}, l = 1, 2, . . . , L
8: r
li
= ˜r
li
+
1
N
li
x
k
∈R
li
sign(r
i−1
(x
k
) − ˜r
li
) · min(δ
i
, |r
i−1
(x
k
| − ˜r
li
), l = 1, 2, . . . , L 。
9: F
i
(x) = F
i−1
(x) + r
li
I(x ∈ R
li
)
10: end for
多分类 Boost
上面的 GBDT 都是处理二分类问题的，下面我们考虑一个 C 分类问题。定义损失函数为
L({y
c
, F
c
(x)}
C
c=1
) = −
C
c=1
y
c
log p
c
(x)
其中：y
c
= 1 ∈ {0, 1}，p
c
(x) = P (y
c
= 1|x)，we use the symmetric multiple logistic transform
F
c
(x) = log p
c
(x) −
1
C
C
c=1
log p
c
(x)
or equivalently
p
c
(x) =
e
F
c
(x)
c
e
F
c
(x)
先来求梯度
g
k
c
= −
∂L({y
k
c
, F
c
(x
k
)}
C
c=1
)
∂F
c
(x
k
)
{F
c
(x
k
)=F
c,i−1
(x
k
)}
C
1
=y
k
c
− p
c
(x
k
)
对于残差 {y
k
c
− p
c
(x
k
)}
m
k=1
，我们使用 C 个树，每个树有 L 个叶节点，将样本空间划分为 R
cli
r
cli
= arg min
r
x
k
∈R
cli
ϕ
c
(y
k
c
, F
c,i−1
(x
k
) + r)
其中：ϕ
c
= −y
c
log p
c
(x)。C 个函数每一个的更新公式为
F
c,i
(x) = F
c,i−1
(x) + r
cli
I(x ∈ R
cli
)
http://www.ma-xy.com 27 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
我们仍然用一个 a single Newton-Raphson 来逼近 r
cli
，有
r
cli
=
C − 1
C
x
k
∈
R
cli
g
k
c
x
k
∈R
cli
|g
k
c
|(1 − |g
k
c
|)
综上，我们有算法 (7)
算法 7 Lk-TreeBoost
1: F
c0
(x) = 0, c = 1, 2, . . . , C。
2: for i = 1, 2, . . . , M do
3: p
c
(x) =
e
F
c
(x)
∑
c
e
F
c
(x)
, c = 1, 2, . . . , c；
4: for c = 1, 2, . . . , C do
5: g
k
c
= y
k
c
− p
c
(x
k
), k = 1, 2, . . . , m；
6: {R
cli
}
L
l=1
= L_terminal_node_tree({x
k
, g
k
c
}
m
k=1
)
7: r
cli
=
C−1
C
∑
x
k
∈R
cli
g
k
c
∑
x
k
∈R
cli
|g
k
c
|(1−|g
k
c
|)
, l = 1, 2, . . . , L ；
8: F
c,i
(x) = F
c,i−1
(x) + r
cli
I(x ∈ R
cli
)
9: end for
10: end for
11: 输出 {F
c,M
(x)}
C
c=1
{F
c,M
(x)}
C
c=1
即是最终的分类器，通过 {F
c,M
(x)}
C
c=1
我们可以获得 {p
c,M
(x)}
C
c=1
的一致估
计量
ˆ
C(x) = arg min
1⩽c⩽C
C
c
′
=1
cost(c, c
′
)p
c
′
,M
(x)
其中：cost(c, c
′
) is the cost associated with predicting the cth class with the truth is c
′
.
注：1. GBDT 是串行运行的，并不适用于并行处理，因为当前时刻的迭代与上一时刻迭代
结果有关。关于 GBDT 的并行处理，以后再详细讨论；2. 对于加法模型而言，我们将其视为一
个整体分类/回归模型，那么前面介绍的许多回归模型的改进方法 (例如：正则化方法) 都可以应
用到加法模型上。
1.2.6 XGboost
仍然继续考虑前面的加法模型
F
M
(x) =
M
i
=1
α
i
f
i
(x; θ
i
)
F
i
(x) = F
i−1
(x) + α
i
f
i
(x; θ
i
)
我们设置加法模型的损失函数 L 以及优化的目标函数
min J(θ, α) =
m
k=1
L(y
k
, F
M
(x
k
))
http://www.ma-xy.com 28 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
像前面的回归模型那样，我们对上述目标加上正则项 Ω(f)，有
min
m
k=1
L(y
k
, F
M
(x
k
)) +
M
i=1
Ω(f
i
)
假设基本分类器 f
i
是决策树，我们不能用 SGD 等方法来寻找 f，因为 f 是决策树而不是
数值向量 (参数)。仍然采用加法模型中的分步前向算法来求解单一的树 f
i
及 α
i
(求解 f
i
时，
f
j
, j = 1, 2, . . . , l − 1 是已知的)，于是第 i 轮的目标为
(θ
i
, α
i
) = arg min
α,θ
m
k=1
L(y
k
, F
i
(x
k
)) +
i
j=1
Ω(f
j
)
= arg min
θ,α
m
k=1
L(y
k
, F
i
−
1
(x
k
) + αf
i
(x
k
; θ)) +
i−1
j=1
Ω(
f
j
) + Ω(
f
i
)
= arg min
α,θ
m
k=1
L(y
k
, F
i−1
(x
k
) + αf
i
(x
k
; θ)) + Ω(f
i
) + constant
设置损失函数是离差平方 L(y, F ) = (y − F )
2
，于是有
J(θ, α) =
m
k=1
L(y
k
, F
i−1
(x
k
) + αf
i
(x
k
; θ)) + Ω(f
i
) + constant (1.4)
=
m
k=1
(y
k
− F
i−1
(x
k
) − αf
i
(x
k
; θ))
2
+ Ω(f
i
) + constant
=
m
k=1
([y
k
− F
i−1
(x
k
)] − αf
i
(x
k
; θ))
2
+ Ω(f
i
) + constant
现在，对 L 运用如下的泰勒展开公式
f(x + ∆x) ≈ f (x) + f
′
(x)∆x +
1
2
f
′′
(x)∆x
2
(1.5)
上述的 ∆x 相当于我们的 f
i
(x
k
; θ)、x 相当于 F 、f 相当于目标 L。定义
g
k
=
∂L(y
k
, F (x
k
))
∂F (x
k
)
F (x)=F
i−1
(x)
h
k
=
∂
2
L(y
k
, F (x
k
))
∂F (x
k
)
2
F (x)=F
i−1
(x)
则 L 的泰勒展开为
L(x
k
, F
i−1
(x
k
) + αf
i
(x
k
; θ)) ≈ L(y
k
, F
i
(x
k
)) + g
k
αf
i
(x
k
; θ) +
1
2
h
k
(αf
i
(x
k
; θ))
2
这里，L 相当于泰勒公式 (1.5) 中的 f 、F
i−1
(x
k
) 相当于 x、g
k
相当于 ∆x、h
k
相当于 ∆x
2
。式
(1.4) 的目标 J 变为
J(θ, α) =
m
k=1
L(y
k
, F
i−1
(x
k
) + αf
i
(x
k
; θ)) + Ω(f
i
) + constant
≈
m
k=1
L(y
k
, F
i
(x
k
)) + g
k
αf
i
(x
k
; θ) +
1
2
h
k
(αf
i
(x
k
; θ))
2
+ Ω(f
i
) + constant (1.6)
http://www.ma-xy.com 29 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
如果对上面 L 的展开不是很清楚，可以看下面这个例子。考虑平方损失 L 的泰勒展开，L
对于 F 形式上 的一阶导数为
g
k
=
∂L(y
k
, F (x
k
))
∂F (X
K
)
F (x)=F
i−1
(x)
=
∂(y
k
− F (x
k
))
2
∂F (x
k
)
F (x)=F
i−1
(x)
= 2(y
k
− F (x
k
))
L 对于 F 形式上 的二阶导数为
h
k
=
∂
2
L(y
k
, F (x
k
))
∂F (x
k
)
2
F (x)=F
i−1
(x)
=
∂
2
(y
k
− F (x
k
))
2
∂F (x
k
)
2
F (x)=F
i−1
(x)
=
∂2(y
k
− F (x
k
))
∂F (x
k
)
F (x)=F
i−1
(x)
= 2
注意到式 (1.6) 的 L(y
k
, F
i−1
(x
k
)) 是常量，可以移到 constant 中。于是，对 L 进行泰勒展
开后，我们的目标是求 α
i
, f
i
(或者写为 α
i
, θ
i
) 使得下面的目标最小
J(θ, α) =
m
k=1
g
k
αf
i
(x
k
; θ) +
1
2
h
k
(αf
i
(x
k
; θ))
2
+ Ω(f
i
) (1.7)
上述目标是由式 (1.6) 去掉 constant 得到的，最优解 α
∗
, θ
∗
即为 α
i
, θ
i
。
上面的 GBDT 是基于梯度的 boost 方法，而这里的 XGboost 是基于二阶导数的，我们称之
为 NewtonBoost。给出 Newton Boost 的一般算法框架 (8)
算法 8 Newton Boost
1: F
0
(x) = f
0
(x) = arg min
θ
m
k=1
L(y
k
, f
0
(x
k
))。
2: for i = 1, 2, . . . , M do
3: g
k
i
=
∂L
(
y
k
,F
(
x
k
))
∂F (X
K
)
F (x)=F
i−1
(x)
, k = 1, 2, . . . , m；
4: h
k
i
=
∂
2
L(y
k
,F (x
k
))
∂F (X
K
)
2
F (x)=F
i−1
(x)
, k = 1, 2, . . . , m；
5: θ
i
, α
i
= arg min
θ,α
m
k=1
g
k
αf
i
(x
k
; θ) +
1
2
h
k
(αf
i
(x
k
; θ))
2
+ Ω(f
i
)
6: F
i
(x) = F
i−1
(x) + α
i
f
i
(x)；
7: end for
下面，来考虑一个实际的决策树 f
i
(x)
f
i
(x) = w
q( x)
http://www.ma-xy.com 30 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
或者写为
f
i
(x) =
L
j=1
w
j
I(x ∈ R
j
)
其中：f
i
(x) 是含有 L 个叶节点的决策树，q(x) : R
n
→ {1, 2, . . . , L}，q(x
k
) 将样本 x
k
投入到 L
个叶节点当中，w ∈ R
L
是 L 个叶节点的权重。定义树 f
i
的正则项为
Ω(f
i
) = γL +
1
2
λ
L
j=1
w
2
j
其中：γL 表示惩罚树 f
i
的叶节点数量，w
j
表示权重的惩罚。
记样本集 S 中被投放到 j(j ∈ {1, 2, . . . , L}) 的子样本集 R
j
= {k|q(x
k
) = j}, j = 1, 2, . . . , L，
于是目标 (1.7) 可以具体写为
J(θ, α) =
m
k=1
g
k
αw
q (x
k
)
+
1
2
h
k
α
2
w
2
q (x
k
)
+ γL +
1
2
λ
L
j=1
w
2
j
=
L
j=1
k
∈
R
j
g
k
αw
j
+
1
2
k∈R
j
(
h
k
α
2
+
λ
)
w
2
j
+
γL
(1.8)
上面试和 L 独立的二次函数，我们先忽略 α，令 G
j
=
k∈R
j
g
k
，H
j
=
k∈R
j
h
k
，则上述目标
(1.8) 写为
J(w, γ) =
L
j=1
k∈R
j
g
k
w
j
+
1
2
k∈R
j
(h
k
+ λ)w
2
j
+ γL
=
L
j=1
G
j
w
j
+
1
2
(H
j
+ λ)w
2
j
+ γL
假设树 f
i
的结构 q(x) 是固定的，那么最优叶节点权重 w 及最优值为
w
∗
j
= −
G
j
H
j
+ λ
J
∗
= −
1
2
L
j
=1
G
2
j
H
j
+ λ
+ γL
注：对于 f = Gx +
1
2
Hx
2
, H > 0，最小 x 在 x = −
G
H
处获得，获得最小值为 f = −
1
2
G
2
H
。
下面我们给出单一树的生成。
Step1. 列出可能的树的结构 q(x)；
Step2. 计算 q(x) 的划分
J(x) = −
1
2
L
j=1
G
2
j
H
j
+ α
+ γL
http://www.ma-xy.com 31 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
Step3. 找到最好的树的结构，并使用最优的权重
w
∗
j
= −
G
j
H
j
+ λ
不断地枚举不同树的结构，利用上式来寻找出一个最优结构的树，加入到模型中，再重复这
样的操作。但是，这种可能的树的结构 q(x) 会有无穷多个，为此，我们使用 Greedy learning 来
生成树，每一次尝试去对已有的叶子加入一个分割。对于一个具体的分割方案，我们可以获得的
增益可以由如下方法计算：
Step1. 设置树的初始深度为 0；
Step2. 对树的每个叶子节点尝试添加一个分割 (split) 节点，添加分割节点后的目标改变量为
Gain =
G
2
L
H
L
+ λ
+
G
2
R
H
R
+ λ
−
(G
L
+ G
R
)
2
H
L
+ H
R
+ λ
− γ
其中：
G
2
L
H
L
+λ
是分割的左端的得分，
G
2
R
H
R
+λ
是分割的右端的得分，
(G
L
+G
R
)
2
H
L
+H
R
+λ
是不分割的得分，γ
是添加节点分割带来的复杂度。
对于 XGboost 更详细的介绍可以参考106。文11分析了 XGboost 的代码及应用。下面简单
介绍两个集成学习的“重器”——XGboost 和 LightGBM。
注：如果不将 GBDT 和 XGboost 中的函数 f 设置为具体的分类器 (比如 f 为决策树)，也
许可以在泛函问题上进行讨论。
1.2.7 应用示例-XGboost
XGboost
是 Tianqi Chen 开发的 C++ 的集成学习工具，并提供了 Python、R 和 Scala 等
的 API。XGboost 的安装可以在网上查找，XGboost 在 Python 下的参数解释可以参考下面代
码中的注释部分
®
。
1 #−−−−−−−−−−−−−−−XGboost 在 python 下 的 参 数 解 释−−−−−−−−−−−#
2 #
3 # General Parameters （ 常 规 参 数 ）
4 # 1 . booster [ d e f a u lt=gb tr ee ] ： 选 择 基 分 类 器 ， gb tr ee : tree−based models/ g bline a r :
l i n e a r models
5 # 2 . s i l e n t [ d e f a u l t =0]: 设 置 成 1 则 没 有 运 行 信 息 输 出 ， 最 好 是 设 置 为 0 .
6 # 3 . nthread [ defaul t to maximum number o f threads avai l a b l e i f not set ] ： 线 程 数
7
8 # Booster Parameters （模 型 参 数 ）
9 # 1 . eta [ d e f a u l t = 0.3]: shrinkage 参 数， 用 于 更 新 叶 子 节 点 权 重 时 ， 乘 以 该 系 数， 避 免 步 长 过
大 。 参 数 值 越 大 ， 越 可 能 无 法 收 敛 。 把 学 习 率 eta 设 置 的 小 一 些 ， 小 学 习 率 可 以 使 得 后 面 的 学 习 更 加 仔
细 。
10 # 2 . min_child_weight [ d e f a u lt =1]: 这 个 参 数 默 认 是 1 ， 是 每 个 叶 子 里 面 h 的 和 至 少 是 多 少 ，
对 正 负 样 本 不 均 衡 时 的 0−1 分 类 而 言 ， 假 设 h 在 0.0 1 附 近 ， min_child_weight 为 1 意 味 着 叶 子 节 点
中 最 少 需 要 包 含 100 个 样 本 。 这 个 参 数 非 常 影 响 结 果， 控 制 叶 子 节 点 中 二 阶 导 的 和 的 最 小 值 ， 该 参 数 值 越
小 ， 越 容 易 o v e r f i t t i n g 。
11 # 3 . max_depth [ defaul t =6]: 每 颗 树 的 最 大 深 度 ， 树 高 越 深 ， 越 容 易 过 拟 合 。
http://xgboost.readthedocs.io/en/latest/
®
http://blog.csdn.net/a819825294/article/details/51206410
http://www.ma-xy.com 32 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
12 # 4 . max_leaf_nodes : 最 大 叶 结 点 数 ， 与max_depth作 用 有 点 重 合。
13 # 5 .gamma [ d e f a u l t =0] ： 后 剪 枝 时 ， 用 于 控 制 是 否 后 剪 枝 的 参 数 。
14 # 6 . max_delta_step [ d e f ault =0] ： 这 个 参 数 在 更 新 步 骤 中 起 作 用 ， 如 果 取 0 表 示 没 有 约 束 ， 如 果
取 正 值 则 使 得 更 新 步 骤 更 加 保 守。 可 以 防 止 做 太 大 的 更 新 步 子 ， 使 更 新 更 加 平 缓 。
15 # 7 . subsample [ defa u l t =1] ： 样 本 随 机 采 样， 较 低 的 值 使 得 算 法 更 加 保 守 ， 防 止 过 拟 合 ， 但 是 太
小 的 值 也 会 造 成 欠 拟 合 。
16 # 8 . colsample_bytree [ d e f ault =1] ： 列 采 样 ， 对 每 棵 树 的 生 成 用 的 特 征 进 行 列 采 样 . 一 般 设 置
为 ： 0.5−1
17 # 9 . lambda [ d e f a u l t =1] ： 控 制 模 型 复 杂 度 的 权 重 值 的 L2正 则 化 项 参 数， 参 数 越 大， 模 型 越 不 容
易 过 拟 合 。
18 # 1 0. alpha [ d e f a u l t =0]: 控 制 模 型 复 杂 程 度 的 权 重 值 的 L1 正 则 项 参 数 ， 参 数 值 越 大 ， 模 型 越
不 容 易 过 拟 合 。
19 # 1 1. scale_pos_weight [ d e f a u l t =1] ： 如 果 取 值 大 于 0 的 话 ， 在 类 别 样 本 不 平 衡 的 情 况 下 有 助 于
快 速 收 敛 。
20
21 # Learning Task Parameters （ 学 习 任 务 参 数 ）
22 # 1 . o b j e c t i v e [ default=re g : l i n e a r ] 定 义 学 习 任 务 及 相 应 的 学 习 目 标 ， 可 选 的 目 标 函 数 如
下 ：
23 # “ reg : l i n e a r ” – 线 性 回 归 。
24 # “ reg : l o g i s t i c ” – 逻 辑 回 归 。
25 # “ binary : l o g i s t i c ” – 二 分 类 的 逻 辑 回 归 问 题 ， 输 出 为 概 率 。
26 # “ binary : l o git r aw ” – 二 分 类 的 逻 辑 回 归 问 题 ， 输 出 的 结 果 为wTx。
27 # “ count : poi ss on ” – 计 数 问 题 的 pois son 回 归， 输 出 结 果 为 poiss on 分 布 。 在 poiss on 回
归 中 ， max_delta_step 的 缺 省 值 为 0 . 7 。 ( used to s af eg ua rd opt imiza ti on )
28 # “ multi : softmax ” – 让XGBoost采 用 softmax 目 标 函 数 处 理 多 分 类 问 题， 同 时 需 要 设 置 参
数 num_class （ 类 别 个 数）
29 # “ multi : s oft pro b ” – 和 softmax 一 样 ， 但 是 输 出 的 是 ndata * n c l a s s 的 向 量 ， 可 以 将 该
向 量 reshape 成 ndata 行 n c lass 列 的 矩 阵 。 没 行 数 据 表 示 样 本 所 属 于 每 个 类 别 的 概 率 。
30 # “ rank : pai r wis e ” – s e t XGBoost to do ranking t ask by minimizing the pai r wis e
l o s s
31 # 上 面 的 参 数 形 式 和MATLAB等 的 形 式 一 致 ： 例 如 ： ’ ob j e c t i v e ’ : ’ binary : l o g i s t i c ’ 表 示 因 变 量
y 是 二 分 类 变 量 ， 用 的 回 归 函 数 是 l o g i s t i c s 回 归 。
32
33 # 2 . ’ eval_metric ’ The c h o ices are l i s t e d below ， 评 估 指 标 :
34 # “ rmse ” : ro ot mean square e r r o r
35 # “ l o g l o s s ” : nega tive log−l i k e l i h o o d
36 # “ error ” : Binary c l a s s i f i c a t i o n e r r o r ra t e . I t i s c a l culate d as #(wrong c ases )
/#( a l l c a ses ) . For the pred i c tion s , the ev alu ati on w i l l regard the i nstan c e s with p r e d i c tion
value l a r g e r than 0.5 as p o s i t i v e inst anc es , and the ot her s as negat iv e i n stanc e s .
37 # “ merror ” : M ulti c l a ss c l a s s i f i c a t i o n e r r o r ra te . I t i s c alcula t e d as #(wrong
cas e s )/#( a l l c ase s ) .
38 # “ m lo gl os s ” : M ulti c l ass l o g l o s s
39 # “ auc ” : Area under the curve f o r ranking ev alu ati on .
40 # “ ndcg ” : Normalized Discounted Cumulative Gain
41 # “map” : Mean average p r e c is i o n
42 # “ndcg@n” , ”map@n” : n can be assig ned as an i n t e g e r to cut o f f the top
p o s i t i o ns in the l i s t s f o r ev alu ati on .
43 # “ ndcg−“ , ”map−“ , ” ndcg@n−“ , ”map@n−“ : In XGBoost, NDCG and MAP w i l l
ev aluat e the s cor e o f a l i s t without any p o s i t i v e samples as 1 . By adding “−” in the
evaluati on metric XGBoost w i l l eval uate t hes e scor e as 0 to be c o n s i s t e n t under some
con d i tio n s .
44 # 3 . lambda [ d e f a u l t =0] L2 正 则 的 惩 罚 系 数
45 # 4 . alpha [ d e f a u l t =0] L1 正 则 的 惩 罚 系 数
http://www.ma-xy.com 33 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
46 # 5 . lambda_bias 在 偏 置 上 的 L2正 则 。 缺 省 值 为 0 （ 在 L1上 没 有 偏 置 项 的 正 则 ， 因 为 L1时 偏 置 不 重
要 ）
47 # 6 . eta [ d e f a u l t =0.3] 为 了 防 止 过 拟 合 ， 更 新 过 程 中 用 到 的 收 缩 步 长 。 在 每 次 提 升 计 算 之 后 ，
算 法 会 直 接 获 得 新 特 征 的 权 重 。 eta 通 过 缩 减 特 征 的 权 重 使 提 升 计 算 过 程 更 加 保 守 。 缺 省 值 为0 . 3 , 取 值 范
围 为 ： [ 0 , 1 ]
48 # 7 . max_depth [ defaul t =6] 数 的 最 大 深 度 。 缺 省 值 为 6 ， 取 值 范 围 为 ： [ 1 , i n f ]
49 # 8 . min_child_weight [ d e f a u lt =1] 孩 子 节 点 中 最 小 的 样 本 权 重 和 。 如 果 一 个 叶 子 节 点 的 样 本 权
重 和 小 于 min_child_weight 则 拆 分 过 程 结 束 。 在 现 行 回 归 模 型 中 ， 这 个 参 数 是 指 建 立 每 个 模 型 所 需 要 的 最
小 样 本 数 。 该 成 熟 越 大 算 法 越 co nserv ative , 取 值 范 围 为 : [ 0 , i n f ] .
50
51 # auc : Area under the curve
52 # 3 . seed [ d e f a u lt =0] ：
53 # The random number seed . 随 机 种 子 ， 用 于 产 生 可 复 现 的 结 果
54 # Can be used f o r g enera ting rep rodu cibl e r e s u l t s and a l s o fo r parameter tuning .
55
56 #−−−−−−−−−−−−−−−−−− XGboost−example−−−−−−−−−−−−−−−−−−−#
57
58 # 1 、 简 单 例 子
59 import xgboost as xgb
60 import numpy as np
61 data = np . random . rand (5 ,1 0) # 5 e n t i t i e s , each con tains 10 f e a tur e s
62 l a b e l = np . random . ra ndint ( 2 , s i z e =5) # binary t a rget
63 d tra in = xgb . DMatrix ( data , l a b e l=l a b e l )
64 d t est = dtra in
65 param = { ’ bst : max_depth ’ : 2 , ’ bst : eta ’ : 1 , ’ s i l e n t ’ : 1 , ’ o b j e c t i v e ’ : ’ binary : l o g i s t i c ’ }
66 param [ ’ nthread ’ ] = 4
67 param [ ’ eval_metric ’ ] = ’ auc ’
68 e v a l l i s t = [ ( dtest , ’ e val ’ ) , ( dtrain , ’ tr a i n ’ ) ]
69 num_round = 10
70 bst = xgb . t r a i n ( param , dtrain , num_round , e v a l l i s t )
71 bst . dump_model( ’dump. raw . txt ’ )
72
73 # 2 、 实 际 例 子
74 from __future__ import di v i s i o n
75 import numpy as np
76 import xgboost as xgb
77
78 # l a b e l need to be 0 to num_class −1
79 data = np . l oad txt ( ’ . / dermatology . data ’ , d e l i m i t e r=’ , ’ ,
80 con v ert e rs ={33: lambda x : int (x == ’ ? ’ ) , 34: lambda x : i n t ( x)−1})
81 sz = data . shape
82
83 train = data [ : i n t ( s z [ 0 ] * 0 . 7 ) , : ]
84 t e s t = data [ i n t ( s z [ 0 ] * 0 . 7 ) : , : ]
85
86 train_X = train [ : , : 3 3 ]
87 train_Y = train [ : , 34]
88
89 test_X = t e s t [ : , : 3 3 ]
90 test_Y = t e s t [ : , 34]
91
92 xg_train = xgb . DMatrix ( train_X , l a b e l=train_Y )
93 xg_test = xgb . DMatrix ( test_X , l a b e l=test_Y )
http://www.ma-xy.com 34 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
94 # setup parameters f o r xgboost
95 param = {}
96 # use softmax multi−c l a s s c l a s s i f i c a t i o n
97 param [ ’ o b j e c t i v e ’ ] = ’ multi : softmax ’
98 # s c a l e weight of p o s i t i v e examples
99 param [ ’ et a ’ ] = 0. 1
100 param [ ’max_depth ’ ] = 6
101 param [ ’ s i l e n t ’ ] = 1
102 param [ ’ nthread ’ ] = 4
103 param [ ’ num_class ’ ] = 6
104
105 w a t c h list = [ ( xg_train , ’ t r a i n ’ ) , ( xg_test , ’ t e s t ’ ) ]
106 num_round = 5
107 bst = xgb . t r a i n (param , xg_train , num_round, w a t c hlist )
108 # get p r edicti o n
109 pred = b st . p redi c t ( xg_test )
110 error _r ate = np . sum( pred != test_Y ) / test_Y . shape [ 0 ]
111 p r int ( ’ Test error using softmax = {} ’ . format ( err or_rate ) )
112
113 # do the same thing again , but output p r o b a b i l i t i e s
114 param [ ’ o b j e c t i v e ’ ] = ’ multi : s oft pro b ’
115 bst = xgb . t r a i n (param , xg_train , num_round, w a t c hlist )
116 # Note : t h i s convention has been changed s i n c e xgboost−unity
117 # get pre dict ion , t h i s i s in 1D array , need reshape to ( ndata , nclass )
118 pred_prob = b st . p redi c t ( xg_test ) . reshape ( test_Y . shape [ 0 ] , 6)
119 pred_label = np . argmax ( pred_prob , axi s =1)
120 error _r ate = np . sum( pred_label != test_Y ) / test_Y . shape [ 0 ]
121 p r int ( ’ Test error using soft pro b = {} ’ . format ( error_ rate ) )
122
123 # 3 、 丢 弃 提 升 DART bo oster （ 这 个 论 文 还 要 仔 细 看 ）
124 import xgboost as xgb
125 # read in data
126 d tra in = xgb . DMatrix ( ’demo/data/ aga r icu s . txt . t r a i n ’ )
127 d t est = xgb . DMatrix ( ’demo/data/ aga r icu s . txt . t e s t ’ )
128 # s p e c i f y parameters vi a map
129 param = { ’ b ooster ’ : ’ dart ’ ,
130 ’max_depth ’ : 5 , ’ le arnin g_rat e ’ : 0 . 1 ,
131 ’ object i v e ’ : ’ binary : l o g i s t i c ’ , ’ s i l e n t ’ : True ,
132 ’ sample_type ’ : ’ uniform ’ ,
133 ’ normalize_type ’ : ’ t r e e ’ ,
134 ’ rate_drop ’ : 0 . 1 ,
135 ’ skip_drop ’ : 0.5}
136 num_round = 50
137 bst = xgb . t r a i n (param , dtrain , num_round)
138 # make p redict i o n
139 # n tree_ lim it must not be 0
140 preds = bst . p redi c t ( dtest , ntre e_lim it=num_round)
141
XGboost 在 R 下的安装可以参考网址
¯
，下面给出一个简单的示例：
1 #−−−−−−−−−−−−−−−−−−XGboost−example−−−−−−−−−−−−−−−#
¯
http://xgboost.readthedocs.io/en/latest/R-package/xgboostPresentation.html
http://www.ma-xy.com 35 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
2
3 # i n s t a l l package
4 # d evt ools : : i n s t a l l_github ( ’ dmlc/xgboost ’ , sub di r=’R−package ’ )
5 i n s t a l l . packages ( ” xgboost ” )
6 r e q u i r e ( xgboost )
7 # load data
8 data ( a gari cus . tra in , package=’ xgboost ’ )
9 data ( a gari cus . t est , package=’ xgboost ’ )
10 train <− ag aric us . train
11 t e s t <− a g ari c us . t e s t
12 c l a s s ( train $ data )
13 attr ( , ” package ” )
14 # f i t model
15 bst <− xgboost ( data = t r a i n $data , l a b e l = t r a i n $ labe l , max. depth = 2 , eta = 1 ,nround
= 2 , o b j e c t i v e = ” binary : l o g i s t i c ” )
16 # predi c t
17 pred <− predi c t ( bst , t e s t $data )
18 cv . r e s <− xgb . cv ( data = t r a i n $data , l a b e l = tr a i n $ lab e l , max . depth = 2 , e ta = 1 ,
nround = 2 , o bjective = ” binary : l o g i s t i c ” ,
19 n fol d = 5)
20 cv . r e s
21
1.2.8 应用示例-LightGBM
LightGBM
°
是微软开发的一个集成学习工具，安装可以参考网址
±²
，参数解释可以参考网
址
³´
。Python 的示例
µ
如下：
1 # coding : utf−8
2 # p ylint : d i s a b l e = in v alid−name , C0111
3
4 #−−−−−−−−−−−−−−−LightGBM−example_1−−−−−−−−−−−−−#
5 import j son
6 import lightgbm as lgb
7 import pandas as pd
8 from s k lear n . metrics import mean_squared_error
9
10 # load or c r eate your dat aset
11 p r int ( ’ Load data . . . ’ )
12 df_train = pd . read_csv ( ’ . . / reg r e s s i o n / r e g res s i o n . t r a i n ’ , header=None , sep=’ \ t ’ )
13 df _test = pd . read_csv ( ’ . . / r e g re s s i o n / r e g r e s si o n . t e s t ’ , header=None , sep=’ \ t ’ )
14
15 y_train = df_train [ 0 ] . val ues
16 y_test = df_tes t [ 0 ] . val ues
17 X_train = df_train . drop (0 , axi s =1) . val ues
°
https://github.com/Microsoft/LightGBM
±
编译：https://github.com/Microsoft/LightGBM/wiki/Installation-Guide
²
python 安装：https://github.com/Microsoft/LightGBM/blob/master/docs/Python-intro.md
³
https://github.com/Microsoft/LightGBM/blob/master/docs/Parameters.md
´
https://zhuanlan.zhihu.com/p/27916208
µ
https://github.com/Microsoft/LightGBM/blob/master/examples/python-guide/simple_example.py
http://www.ma-xy.com 36 http://www.ma-xy.com
http://www.ma-xy.com
第一章 决策树和集成学习 1.2 集成学习
18 X_test = df_tes t . drop (0 , axi s =1) . val ues
19
20 # crea t e dat as et f o r lightgbm
21 lgb_train = lgb . Dataset ( X_train , y_train )
22 lgb_eval = lgb . Dataset ( X_test , y_test , r e f e r e n c e=lgb_trai n )
23
24 # s p e c i f y your config u r a t i o n s as a d i c t
25 params = {
26 ’ task ’ : ’ t r a i n ’ ,
27 ’ boosting_type ’ : ’ gbdt ’ ,
28 ’ object i v e ’ : ’ r e g res s i o n ’ ,
29 ’ metric ’ : { ’ l2 ’ , ’ auc ’ } ,
30 ’ num_leaves ’ : 31 ,
31 ’ learni ng _rate ’ : 0.05 ,
32 ’ fe a t u re_f r a c tion ’ : 0 . 9 ,
33 ’ bagging_fractio n ’ : 0 . 8 ,
34 ’ bagging_freq ’ : 5 ,
35 ’ verbose ’ : 0
36 }
37
38 p r int ( ’ St ar t t r a i n i n g . . . ’ )
39 # t r a i n
40 gbm = lgb . t r a i n ( params ,
41 lgb_train ,
42 num_boost_round=20,
43 v ali d_s e ts=lgb_eval ,
44 early_stopping_rounds=5)
45
46 p r int ( ’ Save model . . . ’ )
47 # save model to f i l e
48 gbm. save_model ( ’ model . tx t ’ )
49
50 p r int ( ’ St ar t p r e d icting . . . ’ )
51 # predi c t
52 y_pred = gbm . p redic t ( X_test , num_iteration=gbm. best _ i tera t i on )
53 # e val
54 p r int ( ’The rmse o f p r e d i ction i s : ’ , mean_squared_error ( y_test , y_pred ) ** 0 . 5 )
55
R 的示例
¶
如下，R 包安装参考
·
1 #−−−−−−−−−−−−−−−LightGBM−example_1−−−−−−−−−−−−−#
2 # 安 装 参 考 http s : //github . com/ M icrosof t /LightGBM/blob/ master/R−package/README.md
3 r e q u i r e ( lightgbm )
4 r e q u i r e ( methods )
5
6 # Load in the aga ricu s datas et
7 data ( a gari cus . tra in , package = ” lightgbm ” )
8 data ( a gari cus . t est , package = ” lightgbm ” )
9 d tra in <− lgb . Dataset ( ag a ric u s . t r a i n $data , l a b e l = a g ari c us . train $ l a b e l )
10 d t est <− lgb . Dataset ( aga r icu s . t e s t $data , l a b e l = a g ari c us . t e s t $ l a b e l )
¶
https://github.com/Microsoft/LightGBM/blob/master/R-package/demo/boost_from_prediction.R
·
安装参考 https://github.com/Microsoft/LightGBM/blob/master/R-package/README.md
http://www.ma-xy.com 37 http://www.ma-xy.com
http://www.ma-xy.com
1.2 集成学习 第一章 决策树和集成学习
11
12 va l i d s <− l i s t ( eva l = dte st , t r a i n = dtr a in )
13 #−−−−−−−−−−−−−−−−−−−−Advanced f e a ture s −−−−−−−−−−−−−−−−−−−−−−−−−−−
14 # advanced : st a r t from a i n i t i a l base p r edicti o n
15 p r int ( ” S tart running example to s t a r t from a i n i t i a l p r e d i ction ” )
16
17 # Train lightgbm f o r 1 round
18 param <− l i s t (num_l eaves = 4 ,
19 learn i n g_rate = 1 ,
20 nthread = 2 ,
21 o b j e c t i v e = ” binary ” )
22 bst <− lgb . t r a i n (param , dtrain , 1 , v a l i d s = v a l i d s )
23
24 # Note : we need the margin value in ste ad of transformed p r e d iction in s e t_i n i t_scor e
25 p tra in <− pr e d ict ( bst , a gar i cus . train $data , rawscore = TRUE)
26 p t est <− pr e d i ct ( bst , aga r icu s . t e s t $data , rawscore = TRUE)
27
28 # s e t the i n i t_s c ore property o f d tra in and d t e st
29 # base margin i s the base p r edicti o n we w i l l boost from
30 s e t i n f o ( dtrain , ” i n i t_scor e ” , p tra in )
31 s e t i n f o ( dtest , ” i n i t_scor e ” , p t est )
32
33 p r int ( ”This i s r e s u l t of boost from i n i t i a l p r edicti o n ” )
34 bst <− lgb . t r a i n ( params = param ,
35 data = dtrain ,
36 nrounds = 5 ,
37 va l i d s = valids )
38
http://www.ma-xy.com 38 http://www.ma-xy.com
http://www.ma-xy.com
参考文献
[1] Kohavi R auer E. An empirical comparison of voting classication algorithms bagging,
boosting, and variants. 1999.
[2] Tibshirani R Friedman J, Hastie T. Additive logistic regression a statistical view of boosting.
2000.
[3] Dietterich T G. An experimental comparison of three methods for constructing ensembles
of decision trees bagging, boosting, and randomization. 2000.
[4] Valiant L G. A theory of the learnable. 1984.
[5] Friedman J H. Greedy function approximation a gradient boosting machine. 2000.
[6] Didrik Nielsen. Tree boosting with xgboost - why does xgboost win every machine learning
competition. 2016.
[7] Rojas. Adaboost and the super bowl of classiers a tutorial introduction to adaptive boost-
ing. 2009.
[8] Bartlett P Schapire R E, Freund Y. Boosting the margin a new explanation for the eec-
tiveness of voting methods. 1997.
[9] Singer Y Schapire R E. Improved boosting algorithms using condence-rated predictions.
1998.
[10] Carlos Guestrin Tianqi Chen. Xgboost: A scalable tree boosting system. 2016.
[11] 王超 (@ 德川), 陈帅华 ( @ 陈帅华 BigData ) .xgboost 导读和实战.
[12] Freund Y. Experiments with a new boosting algorithm. 1996.
[13] Robert E Yoav Freund. A desicion-theoretic generalization of on-line learning and an appli-
cation to boosting. 1995.
39
