全面总结机器学习项目和面试中几乎绕不开的决策树

定义

决策树是一种常见的机器学习算法，它的思想十分朴素，类似于我们平时利用选择做决策的过程。

例如有人给我们介绍新的对象的时候，我们就要一个个特点去判断，于是这种判断的过程就可以画成一棵树，例如根据特点依次判断：

如上，决策的形式以树的形式进行示意和编码，就形成了决策树。

结构

显然，决策树在逻辑上以树的形式存在，包含根节点、内部结点和叶节点。

根节点：包含数据集中的所有数据的集合
内部节点：每个内部节点为一个判断条件，并且包含数据集中满足从根节点到该节点所有条件的数据的集合。根据内部结点的判断条件测试结果，内部节点对应的数据的集合别分到两个或多个子节点中。
叶节点：叶节点为最终的类别，被包含在该叶节点的数据属于该类别。

简而言之，决策树是一个利用树的模型进行决策的多分类模型，简单有效，易于理解。

伪代码

决策树算法的伪代码（参照了python语法）如下图所示：

代码语言：javascript复制

 1# D = {(x1,y1)、(x2,y2)......(xm,yn)} 是数据集
 2# A = {a1、a2、a3.} 是划分节点的属性集
 3# 节点node有两个主要属性：content代表该节点需要分类的训练集，type代表叶节点的决策类型
 4def generateTree(D,A):
 5    newNode = 空 #生成新的节点
 6    # 如果当前数据集都为一个种类，则设为一个叶节点并返回
 7    if D 中数据皆属于类别 C:
 8        newNode.content = D
 9        newNode.type = C
10        return    
11    # 如果已经没有属性了或者数据集在剩余属性中表现相同（属性无法区分）
12    if A = 空集 or D中数据在A中取值相同:
13        newNode.content = D
14        newNode.type = D中最多的类
15        return
16    #从A中选取最优的属性a
17    a=selectBestPorperty(A)
18    #为a的每一个取值生成一个节点，递归进行处理
19    for a的每一个取值 res[i]:
20        生成新的分支节点 node[i]
21        D[i] = D中取值为res[i]的数据
22        node[i].content = D[i]
23        if node[i].content == null:
24            node[i].type = D中最多的类
25        else:
26            generateTree(D[i],A - {a})
27    return

划分选择

可以看到，在伪代码中，大部分步骤都是简单而明确的，而最重要的步骤在于从A中选取最优的属性a，可以说，属性选择的质量，决定了决策树的预测准确度。这很容易理解，例如我们看一个学生聪明与否可以看他的成绩，但是如果依靠他的身高预测他是否聪明，显然得不到好的结果。

一般的原则是，希望通过不断划分节点，使得一个分支节点包含的数据尽可能的属于同一个类别，即“纯度“越来越高。

这里列出三种常用的准则。

信息增益准则

我们先对一个节点的纯度进行定义，我们将其称之为信息熵：

其中

代表当前节点D的数据中第k类样本所占的比例。

观察该信息熵的定义，有以下几个特点：

都属于[0,1]，Ent(D)必定为正值，值越大说明纯度越低

Ent(D)在k=1=1时取值最小值0，

时取值最大值

信息熵是一个节点的固有性质，和该节点选取什么属性进行下一步的划分无关

在定义了信息熵之后，对信息增益进行定义，假设选取属性a有V个取值，

，按照决策树的规则，D将被划分为V个不同的节点数据集，

代表其中第v个节点：

观察该式，有以下几点说明：

Ent(D)是确定的，和选取的属性a无关，我们可以将之看为定值

表示分支节点所占的比例大小，显然数据集越大的分支节点权重越高

分支节点整体纯度越大，则后一项越小，信息增益Gain变得越大，所以我们的目标是如何最大化信息增益

由此，我们得到了一种选择划分属性的方法，计算以每个属性进行划分子节点得到的信息增益，选择其中最大的作为选择的属性。

信息增益率准则

信息增益原则对于每个分支节点，都会乘以其权重，也就是说，由于权重之和为1，所以分支节点分的越多，即每个节点数据越小，纯度可能越高。这样会导致信息熵准则偏爱那些取值数目较多的属性。

为了解决该问题，这里引入了信息增益率，定义如下：

相当于引入了修正项IV(a)，它是对于属性a的固有值。

需要注意的是，信息增益率原则可能对取值数目较少的属性更加偏爱,为了解决这个问题，可以先找出信息增益在平均值以上的属性，在从中选择信息增益率最高的。

基尼指数准则

在CART决策树中，使用基尼指数来选择属性，首先定义数据集D的基尼值：

形象的说，基尼值代表了从D中随机选择两个样本，其类别不一致的概率。

有了基尼值后，可以在此基础上定义基尼指数：

其的含义和之前相同，可以看出基尼指数越小，说明纯度越高，我们可以通过选择基尼指数小的属性来划分子节点。

剪枝

剪枝是应该决策树过拟合的一种重要方法，主要分为以下两种：

预剪枝：该策略就是在对一个节点进行划分前进行估计，如果不能提升决策树泛化精度，就停止划分，将当前节点设置为叶节点。那么怎么测量泛化精度，就是留出一部分训练数据当做测试集，每次划分前比较划分前后的测试集预测精度。
优点：降低了过拟合风险，降低了训练所需的时间。
缺点：预剪枝是一种贪心操作，可能有些划分暂时无法提升精度，但是后续划分可以提升精度。故产生了欠拟合的风险。
后剪枝：该策略是首先正常建立一个决策树，然后对整个决策树进行剪枝。按照决策树的广度优先搜索的反序，依次对内部节点进行剪枝，如果将某以内部节点为根的子树换成一个叶节点，可以提高泛化性能，就进行剪枝。
优先：降低过拟合风险，降低欠拟合风险，决策树效果提升比预剪枝强
缺点：时间开销大得多