基于决策树的分类回归（随机森林，xgboost, gbdt)

最近找工作，因为觉得以前做过比赛, 觉得自己听懂xgboost，随机森林的, 今天同实验室的一个小姐姐问了我几个问题，才发现一团乱麻，连最基本的都不懂，所以整理了一下思路。这里不重点讲定义，主要说明关系。

决策树

决策树生成包含三个步骤: 特征选择 ——> 决策树生成——> 决策树修剪:

1. 特征选择：理解: 根据某些规则选取使决策树性能最好的特征

   1.1 信息熵

   1.2 信息增益（缺点：偏向于选取值较多的特征）

   1.3 信息增益比（基于信息增益的改进，克服了了上述信息增益的缺点）

2. 决策树生成：

   2.1 ID3:在各个节点应用信息增益准测选择特征，递归构建决策树

   2.2 C4.5:在ID3的基础上进行了改进，其实就是使用了信息增益比准则进行特征选择， 其余不变

3. 决策树剪枝：防止过拟合

   3.1 生成树建好后， 通过最小化loss function 去掉可以说使性能变差或无用的

因为决策树生成是一步一步的， 决策树生成是学习局部模型， 而剪枝是在整个生成树的基础上最小化loss function，所以剪枝是学习全局模型。

随机森林

随机森林是由多个决策树构成(M个）， 每个决策树单独对数据进行预测， 最终结果取这M个决策树中类别最多的那一类。不同分类器是相互独立的。

在随机森林中，对每个决策树，加入了两个随机特征：

1. 随机选择样本： 对于N个样本的训练集，采取有放回抽样， boostraping N个样本，这样可以保证

   M个决策树的样本不同，防止over-fitting.

2. 对特征进行采样

gbdt vs xgboost.

首先这两个都是基于boosting的。当然也具有随机森林所提到的随机性。

关于boosting，大多数boosting 方法都是改变训练数据的概率分布，针对不同的训练数据分布调用弱分类器算法学习一系列弱分类器，一个分类器的训练是基于另一个分类器的， 所以boosting 是串行的。

不同的boosting具体规则又不同：

Adaboost:

1. 提高那些被前一轮分类器分错的样本的权值，这样分错的样本在下一轮随机选取中被选到的概率就很大，使得分类器讲注意力放在分错的样本上
2. 投票时，对于分类误差率较小的弱分类器赋予最大权值。

gbdt vs xgboost.

二者都是基于 上一个分类器的残差: 比如样本（x1, 10), (x2, 5), 第一分类器结果（x1, 6), (x2, 3),那么下一个分类器的训练样本就是（x1, 10-6), (x2, 5-3), 以次类推，直至残差为0，或小于某个阈值。

不同的是：

1. xgboost加入了第二项Ω， 模型复杂性惩罚项。

2. 在xgboost 中特征选择是基于自己定义的评估函数，类似于信息增益。

xgboost工具支持并行。boosting不是一种串行的结构吗?怎么并行的？注意xgboost的并行不是tree粒度的并行，xgboost也是一次迭代完才能进行下一次迭代的（第t次迭代的代价函数里包含了前面t-1次迭代的预测值）。xgboost的并行是在特征粒度上的。我们知道，决策树的学习最耗时的一个步骤就是对特征的值进行排序（因为要确定最佳分割点），xgboost在训练之前，预先对数据进行了排序，然后保存为block结构，后面的迭代中重复地使用这个结构，大大减小计算量。这个block结构也使得并行成为了可能，在进行节点的分裂时，需要计算每个特征的增益，最终选增益最大的那个特征去做分裂，那么各个特征的增益计算就可以开多线程进行。

xgboost 有用链接：ChenTianqi xgboost论文，讲真到现在我也才看到3.2

雪伦大神写的详细的xgboost

Weapon回答的xgboost和gbdt区别