XGboost

概述

• 构造一个性能很高的预测(强学习器)是一件很困难事情
• 构造一个性能一般的预测(弱分类器)并不难
• 弱学习器：性能比随机猜测好(层数不深的CART(分类回归树)是一个好的选择)

集成算法在数据上构建很多个模型(多个弱评估器)，利用这些模型建模的结果，加以汇总，以获取比单个模型更好的回归或分类表现。这要求每一个单独的模型(弱评估器)必须要比随机猜测好，即预测准确率不低于50%(比如组哟分类，分类准确率治得好50%以上)，只有这样集成(ensemble)出来的结果才有可能比单个的要好。

集成算法有两种主流bagging（装袋法）和boosting（提升法）

• bagging：一次性建立多个平行独立的弱评估器（例如随机森林），同时对这些弱评估器的结果取平均来得到最终结果。
• boosting：逐一构建弱评估器，经过多次迭代逐渐积累多个弱评估器的方法（每一次迭代的过程中都增加一棵树，直到k次迭代建立k棵树为止）

boosting算法 如下图所示

提升集成算法

• 梯度提升树（分类树、回归树—— CART树算法为主流(全是二叉树)）
• Adaboost（adaboost也是以提升树为基准建立的集成模型）
• XGboost（由Gradient Boosting Tree 发展而来，其背后也是CART树）

下面讲一下XGboost

对于XGboost集成算法，我们要把所有的树都综合考虑进来，因为每棵树都会对结果产生影响。每次迭代增加一棵树时，都要使此时整体表达效果处于提升的状态。

• Objective for Tree Ensemble

模型：假设我们有K个树

目标函数（损失+正则化目标模式应用于回归树学习(函数学习)）：

接下来我们想一下：
有哪些可以定义Ω（正则化）的方法：
比如树的节点个数或深度、叶子结点权重的L2范数

• Gradient Boosting

对于上边给出的目标函数，我们不能使用SGD这样的方法来求f (因为它们是树，而不是数值向量)

解决办法：Additive Training (Boosting)

从常数预测开始，每次添加一个新函数

以下内容将用手写图片展现（流量警告！！！）

• 第一步

• 第二步（细化树的定义——其实就是告诉我们Ωf(x)长啥样）

• 第三步（这里使用平方损失，其实用别的也行）

• 第四步（想方设法的化简或变形objective 花里胡哨的）

泰勒展开 以及 定义一个一阶导g和一个二阶导h （就问你想不想得到吧= =）

对于上图小提示一下，泰勒展开中的f(x+△x)是把l(y,y(t-1)_hat)（真实值和前t-1次预测值的平方损失函数）当成x，把ft(xi)（即第t回要添加的树model）当成△x。

如果看不懂新目标函数是怎么来的，可以不想泰勒展开，把图中的圈1、圈2和圈3结合起来看一下就懂了，就是一个求完导后的恒等变形。

l(y,y(t-1)_hat)可以看成一个constant，新目标函数的常数项可以去掉。 最终话成这个鸭子！

• 第五步 （定义实例集 j，也表示叶子结点）

提示：对于树模型，样本最终会落到叶子结点上，在一棵树中的一个叶子节点上可能有多个样本落在了这里。

• 第六步（最终得到一个目标函数，评价公式Obj）

• 第七步（对于第六步中得到的目标函数进行举例）

• 第八步（Searching Algorithm for Single Tree）

• 第九步

可以想一下决策树中的熵值和基尼系数

• 最后举个例子说明一下第九步

更多详细内容参考下边的资料

以上内容是基于XGboost资料——Tianqi Chen大佬的slide

补充知识：

分类与回归树（classification and regression tree, CART）模型是应用广泛的决策树学习方法，同样由特征选择、树的生成和剪枝组成，既可以用于分类也可以用于回归。

CART算法主要由以下两步组成：

1. 决策树生成：基于训练数据集生成决策树，生成的决策树要尽量大。
2. 决策树剪枝：用验证数据集对已生成的树进行剪枝并选择最优子树，这时用损失函数最小作为剪枝的标准。