机器学习

决策树

计算机学院 张腾

tengzhang@hust.edu.cn

大纲

符号学派 规则学习

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

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

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

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

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

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

覆盖

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

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

冲突

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

冲突消解 (conflict resolution)：

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

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

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

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

序贯覆盖

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

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

序贯覆盖 单文字规则

$是 \gets (时间 = 周六)$

序贯覆盖 单文字规则

$是 \gets (时间 = 周日)$

序贯覆盖 双文字规则

$是 \gets (时间 = 周六) \wedge (方式 = 吃饭)$

序贯覆盖 双文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

序贯覆盖 双文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

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

序贯覆盖 双文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

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

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

序贯覆盖 双文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

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

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

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

序贯覆盖 双文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

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

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

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

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

序贯覆盖 三文字规则

$是 \gets (时间 = 周日) \wedge (方式 = 吃饭)$

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

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

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

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

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

决策树

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

基本算法

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

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

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

信息增益

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

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

\begin{align} H(\dc) = - \sum_{k \in [C]} p_k \log p_k \end{align}

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

设属性$a$取值为$a_1, \ldots, a_V$，据此可将$\dc$划分为$\dc_1, \ldots, \dc_V$

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

\begin{align} \gain(\dc,a) = H(\dc) - \sum_{v \in [V]} \frac{|\dc_v|}{|\dc|} H(\dc_v) \end{align}

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

构建决策树

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

构建决策树

\begin{align} & \gain (\dc_1, 时间) = H (\dc_1) - \frac{4}{9} \class{red}{H(\{ 1,4,6,10 \})} - \frac{4}{9} \class{yellow}{H(\{ 2,3,8,15 \})} - \frac{1}{9} \class{blue}{H(\{ 5 \})} \\ & = \left( - \frac{7}{9} \log \frac{7}{9} - \frac{2}{9} \log \frac{2}{9} \right) - \frac{4}{9} \left( - \frac{3}{4} \log \frac{3}{4} - \frac{1}{4} \log \frac{1}{4} \right) - \frac{4}{9} \left( - \frac{3}{4} \log \frac{3}{4} - \frac{1}{4} \log \frac{1}{4} \right) \\ & = \frac{8}{3} \log 3 - \frac{7}{9} \log 7 - 2 = 0.043 \end{align}

构建决策树

\begin{align} & \gain (\dc_1, 方式) = H (\dc_1) - \frac{5}{9} \class{red}{H(\{ 1,2,3,4,5 \})} - \frac{3}{9} \class{yellow}{H(\{ 6,8,15 \})} - \frac{1}{9} \class{blue}{H(\{ 10 \})} \\ & = \left( - \frac{7}{9} \log \frac{7}{9} - \frac{2}{9} \log \frac{2}{9} \right) - \frac{3}{9} \left( - \frac{2}{3} \log \frac{2}{3} - \frac{1}{3} \log \frac{1}{3} \right) \\ & = \frac{5}{3} \log 3 - \frac{7}{9} \log 7 = 0.458 \end{align}

构建决策树

\begin{align} & \gain (\dc_1, 天气) = H (\dc_1) - \frac{6}{9} \class{red}{H(\{ 1,3,5,6,8,15 \})} - \frac{2}{9} \class{yellow}{H(\{ 2,4 \})} - \frac{1}{9} \class{blue}{H(\{ 10 \})} \\ & = \left( - \frac{7}{9} \log \frac{7}{9} - \frac{2}{9} \log \frac{2}{9} \right) - \frac{6}{9} \left( - \frac{5}{6} \log \frac{5}{6} - \frac{1}{6} \log \frac{1}{6} \right) \\ & = \frac{4}{3} \log 3 - \frac{7}{9} \log 7 + \frac{5}{9} \log 5 - \frac{8}{9} = 0.331 \end{align}

构建决策树

\begin{align} & \gain (\dc_1, 疫情) = H (\dc_1) - \frac{5}{9} \class{red}{H(\{ 1,2,3,4,5 \})} - \frac{3}{9} \class{yellow}{H(\{ 6,8,15 \})} - \frac{1}{9} \class{blue}{H(\{ 10 \})} \\ & = \left( - \frac{7}{9} \log \frac{7}{9} - \frac{2}{9} \log \frac{2}{9} \right) - \frac{3}{9} \left( - \frac{2}{3} \log \frac{2}{3} - \frac{1}{3} \log \frac{1}{3} \right) \\ & = \frac{5}{3} \log 3 - \frac{7}{9} \log 7 = 0.458 \end{align}

构建决策树

\begin{align} & \gain (\dc_1, 电视) = H (\dc_1) - \frac{6}{9} \class{red}{H(\{ 1,2,3,4,5,8 \})} - \frac{3}{9} \class{yellow}{H(\{ 6,10,15 \})} \\ & = \left( - \frac{7}{9} \log \frac{7}{9} - \frac{2}{9} \log \frac{2}{9} \right) - \frac{3}{9} \left( - \frac{2}{3} \log \frac{2}{3} - \frac{1}{3} \log \frac{1}{3} \right) \\ & = \frac{5}{3} \log 3 - \frac{7}{9} \log 7 = 0.458 \end{align}

构建决策树

\begin{align} & \gain (\dc_1, 时间) = 0.043 \\ & \gain (\dc_1, 方式) = 0.458 \\ & \gain (\dc_1, 天气) = 0.331 \\ & \gain (\dc_1, 疫情) = \class{blue}{0.458} \\ & \gain (\dc_1, 电视) = 0.458 \\[4pt] & \{ 1, 2, 3, 4, 5 \} 全正，\{ 10 \} 全负 \\[4pt] & \dc_4 = \{ 6, 8, 15 \} \\ \end{align}

\begin{align} & \gain (\dc_4, 时间) = \gain (\dc_4, 电视) = H(\dc_4) - \frac{2}{3} \times 1, ~ 不妨选时间 \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