ID3、C4.5、CART、GBDT、XGBoost、RF、AdaBoost等模型原理及联系

ID3、C4.5、CART、GBDT、XGBoost、RF、AdaBoost等模型原理及联系

---

---

联系

因为都是关于树的，所以将之总结在一起，方便理解和学习。差异表现在除了决策树和分类回归树外，其他四个学习模型(算法)利用了一个集成学习的思想。集成学习三大流派：boosting，bagging，stacking。其中，GBDT、AdaBoost属于boosting，而RF属于bagging。boosting类串行训练，预测可并行。bagging类训练预测都可并行，利用好这一特点可以在模型使用效率上有个很大的提升。

---

前提知识

问题描述和相关定义

熵的概念和物理学上的有点雷同，但是表示不太一样。我们关注信息世界的定义。熵表示一个随机变量的不确定性度量，联想物理熵可以知道一个常识：混乱程度越大其熵越大。信息熵中不确定性越大其熵越大。以下是相关定义。

• 一个随机变量
• $P(X=x_i)=p_i,i=1,2,3?$
• 两个随机变量
• $P(X=x_i,Y=y_i)=p_{ij},i=1,2,3,?,n;j=1,2,3,?,m$

推导该结论的过程如下。
刻画信息熵的概念，可以构造一个函数表达式：（注意：这里是通过客观世界对信息熵概念而构造出的函数，就和机器学习的损失函数构造过程相似，并不是由某个理论推导而来，而是因为有一个概念，我们通过一个函数去反映我们要表达的概念。）

• 一个随机变量
  单个随机变量的信息熵:$H（X）=?{\sum }_{i=1}^n{p}_{i}log{p}_i$
• 两个随机变量
  条件熵
  $H(Y|X)={\sum }_{i=1}^n{p}_{i}H(Y|X=x_i),p_i=P(X=x_i),i=1,2,?,n$
  有了条件熵就可以刻画信息增益这个概念
  $g（D，A）=H(D)?H(D|A)$
  互信息
  $H(Y)?H(Y|X)$
  对比高亮的两个部分可以发现，其公式内涵相同，所以，在决策树中，信息增益是指特征和分类的互信息，实质上信息增益就是互信息，信息增益是在树模型中的一个统一叫法，但也不排除在其他类似场景中依然可以这样称呼。

根据信息熵的定义：判定一个事件不确定的度量。那么事件在决策树是什么事件，在给定很多样本特征的条件下，选择一个特征进行分支，使得分支后使得整个分类结果不确定性减少最多。所以这是决策树的分支过程核心，即并不是随机选取一个特征进行选择分支的，而是依赖于信息熵和信息增益的概念。
比如：我们要分类一批水果，判断是否是苹果，在你面前是无数个水果（样本），你要选取一个特征要最快得出它是苹果（既是代价函数也是标签），那么样本有无数个特征（属性），对于所有样本的某个特征( { X = x i 1 , x i 2 , x i 3 , ? , x i n } ) （ 这 里 的 \{X=x_{i}^{1},x_{i}^{2},x_{i}^{3},\cdots,x_{i}^n\})（这里的 { X=xi1?,xi2?,xi3?,?,xin?})（这里的n$为样本数，$i$为特征数。以之并列的是其他特征，是作为已经发生的条件）$所以$X$是一个事件，选取特征实现分支（初分类）也是一个事件，后者这个事件是针对信息熵使用来说的那个事件，前者是针对信息熵定义$H(Y|X)={\sum }_{i=1}^n{p}_{i}H(Y|X=x_i),p_i=P(X=x_i),i=1,2,?,n$都有一个信息增益，我们可以算出这个信息熵、信息增益、互信息。这里假设有个特征苹果口味，根据常识，如果根据这个特征来判定它是苹果可以说确定下来这个事件的可能性很，则信息量对于这个结果来讲很大，也就是信息熵$H(X)$越大，所以这个信息熵是相对确定这个结果来讲的，所以需要$H(D)$的概念，这才有知道特征确定结果的可能性，如果没有进行做差操作，就只是单纯的就某个特征来讲信息量有多大，就这个事件本身的不确定性是多大。如果还不能理解请再关注以下公式，它是指一个事件的总的信息量。而信息增益加入了相对的概念，特征到结果的过程包含两个事件。$用H和D刻画$，其值越大就说明这个特征使得事件被确定下来的可能性越大，这里可以看出，这就是决策树的一个损失函数，我们根据这个评估标准去训练整个模型，再在其基础上加入正则项防止过拟合。关于损失函数这一点，这里似乎和极大似然函数有关系，它们都是从统计量的角度思考特征和标签的关系进行不断拟合的过程，后续将更新对损失函数的进一步理解。
计算机和统计学领域，我们说的熵通常是信息熵，经验熵和熵有啥不一样？经验熵是统计量，根据样本统计出来的熵，可能同一个事件统计出来的数据不同而发生改变了，这就是经验熵，因为一个事件对应一个熵，从理论上说是不会有第二值的，除非事件条件改变。

