第3章
CHAPTER 3


基于规则的决策树模型





决策树模型是一种机器学习的方法。在各种论文中经常会看到treebased model就是指决策树的庞大家族了。时至今日，决策树虽然有了一个新的劲敌——神经网络，但是依然在机器学习领域中占有一席之地，图3．1就是一个简单的决策树模型。


图3．1决策树外貌图


本章主要涉及的知识点： 
 决策树及其算法的发展史； 
 决策树算法的讲解及实现； 
 随机森林算法的讲解及实现； 
 Boosting模型的讲解及实现。
3．1决策树发展史
决策树是一种归纳学习算法，从一些没有规则、没有顺序、杂乱无章的数据中，推理出决策模型。决策树的发展经历了以下进程： 
(1) 1986年，Quinlan提出了决策树ID(Iterative Dichotomizer)3算法； 
(2) 1993年，Quinlan在ID3算法的基础上，提出了C4．5（也称为ID4.5）算法;
(3) 以上两者都是处理分类问题的，对于回归问题，在1984年，Breiman等提出了分类和回归树(Classification And Regression Tree，CART);
(4) 而决策树更强大的算法，就是随机森林(Random Forest)算法(Leo Breiman和Adele Cutler在1995年提出)； 
(5) 2014年，有了效果更好的Boosting算法，极端梯度提升(eXtreme Gradient Boosting，XGBoost)由陈天奇提出； 
(6) 2017年1月，微软公司发布了首个稳定版本的LGM（LightGBM）； 
(7) 2017年4月，Tandex公司开源了CatBoost。
根据作者在数据竞赛中的经验，现在最常用、效果最好的模型就是LGM与CatBoost。
注意： XGBoost虽然准确率和运行速度都不如LGM，但是有的时候也会以一个小模块加入到最终预测结果中。
3．2决策树算法
本节以通俗易懂的、尽可能减少数学推导的方式依次讲解ID3、C4．5和CART算法，最后讲述如何用Python实现决策树算法，方便读者实际应用。
不管是什么算法的决策树，都是一种对实例进行分类的树形结构，如图3．1所示。因此，决策树有三个要素： 节点(Node)、分支(Branches)和结果(Leaf)。
当然一棵树状图，也有子节点、父节点、根节点、树的深度这样的概念，不过以上三个是最关键的。
注意： 这里用图3．1举例，“条件1”“条件2”是节点； “不满足条件1”是一个分支； “结果1”“结果2”是结果； 对于整棵树，“条件1”就是根节点； 对于“条件2”，“条件1”就是“条件2”的父节点； “条件2”就是“条件1”的子节点。每一个父节点可能就是另外一个节点的子节点。
训练决策树，其实就是对训练样本的分析，把样本通过某个边界划分成不同的结果。如图3．2所示，王华想玩游戏，但是他妈妈要求他写完作业才能玩。


图3．2决策树——打游戏1


当然，一个家庭里面，除了妈妈还有爸爸，爸爸要求王华去做运动，做完运动才能玩，这样决策树就会变得复杂一点，如图3．3所示。


图3．3决策树——打游戏2


如果是真实的数据竞赛中，肯定不止爸爸妈妈，还会有更多的分类特征，这样决策树就会变得非常长而复杂。
3．2．1ID3算法
ID3算法通过熵(Entropy)来决定谁来做父节点，也就是“条件”。一般来说，决策树就是不断地if…else…，不断地做判断，每做一个判断就会产生新的分支，这个叫分裂。谁来分类，是根据Entropy最小的原则来判断的。
(1) Entropy衡量一个系统的混乱程度，例如，气体的Entropy会高于固体的Entropy。
(2) Entropy可以表示一个随机变量的不确定性，例如，很多低概率事件的Entropy就很高，很少高概率事件的Entropy会很低。
(3) Entropy也可以用来计算比特信息量。
注意： Entropy这个概念在物理、信息论、沟通、加密和压缩等多个领域中应用。
Entropy的计算公式如下： 

E=-1∑Ck=1Prklog2(Pr(k))(3.1)

其中，乘以(-1)是为了保证E是一个正数； Pr(k)是一个样本属于k类别的概率； C是类别总数。
假设有10个样本，5个是猫，5个是狗，则采用二元组表示(猫，狗)，如图3．4所示。


图3．4决策树——猫狗


