6.GBDT、随机森林(RF)、Xgboost、LightGBM
文章目录
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}\sum\limits_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} = \sum\limits_{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(\sum\limits_{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 \sum\limits_{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 \sum\limits_{{x_i} \in {R_{mj}}} {L({y_i},{f_{m - 1}}({x_i}) + c)}$
- 更新${f_m}(x) = {f_{m - 1}}(x) + \sum\limits_{j = 1}^J {{C_{mj}}I(x \in {R_{mj}})}$
3.得到回归树:${f_m}(x) = \sum\limits_{m = 1}^M {\sum\limits_{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 \sum\limits_{i = 1}^N {L({y_i},c)}$
2.对设置M棵树m=1,2,...,M:
- 对i=1,2,...,N个样本,计算一阶导数合${G_t} = \sum\limits_{i = 1}^N {{g_{ti}}} $以及二阶导数合${H_t} = \sum\limits_{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}} = \sum\limits_{xi \in {R_{tj}}}^{} {{g_{ti}}} ,{H_{tj}} = \sum\limits_{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) = \sum\limits_{m = 1}^M {\sum\limits_{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支持列抽样,参考随机森林的特征抽样
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论