机器学习系列6：决策树

2019-06-10 本文已影响0人 _世界和平_

决策树是一种基本的分类与回归方法。这里主要讨论决策树用于分类。
决策树模型是描述对样本进行分类的树形结构。树由结点和有向边组成：

内部结点表示一个特征或者属性。
叶子结点表示一个分类。
有向边代表了一个划分规则。

决策树从根结点到子结点的的有向边代表了一条路径。决策树的路径是互斥并且是完备的。
用决策树分类时，对样本的某个特征进行测试，根据测试结果将样本分配到树的子结点上。此时每个子结点对应该特征的一个取值。
递归地对样本测试，直到该样本被划分叶结点。最后将样本分配为叶结点所属的类。
决策树的优点：可读性强，分类速度快。
决策树学习通常包括3个步骤：

特征选择。
决策树生成。
决策树剪枝。

决策树可以看成是一系列 if-then规则的集合，如下图所示，圆圈代表一个特征，方框是叶节点，表示得到的一个分类。决策树就是一个树状的流程图，将一个样本数据按照树中的条件一步步判断，就能得到最终的分类结果。

image.png

下面结合例子来详细理解决策树算法。

一、特征选择

首先我们需要确定，根节点，也就是第一个用来比较判断的特征是哪个特征。直觉上来讲，这个特征一定是最有助于帮助该样本进行分类的特征。在最好的情况下，该特征的分布与最终的分类结果完全一致，那么这个决策树就只有一个内部节点。一般情况下不会出现这种理想的特征，所以我们需要一个准则来判断哪个特征对分类最有帮助。通常的准则是信息增益或信息增益比。

在之前系列中介绍过熵的概念，熵表示一个随机变量不确定性的度量，设X是一个取有限个值的离散随机变量，其概率分布为： $P\left(X=x_{i}\right)=p_{i}, \quad i=1,2, \cdots, n$
则X的熵定义为： $H(X)=-\sum_{i=1}^{n} p_{i} \log p_{i}$

条件熵：

条件熵H(Y|X)表示在已知变量X的条件下随机变量Y的不确定性。定义为X给定条件下Y的条件概率分布对于X的数学期望。
$H(Y | X)=\sum_{i=1}^{n} p_{i} H\left(Y | X=x_{i}\right)$
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵和条件熵被称为经验熵和经验条件熵。

信息增益

特征A对训练数据集D的信息增益g(D,A)，定义为集合D的经验熵H(D)与特征A给定条件下D的经验条件熵H(D|A)之差，即： $g(D, A)=H(D)-H(D | A)$
所以我们对一个数据集D，计算其每个特征的信息增益，并选出最大的那个特征。

先来规定一些符号的含义：

设训练集为D，|D|表示其样本容量，即样本个数。设有K个类，分别为 $C_k$ 。 $|C_k|$ 为属于这个类的样本数。则 $\sum_{k=1}^{K}\left|C_{k}\right|=|D|$ 。设某个特征 $A$ 有n个不同的特征： $A = \left\{a_{1}, a_{2}, \dots, a_{n}\right\}$ 。根据A的取值将D划分成n个子集 $\mathrm{D}_{1}, \mathrm{D}_{2}, \ldots, \mathrm{D}_{\mathrm{n}}$ ， $\left|\mathrm{D}_{\mathrm{i}}\right|$ 为 $D_i$ 的样本个数， $则\sum_{i=1}^{n}\left|D_{i}\right|=|D|$ 。记子集 $D_i$ 中属于类 $C_k$ 的样本的集合为 $D_{ik}$ ，即 $\mathrm{D}_{\mathrm{ik}}=\mathrm{D}_{\mathrm{i}} \cap \mathrm{C}_{\mathrm{k}}$ ${D}_{\mathrm{ik}}$ 为 $D_{ik}$ 的样本数。

下面举例：

贷款情况表

