第 3 章 决策树
1. 本章概要
-
分类决策树模型是基于特征对数据集进行分类的树形结构。它可以转换成 if-else 规则的集合
-
决策树的学习旨在构建一个对训练集拟合良好的、复杂度小的树
-
决策树学习算法有三种：ID3、C4.5 和 CART 算法
-
特征选取的目的在于：选择划分数据集的最佳特征。
-
特征选取的关键是选择准则，常用准则有：
-
集合 D 对属性 $A_i$ 的信息增益（ID3）
$ H(D) = p_i \log_2 p_i $
$ H(D \mid A_i) = \sum\limits_{j=1}^n p_j H(D_j)$-
其中：
- H(D)是数据集D的熵
- $H(D_j)$ 是数据集 $D_j$ 的熵
- $H(D \mid A_i) 是数据集D对特征 $A_i$ 的条件熵
- $D_j$ 是D中特征 $A_i$ 取第 j 个值的样本子集
- 集合 D 对特征$A_i$ 的信息增益比（C4.5）
- 样本集合 D 的基尼指数（CART）
特征 $A_i$ 下集合 D 的基尼指数：
-
-
-
决策树的生成，使用选择准则最佳的特征
-
决策树的剪枝。由于生成的决策树存在过拟合，所以需要剪枝。
2. 目录
- 决策树的构造 1.1 信息增益 1.2 划分数据集 1.3 递归构建决策树
- 决策树的绘制
- 测试和存储决策树
- 用决策树预测
3. 学习笔记
3.1 决策树的构造
决策树是一种基本的分类和回归方法，它呈树形结构。在分类问题中，基于特征对实例进行分类，可以认为是 if-else 规则的集合，也可以认为是定义在特征空间与类空间上的条件概率分布。
决策树由节点（node）和有向边（directed edge）也称为分支组成。节点分为内节点(决策节点）和叶节点。内节点表示一个特征或属性，叶节点表示一个分类。
要构建一棵决策树，首先要确定当前数据集上的特征，哪一个是用于划分的最佳特征。确定了最佳特征后，根据最佳特征的各个特征值将原数据集划分为相应的多个子集，这样子集就分布在第一个决策点的所有分支上。如果子集中数据属于同一类，无需再分；如果子集内数据不属于同一类，则需要再重复子集划分的过程。
下面就是决策树构建的算法：
构建决策树：
1. D 中样本属于同一类别，返回分类标签
2. D 中样本没有属性，返回多数类标签
3. 找出最佳划分属性
4. 创建中间节点
5. 对于每个属性值：
5.1 用属性值抽取子集
5.2 调用create_tree构建决策树，并放入中间节点
6. 返回决策树
3.1.1 信息增益
划分数据的最大原则就是，将无序的数据变得有序。对数据的无序进行度量的方法是信息熵，划分数据集前后信息发生的变化量称为信息增益，获得信息增益最高的特征就是最佳特征
熵可以认为是随机事件 X 包含的信息量大小，而信息的定义为：
其中 $p(x_i)$ 是选择该分类的概率
为了计算熵，需要计算所有类别所有可能值包含的信息期望值，所以熵为：
下面是计算熵的算法：
def calc_ent(dataset):
'''
计算数据集的信息熵
'''
# 1. 解析出数据集的分类列表
label_list = [sample[-1] for sample in dataset]
label_len = len(label_list)
label_count = Counter(label_list)
# 2. 对于每个分类：
dataset_ent = 0
for count in label_count.values():
# 2.1 计算分类的占比
prob = count / label_len
# 2.2 累加信息熵
dataset_ent -= prob * log(prob, 2)
# 3. 返回熵
return dataset_ent
3.1.2 划分数据集
我们需要用最佳特征来划分数据集，而最佳特征是划分数据集前后信息增益最大的特征，即：
而
所以，要找到 $Gain(D, A_i)$ 最大的特征 $A_i$ 。首先我们要能对数据集划分，下面就是用特征对数据集进行划分的方法：
def get_subset(dataset, attr_idx, attr_value):
'''
用属性值抽取子集
'''
sub_dataset = []
# 1. 对于数据集中的每一个样本：
for sample in dataset:
# 1.1 如果样本的idx属性值==value，则取出去除了此属性的样本
if sample[attr_idx] == attr_value:
sub_sample = sample[:attr_idx]
sub_sample.extend(sample[attr_idx+1:])
# 1.2 把此样本放入子集中
sub_dataset.append(sub_sample)
# 2. 返回子集
return sub_dataset
接下来，我们将遍历整个数据集的特征，计算信息增益，找到最好的特征划分方式：
def find_best_label_idx(dataset):
'''
找到划分数据集的最佳属性
'''
# 1. 求 H(D)
data_ent = calc_ent(dataset)
dataset_len = len(dataset)
# 2. 对于D的每一个属性Ai
num_attr = len(dataset[0]) - 1
max_info_gain = -1
for i in range(num_attr):
attr_values = [sample[i] for sample in dataset]
unique_attr_values = set(attr_values)
# 2.1 对于Ai的每一个属性值 aj:
condition_ent = 0
for value in unique_attr_values:
# 2.1.1 用aj从D中抽取子集Dj
sub_dataset = get_subset(dataset, i, value)
# 2.1.2 计算 H(Dj)
sub_dataset_ent = calc_ent(sub_dataset)
sub_dataset_len = len(sub_dataset)
# 2.1.3 计算 H(D|Ai)
prob = float(sub_dataset_len) / dataset_len
condition_ent += prob * sub_dataset_ent
# 2.2 计算信息增益 Gain(D, Ai) = H(D) - H(D|Ai)
info_gain = data_ent - condition_ent
# 2.3 更新信息增益最大的属性序号
if info_gain > max_info_gain:
max_info_gain = info_gain
best_attr_idx = i
# 3. 返回序号
return best_attr_idx
3.1.3 构建决策树
现在我们来回顾一下构建树的过程，我们得到原始数据，然后基于最佳特征划分数据集。由于特征值可能多个两个，因此可能存在大于两个分支的数据集划分。第一次划分后，数据将向下传向树分支的下一个节点，在这个节点上，我们可以再次划分数据。因此可以采用递归的原则处理数据。 递归结束的条件是：遍历完所有属性，或者每个分支下的所有实例都具有相同分类。如果是这样，则得到一个叶子节点。对于第一种情况，我们采用多数表决的方法决定叶子节点的分类。
下面是多数表决的程序：
def majority_label(label_list):
'''
返回多数类别名称
'''
label_count = Counter(label_list)
return label_count.most_common(1)[0][0
有了多数表决器，我们的决策村就可以构建出来了：
def create_tree(dataset, labels):
'''
构建决策树：
1. D 中样本属于同一类别，返回分类标签
2. D 中样本没有属性，返回多数类标签
3. 找出最佳划分属性
4. 创建中间节点
5. 对于每个属性值：
5.1 用属性值抽取子集
5.2 调用create_tree构建决策树，并放入中间节点
6. 返回决策树
'''
label_list = [sample[-1] for sample in dataset]
if label_list.count(label_list[0]) == len(label_list):
return label_list[0]
if len(dataset[0]) == 1:
return majority_label(dataset)
best_label_idx = find_best_label_idx(dataset)
best_label_name = labels[best_label_idx]
mytree = {best_label_name: {}}
del labels[best_label_idx]
best_attr_values = [sample[best_label_idx] for sample in dataset]
unique_values = set(best_attr_values)
for value in unique_values:
sub_dataset = get_subset(dataset, best_label_idx, value)
sub_labels = labels[:]
mytree[best_label_name][value] = create_tree(sub_dataset, sub_labels)
return mytree
3.2 绘制决策树
3.2.1 绘制子树
绘制决策树是一个递归过程，其中最重要的是绘制子树的部分：
def plot_child_tree(tree, parent_pos, attr_value):
'''
画出子树
1. 计算子树的宽
2. 计算子树桩节点位置
3. 画出子树支及属性值
4. 画出子树桩节点
5. 对于子树桩下的每一个分支：
5.1 如果树枝端是子树：
5.1.1 画出子树
5.2 如果树枝端是叶子：
5.2.1 画出子树分支及属性值
5.2.2 画出叶子节点
'''
leaf_node = dict(boxstyle='round4', fc='0.8')
arrow_type = dict(arrowstyle='<-')
decision_node = dict(boxstyle='sawtooth', fc='0.8')
tree_w = get_num_leafs(tree)
tree_stump = list(tree.keys())[0]
child_tree = tree[tree_stump]
cntr_pos = (create_plot.xoff + (1 + tree_w) / 2 / create_plot.totalw,
create_plot.yoff)
plot_attr_value(cntr_pos, parent_pos, attr_value)
plot_node(tree_stump, parent_pos, cntr_pos, decision_node, arrow_type)
create_plot.yoff -= 1 / create_plot.totalh
for branch in child_tree.keys():
if type(child_tree[branch]).__name__ == 'dict':
plot_child_tree(child_tree[branch], cntr_pos, branch)
else:
create_plot.xoff += 1 / create_plot.totalw
plot_attr_value((create_plot.xoff, create_plot.yoff),
cntr_pos, branch)
plot_node(child_tree[branch], cntr_pos,
(create_plot.xoff, create_plot.yoff),
leaf_node, arrow_type)
create_plot.yoff += 1 / create_plot.totalh
其中获取树的叶子节点个数：
def get_num_leafs(tree):
'''
获取决策树的叶子数
1. 获取树的根节点
2. 对于连接根的每一个树枝：
2.1 如果树枝端是子树：
2.1.1 调用get_num_leafs返回子树的叶子数
2.2 如果树枝端是叶子：
2.2.1 返回1
3. 返回叶子数
'''
num_leafs = 0
root_node = list(tree.keys())[0]
child_tree = tree[root_node]
for brach in child_tree.keys():
if type(child_tree[brach]).__name__ == 'dict':
num_leafs += get_num_leafs(child_tree[brach])
else:
num_leafs += 1
return num_leafs
获取树的层数的代码如下
def get_num_layers(tree):
'''
获取决策树的层数
1. 获取树的根节点
2. 对于连接根的每一个树枝：
2.1 如果树枝端是子树：
2.1.1 分支层数 = 1 + 子树层数
2.2 如果树枝端是叶子：
2.2.1 分支层数 = 1
2.3 如果 分支层数 > 最大层数：保存为最大层数
3. 返回最大层数
'''
root_node = list(tree.keys())[0]
child_tree = tree[root_node]
max_layer = 0
for brach in child_tree.keys():
if type(child_tree[brach]).__name__ == 'dict':
branch_layers = 1 + get_num_layers(child_tree[brach])
else:
branch_layers = 1
if branch_layers > max_layer:
max_layer = branch_layers
return max_layer
3.2.2 绘制节点
要把树的节点绘制出来，依靠 annotate 函数
def plot_node(node_text, parentpt, cntrpt, node_type, arrow_type):
'''
画出节点图
'''
create_plot.ax1.annotate(node_text, xy=parentpt, xycoords='axes fraction',
xytext=cntrpt, textcoords='axes fraction',
ha='center', va='center',
bbox=node_type, arrowprops=arrow_type
)
# plt.pause(1)
绘制分支（有向边）的方法如下：
def plot_attr_value(child_pos, parent_pos, attr_value):
'''画出子树支及属性值
1. 求出父子节点的中间坐标
2. 在中间坐标写文本
'''
xmid = (child_pos[0] + parent_pos[0]) / 2
ymid = (child_pos[1] + parent_pos[1]) / 2
create_plot.ax1.text(xmid, ymid, attr_value)
# plt.pause(1)
3.2.3 绘制完整决策树
下面是绘制决策树的代码：
def create_plot(tree):
'''
画出完整决策树绘图
1. 创建绘图
2. 获取整棵树的宽、高
3. 绘制决策树
'''
fig = plt.figure(1, facecolor='white')
fig.clf()
axprops = dict(xticks=[], yticks=[])
create_plot.ax1 = plt.subplot(111, frameon=False, **axprops)
create_plot.totalw = get_num_leafs(tree)
create_plot.totalh = get_num_layers(tree)
create_plot.xoff = -0.5 / create_plot.totalw
create_plot.yoff = 1.0
plot_child_tree(tree, (0.5, 1.0), '')
plt.show()
3.3 测试和存储分类器
3.3.1 测试算法：使用决策树进行分类
依靠训练出的决策树，对新的数据进行分类
def classify(tree, feat_labels, test_inst):
'''分类测试实例
1. 获取树的根节点和分支，以及节点的标签索引
2. 对于连接根的每一个分支：
2.1 如果测试实例的属性值 == 分支值：
2.1.1 如果分支节点是子树：
测试实例类别 = 子树返回的类别
2.1.2 否则：
测试实例类别 = 叶子节点类别
3. 返回实例类别
'''
root_node = list(tree.keys())[0]
branchs = tree[root_node]
label_idx = feat_labels.index(root_node)
for branch in branchs:
if test_inst[label_idx] == branch:
if type(branchs[branch]).__name__ == 'dict':
test_label = classify(branchs[branch], feat_labels, test_inst)
else:
test_label = branchs[branch]
return test_label
3.3.2 决策树的存取
保存决策树：
def save_tree(tree, filename):
'''存储决策树
'''
with open(filename, 'w') as file_w:
pickle.dump(tree, file_w)
读取决策树：
def load_tree(filename):
'''读取决策树
'''
with open(filename) as file_l:
tree = pickle.load(file_l)
return tree
3.4 使用决策树进行预测
给测试数据分类：
def test_classify():
'''
用决策树给实例分类
返回：yes
'''
test_dataset, feat_labels = create_dataset()
test_labels = feat_labels[:]
tree = create_tree(test_dataset, test_labels)
test_inst = test_dataset[2][:-1]
test_label = classify(tree, feat_labels, test_inst)
print(test_label)
创建数据集：
def create_dataset():
'''
数据集
'''
# 分类属性
labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
dataset = [[0, 0, 0, 0, 'no'],
[0, 0, 0, 1, 'no'],
[0, 1, 0, 1, 'yes'],
[0, 1, 1, 0, 'yes'],
[0, 0, 0, 0, 'no'],
[1, 0, 0, 0, 'no'],
[1, 0, 0, 1, 'no'],
[1, 1, 1, 1, 'yes'],
[1, 0, 1, 2, 'yes'],
[1, 0, 1, 2, 'yes'],
[2, 0, 1, 2, 'yes'],
[2, 0, 1, 1, 'yes'],
[2, 1, 0, 1, 'yes'],
[2, 1, 0, 2, 'yes'],
[2, 0, 0, 0, 'no']]
# 返回数据集和分类属性
return dataset, labels
读取隐形眼镜数据：
def read_data(filepath):
'''
读取数据
'''
with open(filepath) as file_p:
dataset = [inst.strip().split('\t')
for inst in file_p.readlines()]
labels = ['age', 'prescript', 'astigmatic', 'tearRate']
return dataset, labels
绘制决策树：
def test_create_plot():
'''
绘制决策树
'''
dataset, labels = read_data('data.txt')
tree = create_tree(dataset, labels)
create_plot(tree)
if __name__ == '__main__':
test_create_plot()
其中 data.txt 为：
young myope no reduced no lenses
young myope no normal soft
young myope yes reduced no lenses
young myope yes normal hard
young hyper no reduced no lenses
young hyper no normal soft
young hyper yes reduced no lenses
young hyper yes normal hard
pre myope no reduced no lenses
pre myope no normal soft
pre myope yes reduced no lenses
pre myope yes normal hard
pre hyper no reduced no lenses
pre hyper no normal soft
pre hyper yes reduced no lenses
pre hyper yes normal no lenses
presbyopic myope no reduced no lenses
presbyopic myope no normal no lenses
presbyopic myope yes reduced no lenses
presbyopic myope yes normal hard
presbyopic hyper no reduced no lenses
presbyopic hyper no normal soft
presbyopic hyper yes reduced no lenses
presbyopic hyper yes normal no lenses