先看图3．4(a)的决策树，假如按照“毛发”分类，那么4只猫和2只狗分成一类，1只猫和3只狗分成一类。显而易见，这分类的效果是不好的，不够纯净，不够purity。它的Entropy是这样计算的： 

E(柔顺)=(-1)×46log246+26log226≈0．918


那继续计算“不柔顺”结果的Entropy:

E(不柔顺)=(-1)×14log214+34log234≈0．811


同理，计算图3．4(b)的Entropy： 

E喵=E(汪)=0


可见图3．4(b)的分类比图3．4(a)的分类好。Entropy不断最小化，其实就是提高分类正确率的过程。
3．2．2C4．5
通过对ID3的学习，可以发现一个问题： 如果一个模型，无限地延长分类，越细小的分割错误率就会越小。继续猫狗分类的实验，假设把决策树延伸，最后有10种结果，每个结果都只有1只猫或者1只狗，每个结果的Entropy一定都是0。
但是，这样的分类是没有意义的，即过拟合、过度学习(Overfitting)。举一个简单的例子来理解Overfitting，像是私人定制的衣服非常适合某一个人穿，此时出现一个新人，就无法用这些既定的胸围、腰围来定制衣服了，必须重新测量。
因此，为了避免分割太细，C4．5的改进之处是提出了信息增益率。如果分割太细，会降低信息增益率。此外，其他原理与ID3相差不多。
3．2．3CART
CART的结构非常简单，一个父节点只能分为2个子节点，它使用的是GINI指标来决定怎么分类的。其实GINI跟Entropy相反，总体内包含的类别越多越杂乱，GINI就会越小。

G=∑Ck=1Pr(k)2(3.2)

其中，G表示GINI系数。
CART之所以是回归树，是因为使用回归方法来决定分布是否终止。不管如何分割，总会出现一些结果，仅有一点的不纯净。因此CART对每一个结果(叶子节点)的数据分析均值方差，当方差小于一个给定值，就可以终止分裂。
CART也有与ID3类似的问题，就是分割过于细小，这里使用了一个技巧——剪枝，把特别长的树枝直接剪掉。这个通过计算调整误差率(Adjusted Error Rate)实现： 

AR(R)=E(R)+αleafs(R)(3.3)


如果一个子树中有越多的叶子，这就意味着这个子树特别的长，这样会惩罚式地增加这个子树的误差率(Error Rate)，例如Entropy。
3．2．4随机森林
随机森林是一种集成学习的方法，是把多棵决策树集成在一起的一种算法，基本单元是决策树。其思想从一个直观的角度来解释，就是每一棵决策树，都是一个分类器，很多决策树必然会有很多不一样的结果。这个结果就是每一个决策树的投票，投票次数最多的类别就是最终输出。
3．3Boosting家族
3．3．1XGBoost

XGBoost所应用的算法内核就是GBDT(Gradient Boosting Decision Tree)，也就是梯度提升决策树。
注意： 这里XGBoost应用的算法严格来说是优化的GBDT。
XGBoost是一种集成学习。这种集成学习，与Random Forest的集成学习，两者是不一样的。XGBoost的集成学习是相关联的集成学习，决策树联合决策； 而Random Forest算法中各个决策树是独立的。
假设有这样的一个样本： 

［数据： (1，3，2，4，5)，标签： 5］

第一棵决策树训练之后，得到预测值4．1，那么第二棵决策树训练的时候就不再输入： 

［数据： (1，3，2，4，5)，标签： 5］

而是： 

［数据： (1，3，2，4，5)，标签： 0．9］


第二棵决策树的训练数据，会与前面决策树的训练效果有关，每棵树之间是相互关联的。而Random Forest算法中每棵树都是独立的，彼此之间什么关系都没有。
这里简单介绍一下XGBoost的算法和损失函数，首先根据上面讲解，XGBoost模型的预测值应该是里面每一棵树的预测值的和： 

y^=∑Ek=1fk(xi)(3.4)

其中，xi是输入的样本，fk(xi)表示输入的样本在第k棵决策树得到的预测结果，E是决策树总数。定义损失函数为： 

Obj(θ)=∑ni=1l(yi,y^i)+∑Kk=1Ω(fk)(3.5)

