机器学习 - 决策树算法[一]

作者: nlpming | 来源:发表于2020-08-09 21:37 被阅读0次

1 决策树模型与学习

1.1 决策树模型

决策树定义： 分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。
下图是一个对西瓜进行二分类的例子，西瓜包括4个特征：纹理、根蒂、色泽、触感；类别：好瓜、坏瓜。
决策树与if-then规则：可以将决策树看成一个if-then规则的集合。将决策树转换成if-then规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则；路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。

决策树示例.png

1.2 决策树学习

假设给定训练数据集： $D = \{ (x_1,y_1), (x_2,y_2), ..., (x_N,y_N) \}$ ，其中 $x_i = (x_i^{(1)}, x_i^{(2)}, ..., x_i^{(n)})$ 为输入实例（特征向量）， $n$ 为特征个数。 $y_i \in \{ 1,2, ..., K \}$ 为类标记。 $i=1,2, ...,N$ ， $N$ 为样本个数。决策树学习的目标是根据给定的训练数据集构建一个决策树模型，使它能够对实例进行正确的分类。
决策树学习的损失函数通常是正则化的极大似然损失。 当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是NP完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题。这样得到的决策树是次最优的。
决策树学习算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程。这一过程对应着特征空间的划分，也对应着决策树的构建。
决策树学习过程如下：
（1）开始，构建根结点，将所有训练数据都放在根结点。选择一个最优特征，按照这一特征将训练数据分割成子集，使得各个子集有一个在当前条件下最好的分类。
（2）如果这些子集能够被基本正确分类，那么构建叶结点，并将这些子集分到所对应的叶结点中去。如果还有子集不能被正确分类，那么就对这些子集选择新的最优特征，继续对其进行分割，构建相应的结点。
（3）如此递归地进行下去，直到所有训练数据子集都被基本正确分类，或者没有合适的特征为止。
（4）最后，每个子集都被分到叶结点上，即都有了明确的类。这就生成了一棵决策树。
决策树很容易发生过拟合，因此需要对决策树进行剪枝。 具体地，就是去掉过于细分的叶结点，使其回退到父结点甚至更高的结点，然后将其父结点或更高的结点改为叶结点。

2 特征选择

信用贷款申请数据集，总共有15个样本；每个样本的特征包括：年龄、有工作、有自己的房子、信贷情况；类别：是、否。
信用贷款申请数据集.png
特征选择是决定用哪个特征来划分特征空间。如果一个特征具有更好的分类能力，或者说按照这一特征将训练数据集分割成子集，使得各个子集在当前条件下有最好的分类，那么就更应该选择这个特征。

2.1 信息增益

2.1.1 信息熵

在信息论与概率统计中，熵（entropy）是表示随机变量不确定的度量。 设 $X$ 是一个取有限个值的离散随机变量，其概率分布为 $P(X = x_i) = p_i, i = 1,2,...,n$ ；则随机变量 $X$ 的熵定义为：
$H(X) = -\sum_{i=1}^n p_i log p_i$
熵越大，随机变量的不确定性就越大。从定义可验证： $0 \leq H(p) \leq logn$
均匀分布（ $p=1/n$ ）随机变量熵最大；

2.1.2 条件熵

条件熵 $H(Y|X)$ 表示在已知随机变量 $X$ 的条件下随机变量 $Y$ 的不确定性。 定义为 $X$ 给定条件下 $Y$ 的条件概率分布的熵对 $X$ 的数学期望：
$H(Y|X) = \sum_{i=1}^n p_i H(Y|X = x_i)$
上式中， $p_i = P(X = x_i), i = 1,2,...,n$
当熵和条件熵中的概率由数据估计（特别是极大似然估计）得到时，所对应的熵与条件熵分别称为经验熵（empirical entropy）和经验条件熵（empirical conditional entropy）；

2.1.3 信息增益

信息增益（information gain）表示得知特征 $X$ 的信息而使得类 $Y$ 的信息不确定性减少的程度。
信息增益定义： 特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$ ，定义为 $D$ 的经验熵 $H(D)$ 与特征 $A$ 给定条件下 $D$ 的经验条件熵 $H(D|A)$ 之差，即
$g(D,A) = H(D) - H(D|A)$
$H(D)$ 表示对数据集 $D$ 进行分类的不确定性，而经验条件熵 $H(D|A)$ 表示在特征 $A$ 给定条件下对数据集 $D$ 进行分类的不确定性。则信息增益表示由于特征 $A$ 而使得对数据集 $D$ 的分类不确定性减少的程度。