例5.1中，|D|=15；k=2,（标签类别：是or否）， $C_1=9$ (类别为是的样本数）， $C_2=6$ (类别为否的样本数)。假设特征A是“年龄”特征，那么A有三个取值（青年，中年，老年）可以划分成三个子集， $D_1,D_2,D_3$ 都等于5，那么 $D_{11}$ 表示年龄为青年的样本中，类别为“是”的样本数， $D_{11}=2$ ， $D_{12}=3$ ，同理， $D_{21}=3$ ， $D_{22}=2$ ， $D_{31}=4$ ， $D_{32}=1$ 。

信息增益的算法如下：

输入：训练数据集D和特征A；
输出：特征A对训练数据集D的信息增益g(D,A)。
（1）计算数据集D的经验熵H(D)：
$H(D)=-\sum_{k=1}^{K} \frac{\left|C_{k}\right|}{|D|} \log _{2} \frac{\left|C_{k}\right|}{|D|}$ （2）计算特征A对数据集D的经验条件熵H(D|A)： $H(D | A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{D |} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|}$ （3）计算信息增益 $g(D, A)=H(D)-H(D | A)$
下面再举例，还是上面的数据集，计算其信息增益并选择最优特征。

首先计算经验熵H(D): $H(D)=-\frac{9}{15} \log _{2} \frac{9}{15}-\frac{6}{15} \log _{2} \frac{6}{15}=0.971$
然后计算各特征对数据集D的信息增益。分别以A1，A2，A3，A4表示年龄、有工作、有自己的房子和信贷情况4个特征，则：
（1） $\begin{aligned} g\left(D, A_{1}\right) &=H(D)-\left[\frac{5}{15} H\left(D_{1}\right)+\frac{5}{15} H\left(D_{2}\right)+\frac{5}{15} H\left(D_{3}\right)\right] \\ &=0.971-\left[\frac{5}{15}\left(-\frac{2}{5} \log _{2} \frac{2}{5}-\frac{3}{5} \log _{2} \frac{3}{5}\right)\right. \\ & +\frac{5}{15}\left(-\frac{3}{5} \log _{2} \frac{3}{5}-\frac{2}{5} \log _{2} \frac{2}{5}\right)+\frac{5}{15}\left(-\frac{4}{5} \log _{2} \frac{4}{5}-\frac{1}{5} \log _{2} \frac{1}{5}\right)] \\ & = 0.971 - 0.888 \\ & = 0.083 \end{aligned}$
同理：对于A2： $\begin{aligned} g\left(D, A_{2}\right) &=H(D)-\left[\frac{5}{15} H\left(D_{1}\right)+\frac{10}{15} H\left(D_{2}\right)\right] \\ &=0.971-\left[\frac{5}{15} \times 0+\frac{10}{15}\left(-\frac{4}{10} \log _{2} \frac{4}{10}-\frac{6}{10} \log _{2} \frac{6}{10}\right)\right]=0.324 \end{aligned}$
A3： $\begin{aligned} g\left(D, A_{3}\right) &=0.971-\left[\frac{6}{15} \times 0+\frac{9}{15}\left(-\frac{3}{9} \log _{2} \frac{3}{9}-\frac{6}{9} \log _{2} \frac{6}{9}\right)\right] \\ &=0.971-0.551=0.420 \end{aligned}$
A4： $g\left(D, A_{4}\right)=0.971-0.608=0.363$
最后，比较各特征的信息增益值。由于特征A3（有自己的房子）的信息增益值最大，所以选择特征A3作为最优特征。

信息增益比：

信息增益值的大小是相对于训练数据集而言的，并没有绝对意义。在分类问题困时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大。反之，信息增益值会偏小。使用信息增益比（information gain ratio）可以对这一问题进行校正。这是特征选择的另一准则。

信息增益比：特征A对训练数据集D的信息增益比gR(D,A)定义为其信息增益g(D,A)与训练数据集D的经验熵H(D)之比：
$g_{R}(D, A)=\frac{g(D, A)}{H(D)}$

二、决策树生成

ID3算法

输入：训练数据集D，特征集A，阈值；
输出：决策树T。
（1）若D中所有实例属于同一类Ck，则T为单结点树，并将类Ck作为该结点的类标记，返回T；
（2）若A＝Ø，则T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
（3）否则，按算法5.1计算A中各特征对D的信息增益，选择信息增益最大的特征Ag；
（4）如果Ag的信息增益小于阈值，则置T为单结点树，并将D中实例数最大的类Ck作为该结点的类标记，返回T；
（5）否则，对Ag的每一可能值ai，依Ag＝ai将D分割为若干非空子集Di，将Di中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
（6）对第i个子结点，以Di为训练集，以A-{Ag}为特征集，递归地调用步（1）～步（5），得到子树Ti，返回Ti。

对表5.1的训练数据集，利用ID3算法建立决策树。

由于特征A3（有自己的房子）的信息增益值最大，所以选择特征A3作为根结点的特征。它将训练数据集D划分为两个子集D1（A3取值为“是”）和D2（A3取值为“否”）。
由于D1（有自己的房子）可以直接得出其类别为是，所以它成为一个叶结点，结点的类标记为“是”。

对D2则需从特征A1（年龄），A2（有工作）和A4（信贷情况）中选择新的特征。（剔除原来的特征）计算各个特征的信息增益： $\begin{array}{l}{g\left(D_{2}, A_{1}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{1}\right)=0.918-0.667=0.251} \\ {g\left(D_{2}, A_{2}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{2}\right)=0.918} \\ {g\left(D_{2}, A_{4}\right)=H\left(D_{2}\right)-H\left(D_{2} | A_{4}\right)=0.474}\end{array}$

选择信息增益最大的特征A2（有工作）作为结点的特征。由于A2有两个可能取值，从这一结点引出两个子结点：一个对应“是”（有工作）的子结点，包含3个样本，它们属于同一类，所以这是一个叶结点，类标记为“是”；另一个是对应“否”（无工作）的子结点，包含6个样本，它们也属于同一类，所以这也是一个叶结点，类标记为“否”。

这样生成一个如图5.5所示的决策树。该决策树只用了两个特征（有两个内部结点）。

image.png

C4.5算法

C4.5 生成算法与 ID3 算法相似，但是 C4.5 算法在生成过程中用信息增益比来选择特征。

决策树实战python代码：基于机器学习实战。

https://github.com/yuki9965/decision-tree