其中，l(yi,y^i)是样本xi的训练误差，Ω(fk)表示第k棵树的复杂度的函数，复杂度越小，函数值就越小。这里不进一步推导XGBoost算法，了解这么多对实战应用足够用了。
注意： 复杂度越小，就意味着模型的泛化能力强。
3．3．2LightGBM
XGBoost在每一次迭代的时候，都需要遍历整个训练数据多次。如果把整个训练集都放在内存就需要大量内存，如果不装进内存，每次读写就需要大量时间。所以XGBoost的缺点主要就是计算量巨大，内存占用巨大。因为XGBoost采用的贪婪算法，可以找到最精确的划分条件(就是节点的分裂条件)，但是这也是一个会导致过拟合的因素。
而LightGBM采用直方图算法(Histogram Algorithm)，思想很简单，就是把连续的浮点数据离散化，然后把原来的数据用离散之后的数据替代。换句话说，就是把连续数据变成了离散数据。例如，现在有几个数字［0,0．1,0．2,0．3,0．8,0．9,0．9］，把这些分为两类，最后离散结果就是： ［0,0,0,0,1,1,1］。显而易见，很多数据的细节被放弃了，相似的数据被划分到同一个bin中，数据差异消失了。
注意： ①bin是指直方图中的一个柱子，直译过来是桶。②很多数据细节被放弃了，这从另一个角度来看可以增加模型的泛化能力，防止过拟合。
除此之外，LightGBM还支持类别特征。大多数机器学习工具无法支持类别特征，而需要把类别特征通过onehot编码。这里简单讲一下onehot编码，如图3．5所示（其中，“0”代表不是，“1”代表是）。


图3．5onehot编码


这样的编码方式会降低时间和空间的效率。尤其是当原来的特征动物类别中有几百种时，onehot编码之后会多出几百列特征，效率非常低。此外，onehot编码会导致决策树分类时出现很多数据量很小的空间，容易导致过拟合问题。如图3．6(a)所示，XGBoost会生成一棵更长、泛化能力更弱的决策树，而图3.6(b)的LightGBM可以生成一个泛化能力强的模型。


图3．6XGBoost与LightGBM对类别特征的处理


3．3．3CatBoost
CatBoost的优势是可以很好地处理类别特征(如图3．5所示的动物类别特征)，不是数值型的连续的浮点特征，而是离散的集合。CatBoost提供了一种处理类别特征的方案： 
(1) 对所有的样本进行随机排序； 
(2) 把类别特征转化为数值型特征，每个数值型特征都是基于排在该样本之前的类别标签取均值，同时加入了优先级及权重系数。
先来看基本编码公式： 

x^k=∑nj=1Ixj=xk×yj∑nj=1Ixj=xk(3.6)

其中，x^k类别特征xk的转化为数值型特征的估计值； Ixj=xk是指示函数(英文是Iverson brackets，条件满足为1，条件不满足为0)。当xj=xk成立的时候，为1； 不成立的时候，为0。因此∑nj=1Ixj=xk就表示在整个数据库中相同类别的数量。数据库中相同类别的用其标签的平均值作为它们的数值特征，如图3．7所示。


图3．7Catboost编码


如图3．7所示，所有类别为猫的都被编码成了3，因为(2+4+3)/3=3； 而狗只有一个样本，所以它的标签值就是编码值。假如数据中的某类样本的数量特别少，那其编码就是标签，则这些样本一定会过拟合，所以可以用先验值P来处理： 

x^k=∑nj=1Ixj=xk×yj+aP∑nj=1Ixj=xk+a(3.7)

其中，a是一个大于0的参数； P通常是所有数据中目标变量的平均值(所有变量标签的平均值)。
3．4小结
简要回顾一下本章主要内容。
(1) 介绍了决策树的发展史。基本上后续的算法都是优于先前的算法的。
(2) ID3算法： 输入只能是分类数据(这意味着ID3只能处理分类问题，不能处理回归任务)，分裂的标准是Entropy。
(3) CART算法： 输入可以是分类数据(categorical)，也可以是连续数据(numerical)。分裂标准是GINI指标。
(4) Random Forest和XGBoost算法虽然都是集成学习，但是二者存在不同。
(5) XGBoost虽然精准分裂，但是容易过拟合、耗时长、效率低； LightGBM使用直方图算法，速度快、泛化能力较强。
(6) XGBoost使用onehot编码，LightGBM可以直接对类别特征进行处理； CatBoost在处理类别特征的时候，更胜LightGBM一筹。总之，对于大数据的竞赛，LightGBM和CatBoost是主力。