# 决策树

## 决策树能用来干什么？

构建分类模型和使用分类模型进行预测、分类。

例如，我现在给你一个训练集，是客户是否买房与客户年龄、性别、收入、婚姻状况等因素相关性的表格。

这样，你就能通过决策树算法构建一个客户是否会买房的决策树；你还能通过这个模型去预测，新来的客户是否会买房。

## 什么是决策树算法？

可以理解是一种决策流程，例如顾客买不买车，有如下这样的决策流程：

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-74a07da314176af7f8bfe2ac37075cd4e160ee02%2Fdecision_tree.png?alt=media)

对于一个复杂的问题，可能有非常多的影响因素，如何判断哪个因素对最终结果影响大呢？决策流程如何设计更合理呢？这就是决策树算法存在的意义。

对于从训练集生成的决策树模型，可以精确的解释该决策树是怎样生成的，又会进行怎样的预测，决策树有很好的可解释性。

## ID3决策树算法构造案例

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-7bbf0f0c6ffa8c6b34e9dd401de80f4f4fcad6e8%2Fdemo.jpeg?alt=media)

有四个纬度，年龄，性别，收入，婚姻状况，其中，我们可以看到年龄、收入两个维度由具体数值构成，为了更加方便的进行分层，我们将它划分为几个层次\~年龄分为20-30，30-40，40+三个阶段，把收入分为10-20，20-40，40+三个级别。[参考](https://zhuanlan.zhihu.com/p/341732294)

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-d3ff3149848322cdd7a6d65a4bc0595ad3e1fbb4%2Fdemo_dimension.png?alt=media)

### 信息熵（Entropy）

度量随机变量Y={c1，c2,c3…,ck}的不确定性，熵越大，不确定性越高。在分类中类别越多，也就说包含的信息越多，熵越大（越不确定是哪个分类）。如果只有一个分类，则p(x)=1,熵即为0，熵越小，越确定。

比如预测客户是否会买房，那么“客户的收入”这个条件比“今天晚上吃不吃鸡腿”这个信息更能确定用户买房的确定性，它的信息熵就更小。

![熵值计算公式](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-1e67f141903886a581ffa3b481e18268d6bde0da%2Fentropy_formula.png?alt=media)

对上述数据集，一共8条，其中3人买房，5人没买。

![总熵值计算](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-c8a6bd655982f2eb3d7474ee0fc59b0b44cfa316%2Fentropy_count.png?alt=media)

将20-30，30-40，40+三个阶段的条件熵按照总体比例相乘累加（分子的8指的是总共有8条数据，分母则对应的是20-30（3人）；30-40（2人）；40+（3人）这三个特定年龄阶段的人数，得到以AGE为特征的总体熵值。

![以Age为特征的条件熵值计算](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-ea571e1114a874902f58b06d23f933373b7ee2a8%2Fentropy_condition_count.jpeg?alt=media)

### 信息增益（Information Gain）

信息增益=总熵-以某特性为特征的条件熵

![信息增益计算](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-3c39798867f70f9f00c0606b3c828e7769948e13%2Fentropy_gain.png?alt=media)

同理可计算出收入、婚姻、性别的相关熵值、信息增益

![信息增益计算](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-8313c8c134be53e902f6fa4c4fdd007cfc165939%2Fentropy_gain1.jpeg?alt=media)

可知，以收入为特征的信息增益最大，那么就可以以收入特征作为根节点来构造决策树：

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-58410e54df1f22fb8d42b065fab28c4568c63a7d%2Fdemo1.jpeg?alt=media)

## CART决策树算法

CART 树（分类回归树）分为分类树和回归树。分类树用于处理分类问题；回归树用来处理回归问题。

CART 树和 ID3、C4.5 决策树相似，都用来处理分类问题。不同之处是划分方法，CART 树利用基尼系数进行二分，生成决策树的结构与二叉树一致。

### 基尼杂质系数/基尼不纯系数（Gini Impurity）

