1.决策树的定义

树想必大家都会比较熟悉，是由节点和边两种元素组成的结构。理解树，就需要理解几个关键词：根节点、父节点、子节点和叶子节点。

父节点和子节点是相对的，说白了子节点由父节点根据某一规则分裂而来，然后子节点作为新的父亲节点继续分裂，直至不能分裂为止。而根节点是没有父节点的节点，即初始分裂节点，叶子节点是没有子节点的节点，如下图所示：

图1.1 树的结构示意图

决策树利用如上图所示的树结构进行决策，每一个非叶子节点是一个判断条件，每一个叶子节点是结论。从跟节点开始，经过多次判断得出结论。

2. 决策树如何做决策

从一个分类例子说起：

银行希望能够通过一个人的信息（包括职业、年龄、收入、学历）去判断他是否有贷款的意向，从而更有针对性地完成工作。下表是银行现在能够掌握的信息，我们的目标是通过对下面的数据进行分析建立一个预测用户贷款一下的模型。

（注：上表中的数据都由本人捏造，不具有任何实际的意义）

上边中有4个客户的属性，如何综合利用这些属性去判断用户的贷款意向？决策树的做法是每次选择一个属性进行判断，如果不能得出结论，继续选择其他属性进行判断，直到能够“肯定地”判断出用户的类型或者是上述属性都已经使用完毕。比如说我们要判断一个客户的贷款意向，我们可以先根据客户的职业进行判断，如果不能得出结论，再根据年龄作判断，这样以此类推，直到可以得出结论为止。

决策树用树结构实现上述的判断流程，如图2.1所示：

　图2.1 银行贷款意向分析决策树示意图

通过图2.1的训练数据，我们可以建议图2.1所示的决策树，其输入是用户的信息，输出是用户的贷款意向。如果要判断某一客户是否有贷款的意向，直接根据用户的职业、收入、年龄以及学历就可以分析得出用户的类型。如某客户的信息为：{职业、年龄，收入，学历}={工人、39， 1800，小学}，将信息输入上述决策树，可以得到下列的分析步骤和结论。

第一步：根据该客户的职业进行判断，选择“工人”分支；

第二步：根据客户的年龄进行选择，选择年龄”<=40”这一分支；

第三步：根据客户的学历进行选择，选择”小学”这一分支，得出该客户无贷款意向的结论。

3. 决策树的构建

那么问题就来了，如何构建如图2.1所示一棵决策树呢？决策树的构建是数据逐步分裂的过程，构建的步骤如下:

步骤1：将所有的数据看成是一个节点，进入步骤2；

步骤2：从所有的数据特征中挑选一个数据特征对节点进行分割，进入步骤3；

步骤3：生成若干孩子节点，对每一个孩子节点进行判断，如果满足停止分裂的条件，进入步骤4；否则，进入步骤2；

步骤4：设置该节点是子节点，其输出的结果为该节点数量占比最大的类别。

从上述步骤可以看出，决策生成过程中有两个重要的问题：

（1）数据如何分割

（2）如何选择分裂的属性

（3）什么时候停止分裂

3.1 数据分割

假如我们已经选择了一个分裂的属性，那怎样对数据进行分裂呢？

分裂属性的数据类型分为离散型和连续性两种情况，对于离散型的数据，按照属性值进行分裂，每个属性值对应一个分裂节点；对于连续性属性，一般性的做法是对数据按照该属性进行排序，再将数据分成若干区间，如[0,10]、[10,20]、[20,30]…，一个区间对应一个节点，若数据的属性值落入某一区间则该数据就属于其对应的节点。

例：

表3.1 分类信息表

（1）属性1“职业”是离散型变量，有三个取值，分别为白领、工人和学生，根据三个取值对原始的数据进行分割，如下表所示:

表3.2 属性1数据分割表

表3.2可以表示成如下的决策树结构

（2）属性2是连续性变量，这里将数据分成三个区间，分别是[10，20]、[20,30]、[30,40]，则每一个区间的分裂结果如下：

表3.3 属性2数据分割表

表3.3可以表示成如下的决策树结构：

3.2 分裂属性的选择

我们知道了分裂属性是如何对数据进行分割的，那么我们怎样选择分裂的属性呢？

决策树采用贪婪思想进行分裂，即选择可以得到最优分裂结果的属性进行分裂。那么怎样才算是最优的分裂结果？最理想的情况当然是能找到一个属性刚好能够将不同类别分开，但是大多数情况下分裂很难一步到位，我们希望每一次分裂之后孩子节点的数据尽量”纯”，以下图为例：

