1、 前言
之前我们已经说了，机器学习的从线性回归，概率这个出发点发展的算法。这次我们讲从第三个出发点，使用信息熵的算法，决策树。
在前面的章节中我们已经介绍了机器学习中常用的线性回归相关的算法。这次我们引入一个新的小伙伴决策树。
2、 前置知识
决策树在“决策”的时候需要有一个判断依据，那就是信息熵。为了后续阅读能够更加流畅，我们在这里来介绍什么是信息熵，信息熵是 1948 年，香农引入信息熵。一个系统越是有序，信息熵就越低，一个系统越是混乱，信息熵就越高。所以信息熵被认为是一个系统有序程度的度量方案。举个例子，太阳从东边升起这个规律人人都知道，所以信息熵低，而 GAN 算法是怎么推导的知道的人就不多，所以它的信息熵高。而对应到事件的话，则可以说 一个事件发生的概率大，那么它含有的信息少。
信息熵公式如下：
\[H(x) = - \sum_{i=1}^m p_i log_2(p_i)\]条件熵的定义为： 给定条件 X 的情况下，所有不同取值情况下 Y 的信息熵的平均值叫做条件熵，对应的公式如下：
\(H(Y|X) = \sum_{i=1}P(X = x_i)H(Y|X = x_i)\) \(H(Y|X) = H(X,Y) - H(X)\)
3、 纵览决策树算法
在了解了信息熵是什么之后，我们来深入了解下决策树的细节。决策树是在已知各种情况发生概率的基础上，通过构建决策树来进行分析的一种推理方法，是一种直观应用概率分析的一种图解法。决策树是一种树形结构， 其中每个内部节点表示一个属性的测试，每个分支表示一个测试输出，每个叶节点代表一种类别。换句话说，决策树的使用是一种模拟了简单的人类思考过程的思路。通过许多if...else...进行判断最后得到一个结论。
3.1、构建决策树
构建步骤如下:
- 将所有的特征看成一个一个的节点;
- 遍历每个特征的每一种分割方式，找到最好的分割点;将数据划分为不同的子节点 $N_1, N_2,…,N_m$。计算划分之后所有子节点的纯度信息。
- 对第二步产生的分割，选择出最优的特征以及最优的划分方式。得出最终的子节点: $N_1,N_2,…,N_m$
- 对子节点分别继续执行 2-3 步，直到每个最终的子节点都足够纯。
注：这里的纯度指的是每个字节点的类别尽量相同。注意构建过程中的选择最优特征的步骤决定了后期算法的不同
3.2、划分方式的选择
在上述 3.1 中提到了两个关键性的事情，叫做划分方式和选择最优特征，这里我们就要讨论的是划分方式。众所周知，数据分为离散的和连续的，显然我们对他们的处理有些不同。
如果属性是离散值，且要求是二叉树，我们就可以按照一般的逻辑方式，按照属于此子集和不属于此子集分成两个分支。如果没有要求是二叉树则一个属性就是一个分支。
如果是属性为连续值，则可以确定一个值作为分裂点split_point，按照>split_point和<=split_point生成两个分支。
3.3、 决策树分割属性选择
之前我们说了划分方式，那么我们如何选择最优的特征呢。答案是比较纯度。首先决策树算法是一种“贪心”算法策略，只考虑在当前数据特征情况下的最好分割方式，且不能进行回溯操作。而对于整体的数据集而言，通过查看每个特征属性划分后，纯度的变化进行比较，选择能让数据集变得更纯的特征属性进行分割。之后重复上述步骤直到满足条件。
注：题外话，虽然我们很少需要自己造轮子，但是还是需要知道树的结构是符合递归规律的，一般而言树的构建都可以使用递归算法
那么纯度是什么，纯度其实就是一种判断决策树是否向着正确方向前进的判断。粗鄙的类比，就是母猪配种，选择最合适的方式将不同种的猪分开，尽量保证每波猪都是纯种的。纯度的判断标准不同也决定了之后的算法的名称不同，其标准如下三种：
- 基尼系数：$Gini = 1 - \sum_{i=1}^nP(i)^2$
- 信息熵：$-\sum_{i=1}^n P(i)log_2(P(i))$
- 误差率：$Error = 1 - max_{i=1}^n {P(i)}$
上面是基础的一些系数，在剪枝和判断的时候需要一个种体现变化的系数，于是出现了如下公式来作为 C4.5 和 ID3 的判别标准。简单的理解为，这个公式表达了以 A 属性划分后，信息量增加的量，或者说指代的是纯度变纯了多少。
\[Gain = \Delta = H(D)-H(D|A)\]注 1：这里我说的是算法名称不同，其实更多的想指代他们是一个系列的算法。就如同 LR 与 Lasso 和 Ridge 的关系一样
注 2：如上公式都体现了纯度值越小信息量越大这个理念
3.4、 树构建的停止条件
决策树构建的过程是不断递归的过程，就像 (是) while 循环一样，必须有跳出循环的条件。以下是两个停止条件。
- 每个字节点只有一种类型时停止条件。（容易过拟合）
- 节点中记录数小于某个阀值的时候，或者迭代次数达到给定值的时候停止构建。
3.5、 决策树的评估
\[loss = \sum_{t=1}^{leaf} \frac{|D_t|}{D}H(t)\]其中 $H(t)$ 前的参数 $\frac{D_t}{D}$ 主要的目的其实是给信息熵加权值，$D_t$ 代表着该特征的样本数量，即特征中的样本点越多它越重要。
4、 算法对比
其实到这里决策树的核心就介绍完了，现在来看实际中的算法应用，也是面试种可能（不太可能）问到的算法，即 ID3，C4.5，CART。其中 CART 最重要，会在之后的i GBDT 算法中的弱分类器就是 CART。
4.1 、ID3算法
ID3 算法是决策树的一个经典的构造算法，每次迭代选择分割属性的方式为，使用 3.3 章节中的信息增益 $Gain$ 作为评判标准。
优点为：
- 决策树构建速度快，实现简单。
缺点为：
- 特征数目较多（$D_t$ 较大）的特征不一定非常重要，这会导致模型更关注“最多”而不是最好的特征。
- ID3 算法不是递增算法，是单变量决策树，对于特征属性之间的关系不会考虑到。
- 由于它的数据要扔到内存中，所以只适合小规模数据集。
4.2、C4.5算法
在 ID3 算法的基础上，进行算法优化提出的一种算法 (C4.5)。其使用信息增益率来取代 ID3 算法中的信息增益，同时在树的构造过程中会进行剪枝操作进行优化。能够自动完成对连续属性的离散化处理。C4.5算法在选中分割属性的时候选择信息增益率最大的属性。信息增益率公式如下：
\[Gain\_ratio(A) = \frac{Gain(A)}{H(A)}\]优点：
- 产生的规则易于理解，同时准确率较高且实现简单，特征增益率缓解了模型更偏向特征数目多的特征的问题。
缺点：
- 由于采用了剪枝优化，所以对数据集需要进行多次顺序扫描和排序，所以效率较低 ，和 ID3 一样同样需要将数据放在内存，故只适合小规模数据集。
注：这里的能够处理连续值和剪枝优化都算是后期加的，只是 Sklearn 中没有给 ID3 赋予这个功能。他们的核心差别就在是增益率还是增益。剪枝优化会在决策树优化中讲
CART
好了，轮到了这个决策树中最重要的算法了，它使用基尼系数作为数据纯度的量化指标来构建的决策树。CART 拆开是，Classification And Regression Tree，中文是分类回归树。这么叫的原因是它可以用来做分类和回归两类问题。值得注意的是：CART构建是二叉树
其 GINI 增益公式如下：
\[Gain = \Delta = Gini(D) - Gini(D|A)\]注：GINI系数的计算不牵扯信息熵运算中的对数运算，故速度比较快
总结
- ID3 和 C4.5 基本上是一回事，所以他们都是单变量决策树，都只使用在小规模数据集
- C4.5 算是 ID3 的优化，所以当属性取值较多的时候，可以考虑 C4.5 而不是 ID3
-
决策树的树是存在内存中的，所以一般只适用于小数据量。
注：一般你要是看到了类似B+树的结构，一般不是完全在内存中
- CART是最常用的，尤其是后期集成算法GBDT中用的就是CART。CART是二叉树，ID3和C4.5不一定是。
最后
这章的重点在于知道决策树的生成规律，而三种算法的区别仅仅只是对于树形成节点的规则不同而已，ID3 使用信息增益、 C4.5 使用信息增益率、CART使用基尼系数。这一章依旧是一个轻松愉悦的章节，内容非常 easy。之后我们会开始进入基础算法之后的升级版就困难不少。
BTW，没想到有这么多人关注专栏，再次感谢大家。
Changlog
- 2020-07-18: Fix typo + add new info