机器学习

决策树

计算机学院 张腾

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. 生成结点$v$
2. if $\dc$中样本全属于同一类别$C$ then     // 递归情形 1
3.   将$v$标记为$C$类叶结点 return
4. if $\ac = \emptyset$ or $\dc$中样本在$\ac$上取值相同 then     // 递归情形 2
5.   将$v$标记为叶结点，其类别标记为$\dc$中样本最多的类 return
6. 从$\ac$中选择最优划分属性$a^\star$，对$a^\star$的每一个取值$a^\star_v$，为$v$生成一个分支，令$\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 \})$为分支结点

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

信息增益

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

设数据集$\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!)
# ============== ==== ==== ======= ===== ====================
#
# :Missing Attribute Values: None
# :Class Distribution: 33.3% for each of 3 classes.
# :Creator: R.A. Fisher
# :Donor: Michael Marshall (MARSHALL%PLU@io.arc.nasa.gov)
# :Date: July, 1988
#
# The famous Iris database, first used by Sir R.A. Fisher. The dataset is taken
# from Fisher's paper. Note that it's the same as in R, but not as in the UCI
# Machine Learning Repository, which has two wrong data points.
#
# This is perhaps the best known database to be found in the
# pattern recognition literature.  Fisher's paper is a classic in the field and
# is referenced frequently to this day.  (See Duda & Hart, for example.)  The
# data set contains 3 classes of 50 instances each, where each class refers to a
# type of iris plant.  One class is linearly separable from the other 2; the
# latter are NOT linearly separable from each other.
#
# .. dropdown:: References
#
#   - Fisher, R.A. "The use of multiple measurements in taxonomic problems"
#     Annual Eugenics, 7, Part II, 179-188 (1936); also in "Contributions to
#     Mathematical Statistics" (John Wiley, NY, 1950).
#   - Duda, R.O., & Hart, P.E. (1973) Pattern Classification and Scene Analysis.
#     (Q327.D83) John Wiley & Sons.  ISBN 0-471-22361-1.  See page 218.
#   - Dasarathy, B.V. (1980) "Nosing Around the Neighborhood: A New System
#     Structure and Classification Rule for Recognition in Partially Exposed
#     Environments".  IEEE Transactions on Pattern Analysis and Machine
#     Intelligence, Vol. PAMI-2, No. 1, 67-71.
#   - Gates, G.W. (1972) "The Reduced Nearest Neighbor Rule".  IEEE Transactions
#     on Information Theory, May 1972, 431-433.
#   - See also: 1988 MLC Proceedings, 54-64.  Cheeseman et al"s AUTOCLASS II
#     conceptual clustering system finds 3 classes in the data.
#   - Many, many more ...

X, y = iris.data, iris.target

irisdf = pd.DataFrame(  # numpy格式 -> pandas格式
    np.hstack((X, y[:, np.newaxis])),
    columns=['sepal-length', 'sepal-width', 'petal-length', 'petal-width', 'class']
)
kind_dict = {0: "setosa", 1: "versicolor", 2: "virginica"}
irisdf["class"] = irisdf["class"].map(kind_dict)

print(irisdf.head())  # 前5个样本
# --------------------
#    sepal-length  sepal-width  petal-length  petal-width   class
# 0           5.1          3.5           1.4          0.2  setosa
# 1           4.9          3.0           1.4          0.2  setosa
# 2           4.7          3.2           1.3          0.2  setosa
# 3           4.6          3.1           1.5          0.2  setosa
# 4           5.0          3.6           1.4          0.2  setosa

print(irisdf.tail())  # 最后5个样本
# --------------------
#      sepal-length  sepal-width  petal-length  petal-width      class
# 145           6.7          3.0           5.2          2.3  virginica
# 146           6.3          2.5           5.0          1.9  virginica
# 147           6.5          3.0           5.2          2.0  virginica
# 148           6.2          3.4           5.4          2.3  virginica
# 149           5.9          3.0           5.1          1.8  virginica

print(irisdf.describe())  # 特征统计信息
# --------------------
#        sepal-length  sepal-width  petal-length  petal-width
# count    150.000000   150.000000    150.000000   150.000000
# mean       5.843333     3.057333      3.758000     1.199333
# std        0.828066     0.435866      1.765298     0.762238
# min        4.300000     2.000000      1.000000     0.100000
# 25%        5.100000     2.800000      1.600000     0.300000
# 50%        5.800000     3.000000      4.350000     1.300000
# 75%        6.400000     3.300000      5.100000     1.800000
# max        7.900000     4.400000      6.900000     2.500000

鸢尾花数据集

鸢尾花数据集

用决策树分类鸢尾花

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