梯度提升决策树(GBDT)

GCDT:梯度提升决策树

Gradient Boosting Decision Tree,又叫做MART(Multiple Additive Regression Tree)迭代的决策树算法,由多颗决策树组成,具有较强的泛化能力。GBDT是一回归树用来做回归预测,调整后可以用于分类。

Regression Decision Tree:回归树

回归树的每一个节点都会有一个预测值(例如平均值),分支时穷举每一个feature的每个阈值找到最好的分割点,且用最小化平方误差进行衡量分类标准。也就是说分类错误越多平方误差越大,直到每个叶子节点上的预测值都能达到预设的终止条件。

Boosting Decision Tree:提升树算法

Boosting:将弱学习提升为强学习器的算法。主要思想:对于负责任务,将多个专家的判断进行适当综合得出对应的判断,比任何一个专家单独的判断要好。

提升树通过迭代多个回归树来进行共同决策。当采用平方误差损失函数,每一个回归树学习的是所有树的结论和残差,拟合得到当前的残差回归树。残差=真实值-预测值。提升树可以视作整个迭代过程生成的回归树的累加。

每一次迭代都增加被错误分类的样本的权重,使模型在之后的迭代中更加注意到难以分类的样本。

Xgboost 和 GBDT 的区别:

GBDT:

  1. GBDT 它的非线性变换比较多,表达能力强,而且不需要做复杂的特征工程和特征变换。
  2. GBDT 的缺点也很明显,Boost 是一个串行过程,不好并行化,而且计算复杂度高,同时不太适合高维稀疏特征;
  3. 传统 GBDT 在优化时只用到一阶导数信息。

Xgboost:

  1. 显示的把树模型复杂度作为正则项加到优化目标中。
  2. 公式推导中用到了二阶导数,用了二阶泰勒展开。(GBDT 用牛顿法貌似也是二阶信息)
  3. 实现了分裂点寻找近似算法。
  4. 利用了特征的稀疏性。
  5. 数据事先排序并且以 block 形式存储,有利于并行计算。
  6. 基于分布式通信框架 rabit,可以运行在 MPI 和 yarn 上。(最新已经不基于 rabit 了)
  7. 实现做了面向体系结构的优化,针对 cache 和内存做了性能优化