训练决策树包括将当前数据分成两个分支。假设我们有以下数据点:

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-d4d349ba28eb2f88dd11c77146d588a7a8e0892f%2Fgini_impurity0.png?alt=media)

现在，我们的分支里有5个蓝点和5个绿点。如果我们在x=2处进行划分:

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-b7711ac5f6fa0efbe075fb872602cd07d6e49326%2Fgini_impurity1.png?alt=media)

这很明显是个完美划分，因为它把数据集分成了两个分支：

* 左分支全是蓝点
* 右分支全是绿点

但如果我们在x=1.5处进行划分呢?

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-f14d3a5c2c64657aaa581ddc4ea6b266dcda7d09%2Fgini_impurity2.png?alt=media)

这个划分把数据集分成了两个分支：

* 左分支，4个蓝点
* 右分支，1个蓝点+5个绿点

很明显，这种划分更糟糕，但我们如何量化呢?

解决方法就是基尼杂质系数。

![Gini 公式](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-7a2b03233a4028fc097daa317574b47454614ee9%2Fgini_formula.png?alt=media)

![以上完美划分的情况](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-d2f8617f992a727af9c7875900b06b0b7c0ec7bb%2Fgini_demo0.png?alt=media)

![以上不完美划分的情况](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-b5a003ceb0a204d25a54c9bedae329ae5fcfff14%2Fgini_demo1.png?alt=media)

### 基尼增益系数/基尼系数增益（Gini Gain）

按以上不完美划分为例：

划分前整个数据集的基尼杂质系数是0.5，划分后，左分支是基尼杂质系数为0，右分支为0.278，由于左分支有4个样本，右分支有6个样本，因此划分后的总体基尼杂质系数为：(0.4∗0)+(0.6∗0.278)=0.167

因此，用这个划分“降低”的杂质量是：0.5−0.167=0.333

这就是基尼增益系数。

## 上面这2个算法的区别？

绝大部分情况下熵（entropy）和基尼指数（Gini Index）在决策树节点分裂时做出的决策都是等价的。

那为啥存在两种常用算法呢？其实是因为\[1]使用了熵，而\[2]使用了基尼指数，两个工作都很有开创性就都保留了下来。

## 剪枝（Pruning）

![](https://2397394804-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-MD8BldiJj1Zbl0abfsw%2Fuploads%2Fgit-blob-02468b3ee6e24a4a5bb7dacc9b38bb460ac547fd%2Fpruning_demo.png?alt=media)

•横轴表示在决策树创建过程中树的结点总数，纵轴表示决策树的预测精度。 •实线显示的是决策树在训练集上的精度，虚线显示的则是在一个独立的测试集上测量出来的精度。

可以看出随着树的增长， 在训练样集上的精度是单调上升的， 然而在独立的测试样例上测出的精度先上升后下降。

产生这种现象的原因如下：

•原因1：噪声、样本冲突，即错误的样本数据。

•原因2：特征即属性不能完全作为分类标准。

•原因3：巧合的规律性，数据量不够大。

这个时候，就需要对生成树进行修剪，也就是***剪枝***。剪枝通常有两种做法：***预剪枝***和***后剪枝***。

### 预剪枝

预剪枝就是在完全正确分类训练集之前，较早地停止树的生长。

由于预剪枝不必生成整棵决策树，且算法相对简单， 效率很高， 适合解决大规模问题。但是尽管这一方法看起来很直接， 但是 怎样精确地估计何时停止树的增长是相当困难的。

预剪枝有一个缺点， 即视野效果问题 。 也就是说在相同的标准下，也许当前的扩展会造成过度拟合训练数据，但是更进一步的扩展能够满足要求，也有可能准确地拟合训练数据。这将使得算法过早地停止决策树的构造。

### 后剪枝

后剪枝，在已生成过拟合决策树上进行剪枝，可以得到简化版的剪枝决策树。