决策树总结（一）

摘要：决策树是一种重要的分类和回归方法，具有可读性强、分类速度快等特点。决策树是一种树形结构，通过多个If-then规则实现分类或者回归的目的。

1.决策树的定义

      树想必大家都会比较熟悉，由节点和边两种元素组成的结构。有几个关键词，根节点、父亲节点、孩子节点和叶子节点。

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

决策树就是用树的结构去做决策，从跟节点开始，不断对数据进行分裂，最终到达的叶子节点就为输出的结果。

2. 决策树如何做决策

从一个简单的分类例子说起：

银行通过一个人的信息去判断这个人是否贷款的意向，具体的信息如下：

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

决策树的做法是利用树的结构，每次用一个属性进行分类，知道得到我们要的结果或者已经不能再分为止，如下图所示：

     通过我们的训练数据，可以得到上述的决策树，如果要分析某一客户是否有贷款的意向，直根据该客户的信息就可以分析得出结果。

如某客户的信息为：{职业、年龄，收入，学历}={工人、39， 1800，小学}，将信息输入上述决策树，可以得到下列的分析步骤和结论。

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

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

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

3. 如何构建决策树

决策树的构建是数据逐步分裂的过程，构建的步骤如下:

步骤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分割数据

表示成决策树的结构：

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

表示成决策树的结构如下图所示：

3.1 分裂属性的选择

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

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

选择分裂属性是要找出能够使所有孩子节点数据更加纯的属性。

决策树使用信息增益或者信息增益率作为选择属性的依据。

（1）信息增益

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

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

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

　　a）熵

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

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

　　b）基尼值

　　基尼值计算公式如3.3所示：

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

下面将以熵作为复杂度的统计量：

属性1：

属性2：

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

（2）信息增益率

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

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

其中m表示子节点的数量， 表示第i个子节点的数据量占父节点数据量的比例，说白了， 其实是分裂节点的熵。信息增益率越高，说明分裂的效果越好。

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

属性1：

属性2：

         由于 ，故选择属性2作为分裂的属性。

3.2 停止分裂的条件

（1）最小节点数

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

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

     由上述可知，熵和基尼值的大小表示数据的复杂程度，当熵或者基尼值过小时，表示数据的纯度比较大。

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

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