统计学习方法习题笔记——第5章 决策树
思维导图
决策树模型
分类决策树模型是一种描述对实例进行分类的树形结构。决策树由结点（node）和有向边（directed edge）组成。结点有两种类型：内部结点（internal node）和叶结点（leaf node）。内部结点表示一个特征或属性，叶结点表示一个类。?用决策树分类，从根结点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子结点；这时，每一个子结点对应着该特征的一个取值，如此递归地对实例进行测试并分配，直至达到叶结点。最后将实例分到叶结点的类中。如下图表示一个相亲的决策过程，决策树的决策过程和人的思维很相似。
从不同角度看决策树
决策树与if-then规则
可以将决策树看成一个 if-then 规则的集合。将决策树转换成 if-then 规则的过程是这样的：由决策树的根结点到叶结点的每一条路径构建一条规则，路径上内部结点的特征对应着规则的条件，而叶结点的类对应着规则的结论。决策树的路径或其对应的 if-then 规则集合具有一个重要的性质：互斥并且完备。这就是说，每一个实例都被一条路径或一条规则所覆盖，而且只被一条路径或一条规则所覆盖。这里所谓覆盖是指实例的特征与路径上的特征一致或实例满足规则的条件。
决策树与条件概率分布
决策树还表示给定特征条件下类的条件概率分布。这一条件概率分布定义在特征空间的一个划分（partition）上。将特征空间划分为互不相交的单元（cell）或区域（region），并在每个单元定义一个类的概率分布就构成了一个条件概率分布，决策树的一条路径对应于划分中的一个单元，决策树所表示的条件概率分布由各个单元给定条件下类的条件概率分布组成。假设X为表示特征的随机变量，Y为表示类的随机变量，那么这个条件概率分布可以表示为 P（Y|X）。X取值于给定划分下单元的集合，Y取值于类的集合。各叶结点（单元）上的条件概率往往偏向某一个类，即属于某一类的概率较大。决策树树分类时将该结点的实例强行分到条件概率大的那一类去。
决策树的学习
决策树的学习通常包含三3个步骤：特征选择、决策树的生成和决策树的剪枝。
决策树学习用损失函数表示这一目标。如下所述，决策树学习的损失函数通常是正则化的极大似然函数，决策树学习的策略是以损失函数为目标函数的最小化。
?当损失函数确定以后，学习问题就变为在损失函数意义下选择最优决策树的问题。因为从所有可能的决策树中选取最优决策树是 NP 完全问题，所以现实中决策树学习算法通常采用启发式方法，近似求解这一最优化问题，这样得到的决策树是次最优（sub-optimal）的。
决策树学习的算法通常是一个递归地选择最优特征，并根据该特征对训练数据进行分割，使得对各个子数据集有一个最好的分类的过程，这一过程对应着对特征空间的划分，也对应着决策树的构建。
特征选择
不同决策树的差别主要在于特征选择的方式，主要有信息增益最大化，信息增益比最大等。首先需要理解熵的概念。
- 熵
在信息论与概率统计中，熵（cntropy）是表示随机变量不确定性的度量.设X 是一个取有限个值的离散随机变量，其概率分布为\(?P(X=x_i)=p_i,\quad i=1,2…,n\) 则随机变量X的熵定义为
- 条件熵
设有随机变量\((X,Y)\)，其联合概率分布为
条件熵 \(H(Y \mid X)\) 表示在已知随机变量 \(X\) 的条件下随机变量 \(Y\) 的不确定性。定义为 \(X\) 给定条件下 \(Y\) 的条件概率分布的熵对 \(X\) 的数学期望
\[H(Y \mid X)=\sum_{i=1}^{n} p_{i} H\left(Y \mid X=x_{i}\right) \]这里, \(p_{i}=P\left(X=x_{i}\right), \quad i=1,2, \cdots, n\).
- 信息增益
设训练数据集为 \(D,|D|\) 表示其样本容量, 即样本个数. 设有 \(K\) 个类 \(C_{k}, k=\) \(1,2, \cdots, K,\left|C_{k}\right|\) 为属于类 \(C_{k}\) 的样本个数, \(\sum_{k=1}^{K}\left|C_{k}\right|=|D|\). 设特征 \(A\) 有 \(n\) 个不同的 取值 \(\left\{a_{1}, a_{2}, \cdots, a_{n}\right\}\), 根据特征 \(A\) 的取值将 \(D\) 划分为 \(n\) 个子集 \(D_{1}, D_{2}, \cdots, D_{n},\left|D_{i}\right|\) 为 \(D_{i}\) 的样本个数, \(\sum_{i=1}^{n}\left|D_{i}\right|=|D|\). 记子集 \(D_{i}\) 中属于类 \(C_{k}\) 的样本的集合为 \(D_{i k}\), 即 \(D_{i k}=D_{i} \cap C_{k},\left|D_{i k}\right|\) 为 \(D_{i k}\) 的样本个数. 于是信息增益的算法如下:
输入: 训练数据集 \(D\) 和特征 \(A\);
输出: 特征 \(A\) 对训练数据集 \(D\) 的信息增益 \(g(D, A)\).
（1）计算数据集 \(D\) 的经验熵 \(H(D)\)
（2）计算特征 \(A\) 对数据集 \(D\) 的经验条件熵 \(H(D \mid A)\)
\[H(D \mid A)=\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} H\left(D_{i}\right)=-\sum_{i=1}^{n} \frac{\left|D_{i}\right|}{|D|} \sum_{k=1}^{K} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \log _{2} \frac{\left|D_{i k}\right|}{\left|D_{i}\right|} \]（3）计算信息增益
\[g(D, A)=H(D)-H(D \mid A) \]- 信息增益比
决策树的生成算法：ID3算法和C4.5算法
ID3算法和C4.5算法的主要区别在于特征选择方式的差异，ID3算法选择信息增益最大的特征，而C4.5选择信息增益比最大的特征。具体如下。
输入: 训练数据集 \(D\), 特征集 \(A\), 阈值 \(\varepsilon\);
输出: 决策树 \(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}\) 的信息增益（比）小于阈值 \(\varepsilon\), 则置 \(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-\left\{A_{g}\right\}\) 为特征集, 递归地调用步 \((1) \sim\) 步 \((5)\), 得到子树 \(T_{i}\), 返回 \(T_{i}\).
决策树的剪枝
输入: 生成算法产生的整个树 \(T\), 参数 \(\alpha\); 输出: 修剪后的子树 \(T_{\alpha}\).
(1) 计算每个结点的经验樀.
(2) 递归地从树的叶结点向上回缩.
设一组叶结点回缩到其父结点之前与之后的整体树分别为 \(T_{B}\) 与 \(T_{A}\), 其对应 的损失函数值分别是 \(C_{\alpha}\left(T_{B}\right)\) 与 \(C_{\alpha}\left(T_{A}\right)\), 如果
则进行剪枝, 即将父结点变为新的叶结点.
(3) 返回 (2), 直至不能继续为止, 得到损失函数最小的子树 \(T_{\alpha}\).
注意, 上只需考虑两个树的损失函数的差, 其计算可以在局部进行. 所以, 决策树的剪枝算法可以由一种动态规划的算法实现.
CART算法
分类与回归树（CART）模型是一种应用非常广泛的决策树学习算法，它是二叉树，既可用于分类也可用于回归，其中回归树用平方误差最小化准则，分类树用基尼指数最小化准则进行特征选择，生成二叉树。
最小二乘回归树算法
输入: 训练数据集 \(D\);
输出: 回归树 \(f(x)\).
在训练数据集所在的输入空间中, 递归地将每个区域划分为两个子区域并决 定每个子区域上的输出值, 构建二叉决策树:
(1) 选择最优切分变量 \(j\) 与切分点 \(s\), 求解
遍历变量 \(j\), 对固定的切分变量 \(j\) 扫描切分点 \(s\), 选择使上式达到最小 值的对 \((j, s)\).
(2) 用选定的对 \((j, s)\) 划分区域并决定相应的输出值:
(3) 继续对两个子区域调用步骤 (1), (2), 直至满足停止条件.
(4) 将输入空间划分为 \(M\) 个区域 \(R_{1}, R_{2}, \cdots, R_{M}\), 生成决策树:
分类树的生成
分类树用基尼指数选择最优特征，同时决定改特征的最优二值切分点。
基尼系数的定义：
分类问题中, 假设有 \(K\) 个类, 样本点属于第 \(k\) 类的概 率为 \(p_{k}\), 则概率分布的基尼指数定义为
对于二类分类问题, 若样本点属于第 1 个类的概率是 \(p\), 则概率分布的基尼指数为
\[\operatorname{Gini}(p)=2 p(1-p) \]对于给定的样本集合 \(D\), 其基尼指数为
\[\operatorname{Gini}(D)=1-\sum_{k=1}^{K}\left(\frac{\left|C_{k}\right|}{|D|}\right)^{2} \]这里, \(C_{k}\) 是 \(D\) 中属于第 \(k\) 类的样本子集, \(K\) 是类的个数.
如果样本集合 \(D\) 根据特征 \(A\) 是否取某一可能值 \(a\) 被分割成 \(D_{1}\) 和 \(D_{2}\) 两部分, 即
则在特征 \(A\) 的条件下, 集合 \(D\) 的基尼指数定义为
\[\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right) \]基尼指数 \(\operatorname{Gini}(D)\) 表示集合 \(D\) 的不确定性, 基尼指数 \(\operatorname{Gini}(D, A)\) 表示经 \(A=a\) 分割 后集合 \(D\) 的不确定性. 基尼指数值越大, 样本集合的不确定性也就越大, 这一点与熵相似.
CART分类树在所有可能的特征A以及它们所有可能的切分点a中，选择基尼指数最小的特征及对应的切分点作为最优特征与最优切分点.算法停止的条件是节点中的样本个数小于预定阈值，或样本集的基尼指数小于预定阈值（样本基本属于同一类），或者没有更多特征。
CART剪枝算法
输入: CART 算法生成的决策树 \(T_{0}\);
输出: 最优决策树 \(T_{\alpha}\).
(1) 设 \(k=0, T=T_{0}\).
(2) 设 \(\alpha=+\infty\).
(3) 自下而上地对各内部结点 \(t\) 计算 \(C\left(T_{t}\right),\left|T_{t}\right|\) 以及
这里, \(T_{t}\) 表示以 \(t\) 为根结点的子树, \(C\left(T_{t}\right)\) 是对训练数据的预测误差, \(\left|T_{t}\right|\) 是 \(T_{t}\) 的 叶结点个数.
(4) 自上而下地访问内部结点 \(t\), 如果有 \(g(t)=\alpha\), 进行剪枝, 并对叶结点 \(t\) 以多数表决法决定其类, 得到树 \(T\).
(5) 设 \(k=k+1, \alpha_{k}=\alpha, T_{k}=T\).
(6) 如果 \(T\) 不是由根结点单独构成的树, 则回到步骤 (4).
(7) 采用交叉验证法在子树序列 \(T_{0}, T_{1}, \cdots, T_{n}\) 中选取最优子树 \(T_{\alpha}\).
习题
5.1 根据表5.1所给的训练数据集，利用信息增益比（C4.5算法）生成决策树。
基于参考文献2的代码生成的C4.5决策树，节点类进行了修改，并添加了生成决策树图像的代码，基于Graphviz
点击查看代码
import json
import graphviz
from collections import Counter
import numpy as np
dot = graphviz.Digraph('c4.5', format='png')
# 节点类
class Node:
node_id = 0
def __init__(self, node_type, class_name, feature_name=None,
info_gain_ratio_value=0.0):
# 结点类型（internal或leaf）
self.node_type = node_type
# 特征名
self.feature_name = feature_name
# 类别名
self.class_name = class_name
# 子结点树
self.child_nodes = []
# Gini指数值
self.info_gain_ratio_value = info_gain_ratio_value
# 节点id
self.idx = str(Node.node_id)
Node.node_id += 1
def __repr__(self):
return json.dumps(self, indent=3, default=lambda obj: obj.__dict__, ensure_ascii=False)
def add_sub_tree(self, key, sub_tree):
self.child_nodes.append({"condition": key, "sub_tree": sub_tree})
def plot(self):
dot.node(self.idx, self.feature_name, fontname='Fangsong')
for sub_node in self.child_nodes:
dot.node(sub_node['sub_tree'].idx, sub_node['sub_tree'].class_name if sub_node['sub_tree'].node_type == 'leaf' else sub_node['sub_tree'].feature_name, fontname='Fangsong')
dot.edge(self.idx, str(sub_node['sub_tree'].idx), sub_node['condition'], fontname='Fangsong')
sub_node['sub_tree'].plot()
class MyDecisionTree:
def __init__(self, epsilon):
self.epsilon = epsilon
self.tree = None
def fit(self, train_set, y, feature_names):
features_indices = list(range(len(feature_names)))
self.tree = self._fit(train_set, y, features_indices, feature_names)
return self
# C4.5算法
def _fit(self, train_data, y, features_indices, feature_labels):
LEAF = 'leaf'
INTERNAL = 'internal'
class_num = len(np.unique(y))
# （1）如果训练数据集所有实例都属于同一类Ck
label_set = set(y)
if len(label_set) == 1:
# 将Ck作为该结点的类
return Node(node_type=LEAF, class_name=label_set.pop())
# （2）如果特征集为空
# 计算每一个类出现的个数
class_len = Counter(y).most_common()
(max_class, max_len) = class_len[0]
if len(features_indices) == 0:
# 将实例数最大的类Ck作为该结点的类
return Node(LEAF, class_name=max_class)
# （3）按式(5.10)计算信息增益，并选择信息增益最大的特征
max_feature = 0
max_gda = 0
D = y.copy()
# 计算特征集A中各特征
for feature in features_indices:
# 选择训练集中的第feature列（即第feature个特征）
A = np.array(train_data[:, feature].flat)
# 计算信息增益
gda = self._calc_ent_grap(A, D)
if self._calc_ent(D) != 0:
# 计算信息增益比
gda /= self._calc_ent(D)
# 选择信息增益最大的特征Ag
if gda > max_gda:
max_gda, max_feature = gda, feature
# （4）如果Ag信息增益小于阈值
if max_gda < self.epsilon:
# 将训练集中实例数最大的类Ck作为该结点的类
return Node(LEAF, class_name=max_class)
max_feature_label = feature_labels[max_feature]
# （6）移除已选特征Ag
sub_feature_indecs = np.setdiff1d(features_indices, max_feature)
sub_feature_labels = np.setdiff1d(feature_labels, max_feature_label)
# （5）构建非空子集
# 构建结点
feature_name = feature_labels[max_feature]
tree = Node(INTERNAL, class_name=None, feature_name=feature_name,
info_gain_ratio_value=max_gda)
max_feature_col = np.array(train_data[:, max_feature].flat)
# 将类按照对应的实例数递减顺序排列
feature_value_list = [x[0] for x in Counter(max_feature_col).most_common()]
# 遍历Ag的每一个可能值ai
for feature_value in feature_value_list:
index = []
for i in range(len(y)):
if train_data[i][max_feature] == feature_value:
index.append(i)
# 递归调用步（1）~步（5），得到子树
sub_train_set = train_data[index]
sub_train_label = y[index]
sub_tree = self._fit(sub_train_set, sub_train_label, sub_feature_indecs, sub_feature_labels)
# 在结点中，添加其子结点构成的树
tree.add_sub_tree(feature_value, sub_tree)
return tree
# 计算数据集x的经验熵H(x)
def _calc_ent(self, x):
x_value_list = set([x[i] for i in range(x.shape[0])])
ent = 0.0
for x_value in x_value_list:
p = float(x[x == x_value].shape[0]) / x.shape[0]
logp = np.log2(p)
ent -= p * logp
return ent
# 计算条件熵H(y/x)
def _calc_condition_ent(self, x, y):
x_value_list = set([x[i] for i in range(x.shape[0])])
ent = 0.0
for x_value in x_value_list:
sub_y = y[x == x_value]
temp_ent = self._calc_ent(sub_y)
ent += (float(sub_y.shape[0]) / y.shape[0]) * temp_ent
return ent
# 计算信息增益
def _calc_ent_grap(self, x, y):
base_ent = self._calc_ent(y)
condition_ent = self._calc_condition_ent(x, y)
ent_grap = base_ent - condition_ent
return ent_grap
def __repr__(self):
return str(self.tree)
# 表5.1的训练数据集
feature_names = np.array(["年龄", "有工作", "有自己的房子", "信贷情况"])
X_train = np.array([
["青年", "否", "否", "一般"],
["青年", "否", "否", "好"],
["青年", "是", "否", "好"],
["青年", "是", "是", "一般"],
["青年", "否", "否", "一般"],
["中年", "否", "否", "一般"],
["中年", "否", "否", "好"],
["中年", "是", "是", "好"],
["中年", "否", "是", "非常好"],
["中年", "否", "是", "非常好"],
["老年", "否", "是", "非常好"],
["老年", "否", "是", "好"],
["老年", "是", "否", "好"],
["老年", "是", "否", "非常好"],
["老年", "否", "否", "一般"]
])
y = np.array(["否", "否", "是", "是", "否",
"否", "否", "是", "是", "是",
"是", "是", "是", "是", "否"])
dt_tree = MyDecisionTree(epsilon=0.1)
dt_tree.fit(X_train, y, feature_names)
print(dt_tree)
dt_tree.tree.plot()
dot.render('tree')
5.2 已知如表5.2所示的训练数据，试用平方误差损失准则生成一个二叉回归树。
基于参考文献2的代码生成构建的回归二叉树
参考资料
- 《统计学习方法》李航
- DataWhale 统计学习方法习题解答