从图3.1和图3.2可以明显看出，属性2分裂后的孩子节点比属性1分裂后的孩子节点更纯：属性1分裂后每个节点的两类的数量还是相同，跟根节点的分类结果相比完全没有提高；按照属性2分裂后每个节点各类的数量相差比较大，可以很大概率认为第一个孩子节点的输出结果为类1，第2个孩子节点的输出结果为2。

选择分裂属性是要找出能够使所有孩子节点数据最纯的属性，决策树使用信息增益或者信息增益率作为选择属性的依据。

（1）信息增益

用信息增益表示分裂前后跟的数据复杂度和分裂节点数据复杂度的变化值，计算公式表示为：

其中Gain表示节点的复杂度，Gain越高，说明复杂度越高。信息增益说白了就是分裂前的数据复杂度减去孩子节点的数据复杂度的和，信息增益越大，分裂后的复杂度减小得越多，分类的效果越明显。

节点的复杂度可以用以下两种不同的计算方式：

a）熵

熵描述了数据的混乱程度，熵越大，混乱程度越高，也就是纯度越低；反之，熵越小，混乱程度越低，纯度越高。 熵的计算公式如下所示：

其中Pi表示类i的数量占比。以二分类问题为例，如果两类的数量相同，此时分类节点的纯度最低，熵等于1；如果节点的数据属于同一类时，此时节点的纯度最高，熵 等于0。

b）基尼值

基尼值计算公式如下：

其中Pi表示类i的数量占比。其同样以上述熵的二分类例子为例，当两类数量相等时，基尼值等于0.5 ；当节点数据属于同一类时，基尼值等于0 。基尼值越大，数据越不纯。

例：

以熵作为节点复杂度的统计量，分别求出下面例子的信息增益，图3.1表示节点选择属性1进行分裂的结果，图3.2表示节点选择属性2进行分裂的结果，通过计算两个属性分裂后的信息增益，选择最优的分裂属性。

属性1：

属性2：

由于Info1 >Info2,所以属性1与属性2相比是更优的分裂属性，故选择属性1作为分裂的属性。

（2）信息增益率

使用信息增益作为选择分裂的条件有一个不可避免的缺点：倾向选择分支比较多的属性进行分裂。为了解决这个问题，引入了信息增益率这个概念。信息增益率是在信息增益的基础上除以分裂节点数据量的信息增益（听起来很拗口），其计算公式如下：

其中Info_Grain表示信息增益，InstrinsicInfo表示分裂子节点数据量的信息增益，其计算公式为：

还是信息增益中提及的例子为例：

属性1的信息增益率：

属性2的信息增益率：

由于Info_Ratio2 >Info_Ratio1,故选择属性2作为分裂的属性。

3.3 停止分裂的条件

决策树不可能不限制地生长，总有停止分裂的时候，最极端的情况是当节点分裂到只剩下一个数据点时自动结束分裂，但这种情况下树过于复杂，而且预测的经度不高。一般情况下为了降低决策树复杂度和提高预测的经度，会适当提前终止节点的分裂。

以下是决策树节点停止分裂的一般性条件：

（1）最小节点数

当节点的数据量小于一个指定的数量时，不继续分裂。两个原因：一是数据量较少时，再做分裂容易强化噪声数据的作用；二是降低树生长的复杂性。提前结束分裂一定程度上有利于降低过拟合的影响。

（2）熵或者基尼值小于阀值。

由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大，如果熵或者基尼值小于一定程度数，节点停止分裂。

（3）决策树的深度达到指定的条件

节点的深度可以理解为节点与决策树跟节点的距离，如根节点的子节点的深度为1，因为这些节点与跟节点的距离为1，子节点的深度要比父节点的深度大1。决策树的深度是所有叶子节点的最大深度，当深度到达指定的上限大小时，停止分裂。

（4）所有特征已经使用完毕，不能继续进行分裂。

被动式停止分裂的条件，当已经没有可分的属性时，直接将当前节点设置为叶子节点。

3.4 决策树的构建方法

根据决策树的输出结果，决策树可以分为分类树和回归树，分类树输出的结果为具体的类别，而回归树输出的结果为一个确定的数值。

决策树的构建算法主要有ID3、C4.5、CART三种，其中ID3和C4.5是分类树，CART是分类回归树，将在本系列的ID3、C4.5和CART中分别讲述。

其中ID3是决策树最基本的构建算法，而C4.5和CART是在ID3的基础上进行优化的算法。

4. 决策树的优化

一棵过于复杂的决策树很可能出现过拟合的情况，如果完全按照3中生成一个完整的决策树可能会出现预测不准确的情况，因此需要对决策树进行优化，优化的方法主要有两种，一是剪枝，二是组合树，将在本系列的剪枝和组合树中分别讲述。