2.1.4 如何计算信息增益？

输入：训练数据集 $D$ 和特征 $A$
输出：特征 $A$ 对训练数据集 $D$ 的信息增益 $g(D,A)$
（1）计算数据集 $D$ 的经验熵 $H(D)$
$H(D) = - \sum_{k=1}^{K} \frac{|C_k|}{|D|} log_2 \frac{|C_k|}{|D|}$
（2）计算特征 $A$ 对数据集 $D$ 的经验条件熵 $H(D|A)$
$H(D|A) = \sum_{i=1}^{n} \frac{|D_i|}{|D|} H(D_i) = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} \sum_{k=1}^{K} \frac{|D_{ik}|}{|D_i|} log_2 \frac{|D_{ik}|}{|D_i|}$
（3）计算信息增益
$g(D,A) = H(D) - H(D|A)$
上式中， $|D|$ 表示训练集样本个数；设有 $K$ 个类别 $C_k， k=1,2,...,K$ ， $|C_k|$ 表示属于类 $C_k$ 的样本个数。 $\sum_{i=1}^{n} |C_k| = |D|$ ；设特征 $A$ 有 $n$ 个不同的取值 ${a_1,a_2,...,a_n}$ ，根据特征 $A$ 的取值将 $D$ 划分成 $n$ 个子集 $D_1,D_2,...,D_n$ ；记子集 $D_i$ 中属于类 $C_k$ 的样本集合为 $D_{ik}$ 。

信息增益选择最优特征.png

2.2 信息增益比

信息增益存在的问题：信息增益存在偏向选取取值较多的特征。 例如，对于上表中的第一列序号特征，给定 $A$ 的情况下样本只有一个所以 $H(D|A) = 0$ ，因此“序号”这个特征的信息增益很大，但是其对于样本分类没有作用。
信息增益比定义： 特征 $A$ 对训练数据集 $D$ 的信息增益比 $g_R(D,A)$ 定义为其信息增益 $g(D,A)$ 与训练数据集 $D$ 关于特征 $A$ 的取值的熵 $H_A(D)$ 之比，即：
$g_R(D, A) = \frac{g(D,A)}{H_A(D)},$
上式中， $H_A(D) = - \sum_{i=1}^{n} \frac{|D_i|}{|D|} log_2 { \frac{|D_i|}{|D|} }$ ， $n$ 是特征 $A$ 的取值个数。

3 ID3、C4.5决策树生成算法

ID3算法的核心： 在决策树各个结点上应用信息增益准则选择特征，递归地构建决策树。
ID3算法生成决策树过程：

输入：训练数据集 $D$ ，特征集 $A$ ，阈值 $\epsilon$ ；
输出：决策树 $T$ ;
（1）若 $D$ 中所有实例属于同一类 $C_k$ ，则 $T$ 为单结点树，并将类 $C_k$ 作为该结点的类标记，返回 $T$ ；
（2）若 $A = \varnothing$ ，则 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
（3）否则，计算 $A$ 中各个特征对 $D$ 的信息增益，选择信息增益最大的特征 $A_g$ ；
（4）如果 $A_g$ 的信息增益小于阈值 $\epsilon$ ，则置 $T$ 为单结点树，并将 $D$ 中实例数最大的类 $C_k$ 作为该结点的类标记，返回 $T$ ；
（5）否则，对 $A_g$ 的每一可能值 $a_i$ ，依 $A_g = a_i$ 将 $D$ 分割为若干非空子集 $D_i$ ，将 $D_i$ 中实例数最大的类作为标记（只是记录，非叶子结点没有类标），构建子结点，由结点及其子结点构成树 $T$ ，返回 $T$ ；
（6）对第 $i$ 个子结点，以 $D_i$ 为训练集，以 $A - {A_g}$ 为特征集，递归地调用步骤（1）~（5）得到子树 $T_i$ ，返回 $T_i$ ；