Boosting
-
Boosting方法是使用同一组数据集进行反复学习,得到一系列简单模型,然后组合这些模型构成一个预测性能十分强大的机器学习模型。 -
Boosting思想提高最终的预测效果是通过不断减少偏差的形式,与Bagging有着本质的不同. -
基本思路 在概率近似正确PAC学习的框架下:
- 弱学习:识别错误率小于1/2(即准确率仅比随机猜测略高的学习算法)
- 强学习:识别准确率很高并能在多项式时间内完成的学习算法
在PAC 学习的框架下,强可学习和弱可学习是等价的,也就是说一个概念是强可学习的充分必要条件是这个概念是弱可学习的。 在学习中,如果已经发现了弱可学习算法,能否将他提升至强可学习算法。因为,弱可学习算法比强可学习算法容易得多。 提升方法就是从弱学习算法出发,反复学习,得到一系列弱分类器(又称为基本分类器),然后通过一定的形式去组合这些弱分类器构成一个强分类器。 大多数的Boosting方法都是通过改变训练数据集的概率分布(训练数据不同样本的权值),针对不同概率分布的数据调用弱分类算法学习一系列的弱分类器。 对于Boosting方法来说,有两个问题需要给出答案:
- 第一个是每一轮学习应该如何改变数据的概率分布,
- 第二个是如何将各个弱分类器组合起来。
Adaboost算法
- 解决方法
- 每一轮学习应该如何改变数据的概率分布: 提高那些被前一轮分类器错误分类的样本的权重,而降低那些被正确分类的样本的权重, 那些在上一轮分类器中没有得到正确分类的样本,由于其权重的增大而在后一轮的训练中“备受关注”
- 如何将各个弱分类器组合起来: 各个弱分类器的组合是通过采取加权多数表决的方式, 即加大分类错误率低的弱分类器的权重, 因为这些分类器能更好地完成分类任务, 而减小分类错误率较大的弱分类器的权重,使其在表决中起较小的作用.
- Adaboost算法
假设给定一个二分类的训练数据集:
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)},其中每个样本点由特征与类别组成。特征
x
i
∈
X
?
R
n
x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}
xi?∈X?Rn,类别
y
i
∈
Y
=
{
?
1
,
+
1
}
y_{i} \in \mathcal{Y}=\{-1,+1\}
yi?∈Y={?1,+1},
X
\mathcal{X}
X是特征空间,
Y
\mathcal{Y}
Y是类别集合,输出最终分类器
G
(
x
)
G(x)
G(x)。如下:
- 初始化训练数据的分布:
D
1
=
(
w
11
,
?
?
,
w
1
i
,
?
?
,
w
1
N
)
,
w
1
i
=
1
N
,
i
=
1
,
2
,
?
?
,
N
D_{1}=\left(w_{11}, \cdots, w_{1 i}, \cdots, w_{1 N}\right), \quad w_{1 i}=\frac{1}{N}, \quad i=1,2, \cdots, N
D1?=(w11?,?,w1i?,?,w1N?),w1i?=N1?,i=1,2,?,N
- 对于m=1,2,…,M
- 使用具有权值分布
D
m
D_m
Dm?的训练数据集进行学习,得到基本分类器:
G
m
(
x
)
:
X
→
{
?
1
,
+
1
}
G_{m}(x): \mathcal{X} \rightarrow\{-1,+1\}
Gm?(x):X→{?1,+1}
- 计算
G
m
(
x
)
G_m(x)
Gm?(x)在训练集上的分类误差率
e
m
=
∑
i
=
1
N
P
(
G
m
(
x
i
)
≠
y
i
)
=
∑
i
=
1
N
w
m
i
I
(
G
m
(
x
i
)
≠
y
i
)
e_{m}=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)=\sum_{i=1}^{N} w_{m i} I\left(G_{m}\left(x_{i}\right) \neq y_{i}\right)
em?=∑i=1N?P(Gm?(xi?)?=yi?)=∑i=1N?wmi?I(Gm?(xi?)?=yi?)
- 计算
G
m
(
x
)
G_m(x)
Gm?(x)的系数
α
m
=
1
2
log
?
1
?
e
m
e
m
\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}
αm?=21?logem?1?em??,这里的log是自然对数ln
- 更新训练数据集的权重分布
D
m
+
1
=
(
w
m
+
1
,
1
,
?
?
,
w
m
+
1
,
i
,
?
?
,
w
m
+
1
,
N
)
w
m
+
1
,
i
=
w
m
i
Z
m
exp
?
(
?
α
m
y
i
G
m
(
x
i
)
)
,
i
=
1
,
2
,
?
?
,
N
\begin{array}{c} D_{m+1}=\left(w_{m+1,1}, \cdots, w_{m+1, i}, \cdots, w_{m+1, N}\right) \\ w_{m+1, i}=\frac{w_{m i}}{Z_{m}} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right), \quad i=1,2, \cdots, N \end{array}
Dm+1?=(wm+1,1?,?,wm+1,i?,?,wm+1,N?)wm+1,i?=Zm?wmi??exp(?αm?yi?Gm?(xi?)),i=1,2,?,N?
这里的
Z
m
Z_m
Zm?是规范化因子,使得
D
m
+
1
D_{m+1}
Dm+1?称为概率分布,
Z
m
=
∑
i
=
1
N
w
m
i
exp
?
(
?
α
m
y
i
G
m
(
x
i
)
)
Z_{m}=\sum_{i=1}^{N} w_{m i} \exp \left(-\alpha_{m} y_{i} G_{m}\left(x_{i}\right)\right)
Zm?=∑i=1N?wmi?exp(?αm?yi?Gm?(xi?)) - 构建基本分类器的线性组合
f
(
x
)
=
∑
m
=
1
M
α
m
G
m
(
x
)
f(x)=\sum_{m=1}^{M} \alpha_{m} G_{m}(x)
f(x)=∑m=1M?αm?Gm?(x),得到最终的分类器
G
(
x
)
=
sign
?
(
f
(
x
)
)
=
sign
?
(
∑
m
=
1
M
α
m
G
m
(
x
)
)
G(x) =\operatorname{sign}(f(x)) =\operatorname{sign}\left(\sum_{m=1}^{M} \alpha_{m} G_{m}(x)\right)
G(x)=sign(f(x))=sign(∑m=1M?αm?Gm?(x))
下面对Adaboost算法做如下说明:
-
对于步骤(1),假设训练数据的权值分布是均匀分布,是为了使得第一次没有先验信息的条件下每个样本在基本分类器的学习中作用一样。 -
对于步骤(2),每一次迭代产生的基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)在加权训练数据集上的分类错误率
e
m
=
∑
i
=
1
N
P
(
G
m
(
x
i
)
≠
y
i
)
=
∑
G
m
(
x
i
)
≠
y
i
w
m
i
\begin{aligned}e_{m} &=\sum_{i=1}^{N} P\left(G_{m}\left(x_{i}\right) \neq y_{i}\right) =\sum_{G_{m}\left(x_{i}\right) \neq y_{i}} w_{m i}\end{aligned}
em??=i=1∑N?P(Gm?(xi?)?=yi?)=Gm?(xi?)?=yi?∑?wmi??代表了在
G
m
(
x
)
G_m(x)
Gm?(x)中分类错误的样本权重和,这点直接说明了权重分布
D
m
D_m
Dm?与
G
m
(
x
)
G_m(x)
Gm?(x)的分类错误率
e
m
e_m
em?有直接关系。同时,在步骤(2)中,计算基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的系数
α
m
\alpha_m
αm?,
α
m
=
1
2
log
?
1
?
e
m
e
m
\alpha_{m}=\frac{1}{2} \log \frac{1-e_{m}}{e_{m}}
αm?=21?logem?1?em??,它表示了
G
m
(
x
)
G_m(x)
Gm?(x)在最终分类器的重要性程度,
α
m
\alpha_m
αm?的取值由基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的分类错误率有直接关系,当
e
m
?
1
2
e_{m} \leqslant \frac{1}{2}
em??21?时,
α
m
?
0
\alpha_{m} \geqslant 0
αm??0,并且
α
m
\alpha_m
αm?随着
e
m
e_m
em?的减少而增大,因此分类错误率越小的基本分类器在最终分类器的作用越大! -
最重要的,对于步骤(2)中的样本权重的更新:
w
m
+
1
,
i
=
{
w
m
i
Z
m
e
?
α
m
,
G
m
(
x
i
)
=
y
i
w
m
i
Z
m
e
α
m
,
G
m
(
x
i
)
≠
y
i
w_{m+1, i}=\left\{\begin{array}{ll} \frac{w_{m i}}{Z_{m}} \mathrm{e}^{-\alpha_{m}}, & G_{m}\left(x_{i}\right)=y_{i} \\ \frac{w_{m i}}{Z_{m}} \mathrm{e}^{\alpha_{m}}, & G_{m}\left(x_{i}\right) \neq y_{i} \end{array}\right.
wm+1,i?={Zm?wmi??e?αm?,Zm?wmi??eαm?,?Gm?(xi?)=yi?Gm?(xi?)?=yi?? 因此,从上式可以看到:被基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)错误分类的样本的权重扩大,被正确分类的样本权重减少,二者相比相差
e
2
α
m
=
1
?
e
m
e
m
\mathrm{e}^{2 \alpha_{m}}=\frac{1-e_{m}}{e_{m}}
e2αm?=em?1?em??倍。 -
对于步骤(3),线性组合
f
(
x
)
f(x)
f(x)实现了将M个基本分类器的加权表决,系数
α
m
\alpha_m
αm?标志了基本分类器
G
m
(
x
)
G_m(x)
Gm?(x)的重要性,值得注意的是:所有的
α
m
\alpha_m
αm?之和不为1。
f
(
x
)
f(x)
f(x)的符号决定了样本x属于哪一类。
from sklearn.tree import DecisionTreeClassifier
tree = DecisionTreeClassifier(criterion='entropy',random_state=1,max_depth=1)
'''
AdaBoostClassifier相关参数:
base_estimator:基本分类器,默认为DecisionTreeClassifier(max_depth=1)
n_estimators:终止迭代的次数
learning_rate:学习率
algorithm:训练的相关算法,{'SAMME','SAMME.R'},默认='SAMME.R'
random_state:随机种子
'''
from sklearn.ensemble import AdaBoostClassifier
ada = AdaBoostClassifier(base_estimator=tree,n_estimators=500,learning_rate=0.1,random_state=1)
ada = ada.fit(X_train,y_train)
y_train_pred = ada.predict(X_train)
y_test_pred = ada.predict(X_test)
ada_train = accuracy_score(y_train,y_train_pred)
ada_test = accuracy_score(y_test,y_test_pred)
print('Adaboost train/test accuracies %.3f/%.3f' % (ada_train,ada_test))
- Adaboost模型的决策边界比单层决策树的决策边界要复杂的多。
- Adaboost试图用增加模型复杂度而降低偏差的方式去减少总误差,但是过程中引入了方差,可能出现过拟合,因此在训练集和测试集之间的性能存在较大的差距,
- 值的注意的是:与单个分类器相比,Adaboost等Boosting模型增加了计算的复杂度,在实践中需要仔细思考是否愿意为预测性能的相对改善而增加计算成本,而且Boosting方式无法做到现在流行的并行计算的方式进行训练,因为每一步迭代都要基于上一步的基本分类器。
前向分步算法
需要通过计算M个基本分类器,每个分类器的错误率、样本权重以及模型权重。可以认为:Adaboost每次学习单一分类器以及单一分类器的参数(权重)。
-
加法模型 在Adaboost模型中,我们把每个基本分类器合成一个复杂分类器的方法是每个基本分类器的加权和,即:
f
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
f(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)
f(x)=∑m=1M?βm?b(x;γm?),其中,
b
(
x
;
γ
m
)
b\left(x ; \gamma_{m}\right)
b(x;γm?)为基本分类器,
γ
m
\gamma_{m}
γm?为基本分类器的参数,
β
m
\beta_m
βm?为基本分类器的权重, 在给定训练数据以及损失函数
L
(
y
,
f
(
x
)
)
L(y, f(x))
L(y,f(x))的条件下,学习加法模型
f
(
x
)
f(x)
f(x)就是:
min
?
β
m
,
γ
m
∑
i
=
1
N
L
(
y
i
,
∑
m
=
1
M
β
m
b
(
x
i
;
γ
m
)
)
\min {\beta_m, \gamma_{m}} \sum_{i=1}^{N} L\left(y_{i}, \sum_{m=1}^{M} \beta_{m} b\left(x_{i} ; \gamma_{m}\right)\right)
minβm?,γm?∑i=1N?L(yi?,∑m=1M?βm?b(xi?;γm?)) 通常这是一个复杂的优化问题,很难通过简单的凸优化的相关知识进行解决。前向分步算法可以用来求解这种方式的问题, 基本思路是:因为学习的是加法模型,如果从前向后,每一步只优化一个基函数及其系数,逐步逼近目标函数,那么就可以降低优化的复杂度。具体而言,每一步只需要优化:
min
?
β
,
γ
∑
i
=
1
N
L
(
y
i
,
β
b
(
x
i
;
γ
)
)
\min {\beta, \gamma} \sum{i=1}^{N} L\left(y_{i}, \beta b\left(x_{i} ; \gamma\right)\right)
minβ,γ∑i=1NL(yi?,βb(xi?;γ)) -
前向分步算法: 给定数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)},
x
i
∈
X
?
R
n
x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}
xi?∈X?Rn,
y
i
∈
Y
=
{
+
1
,
?
1
}
y_{i} \in \mathcal{Y}=\{+1,-1\}
yi?∈Y={+1,?1}。损失函数
L
(
y
,
f
(
x
)
)
L(y, f(x))
L(y,f(x)),基函数集合
{
b
(
x
;
γ
)
}
\{b(x ; \gamma)\}
{b(x;γ)},我们需要输出加法模型
f
(
x
)
f(x)
f(x)。
- 初始化:
f
0
(
x
)
=
0
f_{0}(x)=0
f0?(x)=0
- 对m = 1,2,…,M:
- 极小化损失函数:
(
β
m
,
γ
m
)
=
arg
?
min
?
β
,
γ
∑
i
=
1
N
L
(
y
i
,
f
m
?
1
(
x
i
)
+
β
b
(
x
i
;
γ
)
)
\left(\beta_{m}, \gamma_{m}\right)=\arg \min {\beta, \gamma} \sum{i=1}^{N} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+\beta b\left(x_{i} ; \gamma\right)\right)
(βm?,γm?)=argminβ,γ∑i=1NL(yi?,fm?1?(xi?)+βb(xi?;γ)) 得到参数
β
m
\beta_{m}
βm?与
γ
m
\gamma_{m}
γm? - 更新:
f
m
(
x
)
=
f
m
?
1
(
x
)
+
β
m
b
(
x
;
γ
m
)
f_{m}(x)=f_{m-1}(x)+\beta_{m} b\left(x ; \gamma_{m}\right)
fm?(x)=fm?1?(x)+βm?b(x;γm?)
- 得到加法模型:
f
(
x
)
=
f
M
(
x
)
=
∑
m
=
1
M
β
m
b
(
x
;
γ
m
)
f(x)=f_{M}(x)=\sum_{m=1}^{M} \beta_{m} b\left(x ; \gamma_{m}\right)
f(x)=fM?(x)=∑m=1M?βm?b(x;γm?)
这样,前向分步算法将同时求解从m=1到M的所有参数
β
m
\beta_{m}
βm?,
γ
m
\gamma_{m}
γm?的优化问题简化为逐次求解各个
β
m
\beta_{m}
βm?,
γ
m
\gamma_{m}
γm?的问题。 -
前向分步算法与Adaboost的关系: Adaboost算法是前向分步算法的特例,Adaboost算法是由基本分类器组成的加法模型,损失函数为指数损失函数。具体的证明见李航老师的《统计学习方法》第八章的3.2节。
GBDT(梯度提升决策树)
-
基于残差学习的提升树算法
- 使用加法模型+前向分步算法的框架实现回归问题
- 使用决策树分类器, 使用平方损失确定分裂标准
- 使用残差表示预测错误率
- 输入数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
,
x
i
∈
X
?
R
n
,
y
i
∈
Y
?
R
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}, x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}, y_{i} \in \mathcal{Y} \subseteq \mathbf{R}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)},xi?∈X?Rn,yi?∈Y?R,输出最终的提升树
f
M
(
x
)
f_{M}(x)
fM?(x)
- 初始化
f
0
(
x
)
=
0
f_0(x) = 0
f0?(x)=0
- 对m = 1,2,…,M:
- 计算每个样本的残差:
r
m
i
=
y
i
?
f
m
?
1
(
x
i
)
,
i
=
1
,
2
,
?
?
,
N
r_{m i}=y_{i}-f_{m-1}\left(x_{i}\right), \quad i=1,2, \cdots, N
rmi?=yi??fm?1?(xi?),i=1,2,?,N
- 拟合残差
r
m
i
r_{mi}
rmi?学习一棵回归树,得到
T
(
x
;
Θ
m
)
T\left(x ; \Theta_{m}\right)
T(x;Θm?)
- 更新
f
m
(
x
)
=
f
m
?
1
(
x
)
+
T
(
x
;
Θ
m
)
f_{m}(x)=f_{m-1}(x)+T\left(x ; \Theta_{m}\right)
fm?(x)=fm?1?(x)+T(x;Θm?)
- 得到最终的回归问题的提升树:
f
M
(
x
)
=
∑
m
=
1
M
T
(
x
;
Θ
m
)
f_{M}(x)=\sum_{m=1}^{M} T\left(x ; \Theta_{m}\right)
fM?(x)=∑m=1M?T(x;Θm?)
-
梯度提升决策树算法(GBDT)
- 提升树利用加法模型和前向分步算法实现学习的过程,当损失函数为平方损失和指数损失时,每一步优化是相当简单的。但是对于一般的损失函数而言,往往每一步的优化不是那么容易,针对这一问题,我们得分析问题的本质,也就是是什么导致了在一般损失函数条件下的学习困难。对比以下损失函数:
?Setting?
?Loss?Function?
?
?
L
(
y
i
,
f
(
x
i
)
)
/
?
f
(
x
i
)
?Regression?
1
2
[
y
i
?
f
(
x
i
)
]
2
y
i
?
f
(
x
i
)
?Regression?
∣
y
i
?
f
(
x
i
)
∣
sign
?
[
y
i
?
f
(
x
i
)
]
?Regression?
?Huber?
y
i
?
f
(
x
i
)
?for?
∣
y
i
?
f
(
x
i
)
∣
≤
δ
m
δ
m
sign
?
[
y
i
?
f
(
x
i
)
]
?for?
∣
y
i
?
f
(
x
i
)
∣
>
δ
m
?where?
δ
m
=
α
?th-quantile?
{
∣
y
i
?
f
(
x
i
)
∣
}
?Classification?
?Deviance?
k
?th?component:?
I
(
y
i
=
G
k
)
?
p
k
(
x
i
)
\begin{array}{l|l|l} \hline \text { Setting } & \text { Loss Function } & -\partial L\left(y_{i}, f\left(x_{i}\right)\right) / \partial f\left(x_{i}\right) \\ \hline \text { Regression } & \frac{1}{2}\left[y_{i}-f\left(x_{i}\right)\right]^{2} & y_{i}-f\left(x_{i}\right) \\ \hline \text { Regression } & \left|y_{i}-f\left(x_{i}\right)\right| & \operatorname{sign}\left[y_{i}-f\left(x_{i}\right)\right] \\ \hline \text { Regression } & \text { Huber } & y_{i}-f\left(x_{i}\right) \text { for }\left|y_{i}-f\left(x_{i}\right)\right| \leq \delta_{m} \\ & & \delta_{m} \operatorname{sign}\left[y_{i}-f\left(x_{i}\right)\right] \text { for }\left|y_{i}-f\left(x_{i}\right)\right|>\delta_{m} \\ & & \text { where } \delta_{m}=\alpha \text { th-quantile }\left\{\left|y_{i}-f\left(x_{i}\right)\right|\right\} \\ \hline \text { Classification } & \text { Deviance } & k \text { th component: } I\left(y_{i}=\mathcal{G}{k}\right)-p{k}\left(x_{i}\right) \\ \hline \end{array}
?Setting??Regression??Regression??Regression??Classification???Loss?Function?21?[yi??f(xi?)]2∣yi??f(xi?)∣?Huber??Deviance????L(yi?,f(xi?))/?f(xi?)yi??f(xi?)sign[yi??f(xi?)]yi??f(xi?)?for?∣yi??f(xi?)∣≤δm?δm?sign[yi??f(xi?)]?for?∣yi??f(xi?)∣>δm??where?δm?=α?th-quantile?{∣yi??f(xi?)∣}k?th?component:?I(yi?=Gk)?pk(xi?)??
- 观察Huber损失函数:
L
δ
(
y
,
f
(
x
)
)
=
{
1
2
(
y
?
f
(
x
)
)
2
?for?
∣
y
?
f
(
x
)
∣
≤
δ
δ
∣
y
?
f
(
x
)
∣
?
1
2
δ
2
?otherwise?
L_{\delta}(y, f(x))=\left\{\begin{array}{ll} \frac{1}{2}(y-f(x))^{2} & \text { for }|y-f(x)| \leq \delta \\ \delta|y-f(x)|-\frac{1}{2} \delta^{2} & \text { otherwise } \end{array}\right.
Lδ?(y,f(x))={21?(y?f(x))2δ∣y?f(x)∣?21?δ2??for?∣y?f(x)∣≤δ?otherwise??
- 提出了梯度提升算法(gradient boosting),这是利用最速下降法的近似方法,利用损失函数的负梯度在当前模型的值
?
[
?
L
(
y
,
f
(
x
i
)
)
?
f
(
x
i
)
]
f
(
x
)
=
f
m
?
1
(
x
)
-\left[\frac{\partial L\left(y, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]{f(x)=f{m-1}(x)}
?[?f(xi?)?L(y,f(xi?))?]f(x)=fm?1(x)
- 作为回归问题提升树算法中的残差的近似值,拟合回归树。与其说负梯度作为残差的近似值,不如说残差是负梯度的一种特例。
- 梯度提升算法
- 输入训练数据集
T
=
{
(
x
1
,
y
1
)
,
(
x
2
,
y
2
)
,
?
?
,
(
x
N
,
y
N
)
}
,
x
i
∈
X
?
R
n
,
y
i
∈
Y
?
R
T=\left\{\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \cdots,\left(x_{N}, y_{N}\right)\right\}, x_{i} \in \mathcal{X} \subseteq \mathbf{R}^{n}, y_{i} \in \mathcal{Y} \subseteq \mathbf{R}
T={(x1?,y1?),(x2?,y2?),?,(xN?,yN?)},xi?∈X?Rn,yi?∈Y?R和损失函数
L
(
y
,
f
(
x
)
)
L(y, f(x))
L(y,f(x)),输出回归树
f
^
(
x
)
\hat{f}(x)
f^?(x)
- 初始化
f
0
(
x
)
=
arg
?
min
?
c
∑
i
=
1
N
L
(
y
i
,
c
)
f_{0}(x)=\arg \min {c} \sum_{i=1}^{N} L\left(y_{i}, c\right)
f0?(x)=argminc∑i=1N?L(yi?,c)
- 对于m=1,2,…,M:
- 对i = 1,2,…,N计算:
r
m
i
=
?
[
?
L
(
y
i
,
f
(
x
i
)
)
?
f
(
x
i
)
]
f
(
x
)
=
f
m
?
1
(
x
)
r_{m i}=-\left[\frac{\partial L\left(y_{i}, f\left(x_{i}\right)\right)}{\partial f\left(x_{i}\right)}\right]{f(x)=f{m-1}(x)}
rmi?=?[?f(xi?)?L(yi?,f(xi?))?]f(x)=fm?1(x)
- 对
r
m
i
r_{mi}
rmi?拟合一个回归树,得到第m棵树的叶结点区域
R
m
j
,
j
=
1
,
2
,
?
?
,
J
R_{m j}, j=1,2, \cdots, J
Rmj?,j=1,2,?,J
- 对j=1,2,…J,计算:
c
m
j
=
arg
?
min
?
c
∑
x
i
∈
R
m
j
L
(
y
i
,
f
m
?
1
(
x
i
)
+
c
)
c_{m j}=\arg \min {c} \sum{x_{i} \in R_{m j}} L\left(y_{i}, f_{m-1}\left(x_{i}\right)+c\right)
cmj?=argminc∑xi?∈Rmj?L(yi?,fm?1?(xi?)+c)
- 更新
f
m
(
x
)
=
f
m
?
1
(
x
)
+
∑
j
=
1
J
c
m
j
I
(
x
∈
R
m
j
)
f_{m}(x)=f_{m-1}(x)+\sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)
fm?(x)=fm?1?(x)+∑j=1J?cmj?I(x∈Rmj?)
- 得到回归树:
f
^
(
x
)
=
f
M
(
x
)
=
∑
m
=
1
M
∑
j
=
1
J
c
m
j
I
(
x
∈
R
m
j
)
\hat{f}(x)=f_{M}(x)=\sum_{m=1}^{M} \sum_{j=1}^{J} c_{m j} I\left(x \in R_{m j}\right)
f^?(x)=fM?(x)=∑m=1M?∑j=1J?cmj?I(x∈Rmj?)
from sklearn.metrics import mean_squared_error
from sklearn.datasets import make_friedman1
from sklearn.ensemble import GradientBoostingRegressor
'''
GradientBoostingRegressor参数解释:
loss:{‘ls’, ‘lad’, ‘huber’, ‘quantile’}, default=’ls’:‘ls’ 指最小二乘回归. ‘lad’ (最小绝对偏差) 是仅基于输入变量的顺序信息的高度鲁棒的损失函数。. ‘huber’ 是两者的结合. ‘quantile’允许分位数回归(用于alpha指定分位数)
learning_rate:学习率缩小了每棵树的贡献learning_rate。在learning_rate和n_estimators之间需要权衡。
n_estimators:要执行的提升次数。
subsample:用于拟合各个基础学习者的样本比例。如果小于1.0,则将导致随机梯度增强。subsample与参数n_estimators。选择会导致方差减少和偏差增加。subsample < 1.0
criterion:{'friedman_mse','mse','mae'},默认='friedman_mse':“ mse”是均方误差,“ mae”是平均绝对误差。默认值“ friedman_mse”通常是最好的,因为在某些情况下它可以提供更好的近似值。
min_samples_split:拆分内部节点所需的最少样本数
min_samples_leaf:在叶节点处需要的最小样本数。
min_weight_fraction_leaf:在所有叶节点处(所有输入样本)的权重总和中的最小加权分数。如果未提供sample_weight,则样本的权重相等。
max_depth:各个回归模型的最大深度。最大深度限制了树中节点的数量。调整此参数以获得最佳性能;最佳值取决于输入变量的相互作用。
min_impurity_decrease:如果节点分裂会导致杂质的减少大于或等于该值,则该节点将被分裂。
min_impurity_split:提前停止树木生长的阈值。如果节点的杂质高于阈值,则该节点将分裂
max_features{‘auto’, ‘sqrt’, ‘log2’},int或float:寻找最佳分割时要考虑的功能数量:
如果为int,则max_features在每个分割处考虑特征。
如果为float,max_features则为小数,并 在每次拆分时考虑要素。int(max_features * n_features)
如果“auto”,则max_features=n_features。
如果是“ sqrt”,则max_features=sqrt(n_features)。
如果为“ log2”,则为max_features=log2(n_features)。
如果没有,则max_features=n_features。
'''
X, y = make_friedman1(n_samples=1200, random_state=0, noise=1.0)
X_train, X_test = X[:200], X[200:]
y_train, y_test = y[:200], y[200:]
est = GradientBoostingRegressor(n_estimators=100, learning_rate=0.1,
max_depth=1, random_state=0, loss='ls').fit(X_train, y_train)
mean_squared_error(y_test, est.predict(X_test))
XGBoost
-
高效地实现了GBDT算法并进行了算法和工程上的许多改进 -
XGBoost本质上还是一个GBDT,但是力争把速度和效率发挥到极致,所以叫X (Extreme) GBoosted -
XGBoost是一个优化的分布式梯度增强库,旨在实现高效,灵活和便携。 它在Gradient Boosting框架下实现机器学习算法 -
XGBoost提供了并行树提升(也称为GBDT,GBM),可以快速准确地解决许多数据科学问题 -
相同的代码在主要的分布式环境(Hadoop,SGE,MPI)上运行,并且可以解决超过数十亿个样例的问题。XGBoost利用了核外计算并且能够使数据科学家在一个主机上处理数亿的样本数据。 -
Xgboost以CART决策树为子模型,通过Gradient Tree Boosting实现多棵CART树的集成学习,得到最终模型。下面我们来看看XGBoost的最终模型构建: -
数据为:
D
=
{
(
x
i
,
y
i
)
}
(
∣
D
∣
=
n
,
x
i
∈
R
m
,
y
i
∈
R
)
\mathcal{D}=\left\{\left(\mathbf{x}_{i}, y_{i}\right)\right\}\left(|\mathcal{D}|=n, \mathbf{x}_{i} \in \mathbb{R}^{m}, y_{i} \in \mathbb{R}\right)
D={(xi?,yi?)}(∣D∣=n,xi?∈Rm,yi?∈R) -
构造目标函数: 假设有K棵树,则第i个样本的输出为
y
^
i
=
?
(
x
i
)
=
∑
k
=
1
K
f
k
(
x
i
)
,
f
k
∈
F
\hat{y}_{i}=\phi\left(\mathrm{x}_{i}\right)=\sum_{k=1}^{K} f_{k}\left(\mathrm{x}_{i}\right), \quad f_{k} \in \mathcal{F}
y^?i?=?(xi?)=∑k=1K?fk?(xi?),fk?∈F,其中,
F
=
{
f
(
x
)
=
w
q
(
x
)
}
(
q
:
R
m
→
T
,
w
∈
R
T
)
\mathcal{F}=\left\{f(\mathbf{x})=w_{q(\mathbf{x})}\right\}\left(q: \mathbb{R}^{m} \rightarrow T, w \in \mathbb{R}^{T}\right)
F={f(x)=wq(x)?}(q:Rm→T,w∈RT) 目标函数的构建为:
L
(
?
)
=
∑
i
l
(
y
^
i
,
y
i
)
+
∑
k
Ω
(
f
k
)
\mathcal{L}(\phi)=\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)+\sum_{k} \Omega\left(f_{k}\right)
L(?)=∑i?l(y^?i?,yi?)+∑k?Ω(fk?) 其中
∑
i
l
(
y
^
i
,
y
i
)
\sum_{i} l\left(\hat{y}_{i}, y_{i}\right)
∑i?l(y^?i?,yi?)为loss function,
∑
k
Ω
(
f
k
)
\sum_{k} \Omega\left(f_{k}\right)
∑k?Ω(fk?)为正则化项。 -
叠加式的训练(Additive Training): 给定样本
x
i
x_i
xi?,
y
^
i
(
0
)
=
0
\hat{y}_i^{(0)} = 0
y^?i(0)?=0(初始预测),
y
^
i
(
1
)
=
y
^
i
(
0
)
+
f
1
(
x
i
)
\hat{y}_i^{(1)} = \hat{y}_i^{(0)} + f_1(x_i)
y^?i(1)?=y^?i(0)?+f1?(xi?),
y
^
i
(
2
)
=
y
^
i
(
0
)
+
f
1
(
x
i
)
+
f
2
(
x
i
)
=
y
^
i
(
1
)
+
f
2
(
x
i
)
\hat{y}_i^{(2)} = \hat{y}_i^{(0)} + f_1(x_i) + f_2(x_i) = \hat{y}i^{(1)} + f_2(x_i)
y^?i(2)?=y^?i(0)?+f1?(xi?)+f2?(xi?)=y^?i(1)+f2?(xi?)…以此类推,可以得到:
y
^
i
(
K
)
=
y
^
i
(
K
?
1
)
+
f
K
(
x
i
)
\hat{y}_i^{(K)} = \hat{y}_i^{(K-1)} + f_K(x_i)
y^?i(K)?=y^?i(K?1)?+fK?(xi?) ,其中,
y
^
i
(
K
?
1
)
\hat{y}i^{(K-1)}
y^?i(K?1) 为前K-1棵树的预测结果,
f
K
(
x
i
)
f_K(x_i)
fK?(xi?) 为第K棵树的预测结果。 目标函数可以分解为:
L
(
K
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
K
?
1
)
+
f
K
(
x
i
)
)
+
∑
k
Ω
(
f
k
)
\mathcal{L}^{(K)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\sum_{k} \Omega\left(f_{k}\right)
L(K)=∑i=1n?l(yi?,y^?i(K?1)?+fK?(xi?))+∑k?Ω(fk?) 由于正则化项也可以分解为前K-1棵树的复杂度加第K棵树的复杂度,因此:
L
(
K
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
K
?
1
)
+
f
K
(
x
i
)
)
+
∑
k
=
1
K
?
1
Ω
(
f
k
)
+
Ω
(
f
K
)
\mathcal{L}^{(K)}=\sum{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\sum_{k=1} ^{K-1}\Omega\left(f_{k}\right)+\Omega\left(f_{K}\right)
L(K)=∑i=1nl(yi?,y^?i(K?1)?+fK?(xi?))+∑k=1K?1?Ω(fk?)+Ω(fK?),由于
∑
k
=
1
K
?
1
Ω
(
f
k
)
\sum_{k=1} ^{K-1}\Omega\left(f_{k}\right)
∑k=1K?1?Ω(fk?)在模型构建到第K棵树的时候已经固定,无法改变,因此是一个已知的常数,可以在最优化的时候省去,故:
L
(
K
)
=
∑
i
=
1
n
l
(
y
i
,
y
^
i
(
K
?
1
)
+
f
K
(
x
i
)
)
+
Ω
(
f
K
)
\mathcal{L}^{(K)}=\sum_{i=1}^{n} l\left(y_{i}, \hat{y}_{i}^{(K-1)}+f_{K}\left(\mathrm{x}_{i}\right)\right)+\Omega\left(f_{K}\right)
L(K)=∑i=1n?l(yi?,y^?i(K?1)?+fK?(xi?))+Ω(fK?) -
使用泰勒级数近似目标函数:
L
(
K
)
?
∑
i
=
1
n
[
l
(
y
i
,
y
^
(
K
?
1
)
)
+
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
\mathcal{L}^{(K)} \simeq \sum_{i=1}^{n}\left[l\left(y_{i}, \hat{y}^{(K-1)}\right)+g_{i} f_{K}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(\mathrm{x}_{i}\right)\right]+\Omega\left(f_{K}\right)
L(K)?i=1∑n?[l(yi?,y^?(K?1))+gi?fK?(xi?)+21?hi?fK2?(xi?)]+Ω(fK?) 其中,
g
i
=
?
y
^
(
t
?
1
)
l
(
y
i
,
y
^
(
t
?
1
)
)
g_{i}=\partial_{\hat{y}(t-1)} l\left(y_{i}, \hat{y}^{(t-1)}\right)
gi?=?y^?(t?1)?l(yi?,y^?(t?1))和
h
i
=
?
y
^
(
t
?
1
)
2
l
(
y
i
,
y
^
(
t
?
1
)
)
h_{i}=\partial_{\hat{y}^{(t-1)}}^{2} l\left(y_{i}, \hat{y}^{(t-1)}\right)
hi?=?y^?(t?1)2?l(yi?,y^?(t?1)) 由于
∑
i
=
1
n
l
(
y
i
,
y
^
(
K
?
1
)
)
\sum_{i=1}^{n}l\left(y_{i}, \hat{y}^{(K-1)}\right)
∑i=1n?l(yi?,y^?(K?1))在模型构建到第K棵树的时候已经固定,无法改变,因此是一个已知的常数,可以在最优化的时候省去,故:
L
~
(
K
)
=
∑
i
=
1
n
[
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
Ω
(
f
K
)
\tilde{\mathcal{L}}^{(K)}=\sum_{i=1}^{n}\left[g_{i} f_{K}\left(\mathbf{x}_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(\mathbf{x}_{i}\right)\right]+\Omega\left(f_{K}\right)
L~(K)=i=1∑n?[gi?fK?(xi?)+21?hi?fK2?(xi?)]+Ω(fK?) -
如何定义一棵树:
-
样本所在的节点位置
q
(
x
)
q(x)
q(x), -
有哪些样本落在节点j上
I
j
=
{
i
∣
q
(
x
i
)
=
j
}
I_{j}=\left\{i \mid q\left(\mathbf{x}_{i}\right)=j\right\}
Ij?={i∣q(xi?)=j} -
每个结点的预测值
w
q
(
x
)
w_{q(x)}
wq(x)? -
模型复杂度
Ω
(
f
K
)
\Omega\left(f_{K}\right)
Ω(fK?),它可以由叶子节点的个数以及节点函数值来构建,则:
Ω
(
f
K
)
=
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
\Omega\left(f_{K}\right) = \gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2}
Ω(fK?)=γT+21?λ∑j=1T?wj2?。 -
目标函数用以上符号替代后:
L
~
(
K
)
=
∑
i
=
1
n
[
g
i
f
K
(
x
i
)
+
1
2
h
i
f
K
2
(
x
i
)
]
+
γ
T
+
1
2
λ
∑
j
=
1
T
w
j
2
=
∑
j
=
1
T
[
(
∑
i
∈
I
j
g
i
)
w
j
+
1
2
(
∑
i
∈
I
j
h
i
+
λ
)
w
j
2
]
+
γ
T
\begin{aligned} \tilde{\mathcal{L}}^{(K)} &=\sum_{i=1}^{n}\left[g_{i} f_{K}\left(\mathrm{x}_{i}\right)+\frac{1}{2} h_{i} f_{K}^{2}\left(\mathrm{x}_{i}\right)\right]+\gamma T+\frac{1}{2} \lambda \sum_{j=1}^{T} w_{j}^{2} \\ &=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T \end{aligned}
L~(K)?=i=1∑n?[gi?fK?(xi?)+21?hi?fK2?(xi?)]+γT+21?λj=1∑T?wj2?=j=1∑T???????i∈Ij?∑?gi????wj?+21????i∈Ij?∑?hi?+λ???wj2????+γT? -
由于我们的目标就是最小化目标函数,现在的目标函数化简为一个关于w的二次函数:
L
~
(
K
)
=
∑
j
=
1
T
[
(
∑
i
∈
I
j
g
i
)
w
j
+
1
2
(
∑
i
∈
I
j
h
i
+
λ
)
w
j
2
]
+
γ
T
\tilde{\mathcal{L}}^{(K)}=\sum_{j=1}^{T}\left[\left(\sum_{i \in I_{j}} g_{i}\right) w_{j}+\frac{1}{2}\left(\sum_{i \in I_{j}} h_{i}+\lambda\right) w_{j}^{2}\right]+\gamma T
L~(K)=∑j=1T?[(∑i∈Ij??gi?)wj?+21?(∑i∈Ij??hi?+λ)wj2?]+γT,根据二次函数求极值的公式:
y
=
a
x
2
b
x
c
y=ax^2 bx c
y=ax2bxc求极值,对称轴在
x
=
?
b
2
a
x=-\frac{b}{2 a}
x=?2ab?,极值为
y
=
4
a
c
?
b
2
4
a
y=\frac{4 a c-b^{2}}{4 a}
y=4a4ac?b2?,因此:
w
j
?
=
?
∑
i
∈
I
j
g
i
∑
i
∈
I
j
h
i
+
λ
w_{j}^{*}=-\frac{\sum_{i \in I_{j}} g_{i}}{\sum_{i \in I_{j}} h_{i}+\lambda}
wj??=?∑i∈Ij??hi?+λ∑i∈Ij??gi?? 以及
L
~
(
K
)
(
q
)
=
?
1
2
∑
j
=
1
T
(
∑
i
∈
I
j
g
i
)
2
∑
i
∈
I
j
h
i
+
λ
+
γ
T
\tilde{\mathcal{L}}^{(K)}(q)=-\frac{1}{2} \sum_{j=1}^{T} \frac{\left(\sum_{i \in I_{j}} g_{i}\right)^{2}}{\sum_{i \in I_{j}} h_{i}+\lambda}+\gamma T
L~(K)(q)=?21?∑j=1T?∑i∈Ij??hi?+λ(∑i∈Ij??gi?)2?+γT -
如何寻找树的形状:
-
上述基于树的形状已经确定了计算w和L,但是实际上我们需要像学习决策树一样找到树的形状。因此,我们借助决策树学习的方式,使用目标函数的变化来作为分裂节点的标准。 -
分割节点的标准为
m
a
x
{
L
~
(
o
l
d
)
?
L
~
(
n
e
w
)
}
max\{\tilde{\mathcal{L}}^{(old)} - \tilde{\mathcal{L}}^{(new)} \}
max{L~(old)?L~(new)},即:
L
split?
=
1
2
[
(
∑
i
∈
I
L
g
i
)
2
∑
i
∈
I
L
h
i
+
λ
+
(
∑
i
∈
I
R
g
i
)
2
∑
i
∈
I
R
h
i
+
λ
?
(
∑
i
∈
I
g
i
)
2
∑
i
∈
I
h
i
+
λ
]
?
γ
\mathcal{L}_{\text {split }}=\frac{1}{2}\left[\frac{\left(\sum_{i \in I_{L}} g_{i}\right)^{2}}{\sum_{i \in I_{L}} h_{i}+\lambda}+\frac{\left(\sum_{i \in I_{R}} g_{i}\right)^{2}}{\sum_{i \in I_{R}} h_{i}+\lambda}-\frac{\left(\sum_{i \in I} g_{i}\right)^{2}}{\sum_{i \in I} h_{i}+\lambda}\right]-\gamma
Lsplit??=21?[∑i∈IL??hi?+λ(∑i∈IL??gi?)2?+∑i∈IR??hi?+λ(∑i∈IR??gi?)2??∑i∈I?hi?+λ(∑i∈I?gi?)2?]?γ -
精确贪心分裂算法: XGBoost在生成新树的过程中,最基本的操作是节点分裂。节点分裂中最重 要的环节是找到最优特征及最优切分点, 然后将叶子节点按照最优特征和最优切 分点进行分裂。选取最优特征和最优切分点的一种思路如下:首先找到所有的候 选特征及所有的候选切分点, 一一求得其
L
split?
\mathcal{L}_{\text {split }}
Lsplit??, 然后选择
L
s
p
l
i
t
\mathcal{L}_{\mathrm{split}}
Lsplit? 最大的特征及 对应切分点作为最优特征和最优切分点。我们称此种方法为精确贪心算法。该算法是一种启发式算法, 因为在节点分裂时只选择当前最优的分裂策略, 而非全局最优的分裂策略。精确贪心算法的计算过程如下所示: [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4XtNbVEP-1627034704945)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/6a448f99-8336-49ac-9d51-3c964536e82f/18.png)] -
基于直方图的近似算法 精确贪心算法在选择最优特征和最优切分点时是一种十分有效的方法。它计算了所有特征、所有切分点的收益, 并从中选择了最优的, 从而保证模型能比较好地拟合了训练数据。但是当数据不能完全加载到内存时,精确贪心算法会变得 非常低效,算法在计算过程中需要不断在内存与磁盘之间进行数据交换,这是个非常耗时的过程, 并且在分布式环境中面临同样的问题。为了能够更高效地选 择最优特征及切分点, XGBoost提出一种近似算法来解决该问题。 基于直方图的近似算法的主要思想是:对某一特征寻找最优切分点时,首先对该特征的所有切分点按分位数 (如百分位) 分桶, 得到一个候选切分点集。特征的每一个切分点都可以分到对应的分桶; 然后,对每个桶计算特征统计G和H得到直方图, G为该桶内所有样本一阶特征统计g之和, H为该桶内所有样本二阶特征统计h之和; 最后,选择所有候选特征及候选切分点中对应桶的特征统计收益最大的作为最优特征及最优切分点。基于直方图的近似算法的计算过程如下所示:
-
对于每个特征
k
=
1
,
2
,
?
?
,
m
,
k=1,2, \cdots, m,
k=1,2,?,m,按分位数对特征k分桶
Θ
\Theta
Θ可得候选切分点,
S
k
=
{
S
k
1
,
S
k
2
,
?
?
,
S
k
l
}
1
S_{k}=\left\{S_{k 1}, S_{k 2}, \cdots, S_{k l}\right\}^{1}
Sk?={Sk1?,Sk2?,?,Skl?}1 -
对于每个特征
k
=
1
,
2
,
?
?
,
m
,
k=1,2, \cdots, m,
k=1,2,?,m,有
G
k
v
←
=
∑
j
∈
{
j
∣
s
k
,
v
≥
x
j
k
>
s
k
,
v
?
1
??
}
g
j
H
k
v
←
=
∑
j
∈
{
j
∣
s
k
,
v
≥
x
j
k
>
s
k
,
v
?
1
??
}
h
j
\begin{array}{l} G_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}{j k}>s{k, v-1\;}\right\}} g_{j} \\ H_{k v} \leftarrow=\sum_{j \in\left\{j \mid s_{k, v} \geq \mathbf{x}{j k}>s{k, v-1\;}\right\}} h_{j} \end{array}
Gkv?←=∑j∈{j∣sk,v?≥xjk>sk,v?1}?gj?Hkv?←=∑j∈{j∣sk,v?≥xjk>sk,v?1}?hj?? -
类似精确贪心算法,依据梯度统计找到最大增益的候选切分点。 近似算法实现了两种候选切分点的构建策略:全局策略和本地策略。全局策略是在树构建的初始阶段对每一个特征确定一个候选切分点的集合, 并在该树每一层的节点分裂中均采用此集合计算收益, 整个过程候选切分点集合不改变。本地策略则是在每一次节点分裂时均重新确定候选切分点。全局策略需要更细的分桶才能达到本地策略的精确度, 但全局策略在选取候选切分点集合时比本地策略更简单。在XGBoost系统中, 用户可以根据需求自由选择使用精确贪心算法、近似算法全局策略、近似算法本地策略, 算法均可通过参数进行配置。
官方文档:https://xgboost.readthedocs.io/en/latest/python/python_intro.html
笔者自己的总结:https://zhuanlan.zhihu.com/p/143009353
import xgboost as xgb
dtrain = xgb.DMatrix('demo/data/agaricus.txt.train')
dtest = xgb.DMatrix('demo/data/agaricus.txt.test')
param = {'max_depth':2, 'eta':1, 'objective':'binary:logistic' }
num_round = 2
bst = xgb.train(param, dtrain, num_round)
preds = bst.predict(dtest)
XGBoost的参数
XGBoost的参数设置(括号内的名称为sklearn接口对应的参数名字):
推荐博客:https://link.zhihu.com/?target=https%3A//blog.csdn.net/luanpeng825485697/article/details/79907149
推荐官方文档:https://link.zhihu.com/?target=https%3A//xgboost.readthedocs.io/en/latest/parameter.html
- 通用参数:(两种类型的booster,因为tree的性能比线性回归好得多,因此我们很少用线性回归。)
- booster:使用哪个弱学习器训练,默认gbtree,可选gbtree,gblinear 或dart
- nthread:用于运行XGBoost的并行线程数,默认为最大可用线程数
- verbosity:打印消息的详细程度。有效值为0(静默),1(警告),2(信息),3(调试)。
- Tree Booster的参数:
- eta(learning_rate):learning_rate,在更新中使用步长收缩以防止过度拟合,默认= 0.3,范围:[0,1];典型值一般设置为:0.01-0.2
- gamma(min_split_loss):默认= 0,分裂节点时,损失函数减小值只有大于等于gamma节点才分裂,gamma值越大,算法越保守,越不容易过拟合,但性能就不一定能保证,需要平衡。范围:[0,∞]
- max_depth:默认= 6,一棵树的最大深度。增加此值将使模型更复杂,并且更可能过度拟合。范围:[0,∞]
- min_child_weight:默认值= 1,如果新分裂的节点的样本权重和小于min_child_weight则停止分裂 。这个可以用来减少过拟合,但是也不能太高,会导致欠拟合。范围:[0,∞]
- max_delta_step:默认= 0,允许每个叶子输出的最大增量步长。如果将该值设置为0,则表示没有约束。如果将其设置为正值,则可以帮助使更新步骤更加保守。通常不需要此参数,但是当类极度不平衡时,它可能有助于逻辑回归。将其设置为1-10的值可能有助于控制更新。范围:[0,∞]
- subsample:默认值= 1,构建每棵树对样本的采样率,如果设置成0.5,XGBoost会随机选择一半的样本作为训练集。范围:(0,1]
- sampling_method:默认= uniform,用于对训练实例进行采样的方法。
- uniform:每个训练实例的选择概率均等。通常将subsample> = 0.5 设置 为良好的效果。
- gradient_based:每个训练实例的选择概率与规则化的梯度绝对值成正比,具体来说就是
g
2
+
λ
h
2
\sqrt{g^2+\lambda h^2}
g2+λh2
?,subsample可以设置为低至0.1,而不会损失模型精度。
- colsample_bytree:默认= 1,列采样率,也就是特征采样率。范围为(0,1]
- lambda(reg_lambda):默认=1,L2正则化权重项。增加此值将使模型更加保守。
- alpha(reg_alpha):默认= 0,权重的L1正则化项。增加此值将使模型更加保守。
- tree_method:默认=auto,XGBoost中使用的树构建算法。
- auto:使用启发式选择最快的方法。
- 对于小型数据集,exact将使用精确贪婪()。
- 对于较大的数据集,approx将选择近似算法()。它建议尝试hist,gpu_hist,用大量的数据可能更高的性能。(gpu_hist)支持。external memory外部存储器。
- exact:精确的贪婪算法。枚举所有拆分的候选点。
- approx:使用分位数和梯度直方图的近似贪婪算法。
- hist:更快的直方图优化的近似贪婪算法。(LightGBM也是使用直方图算法)
- gpu_hist:GPU hist算法的实现。
- scale_pos_weight:控制正负权重的平衡,这对于不平衡的类别很有用。Kaggle竞赛一般设置sum(negative instances) / sum(positive instances),在类别高度不平衡的情况下,将参数设置大于0,可以加快收敛。
- num_parallel_tree:默认=1,每次迭代期间构造的并行树的数量。此选项用于支持增强型随机森林。
- monotone_constraints:可变单调性的约束,在某些情况下,如果有非常强烈的先验信念认为真实的关系具有一定的质量,则可以使用约束条件来提高模型的预测性能。(例如params_constrained[‘monotone_constraints’] = “(1,-1)”,(1,-1)我们告诉XGBoost对第一个预测变量施加增加的约束,对第二个预测变量施加减小的约束。)
- Linear Booster的参数:
- lambda(reg_lambda):默认= 0,L2正则化权重项。增加此值将使模型更加保守。归一化为训练示例数。
- alpha(reg_alpha):默认= 0,权重的L1正则化项。增加此值将使模型更加保守。归一化为训练示例数。
- updater:默认= shotgun。
- shotgun:基于shotgun算法的平行坐标下降算法。使用“ hogwild”并行性,因此每次运行都产生不确定的解决方案。
- coord_descent:普通坐标下降算法。同样是多线程的,但仍会产生确定性的解决方案。
- feature_selector:默认= cyclic。特征选择和排序方法
- cyclic:通过每次循环一个特征来实现的。
- shuffle:类似于cyclic,但是在每次更新之前都有随机的特征变换。
- random:一个随机(有放回)特征选择器。
- greedy:选择梯度最大的特征。(贪婪选择)
- thrifty:近似贪婪特征选择(近似于greedy)
- top_k:要选择的最重要特征数(在greedy和thrifty内)
- 任务参数(这个参数用来控制理想的优化目标和每一步结果的度量方法。)
- objective:默认=reg:squarederror,表示最小平方误差。
- reg:squarederror,最小平方误差。
- reg:squaredlogerror,对数平方损失。
1
2
[
l
o
g
(
p
r
e
d
+
1
)
?
l
o
g
(
l
a
b
e
l
+
1
)
]
2
\frac{1}{2}[log(pred+1)-log(label+1)]^2
21?[log(pred+1)?log(label+1)]2
- reg:logistic,逻辑回归
- reg:pseudohubererror,使用伪Huber损失进行回归,这是绝对损失的两倍可微选择。
- binary:logistic,二元分类的逻辑回归,输出概率。
- binary:logitraw:用于二进制分类的逻辑回归,逻辑转换之前的输出得分。
- binary:hinge:二进制分类的铰链损失。这使预测为0或1,而不是产生概率。(SVM就是铰链损失函数)
- count:poisson –计数数据的泊松回归,泊松分布的输出平均值。
- survival:cox:针对正确的生存时间数据进行Cox回归(负值被视为正确的生存时间)。
- survival:aft:用于检查生存时间数据的加速故障时间模型。
- aft_loss_distribution:survival:aft和aft-nloglik度量标准使用的概率密度函数。
- multi:softmax:设置XGBoost以使用softmax目标进行多类分类,还需要设置num_class(类数)
- multi:softprob:与softmax相同,但输出向量,可以进一步重整为矩阵。结果包含属于每个类别的每个数据点的预测概率。
- rank:pairwise:使用LambdaMART进行成对排名,从而使成对损失最小化。
- rank:ndcg:使用LambdaMART进行列表式排名,使标准化折让累积收益(NDCG)最大化。
- rank:map:使用LambdaMART进行列表平均排名,使平均平均精度(MAP)最大化。
- reg:gamma:使用对数链接进行伽马回归。输出是伽马分布的平均值。
- reg:tweedie:使用对数链接进行Tweedie回归。
- 自定义损失函数和评价指标:https://xgboost.readthedocs.io/en/latest/tutorials/custom_metric_obj.html
- eval_metric:验证数据的评估指标,将根据目标分配默认指标(回归均方根,分类误差,排名的平均平均精度),用户可以添加多个评估指标
- rmse,均方根误差; rmsle:均方根对数误差; mae:平均绝对误差;mphe:平均伪Huber错误;logloss:负对数似然; error:二进制分类错误率;
- merror:多类分类错误率; mlogloss:多类logloss; auc:曲线下面积; aucpr:PR曲线下的面积;ndcg:归一化累计折扣;map:平均精度;
- seed :随机数种子,[默认= 0]。
- 命令行参数(这里不说了,因为很少用命令行控制台版本)
参数调优的一般步骤
- 确定学习速率和提升参数调优的初始值
- max_depth 和 min_child_weight 参数调优
- gamma参数调优
- subsample 和 colsample_bytree 参数优
- 正则化参数alpha调优
- 降低学习速率和使用更多的决策树
XGBoost详细攻略:
具体的api请查看:
https://xgboost.readthedocs.io/en/latest/python/python_api.html
推荐github:
https://github.com/dmlc/xgboost/tree/master/demo/guide-python
dtrain = xgb.DMatrix('train.svm.txt')
dtest = xgb.DMatrix('test.svm.buffer')
dtrain = xgb.DMatrix('train.csv?format=csv&label_column=0')
dtest = xgb.DMatrix('test.csv?format=csv&label_column=0')
data = np.random.rand(5, 10)
label = np.random.randint(2, size=5)
dtrain = xgb.DMatrix(data, label=label)
csr = scipy.sparse.csr_matrix((dat, (row, col)))
dtrain = xgb.DMatrix(csr)
data = pandas.DataFrame(np.arange(12).reshape((4,3)), columns=['a', 'b', 'c'])
label = pandas.DataFrame(np.random.randint(2, size=4))
dtrain = xgb.DMatrix(data, label=label)
dtrain = xgb.DMatrix('train.svm.txt')
dtrain.save_binary('train.buffer')
dtrain = xgb.DMatrix(data, label=label, missing=-999.0)
w = np.random.rand(5, 1)
dtrain = xgb.DMatrix(data, label=label, missing=-999.0, weight=w)
df_wine = pd.read_csv('https://archive.ics.uci.edu/ml/machine-learning-databases/wine/wine.data',header=None)
df_wine.columns = ['Class label', 'Alcohol','Malic acid', 'Ash','Alcalinity of ash','Magnesium', 'Total phenols',
'Flavanoids', 'Nonflavanoid phenols','Proanthocyanins','Color intensity', 'Hue','OD280/OD315 of diluted wines','Proline']
df_wine = df_wine[df_wine['Class label'] != 1]
y = df_wine['Class label'].values
X = df_wine[['Alcohol','OD280/OD315 of diluted wines']].values
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import LabelEncoder
le = LabelEncoder()
y = le.fit_transform(y)
X_train,X_test,y_train,y_test = train_test_split(X,y,test_size=0.2,random_state=1,stratify=y)
dtrain = xgb.DMatrix(X_train, label=y_train)
dtest = xgb.DMatrix(X_test)
params = {
'booster': 'gbtree',
'objective': 'multi:softmax',
'num_class': 10,
'gamma': 0.1,
'max_depth': 12,
'lambda': 2,
'subsample': 0.7,
'colsample_bytree': 0.7,
'min_child_weight': 3,
'silent': 1,
'eta': 0.007,
'seed': 1000,
'nthread': 4,
'eval_metric':'auc'
}
plst = params.items()
num_round = 10
bst = xgb.train( plst, dtrain, num_round)
bst.save_model('0001.model')
bst.dump_model('dump.raw.txt')
bst = xgb.Booster({'nthread': 4})
bst.load_model('0001.model')
train(..., evals=evals, early_stopping_rounds=10)
ypred = bst.predict(dtest)
xgb.plot_importance(bst)
LightGBM算法
LightGBM也是像XGBoost一样,是一类集成算法,他跟XGBoost总体来说是一样的,算法本质上与Xgboost没有出入,只是在XGBoost的基础上进行了优化,因此就不对原理进行重复介绍,在这里我们来看看几种算法的差别:
- 优化速度和内存使用
- 降低了计算每个分割增益的成本。
- 使用直方图减法进一步提高速度。
- 减少内存使用。
- 减少并行学习的计算成本。
- 稀疏优化
- 用离散的bin替换连续的值。如果#bins较小,则可以使用较小的数据类型(例如uint8_t)来存储训练数据 。
- 无需存储其他信息即可对特征数值进行预排序 。
- 精度优化
- 使用叶子数为导向的决策树建立算法而不是树的深度导向。
- 分类特征的编码方式的优化
- 通信网络的优化
- 并行学习的优化
- GPU支持
- LightGBM的优点:
- 更快的训练效率
- 低内存使用
- 更高的准确率
- 支持并行化学习
- 可以处理大规模数据
LightGBM参数说明:
推荐文档1:
https://lightgbm.apachecn.org/#/docs/6
推荐文档2:
https://lightgbm.readthedocs.io/en/latest/Parameters.html
1.核心参数:(括号内名称是别名)
- objective(objective,app ,application):默认regression,用于设置损失函数
- 回归问题:
- L2损失:regression(regression_l2,l2,mean_squared_error,mse,l2_root,root_mean_squared_error,rmse)
- L1损失:regression_l1(l1, mean_absolute_error, mae)
- 其他损失:huber,fair,poisson,quantile,mape,gamma,tweedie
- 二分类问题:二进制对数损失分类(或逻辑回归):binary
- 多类别分类:
- softmax目标函数: multiclass(softmax)
- One-vs-All 目标函数:multiclassova(multiclass_ova,ova,ovr)
- 交叉熵:
- 用于交叉熵的目标函数(具有可选的线性权重):cross_entropy(xentropy)
- 交叉熵的替代参数化:cross_entropy_lambda(xentlambda)
- boosting :默认gbdt,设置提升类型,选项有gbdt,rf,dart,goss,别名:boosting_type,boost
- gbdt(gbrt):传统的梯度提升决策树
- rf(random_forest):随机森林
- dart:多个加性回归树的DROPOUT方法 Dropouts meet Multiple Additive Regression Trees,参见:https://arxiv.org/abs/1505.01866
- goss:基于梯度的单边采样 Gradient-based One-Side Sampling
- data(train,train_data,train_data_file,data_filename):用于训练的数据或数据file
- valid (test,valid_data,valid_data_file,test_data,test_data_file,valid_filenames):验证/测试数据的路径,LightGBM将输出这些数据的指标
- num_iterations:默认=100,类型= INT
- n_estimators:提升迭代次数,LightGBM构造用于多类分类问题的树num_class * num_iterations
- learning_rate(shrinkage_rate,eta) :收缩率,默认=0.1
- num_leaves(num_leaf,max_leaves,max_leaf) :默认=31,一棵树上的最大叶子数
- tree_learner (tree,tree_type,tree_learner_type):默认=serial,可选:serial,feature,data,voting
- serial:单台机器的 tree learner
- feature:特征并行的 tree learner
- data:数据并行的 tree learner
- voting:投票并行的 tree learner
- num_threads(num_thread, nthread):LightGBM 的线程数,为了更快的速度, 将此设置为真正的 CPU 内核数, 而不是线程的数量 (大多数 CPU 使用超线程来使每个 CPU 内核生成 2 个线程),当你的数据集小的时候不要将它设置的过大 (比如, 当数据集有 10,000 行时不要使用 64 线程),对于并行学习, 不应该使用全部的 CPU 内核, 因为这会导致网络性能不佳。
- device(device_type):默认cpu,为树学习选择设备, 你可以使用 GPU 来获得更快的学习速度,可选cpu, gpu。
- seed (random_seed,random_state):与其他种子相比,该种子具有较低的优先级,这意味着如果您明确设置其他种子,它将被覆盖。
2.用于控制模型学习过程的参数:
- max_depth:限制树模型的最大深度. 这可以在 #data 小的情况下防止过拟合. 树仍然可以通过 leaf-wise 生长。
- min_data_in_leaf: 默认=20,一个叶子上数据的最小数量. 可以用来处理过拟合。
- min_sum_hessian_in_leaf(min_sum_hessian_per_leaf, min_sum_hessian, min_hessian):默认=1e-3,一个叶子上的最小 hessian 和. 类似于 min_data_in_leaf, 可以用来处理过拟合.
- feature_fraction:default=1.0,如果 feature_fraction 小于 1.0, LightGBM 将会在每次迭代中随机选择部分特征. 例如, 如果设置为 0.8, 将会在每棵树训练之前选择 80% 的特征,可以用来加速训练,可以用来处理过拟合。
- feature_fraction_seed:默认=2,feature_fraction 的随机数种子。
- bagging_fraction(sub_row, subsample):默认=1,不进行重采样的情况下随机选择部分数据
- bagging_freq(subsample_freq):bagging 的频率, 0 意味着禁用 bagging. k 意味着每 k 次迭代执行bagging
- bagging_seed(bagging_fraction_seed) :默认=3,bagging 随机数种子。
- early_stopping_round(early_stopping_rounds, early_stopping):默认=0,如果一个验证集的度量在 early_stopping_round 循环中没有提升, 将停止训练
- lambda_l1(reg_alpha):L1正则化系数
- lambda_l2(reg_lambda):L2正则化系数
- min_split_gain(min_gain_to_split):执行切分的最小增益,默认=0.
- cat_smooth:默认=10,用于分类特征,可以降低噪声在分类特征中的影响, 尤其是对数据很少的类别
3.度量参数:
- metric:default={l2 for regression}, {binary_logloss for binary classification}, {ndcg for lambdarank}, type=multi-enum, options=l1, l2, ndcg, auc, binary_logloss, binary_error …
- l1, absolute loss, alias=mean_absolute_error, mae
- l2, square loss, alias=mean_squared_error, mse
- l2_root, root square loss, alias=root_mean_squared_error, rmse
- quantile, Quantile regression
- huber, Huber loss
- fair, Fair loss
- poisson, Poisson regression
- ndcg, NDCG
- map, MAP
- auc, AUC
- binary_logloss, log loss
- binary_error, 样本: 0 的正确分类, 1 错误分类
- multi_logloss, mulit-class 损失日志分类
- multi_error, error rate for mulit-class 出错率分类
- xentropy, cross-entropy (与可选的线性权重), alias=cross_entropy
- xentlambda, “intensity-weighted” 交叉熵, alias=cross_entropy_lambda
- kldiv, Kullback-Leibler divergence, alias=kullback_leibler
- 支持多指标, 使用 , 分隔
- train_metric(training_metric, is_training_metric):默认=False,如果你需要输出训练的度量结果则设置 true
4.GPU 参数:
- gpu_device_id:default为-1, 这个default意味着选定平台上的设备。
作业
- Adaboost的基本思路
- 每一轮学习应该如何改变数据的概率分布: 提高那些被前一轮分类器错误分类的样本的权重,而降低那些被正确分类的样本的权重, 那些在上一轮分类器中没有得到正确分类的样本,由于其权重的增大而在后一轮的训练中“备受关注”
- 如何将各个弱分类器组合起来: 各个弱分类器的组合是通过采取加权多数表决的方式, 即加大分类错误率低的弱分类器的权重, 因为这些分类器能更好地完成分类任务, 而减小分类错误率较大的弱分类器的权重,使其在表决中起较小的作用.
- Adaboost与GBDT的联系与区别
![在这里插入图片描述](https://img-blog.csdnimg.cn/56c0983022ca4413abfd1a449dbd438e.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk1NTI1NQ==,size_16,color_FFFFFF,t_70)
- Boosting与Baggin的区别, 以及如何提升模型的精度
- Boosting方法是使用同一组数据集进行反复学习,得到一系列简单模型,然后组合这些模型构成一个预测性能十分强大的机器学习模型。Boosting思想提高最终的预测效果是通过不断减少偏差的形式,与Bagging有着本质的不同.
- Bagging通过组合不同的基学习器来做到模型精度的提升
- 使用基本分类模型和Boosting提升的模型, 并画出他们的决策边界
![在这里插入图片描述](https://img-blog.csdnimg.cn/5b8a9a864cf54249bc2e64532b3780ef.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTk1NTI1NQ==,size_16,color_FFFFFF,t_70)
- 尝试使用XGboost模型完成一个具体的分类任务, 并进行调参
参考
|