• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

6.GBDT、随机森林(RF)、Xgboost、LightGBM

互联网 diligentman 2周前 (10-15) 14次浏览

GBDT、随机森林(RF)、Xgboost、LightGBM

1.CART树

损失函数参考上一章

算法流程:

Step1:对于数据集D,遍历所有特征,根据Gini(D,A)找到A,用A对D进行划分

Step2:重复步骤1,为每个节点找寻到最佳特征直到:1)节点样本数小于阈值2)Gini(D,A)小于阈值3)没有更多的特征值

2.随机森林(bagging)

初始化:决策树的个数n,每个决策树里每次分裂所选取的特征个数k,$k = {log _2}n$

森林函数:$f(x) = frac{1}{n}sumlimits_i^n {{varphi _i}(x)}$

算法流程:

Step1:从原始数据集中有放回的抽n次,每次m个样本

Step2:$k = {log _2}n$,对每一组m个数据进行训练CART树,特征是从原始特征中随机选择k个

Setp3:每个树分裂下去,直到停止条件(参考CART树)

3.AdaBoost(Boosting

AdaBoost是boosting的想法,由一个弱学习器不断学习得到强学习器。AdaBoost主要增大了被分错样本的权重,改变的是样本的权重。

算法流程:

Input:训练数据集$T = { ({x_1},{y_1}),({x_2},{y_2}),…,({x_N},{y_N})}$

Output: 最终的分类器$G(x)$

1.初始化样本权重${D_0} = ({w_{0,1}},{w_{0,2}},…,{w_{0,N}})$

2.对设置要训练的M棵树(学习器)

  • 使用${D_m}$的权重样本数据进行训练,得到一个分类器${G_m}(x)$
  • 根据${G_m}(x)$计算分类误差:${e_m} = sumlimits_{i = 1}^N {{w_{mi}}} I({G_m}({x_i}) ne {y_i})$
  • 计算${G_m}(x)$的系数:${alpha _m} = frac{1}{2}log frac{{1 – {e_m}}}{{{e_m}}}$
  • 更新训练样本的权重:

$$
begin{array}{l}
{D_m} = ({w_{m,1}},{w_{m,2}},…,{w_{m,N}})\
{w_{m,i}} = frac{{{w_{m – 1,i}}}}{{{z_m}}}exp ( – {alpha _m}{y_i}{G_m}({x_i}))
end{array}
$$

  • 构建最终分类器的线性组合:

$$
G(x) = sign(sumlimits_{m = 1}^M {{alpha _m}{G_m}(x)} )
$$

其中权重有以下特点:

  • ${e_m}$越小,${alpha _m}$越大
  • 分类错误的${w_{m,i}}$ > 分类正确的${w_{m,i}}$

4.GBDT(Gradient Boost Decision Tree)梯度提升树

GBDT是以回归树为基学习器的算法,采用Boosting思想。GBDT的核心在于:每一棵树学的都是之前所有树叠加后的残差。利用损失函数的负梯度在当前模型的值作为回归树的残差近似值。

算法流程:

Input:训练数据集$T = { ({x_1},{y_1}),({x_2},{y_2}),…,({x_N},{y_N})}$

Output:回归树$widehat f(x)$

1.初始化:${f_0}(x) = mathop {arg min }limits_c sumlimits_{i = 1}^N {L({y_i},c)}$

2.对设置M棵树m=1,2,…,M:

  • 对i=1,2,…,N个样本,计算:${r_{mi}} = – {left[ {frac{{partial L({y_i},f({x_i}))}}{{partial f({x_i})}}} right]_{f(x) = {f_{m – 1}}(x)}}$
  • 对${r_{mi}}$拟合一棵回归树,得到第m棵树的结点最优区域${R_{mj}},j = 1,2,…,J$。这个J是J个类别(分类树),叶子节点个数,可以理解为y的值个数(回归树)
  • 求解最优j区域(特征)的阈值,计算${C_{mj}} = min sumlimits_{{x_i} in {R_{mj}}} {L({y_i},{f_{m – 1}}({x_i}) + c)}$
  • 更新${f_m}(x) = {f_{m – 1}}(x) + sumlimits_{j = 1}^J {{C_{mj}}I(x in {R_{mj}})}$

3.得到回归树:${f_m}(x) = sumlimits_{m = 1}^M {sumlimits_{j = 1}^J {{C_{mj}}I(x in {R_{mj}})} }$

这里需要提一点,如果设置树的深度为5,每次2分裂,那么J=10个叶子节点。有J个叶子节点就有J个判断条件

5.Xgboost

GBDT的升级版,从上面GBDT的算法流程中可以看出在负梯度中是一阶导数,并且在求解Cmj的时候是一个线性搜索,Xgboost把Rmj和Cmj合在一起求解,并且在损失函数中加入正则项

算法流程:

Input:训练数据集$T = { ({x_1},{y_1}),({x_2},{y_2}),…,({x_N},{y_N})}$

Output:回归树$widehat f(x)$

1.初始化:${f_0}(x) = mathop {arg min }limits_c sumlimits_{i = 1}^N {L({y_i},c)}$

2.对设置M棵树m=1,2,…,M:

  • 对i=1,2,…,N个样本,计算一阶导数合${G_t} = sumlimits_{i = 1}^N {{g_{ti}}} $以及二阶导数合${H_t} = sumlimits_{i = 1}^N {{h_{ti}}} $,其中:

$$
begin{array}{l}
{g_{ti}} = frac{{partial L({y_i},{f_{t – 1}}({x_i}))}}{{partial {f_{t – 1}}({x_i})}},
{h_{ti}} = frac{{{partial ^2}L({y_i},{f_{t – 1}}({x_i}))}}{{partial {f_{t – 1}}^2({x_i})}}
end{array}
$$

  • 求解最优j=1,2,…,J区域(特征)以及区域j阈值,根据${G_{tj}} = sumlimits_{xi in {R_{tj}}}^{} {{g_{ti}}} ,{H_{tj}} = sumlimits_{xi in {R_{tj}}}^{} {{h_{ti}}}$,求解叶子节点最优解:${omega _{tj}} = – frac{{{G_{tj}}}}{{{H_{tj}} + lambda }}$,这个类似于GBDT的区域求解。
  • 对于k=1,2,…,K个特征,每个k特征线性划分不同阈值进行线性搜索。初始化${rm{score = 0}},{G_L} = 0,{G_R} = 0$,对每个i样本,求左右树的一阶导数合二阶导数:

$$
begin{array}{l}
{G_L} = {G_L} + {g_{ti}},{G_R} = G – {G_L}\
{H_L} = {H_L} + {h_{ti}},{H_R} = H – {H_L}
end{array}
$$

  • 计算$score = max (score,frac{1}{2}(frac{{G_L^2}}{{{H_L} + lambda }} + frac{{G_R^2}}{{{H_R} + lambda }} – frac{{{{({G_L} + {G_R})}^2}}}{{{H_L} + {H_R} + lambda }}) – gamma )$

3.基于最大的score进行分裂
4.得到回归树:${f_m}(x) = sumlimits_{m = 1}^M {sumlimits_{j = 1}^J {{C_{mj}}I(x in {R_{mj}})} }$

参考https://ranmaosong.github.io/…

6.LightGBM

具体算法参见https://zhuanlan.zhihu.com/p/…
优化点:

  • 特征对不同取值进行直方图分bin
  • 带深度限制的叶子节点分裂,Xgboost在分裂叶子节点时候是对同一层的所有叶子节点无差别分裂,权重相同。这个是不合适的,因为每个叶子节点的分裂增益各不相同。ligtgbm对每一层只找到分裂增益最大的一个叶子节点进行分裂。
  • 对每个样本进行权重加成
  • 稀疏特征合并。

这里比较下GBDT合Xgboost的10个区别:

  • GBDT是机器学习算法,Xgboost是工程实现
  • Xgboost加入了正则项来防止过拟合
  • Xgboost采用一阶和二阶泰勒展开损失函数
  • Xgboost支持多种基学习器
  • Xgboost对缺失值进行了处理
  • Xgboost加入了Shrinkage(缩减),每棵树乘上一个学习率,这样的话可以多学习几轮。
  • Xgboost支持叶子节点分裂的并行操作。
  • Xgboost采用贪心算法,也就是对每次分裂都是最大增益,而不是一个总的最小损失函数
  • Xgboost对特征事先排序
  • Xgboost支持列抽样,参考随机森林的特征抽样

喜欢 (0)