算法

问题描述：设样本数据集D，|D|为样本容量。设有K类$C_k,k=1,2,?,K$,$|C_k|$为属于k类的样本数，${\sum }_{k=1}^K|C_k|=|D|。设特征A将数据集分为N类D_n,n=1,2,3,?,N。|D_i|为D_i的样本数。{\sum }_{i=1}^N|D_i|=|D|,$记子集$D_i中属于类C_k的样本集合是D_{ik},即D_{ik}=D_i\cap C_k,|D_{ik}|为D_{ik}的样本个数。$

信息熵算法（就一个表达式）

（这里计算的是信息熵的近似——经验熵。因为在现实当中，无法计算出真正的事件熵值。所以将问题转化为求经验熵。）

$H(D)=?{\sum }_{k=1}^K\frac{|C_k|}{|D|}lo{g}_2\frac{|C_k|}{|D|}$

信息增益（互信息）算法

（前文已经提到信息增益和互信息本质都是经验熵与条件经验熵的差）

1.计算数据集分类的不确定性(信息熵)

$H(D)=?{\sum }_{k=1}^K\frac{|C_k|}{|D|}lo{g}_2\frac{|C_k|}{|D|}$
2. 计算特征A给定的条件下对数据集进行分类的不确定性（条件经验熵）

$H（D|A）={\sum }_{i=1}^N\frac{|D_i|}{|D|}H(D_i)={\sum }_{i=1}^N\frac{|D_i|}{|D|}{\sum }_{k=1}^K\frac{|D_{ik}|}{|D_i|}lo{g}_2\frac{|D_{ik}|}{|D_i|}$
3. 计算：依据特征A来对D分类的话，不确定性提高的量，也就是信息增益

$g(D,A)=H(D)?D(D|A)$

---

另一个特征选择标准：基尼系数

---

决策树 (decision tree, DT)

由根节点、内部节点、叶子节点构成的对实例进行分类的树形结构。根节点是输入的样本，内部节点表示输入样本的特征或属性，叶子节点表示对样本进行的一个分类。决策树学习本质上是从数据训练出一种分类规则。为了拟合一个较好的分类规则，首先对所有特征遍历求出信息增益值，选取最大的信息增益值作为第一个内部节点进行分支，不断递归调用以上过程实现后续分支，最终特征无法再分停止算法最后输出一个树模型。可以看出模型训练的过程中没有明确的感受到损失函数的存在。实际上，此处的信息增益值可以充当损失函数的角色（通常再加入正则化项防止过拟合）。
决策树算法主要有ID3、C4.5与CART。

ID3

ID3算法及代码实现

C4.5

C4.5算法及代码实现

CART

CART算法

梯度提升决策树 (gradient boost decision tree, GBDT)

极致版梯度提升决策树 (extreme gradient boost, XGBoost)

随机森林 (random forest, RF)

自适应提升树 (adaptive boost, AdaBoost)

---

结语

如果需要对算法进行初步了解，可以参考本文及其链接。进一步了解算法推荐《统计学习方法》进行公式的推导。如果只需要使用上述算法，结合本文线索，选择合适算法，在sklearn库中直接调用。上述算法目前为止发展较为成熟，在模型的更新上会有困难，在解决问题层面XGBoost效果较好（相对）可以优先考虑，重点放在模型的数据处理、模型训练及模型参数调优上。

---

Thanks for reading

---

Reference

https://zhuanlan.zhihu.com/p/32798104
https://www.bilibili.com/video/BV167411t7hQ?from=search&seid=1297323080413152675
https: // blog.csdn.net / leaf_zizi / article / details / 82848682
李航 - 《统计学习方法》