机器学习

决策树

计算机学院    张腾

tengzhang@hust.edu.cn

大纲

符号学派 规则学习

规则学习中的规则 (rule) 指狭义的逻辑规则，呈 if-then 形式

$$ \begin{align*} \quad \overbrace{\otimes}^{\text{规则头}} \underbrace{\longleftarrow}_{\text{蕴含}} \overbrace{f_1 \wedge \underbrace{f_2}_{\text{文字}} \wedge \cdots \wedge f_L}^{\text{规则体}} \end{align*} $$

文字 (literal)：对特征进行检验的布尔表达式，如$(\text{天气 = 雨天})$

• 规则头：也是文字，一般表示规则判定的标记、类别或概念
• 规则体：即前提，由逻辑文字组成的合取式，文字个数称为规则长度

一个规则可以看成一个学习模型

符合规则的样本称为被该规则覆盖 (cover)

覆盖

$\class{blue}{\text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{疫情=清零})}$

$\class{red}{\text{否} \longleftarrow (\text{课业=繁重})}$

冲突

一个样本若被判定结果不同的多个规则覆盖，称发生了冲突

冲突消解 (conflict resolution)：

• 投票法：少数服从多数
• 排序法：在规则集合上定义一个优先级顺序
• 元规则法：规则的规则，例如“发生冲突时使用长度最小的规则”

规则集合未必能覆盖所有未知样本

$$ \begin{align*} \qquad \quad \text{规则集合} = \begin{cases} \text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{疫情=清零}) \\ \text{否} \longleftarrow (\text{课业=繁重}) \end{cases} \end{align*} $$

默认规则：例如“未被规则集合覆盖的都不约会”

序贯覆盖

序贯覆盖 (sequential covering)，即逐条归纳

• 从空规则开始，将正类作为规则头，遍历每个特征的取值
• 若当前规则的规则体仅覆盖正类样本，则由此产生一条规则
• 去掉所有已被覆盖的样本
• 在剩下的训练数据集上重复上述过程

序贯覆盖 单文字规则

$\text{是} \longleftarrow (\text{时间=周六})$

序贯覆盖 单文字规则

$\text{是} \longleftarrow (\text{时间=周日})$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周六}) \wedge (\text{方式=吃饭})$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

$\class{red}{\text{是} \longleftarrow (\text{时间=周间}) \wedge (\text{课业=轻松})}$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

$\class{red}{\text{是} \longleftarrow (\text{时间=周间}) \wedge (\text{课业=轻松})}$

$\class{yellow}{\text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{课业=轻松})}$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

$\class{red}{\text{是} \longleftarrow (\text{时间=周间}) \wedge (\text{课业=轻松})}$

$\class{yellow}{\text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{课业=轻松})}$

$\class{blue}{\text{是} \longleftarrow (\text{课业=轻松}) \wedge (\text{电视=精彩})}$

序贯覆盖 双文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

$\class{red}{\text{是} \longleftarrow (\text{时间=周间}) \wedge (\text{课业=轻松})}$

$\class{yellow}{\text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{课业=轻松})}$

$\class{blue}{\text{是} \longleftarrow (\text{课业=轻松}) \wedge (\text{电视=精彩})}$

$\class{orange}{\text{是} \longleftarrow (\text{课业=适中}) \wedge (\text{电视=无聊})}$

序贯覆盖 三文字规则

$\text{是} \longleftarrow (\text{时间=周日}) \wedge (\text{方式=吃饭})$

$\class{red}{\text{是} \longleftarrow (\text{时间=周间}) \wedge (\text{课业=轻松})}$

$\class{yellow}{\text{是} \longleftarrow (\text{方式=吃饭}) \wedge (\text{课业=轻松})}$

$\class{blue}{\text{是} \longleftarrow (\text{课业=轻松}) \wedge (\text{电视=精彩})}$

$\class{orange}{\text{是} \longleftarrow (\text{课业=适中}) \wedge (\text{电视=无聊})}$

$\class{cyan}{\text{是} \longleftarrow (\text{时间=周六}) \wedge (\text{方式=逛街}) \\ \quad \quad \quad \wedge (\text{课业=轻松})}$

决策树

序贯覆盖：删除样本
决策树：划分样本

基本算法

输入：训练集$D = \{ (\xv_i, y_i) \}_{i \in [m]}$，属性集$A = \{ a_j \}_{j \in [d]}$
过程：函数$\TG(D,A)$

1. 生成结点$\node$
2. if $D$中样本全属于同一类别$C$ then     // 递归情形 1
3.   将$\node$标记为$C$类叶结点 return
4. if $A = \emptyset$ or $D$中样本在$A$上取值相同 then     // 递归情形 2
5.   将$\node$标记为叶结点，其类别标记为$D$中样本最多的类 return
6. 从$A$中选择最优划分属性$a^\star$，对$a^\star$的每一个取值$a^\star_v$，为$\node$生成一个分支，令$D_v$表示$D$在$a^\star$上取值为$a^\star_v$的样本子集
7. if $D_v = \emptyset$ then     // 递归情形 3
8.   将分支结点标记为叶结点，其类别标记为$D$中样本最多的类 return
9. else
10.   以$\TG(D_v, A \setminus \{ a^\star \})$为分支结点

