本文参考文章：
- 《XGBoost中文文档》 http://xgboost.apachecn.org/cn/latest/model.html
- 《xgboost的原理没你想像的那么难》https://www.jianshu.com/p/7467e616f227
1. CART
-
函数
CART就是某种类似输入x，获得y的某种决策树，我们可以将其看作是一个函数y=f(x)。 -
连续 VS 离散
CART的叶子叶子节点处是连续数值，既可以处理回归问题，也可以处理分类问题（CART：Classification And Regression Tree）。 作为对比，decision trees（决策树）的叶子节点一般是离散值，这样就只能用来处理分类问题了。 -
二分
二分切分法：如果特征值大于给定值就走左子树，否则就走右子树。CART就是使用了二分切分来处理连续型变量。
针对每个特征：按照每个特征值，划分数据集两份，计算切分误差，比较当前最小误差，最终选出最佳切分。 -
剪枝
预剪枝：建树的时候，通过设定条件来停止某些点继续划分。比如在实行二分切分法的时候，设定一定条件（设定误差下降值，划分后误差不能下降这么多的话，那么就停止划分；设定最少样本数，划分后某一边的样本不能太少）。
后剪枝：需要将数据集分成测试集和训练集。训练集，构建足够复杂的树；测试集，判断叶节点合并是否可以降低测试误差，是的话就合并。
2. Boosting Decision Tree
-
整体认知
提升树的方法就是：一点一点地提升，不断地向最好的靠近。
比如上图中，TrainData中原有数据是<小明、3.2>，而一个CART树预测的值为<小明、2>，就不准确，我们需要添加CART树来完善结果，如下图。这就是一个Boosting的过程。
-
伪代码示例
有一批数据，一个个的权重一开始是一样的；
{
用一个弱分类器（如：CART）方法训练，找出此刻权重下较好的分类器；
将这个分类器记下，并计算出这个分类器的权重；（如下图）
统计错的、对的，更新一个个数据的权重；（如下图）
更新累计类别估计值；
} 循环到错误率满足条件
3. Gradient Boosting Decision Tree
为了求得最好的模型（求得模型参数），我们构造：损失函数与模型参数之间的函数 loss = f(θ)，并通过“梯度下降”的方式求得θ
θ = θ + Δθ —— 这是我们更新θ 的方式
在提升树（Boosting Decision Tree）的大前提下，我们要寻找的θ是所有树的参数（树的结构、叶子节点的分数），但是这样的话参数太多，因此为了便于计算，我们先将一棵树当作为一个θ，在损失函数与某一棵树之间构建关联，loss = f(tree)，之后再将深入考虑树的参数
以前是loss对θ求导，现在变成了loss对tree求导，这个寻求树的过程就是Gradient Boosting Decision Tree求解的过程。
4. XGBoost
- 本章注意事项：
- 将一个CART决策树看作是一个函数 y = f(x)
- 目标函数 = 损失函数 + 正则化公式
- 假设整个模型所需的K棵树的结构都已经确定，只需求K棵树的叶子节点的值
我们尝试使用数学公式表示XGBoost模型：用f(x)来表示一棵决策树，F表示所有决策树的一个集合，K棵决策树累加起来就是最终的预测结果。我们要做的就是：带入 x 求得 y^，计算 y 与 y^ 的差距（loss），沿着loss梯度下降的路径求解参数。
定义XGBoost的目标函数（它将衡量我们求出的值与实际值之间的差距）：
除了loss之外，这里还加了一个正则化。正则化的作用就是控制模型的复杂度，Ω(f)就表示了一棵树的复杂度。树的复杂度过高会导致过拟合。这里正则化也算是起到了预剪枝的作用。
至于loss函数怎么定义？
如果是回归问题，我们常用的损失函数是MSE，即：
如果是分类问题，我们常用的损失函数是对数损失函数：
正则化又怎么定义？
xgboost是这样定义的：
T代表的是叶子节点的个数，而ω则是每个叶子上的分数。γ和λ是需要手动调整的超参，它们值越大那么树的模型就越简单。至于树结构中的其他参数，正则化中就没有更多体现了，主要是T和ω足够了。
下面通过大量公式来说明加法训练（如上图）中是如何每次优化一棵树的：
学习树结构，由loss=f(tree)进入tree的结构细节
在我们将一片叶子分成两片时，采用如下分数衡量：
这个公式可以分解为 1) 新左叶上的得分 2) 新右叶上的得分 3) 原始叶子上的得分 4) additional leaf（附加叶子）上的正则化。 我们可以在这里看到一个重要的事实：如果增益小于 γ，我们最好不要添加那个分支。这正是基于树模型的 pruning（剪枝） 技术！
再看那个公式，如果Gain值是大于0的，说明下面这个值变大了，那么obj*就变小了，那就值得划分。
对于真实有价值的数据，我们通常要寻找一个最佳的分割。为了有效地做到这一点，我们把所有的实例按照排序顺序排列，如下图所示。
然后从左到右的扫描就足以计算所有可能的拆分解决方案的结构得分，我们可以有效地找到最佳的拆分。
