树及其组合算法二：Bagging
树及其组合算法部分其余内容，个人笔记博客传送门
树及其组合算法一：决策树
| 基本知识介绍 |
决策树有一种“天然”的高方差特征，解决预测高方差问题的一般方法是集成学习(Ensemble Learning)。
1集成学习
1.1集成学习概述
集成学习的基本思路为：
①建模阶段：基于一组独立的训练集，分别建立与之对应的一组回归或分类预测模型，称这里的每个预测模型为基础学习器
②预测阶段：基础学习器将分别给出各自的预测结果，对各预测结果进行平均(回归模型)或投票(分类模型)，确定最终的预测结果。
集成学习的特点：
基础学习器通常由一个现有的学习算法从训练数据产生，例如，C4.5决策树算法、BP神经网络算法等，此时集成中只包含同种类型的基础学习器，例如“决策树集成”中全是决策树，“神经网络集成”中全是神经网络，这样的集成是“同质”的。
要获得好的集成，基础学习器应该“好而不同”，即基础学习器要有一定的“准确性”并且要有“多样性”。
集成学习方法大致分为两类：
- 基础学习器之间存在
强依赖关系、必须串行生成的序列化方法，代表是Boosting。 - 基础学习器之间
不存在强依赖关系，可同时生成的并行化方法，代表是Bagging和“随机森林”。
集成学习的优势为：
- 解决预测模型的高方差问题
- 将一组弱模型联合起来使其成为一个强模型。
1.2集成学习的原理
- （1）解决预测模型的高方差问题
集成学习认为：
若能够基于来自同一总体的B个独立的训练集，建立B个基础学习器得到对
X
0
X_0
X0的B个回归预测值
f
^
(
1
)
(
X
0
)
，
f
^
(
2
)
(
X
0
)
，
.
.
.
，
f
^
(
B
)
(
X
0
)
\hat{f}^{(1)(X_0)}，\hat{f}^{(2)(X_0)}，...，\hat{f}^{(B)(X_0)}
f^(1)(X0)，f^(2)(X0)，...，f^(B)(X0)，若其方差等于
σ
2
\sigma^2
σ2则B个回归预测值的平均值
f
^
a
v
g
(
X
0
)
=
1
B
∑
b
=
1
B
f
^
(
b
)
(
X
0
)
\hat{f}_{avg}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{f}^{(b)}(X_0)
f^avg(X0)=B1∑b=1Bf^(b)(X0)，其方差降到
σ
2
/
B
\sigma^2/B
σ2/B。这里的B个预测模型彼此独立。同时这B个独立的训练集无法直接获得通常需要模拟生成，并由此建立B个独立的基础学习器，得到对
X
0
X_0
X0的B个回归预测值。
模拟生成B个独立训练集的常见策略：重抽样自举法(Bootstrap)，给定一个样本量为N的数据集D，有放回地从中随机抽取N个样本，重复B次，得到B组独立的训练集，每组训练集*有N个样本。称
S
b
∗
(
b
=
1
,
2
,
.
.
.
,
B
)
S_b^{*}(b=1,2,...,B)
Sb∗(b=1,2,...,B)为一个自举样本，B为自举次数。
当N较大时N次均未抽中的概率为
(
1
−
1
N
)
N
≈
1
e
=
0.368
(1-\frac{1}{N})^{N}\approx \frac{1}{e}=0.368
(1−N1)N≈e1=0.368，这也意味着大约有0.368的样本不会进入最后样本，因此，重抽样自举法也被称为0.632自举法。
基于重抽样自举地常见集成学习方法：
袋装法（Bagging）和随机森林（Random Forest）
- （2）从弱模型到强模型地构建
复杂模型导致高方差以及模型过拟合。集成学习将一组弱模型（基础学习器）组成一个“联合委员会”并最终称为强模型。弱模型一般指比随机猜测的误差略低的模型
例如，回归预测中：
B个弱模型对
X
0
X_0
X0地回归预测值分别为：
f
^
∗
(
1
)
(
X
0
)
，
f
^
∗
(
2
)
(
X
0
)
，
.
.
.
，
f
^
∗
(
B
)
(
X
0
)
\hat{f}^{*(1)}(X_0)，\hat{f}^{*(2)}(X_0)，...，\hat{f}^{*(B)}(X_0)
f^∗(1)(X0)，f^∗(2)(X0)，...，f^∗(B)(X0)
“联合委员会”的联合预测结果：
f
^
α
∗
(
X
0
)
=
α
1
f
^
∗
(
1
)
(
X
0
)
+
α
2
f
^
∗
(
2
)
(
X
0
)
+
.
.
.
+
α
B
f
^
∗
(
B
)
(
X
0
)
\hat{f}_{\alpha}^{*}(X_0)=\alpha_1 \hat{f}^{*(1)}(X_0)+\alpha_2 \hat{f}^{*(2)}(X_0)+...+\alpha_B \hat{f}^{*(B)(X_0)}
f^α∗(X0)=α1f^∗(1)(X0)+α2f^∗(2)(X0)+...+αBf^∗(B)(X0)，其中
α
b
(
b
=
1
,
2
,
.
.
.
,
B
)
\alpha_b(b=1,2,...,B)
αb(b=1,2,...,B)为模型权重。
从弱模型到强模型的常见的集成学习法：
提升法（Boosting），梯度提升树，这里的B个弱模型具有顺序相关性
2 Bagging
Bagging （bootstrap aggregating）又称袋装法，是集成学习算法中的一种。
2.1 Bagging的建模
- 训练B个基础学习器
- 通常
基础学习器是训练误差较低的相对复杂的模型，例如回归树或分类树。
2.2 Bagging的预测
T
^
∗
(
b
)
\hat{T}^{*(b)}
T^∗(b)表示第
b
b
b棵树，
T
^
∗
(
b
)
(
X
0
)
\hat{T}^{*(b)}(X_0)
T^∗(b)(X0)表示第
b
b
b棵树对输入变量
X
0
X_0
X0的预测。
那么，回归树中，Bagging袋装预测值为
b
b
b棵树的预测平均值：
f
^
b
a
g
∗
(
X
0
)
=
1
B
∑
b
=
1
B
T
^
∗
(
b
)
(
X
0
)
\hat{f}_{bag}^{*}(X_0)=\frac{1}{B}\sum_{b=1}^{B}\hat{T}^{*(b)}(X_0)
f^bag∗(X0)=B1b=1∑BT^∗(b)(X0)
K分类预测中，Bagging袋装预测值为占比法，计算预测
X
0
X_0
X0属于第
k
k
k类的分类树的占比，占比最高的类别为最终
X
0
X_0
X0的预测值。
f
^
b
a
g
∗
(
X
0
)
=
arg
max
k
P
k
(
X
0
)
\hat{f}_{bag}^{*}(X_0)=\arg \max_{k} P_{k}(X_0)
f^bag∗(X0)=argkmaxPk(X0)
2.3 Bagging测试误差的估计
基于OOB（out of bag）袋外观测的估计，第 b b b棵决策树的袋外观测是没有出现在这棵树测训练数据集 S b ∗ S_b^* Sb∗内的样本观测。
原样本数据集D*有N个样本，
S
b
∗
S_b^*
Sb∗是从D中有放回随机抽取的训练数据集，样本大小也为N，用于构造第
b
b
b棵决策树。对于原样本集D中的每个样本
X
i
(
i
=
1
,
2
,
.
.
.
N
)
X_i(i=1,2,...N)
Xi(i=1,2,...N)，得到其作为袋外观测OOB时基础学习器的预测结果。
具体是如何得到
X
i
X_i
Xi作为OOB的Bagging预测值呢？
若
X
i
X_i
Xi在建模过程中有
q
(
q
<
B
)
q(q<B)
q(q<B)次作为OOB观测，也即有
q
q
q棵决策树的建模过程中没有用到
X
i
X_i
Xi这个样本，那么只有这
q
q
q个基础学习器提供预测值，最终Bagging的预测结果是这q个预测值的平均或投票。
2.4 Bagging袋装法的缺点
袋装法降低预测方差的基本理论是：
来自同一总体的、方差等于
σ
2
\sigma^2
σ2的B个预测值
T
^
∗
(
b
)
(
X
0
)
\hat{T}^{*(b)}(X_0)
T^∗(b)(X0)，假设这B个预测值彼此独立，因此取其均值
f
^
b
a
g
∗
(
X
0
)
\hat{f}_{bag}^{*}(X_0)
f^bag∗(X0)的方差降至
σ
2
/
B
\sigma^2/B
σ2/B
但是：
独立的假设条件在实际情况中是很难实现的，因为树是相似的，即先选某个特征
x
i
x_i
xi进行分支，再选某个特征
x
j
x_j
xj进行分支，这些划分点的选取以及顺序都是类似的，因此树的形状会很相似。
V
a
r
(
Z
ˉ
)
=
v
a
r
(
1
N
∑
i
=
1
N
Z
i
)
=
1
N
2
[
N
σ
2
+
N
(
N
−
1
)
ρ
σ
2
]
=
σ
2
+
(
N
−
1
)
ρ
σ
2
N
=
ρ
σ
2
+
1
−
ρ
N
σ
2
\begin{aligned} Var(\bar{Z})&=var(\frac{1}{N}\sum_{i=1}^{N}Z_i)\\ &=\frac{1}{N^2}[N\sigma^2+N(N-1)\rho \sigma^2]\\ &=\frac{\sigma^2+(N-1)\rho \sigma^2}{N}\\ &=\rho \sigma^2+\frac{1-\rho}{N}\sigma^2 \end{aligned}
Var(Zˉ)=var(N1i=1∑NZi)=N21[Nσ2+N(N−1)ρσ2]=Nσ2+(N−1)ρσ2=ρσ2+N1−ρσ2
若满足彼此独立的条件，则
ρ
=
0
\rho=0
ρ=0，
v
a
r
(
Z
ˉ
)
=
σ
2
N
var(\bar{Z})=\frac{\sigma^2}{N}
var(Zˉ)=Nσ2；若不满足彼此独立的条件，即
ρ
≠
0
\rho \neq 0
ρ=0，
v
a
r
(
Z
ˉ
)
var(\bar{Z})
var(Zˉ)有以上两项。
3 随机森林
用随机方式建立包含多棵决策树的森林。每棵树都是一个基础学习器，“整片”森林对应集成学习。通过随机方式使每棵树的“外观”因彼此“看上去不相同”而不相关。随机森林通过减少预测相关性，即通过降低树间的相似性(高相似的决策树给出高相关的预测值)的策略降低方差。
3.1随机森林降低树间相似性的基本策略：
- 对
训练数据增加随机性扰动：重抽样自举法。 - 对
输入变量增加随机性扰动：决策树建立过程中的当前“最佳”分组变量，是来自输入变量的一个随机子集中的变量。
3.2随机森林建模过程
进行
b
=
1
,
2
,
.
.
.
,
B
b=1,2,...,B
b=1,2,...,B次如下迭代，得到包括B棵树的随机森林：
①对样本量等于N的数据集进行重抽样自举，得到自举样本
S
b
∗
S_b^{*}
Sb∗
②基于自举样本
S
b
∗
S_b^{*}
Sb∗建立树
T
^
∗
b
\hat{T}^{*b}
T^∗b。树从根节点开始按如下方式不断生长，直到满足树的预修剪参数为止：对于决策树的每个节点，先从该节点的属性集合中随机选择一个包含k个属性的子集，然后再从这个子集中选择一个最优属性用于划分。
这里代表子集的大小的参数 k k k控制了随机性的引入程度，若令 k = d k=d k=d，则基决策树的构建与传统决策树相同，若令 k = 1 k=1 k=1，则是随机选择一个属性用于划分；一般情况下， k = [ log 2 d ] k=[\log_2 d] k=[log2d]或者 k = [ d ] k=[\sqrt{d}] k=[d ]，其中 d d d表示原数据集中总的特征属性的个数。
4 AdaBoost
Boosting是一种可以将弱模型提升为强模型的算法。这一类算法的核心类似于：先从初始训练集训练出一个基础学习器，再根据基础学习器的表现对
训练样本的分布进行调整，使得先前的基础学习器中预测错误的训练样本再后续得到更多关注，然后基于调整后的样本分布来训练下一个基础学习器；重复操作直至得到一定个数T的基础学习器，将T个基础学习器的预测结果进行加权平均。
周志华《机器学习》
提升法的经典是AdaBoost(Adaptive Boosting)适应性提升法，提出时主要针对二分类预测问题，分类标签为-1和+1两个类别。AdaBoost算法中涉及两个权重：样本的分布，即迭代更新后第b个模型使用的N个样本的分布 w ( b ) = [ w 1 ( b ) , w 2 ( b ) ， . . . w N ( b ) ] w^{(b)}=[w_1^{(b)},w_2^{(b)}，...w_N^{(b)}] w(b)=[w1(b),w2(b)，...wN(b)]和第b个弱模型的权重 α b \alpha_b αb。 适应性提升的表现：基于 w ( b − 1 ) w^{(b-1)} w(b−1)得到 w ( b ) w^{(b)} w(b)
对于提升方法来说，有两个问题需要回答，AdaBoost有对应的做法：
李航《统计学习方法》
1.在每一轮迭代时如何改变训练数据的权值或概率分布
AdaBoost的做法是，提高那些被前一轮弱分类器错误分类样本的权值，而降低那些被正确分类样本的权值。
2.如何将弱分类器组合成一个强分类器
AdaBoost采取加权多数表决的方法，具体地加大分类误差率小地弱分类器的权值，使其在表决中起较大的作用；减小分类误差率大的弱分类器的权值，使其在表决中起较小作用。
AdaBoost算法具体步骤：
每个样本观测在每次迭代中都有自己的权重
w
(
b
)
=
[
w
1
(
b
)
，
w
2
(
b
)
，
.
.
.
，
w
N
(
b
)
]
w^{(b)}=[w_1^{(b)}，w_2^{(b)}，...，w_N^{(b)}]
w(b)=[w1(b)，w2(b)，...，wN(b)]
初始化：
w
(
1
)
=
[
1
N
，
1
N
，
.
.
.
，
1
N
]
w^{(1)}=[\frac{1}{N}，\frac{1}{N}，...，\frac{1}{N}]
w(1)=[N1，N1，...，N1]，给定需要的弱分类器个数
B
B
B
第一次迭代：
①基于权重
w
(
1
)
w^{(1)}
w(1)对原始数据集S（数据量为N）进行加权有放回的随机抽样得到训练集
S
1
S_1
S1（数据量为N），根据
S
1
S_1
S1数据集得到弱模型
G
1
(
X
)
G_1(X)
G1(X)。
②计算弱模型
G
1
(
X
)
G_1(X)
G1(X)的训练误差：
e
r
r
(
1
)
=
∑
i
=
1
N
P
(
y
i
≠
G
1
(
X
i
)
)
=
∑
i
=
1
N
w
i
(
1
)
I
(
y
i
≠
G
1
(
X
i
)
)
err^{(1)}=\sum_{i=1}^{N} P(y_i\ne G_1(X_i))=\sum_{i=1}^{N} w_i^{(1)}I(y_i\ne G_1(X_i))
err(1)=∑i=1NP(yi=G1(Xi))=∑i=1Nwi(1)I(yi=G1(Xi))
③计算
G
1
(
X
)
G_1(X)
G1(X)模型权重
α
1
=
1
2
ln
(
1
−
e
r
r
(
1
)
e
r
r
(
1
)
)
\alpha_1=\frac{1}{2}\ln (\frac{1-err^{(1)}}{err^{(1)}})
α1=21ln(err(1)1−err(1))
④更新
w
(
2
)
w^{(2)}
w(2)得到：
w
i
(
2
)
=
w
i
(
1
)
e
x
p
(
−
α
1
y
i
G
1
(
X
i
)
)
Z
1
w_i^{(2)}=\frac{w_i^{(1)}exp(-\alpha_1y_iG_1(X_i))}{Z_1}
wi(2)=Z1wi(1)exp(−α1yiG1(Xi))，
i
=
1
,
2
,
.
.
.
,
N
i=1,2,...,N
i=1,2,...,N,
Z
1
=
∑
i
w
i
(
1
)
e
x
p
(
−
α
1
y
i
G
1
(
X
i
)
)
Z_1=\sum_i w_i^{(1)}exp(-\alpha_1y_iG_1(X_i))
Z1=∑iwi(1)exp(−α1yiG1(Xi)),这里
Z
1
Z_1
Z1是规范因子，它使得
w
(
2
)
=
[
w
1
(
2
)
,
w
2
(
2
)
,
.
.
.
,
w
N
(
2
)
]
w^{(2)}=[w_1^{(2)},w_2^{(2)},...,w_N^{(2)}]
w(2)=[w1(2),w2(2),...,wN(2)]是一个概率分布。
第二次迭代：
根据上一轮更新的训练集分布
w
(
2
)
w^{(2)}
w(2)对原数据集S进行加权有放回的随机抽样，得到训练集
S
2
S_2
S2，基于
S
2
S_2
S2训练集得到相应的弱模型
G
2
(
X
)
G_2(X)
G2(X)。注意到这里
G
1
(
X
)
G_1(X)
G1(X)模型预测错误的样本有更大的概率进入训练集
S
2
S_2
S2，同时注意到模型
G
2
(
X
)
G_2(X)
G2(X)关注的是
G
1
(
X
)
G_1(X)
G1(X)没有正确预测的部分样本。
计算
G
2
(
X
)
G_2(X)
G2(X)模型的训练误差
e
r
r
(
2
)
err^{(2)}
err(2)和模型权重
α
2
\alpha_2
α2，并根据
α
2
\alpha_2
α2和
w
(
2
)
w^{(2)}
w(2)得到的更新的
w
(
3
)
w^{(3)}
w(3)。
第三次迭代至第
B
B
B次迭代同理。
最终强模型预测结果为
G
(
X
)
=
s
i
g
n
(
∑
b
=
1
B
α
b
∗
G
b
(
X
)
)
G(X)=sign(\sum_{b=1}^{B} \alpha_b*G_b(X))
G(X)=sign(∑b=1Bαb∗Gb(X))
这里
α
b
\alpha_b
αb表示了基础学习器
G
b
(
X
)
G_b(X)
Gb(X)的重要性，
α
b
\alpha_b
αb之和并不为1.
AdaBoost算法的特点
- 不改变所给的训练数据，而不断改变训练数据权值的分布，使得训练数据在基本分类器的学习中起不同的作用。
- 利用基础学习器的线性组合构建最终分类器。
AdaBoost算法还有另一个解释，即可认为AdaBoost算法是模型为加法模型、损失函数为指数函数、学习算法为前向分步算法的二分类学习方法。
李航《统计学习方法》
这里的指数损失函数为 L ( y ， G ( x ) ) = e x p ( − y ∗ G ( x ) ) L(y，G(x))=exp(-y*G(x)) L(y，G(x))=exp(−y∗G(x))
5 GBDT
补充内容：
梯度：在微积分中对多元函数的参数求偏导，将所有参数的偏导结果写成向量形式就是梯度，如 ∂ f ( w ) ∂ w \frac{\partial f(w)}{\partial w} ∂w∂f(w)。
梯度的几何意义：梯度就是函数在某点变化最快的地方。沿着梯度的方向，是函数增加最快的方向，更容易找到函数的最大值；反过来，沿着梯度的反方向，函数下降最快，更容易找到函数的最小值。
梯度下降算法：沿着梯度的负方向调整。
5.1提升树
提升树是以分类树或回归树为基础学习器的提升方法。针对不同问题的提升树算法，其主要区别在于使用的损失函数不同，包括使用平方误差损失函数的回归问题，用指数损失函数的分类问题，以及用一般损失函数的一般问题。
-
对于二分类问题，只需要将AdaBoost算法中的基础学习器限制为二类分类树即可，AdaBoost算法原理是基于 指数损失函数实现的，并且AdaBoost算法适用于标签为+1，-1的二分类问题。
-
对于回归问题，现在先考虑回归提升树（李航《统计学习方法》）。
当损失函数采用 平方误差损失函数时，构建新的基础学习器时相当于，拟合之前所有模型加和与真实值之间的差值即残差。
5.2梯度提升算法
当损失函数为平方误差损失函数和指数损失函数时，每一步的优化过程是很简单的，但是，对一般损失函数而言，每一步的优化并不那么容易。于是，Freidman提出了梯度提升算法，利用最速下降的近似方法，求一般损失函数的最小值(李航《统计学习方法》)。
GBDT(Gradient Boosted Decision Trees)梯度提升树的核心是：每一棵树学习的都是之前所有树的预测值之和的残差值。这个残差值加上所有树的预测值和正好等于真实值。GBDT算法限制了基础学习器为CART回归树。
注：
算法初始化部分，估计得到使损失函数极小化的常数值，它是只有一个根节点的树。
第2（a）计算损失函数的负梯度在当前模型的值，作为残差的估计。对于平方损失函数它就是通常所说的残差，对于一般损失函数，它就是残差的近似值。
第2（b）估计回归树叶节点区域，拟合残差的近似值，即把(X,
r
m
i
r_{mi}
rmi)作为训练数据训练回归树。
第2（c）步，利用线性搜索估计叶节点区域的值，使损失函数极小化。
第2（d）步，更新回归树。
5.3GBDT算法用于分类
这部分内容摘自相关参考资料中的第5条。
GBDT梯度提升树算法本身是用于CART回归树，这是因为回归树中输出的值是连续的值，损失函数是可导的，但GBDT经过调整也能用于分类。第一种思路是，损失函数定为指数损失函数，这种情况下，GBDT算法退化为AdaBoost；第二种思路是使用类似逻辑回归的对数似然损失函数。重点是对损失函数的调整。
- 二元GBDT分类算法中，损失函数为 L ( y , f ( x ) ) = log ( 1 + exp ( − y ∗ f ( x ) ) ) L(y,f(x))=\log (1+\exp(-y*f(x))) L(y,f(x))=log(1+exp(−y∗f(x)))，这里 y ∈ { + 1 , − 1 } y\in \{+1,-1\} y∈{+1,−1}
- 多元GBDT分类算法中，损失函数为
L
(
y
,
f
(
x
)
)
=
−
∑
k
=
1
K
y
k
log
p
k
(
x
)
L(y,f(x))=-\sum_{k=1}^K y_k \log p_k(x)
L(y,f(x))=−k=1∑Kyklogpk(x)
p k ( x ) = e x p ( f k ( x ) ) ∑ l = 1 K e x p ( f l ( x ) ) p_k(x)=\frac{exp(f_k(x))}{\sum_{l=1}^K exp(f_l(x))} pk(x)=∑l=1Kexp(fl(x))exp(fk(x))
6 XGBoost
XGBoost（eXtreme Gradient Boosting），它所应用的算法就是Gradient Boosting Decision Trees，它是GB算法的高效实现，既可以用于分类问题中，又可以用于回归问题中。相比较于GBDT算法，在目标函数中加入了正则化项。
通俗理解kaggle比赛大杀器xgboost这一篇已经写的很好了，暂不赘述。。。
| 相关参考资料 |
1.有关梯度上升和梯度下降https://www.cnblogs.com/pinard/p/5970503.html。
2.这一篇博客中有XGBoost的实例及代码实现Kaggle 神器 xgboost
3.重点参考GBDT算法原理以及实例理解
4.重点参考李航的书《统计学习方法》
5.这篇博客中提到了GBDT提升树用于分类梯度提升树(GBDT)原理小结
6.这一篇中有GBDT分类算法的原理(损失函数为逻辑回归的对数似然函数)深入理解GBDT二分类算法
7.https://www.cnblogs.com/mantch/p/11164221.html