核心思想

决策树（Decision tree）是基于已知各种情况（特征取值）的基础上，通过构建树型决策结构来进行分析的一种方式，是常用的有监督的分类算法。

模拟人类买衣服

  • 每个内部结点表示一个属性的测试
  • 每个分支表示一个测试输出
  • 每个叶结点代表一种类别

以花分类为例子

其中“画板小于等于2.45”“花瓣大于2.45”…..即为属性
而山鸢尾、变色鸢尾、维吉尼亚鸢尾则是类别(叶子结点)

决策树生长与最优属性的选择

决策树生长流程

主要用递归实现

特别主义三个决策树生长的停止条件：

  • 样本全部属于同一类别（叶子）
  • 属性集合为空/样本属性取值都相同
  • 样本集合为空

最优属性选择

信息熵

消除不确定性所需信息量的度量，也是未知事件可能含有的信息量，可以度量样本集合「纯度」。

  • $p_k$取值为 $\ 1$ 的时候，信息熵为 $\ 0$（很显然这时候概率 $\ 1$ 表示确定事件，没有任何不确定性）；
  • 而当 $p_k$ 是均匀分布的时候，信息熵取最大值$log(|y|)$（此时所有候选同等概率，不确定性最大）。

信息增益

衡量的是我们选择某个属性进行划分时信息熵的变化（可以理解为基于这个规则划分，不确定性降低的程度）

信息增益描述了一个特征带来的信息量的多少

案例

以西瓜数据集为例。
数据集分为好瓜、坏瓜，所以 $|y|=2$。
根结点包含 $\ 17$ 个训练样例，其中好瓜共计 $\ 8$ 个样例，所占比例为 $\ 8/17$。
坏瓜共计 $\ 9$ 个样例，所占比例为 $\ 9/17$。

根结点信息熵

以属性「色泽」为例，其对应的 $\ 3$ 个数据子集：

  • $\ D1(色泽=青绿)$，包含 ${1，4，5，10，13，17}$，$\ 6$ 个样例，其中好瓜样例为{1，4，6} $\ %5Cleft%5C%7B%201%2C4%2C6%20%20%5Cright%5C%7D$，比例为 $\ 3/6$，坏瓜样例为{10，13，17}，比例为 $\ 3/6$。将数据带入信息熵计算公式即可得到该结点的信息熵。
    …..以此类推
    决策树算法详解; 最优属性选择; 信息增益示例;【图应该为结果2个类别，打错了】

色泽属性的信息增益为：

决策树算法详解; 最优属性选择; 信息增益示例;

同样的方法，计算其他属性的信息增益为：

决策树算法详解; 最优属性选择; 信息增益示例;

对比不同属性，我们发现「纹理」信息增益最大，其被选为划分属性清晰{1，2，3，4，5，6，8，10，15}、稍糊{7，9，13，14，17}、模糊{11，12，16}

再往下一步，我们看看「纹理」=「清晰」的节点分支，该节点包含的样例集合D1中有编号{1，2，3，4，5，6，8，10，15}共计9.

可用属性集合为{色泽、根蒂、敲声、脐部、触感}（此时「纹理」不再作为划分属性），我们同样的方式再计算各属性的信息增益为：

决策树算法详解; 最优属性选择; 信息增益示例;

从上图可以看出「根蒂」、「脐部」、「触感」$\ 3$ 个属性均取得了最大的信息增益，可用任选其一作为划分属性。同理，对每个分支结点进行类似操作，即可得到最终的决策树。

基尼系数

显然我们进行分类时，每一个类别实际混入其他类的数量越少分类就越纯粹，这种纯度我们通过如下公式表示：

我们使用基尼(gini)不纯度来衡量决策树的好坏。
目标：最小化基尼不纯度

对于基尼指数的一种理解方式是，之所以它可以用作纯度的度量，大家可以想象在一个漆黑的袋里摸球，有不同颜色的球，其中第k类占比记作$p_k$，那两次摸到的球都是第k类的概率就是$p_k^2$

那两次摸到的球颜色不一致的概率就是$1-\sum p_{k}^{2}$ ，它的取值越小，两次摸球颜色不一致的概率就越小，纯度就越高。

过拟合与剪枝

如果我们让决策树一直生长，最后得到的决策树可能很庞大

决策树与剪枝操作

  • 预剪枝（pre-pruning）：在决策树生长过程中，对每个结点在划分前进行估计，若当前结点的划分不能带来决策树泛化性能的提升，则停止划分并将当前结点标记为叶结点。

  • 后剪枝（post-pruning）：先从训练集生成一颗完整的决策树，然后自底向上地对非叶结点进行考察，若将该结点对应的子树替换为叶结点能带来决策树泛化性能的提升，则将该子树替换为叶结点。

预剪枝与后剪枝案例

预剪枝

决策树算法详解

预剪枝过程如下：将其标记为叶结点，类别标记为训练样例中最多的类别。

  • 若选「好瓜」，验证集中{4,5,8} 被分类正确，得到验证集精度为3/7x100%=42.9%
  • 根据结点 ② ③ ④ 的训练样例，将这 $\ 3$ 个结点分别标记为「好瓜」、「好瓜」、「坏瓜」(③ 的训练样例中好瓜更多，因此标记为好瓜)。
  • 此时，验证集中编号为{4,5,8,11,12}的样例被划分正确，验证精度提高至71.4%

后剪

我们在生成的完整决策树上进行「后剪枝」：

  • 用验证集的数据对该决策树进行评估，样例{4，11，12}分类正确，而样例{5，8，9，13}错误，此时的精度为 42.9%

  • 当对该决策树进行后剪枝，结点⑥的标记为好瓜此时，精度为 57.1%
    剪枝后的精度提升了，因此该决策树需要在结点 ⑥ 处进行剪枝。

总结：
时间开销：

  • 预剪枝：训练时间开销降低，测试时间开销降低。
  • 后剪枝：训练时间开销增加，测试时间开销降低。
    过/欠拟合风险：
  • 预剪枝：过拟合风险降低，欠拟合风险增加。
  • 后剪枝：过拟合风险降低，欠拟合风险基本不变。
    泛化性能：后剪枝通常优于预剪枝。

决策树代码实践

1
2
3
4
5
6
7
8
9
10
11
12
13
14
import numpy as np
import pandas as pd
from sklearn.tree import DecisionTreeClassifier

#引入数据集
df = pd.read_csv('https://blog.caiyongji.com/assets/iris.csv')

#决策树模型
X = df[['petal_length','petal_width']].to_numpy() 
y = df['species']
tree_clf = DecisionTreeClassifier(max_depth=2, random_state=42)
# random_state是随机种子
tree_clf.fit(X, y)

可视化决策树：

1
2
3
4
5
import matplotlib.pyplot as plt
from sklearn.tree import plot_tree
plt.figure(figsize=(12,8))
plot_tree(tree_clf,filled=True);


如上图，我们可以看到根节点总实例数为150时，由value = [50, 50, 50]可知，实际样本分类为50个山鸢尾花实例、50个变色鸢尾花实例、50个维吉尼亚鸢尾花实例。
我们再看最末尾右侧的叶子节点（紫色），由value = [0, 1, 45]可知，实际样本分类为0个山鸢尾花实例、1个变色鸢尾花实例、45个维吉尼亚鸢尾花实例。