XGBoost

效率优化

• 并行

  • boosting 算法的弱学习器无法并行迭代，弱学习器迭代过程中最耗时的部分是决策树的分裂过程。

  • 在不同线程中并行选择特征最大增益的特征划分点

• 内存优化

  • 对训练的每个特征排序并且以块的结构存储在内存中

• 存储+IO

  • 合理设置块的大小，充分利用 CPU 缓存进行读取加速

  • 分块压缩并且存储到硬盘上，将分块分区到多个硬盘上实现更大的 io

效果优化

• 缺失值处理

  • 首先忽略带缺失值的数据，像正常情况下一样将前两种数据分别计算并导流到左子树和右子树。
  • 然后计算带缺失值的数据导流向左右子树，计算两种方案下的Objective 情况，取得分最小的作为在这个节点的默认情况。

• 树模型的正则项控制模型复杂度

  • 叶子节点个数 + 叶子节点权重的 L2 正则化

  • 采用预剪枝策略，只有分裂后增益大于 0 才会进行分裂

寻找最佳分裂点以及如何加速

• 贪心算法 :-> 对特征值先排序，然后遍历所有可能分裂点计算分裂增益，取分裂增益最大的点，作为最优分裂点。
• 近似算法 :-> 使用特征值的分位数作为候选分裂点，三分位数
  稀疏感知算法

[[XGBoost/Loss]]

[[XGBoost/booster]]

[[XGBoost/特征重要性]]

[[XGBoost/code]]

[[XGBoost/Question]]

k分类实现

• 每一轮训练k棵树。

• 第一轮用 (x,0), (x,1) 去训练树，x 在每一棵树上的预测结果求 softmax 得出分类概率，然后计算残差。

• 第二轮用 (x,0-fi(x)), (x,1-fi(x)) 去训练树，和上面相同。

• 利用最后一轮的结果的 softmax 结果。