输出：以$\node$为根结点的一棵决策树

信息增益

目标：随着划分的不断进行，决策树结点的纯度越来越高

设数据集$D$中第$k$类样本的比例为$p_k = p(y = k)$，熵定义为

$$ \begin{align*} \quad H(D) = - \sum_{k \in [C]} p_k \log p_k \end{align*} $$

• 当$p_1 = \cdots = p_C = 1/C$时，$H(D) = \log C$，熵最大，纯度最低
• 当某个$p_i = 1$、其余为零时，$H(D) = 0$，熵最小，纯度最高

设属性$a$取值为$a_1, \ldots, a_V$，据此可将$D$划分为$D_1, \ldots, D_V$

用属性$a$对$D$进行划分产生的信息增益 (information gain)

$$ \begin{align*} \quad \gain(D,a) = H(D) - \sum_{v \in [V]} \frac{|D_v|}{|D|} H(D_v) \end{align*} $$

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

$$ \begin{align*} & \text{时间：} \frac{2}{5} H(\class{blue}{\{ 7,9 \}}) + \frac{2}{5} H(\{ 13,17 \}) + \frac{1}{5} H(\{ 14 \}) > 0 \\ & \text{方式：} \frac{4}{5} H(\class{blue}{\{ 7,9,13,14 \}}) + \frac{1}{5} H(\{ 17 \}) > 0 \\ & \text{天气：} \frac{2}{5} H(\class{blue}{\{ 7,13 \}}) + \frac{3}{5} H(\{ 9,14,17 \}) > 0 \\ & \text{疫情：} \frac{3}{5} H(\class{blue}{\{ 7,9,17 \}}) + \frac{2}{5} H(\{ 13,14 \}) > 0 \\ & \text{电视：} \frac{1}{5} H(\{ 7 \}) + \frac{4}{5} H(\{ 9,13,14,17 \}) = 0 \end{align*} $$

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

$$ \begin{align*} & \gain (D_1, \text{时间}) = 0.043 \\ & \gain (D_1, \text{方式}) = 0.458 \\ & \gain (D_1, \text{天气}) = 0.331 \\ & \gain (D_1, \text{疫情}) = 0.458 ~ \surd \\ & \gain (D_1, \text{电视}) = 0.458 \\[4pt] & \{ 1, 2, 3, 4, 5 \} \text{全正，}\{ 10 \}\text{全负} \\ & D_4 = \{ 6, 8, 15 \} \\ \end{align*} $$

$$ \begin{align*} & \gain (D_4, \text{时间}) = \gain (D_4, \text{电视}) = H(D_4) - \frac{2}{3} \times 1 \text{，不妨选时间} \end{align*} $$

ID3 决策树

ID3 (iterative dichotomiser)

鸢尾花数据集

美国植物学家安德森收集，英国统计学家费雪引入到统计分析中

150 个样本

4 个特征

• 花萼长度 sepal length
• 花萼宽度 sepal width
• 花瓣长度 petal length
• 花瓣宽度 petal width

3 个类别，每类 50 个样本

• 山鸢尾 iris setosa
• 杂色鸢尾 iris versicolour
• 维吉尼亚鸢尾 iris virginica

鸢尾花数据集

import numpy as np
import pandas as pd
from sklearn.datasets import load_iris

iris = load_iris()
print(iris.DESCR)
# --------------------
# Iris plants dataset
#
# **Data Set Characteristics:**
#
# :Number of Instances: 150 (50 in each of three classes)
# :Number of Attributes: 4 numeric, predictive attributes and the class
# :Attribute Information:
#     - sepal length in cm        花萼长度
#     - sepal width in cm         花萼宽度
#     - petal length in cm        花瓣长度
#     - petal width in cm         花瓣宽度
#     - class:
#             - Iris-Setosa       山鸢尾
#             - Iris-Versicolour  杂色鸢尾
#             - Iris-Virginica    维吉尼亚鸢尾
#
# :Summary Statistics:
#
# ============== ==== ==== ======= ===== ====================
#                 Min  Max   Mean    SD   Class Correlation
# ============== ==== ==== ======= ===== ====================
# sepal length:   4.3  7.9   5.84   0.83    0.7826
# sepal width:    2.0  4.4   3.05   0.43   -0.4194
# petal length:   1.0  6.9   3.76   1.76    0.9490  (high!)
# petal width:    0.1  2.5   1.20   0.76    0.9565  (high!)
# ============== ==== ==== ======= ===== ====================
#

鸢尾花数据集

用决策树分类鸢尾花

from sklearn import tree
import graphviz

clf = tree.DecisionTreeClassifier()
clf = clf.fit(X, y)
dot_data = tree.export_graphviz(
    clf, out_file=None
)
graph = graphviz.Source(dot_data)
graph

用决策树分类鸢尾花

from sklearn import tree
import graphviz

clf = tree.DecisionTreeClassifier(
    criterion='entropy', max_depth=4
)
clf = clf.fit(X, y)
dot_data = tree.export_graphviz(
    clf, out_file=None
)
graph = graphviz.Source(dot_data)
graph