5.2 决策树¶

决策树是一种通过树形结构进行分类的方法。在决策树中，树形结构中每个节点表示对分类目标在属性上的一个判断，每个分支代表基于该属性做出的一个判断，最后树形结构中每个叶子结点代表一种分类结果。

5.2.1 决策树分类概念¶

数据: 游乐场经营者提供天气情况（如晴、雨、多云）、温度高低、湿度大小、风力强弱等气象特点以及游客当天是否前往游乐场。

目标: 预测游客是否来游乐场游玩。

序号	天气	温度（℃）	湿度	是否有风	是（1）否（0）前往游乐场
1	晴	29	85	否	0
2	晴	26	88	是	0
3	多云	28	78	否	1
4	雨	21	96	否	1
5	雨	20	80	否	1
6	雨	18	70	是	0
7	多云	18	65	是	1
8	晴	22	90	否	0
9	晴	21	68	否	1
10	雨	24	80	否	1
11	晴	24	63	是	1
12	多云	22	90	是	1
13	多云	27	75	否	1
14	雨	21	80	是	0

根据上表，绘制如图所示的决策树：

第一层是天气状况，具有雨、多云和晴三种属性取值。

多云: 样本子集是 { 3, 7, 12, 13 } ，仅有“前往游乐场游玩”一个类别，即肯定去游乐场。

晴: 样本子集是 { 1, 2, 8, 9, 11 }
- 湿度大于 75：样本子集为 { 1, 2, 8 }，不前往游乐场。
- 湿度不大于 75：样本子集 { 9, 11 }，前往游乐场。

雨：样本子集为 { 4, 5, 6, 10, 14 }
- 有风：样本子集 { 6, 14 },不去游乐场。
- 无风：样本子集 { 4, 5, 10 }，前往游乐场。

由上面的例子可以看到，构建决策树的过程就是：

选择一个属性值；
基于该属性对样本集进行划分；
重复步骤 1 和 2 直到最后所得划分结果中每个样本为同一类别。

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
%matplotlib inline

import math
from math import log
import warnings
warnings.filterwarnings("ignore")

# 原始数据
datasets = [
    ['晴',29,85,'否','0'],
    ['晴',26,88,'是','0'],
    ['多云',28,78,'否','1'],
    ['雨',21,96,'否','1'],
    ['雨',20,80,'否','1'],
    ['雨',18,70,'是','0'],
    ['多云',18,65,'是','1'],
    ['晴',22,90,'否','0'],
    ['晴',21,68,'否','1'],
    ['雨',24,80,'否','1'],
    ['晴',24,63,'是','1'],
    ['多云',22,90,'是','1'],
    ['多云',27,75,'否','1'],
    ['雨',21,80,'是','0']
]

# 数据的列名
labels = ['天气','温度','湿度','是否有风','是否前往游乐场']

# 将湿度大小分为大于 75 和小于等于 75 这两个属性值，
# 将温度大小分为大于 26 和小于等于 26 这两个属性值
for i in range(len(datasets)):
    if datasets[i][2] > 75:
        datasets[i][2] = '>75'
    else:
        datasets[i][2] = '<=75'
    if datasets[i][1] > 26:
        datasets[i][1] = '>26'
    else:
        datasets[i][1] = '<=26'

# 构建 dataframe 并查看数据
df = pd.DataFrame(datasets, columns=labels)
df

5.2.2 构建决策树¶

信息增益用来衡量样本集合复杂度（不确定性）所减少的程度。

信息熵用来度量信息量的大小。从信息论的角度来看，对信息的度量等于计算信息不确定性的多少。

假设有 $K$ 个信息，其组成了集合样本 $D$ ，记第 $k$ 个信息发生的概率为$P_k(1≤k≤K)$。
这 $K$ 个信息的信息熵：
$$E(D)=-\sum_{k=1}^{K}p_k log_{2} p_k$$

需要指出：所有 $p_k$ 累加起来的和为1。

def calc_entropy(total_num, count_dict):
    """
    计算信息熵
    :param total_num: 总样本数
    :param count_dict: 每类样本及其对应数目的字典
    :return: 信息熵
    """
    # 使用信息熵公式计算
    ent = -sum([(p / total_num) * log(p / total_num, 2) for p in count_dict.values() if p != 0])
    # 避免 print 显示异常
    if ent == 0:
        ent = 0
    # 返回信息熵，精确到小数点后 4 位
    return round(ent, 4)

现在用熵来构建决策树。数据中 14 个样本分为 “游客来游乐场（ 9 个样本）” 和 “游客不来游乐场（ 5 个样本）” 两个类别，即 K = 2。

记 “游客来游乐场” 和 “游客不来游乐场” 的概率分别为 $p_1$ 和 $p_2$ ,显然 $p_1=\frac{9}{14}$，$p_1=\frac{5}{14}$，则这 14 个样本所蕴含的信息熵：

$$E(D)=-\sum_{k=1}^{2}p_{k}log_{2}{p_k}=-(\frac{9}{14}×log_{2}{\frac{9}{14}}+\frac{5}{14}×log_{2}{\frac{5}{14}})=0.940$$

我们可以用下面这种方式对 daraframe 的数据按条件进行筛选。

# 例如：按 是否前往游乐场==0 进行筛选
df[df['是否前往游乐场']=='0']

使用上面的方法，可以得到计算信息熵所需的总样本数，以及每类样本及其对应数目的字典，然后计算信息熵。

# 总样本数
total_num = df.shape[0]
# 每类样本及其对应数目的字典
count_dict = {'前往':df[df['是否前往游乐场']=='1'].shape[0], '不前往':df[df['是否前往游乐场']=='1'].shape[1]}
# 计算信息熵
entropy = calc_entropy(total_num, count_dict)
entropy

0.9403

计算天气状况所对应的信息熵：
天气状况的三个属性记为 $a_0=“晴”$ ，$a_1=“多云”$ ，$a_2=“雨”$ ，
属性取值为 $a_i$ 对应分支节点所包含子样本集记为 $D_i$ ,该子样本集包含样本数量记为 $|D_i|$ 。

天气属性取值$a_i$	“晴”	“多云”	“雨”
对应样本数$	D_i	$	5	4	5
正负样本数量	（2+，3-）	（4+，0-）	（3+，2-）

计算天气状况每个属性值的信息熵：

$“晴”：E(D_0)=-(\frac{2}{5}×log_{2}{\frac{2}{5}}+\frac{3}{5}×log_{2}{\frac{3}{5}})=0.971$

$“多云”：E(D_1)=-(\frac{4}{4}×log_{2}{\frac{4}{4}})=0$

$“雨”：E(D_2)=-(\frac{3}{5}×log_{2}{\frac{3}{5}}+\frac{2}{5}×log_{2}{\frac{2}{5}})=0.971$

我们可以使用下面的写法，对 dataframe 进行多个条件的筛选。

# 筛选出 天气为晴并且去游乐场的样本数据
df[(df['天气']=='晴') & (df['是否前往游乐场']=='1')]

# 天气为晴的总天数
total_num_sun = df[df['天气']=='晴'].shape[0]
# 天气为晴时，去游乐场和不去游乐场的人数
count_dict_sun = {'前往':df[(df['天气']=='晴') & (df['是否前往游乐场']=='1')].shape[0], 
              '不前往':df[(df['天气']=='晴') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_sun)
# 计算天气-晴 的信息熵
ent_sun = calc_entropy(total_num_sun, count_dict_sun)
print('天气-晴 的信息熵为：%s' % ent_sun)

{'不前往': 3, '前往': 2}
天气-晴 的信息熵为：0.971

# 天气为多云的总天数
total_num_cloud = df[df['天气']=='多云'].shape[0]
# 天气为多云时，去游乐场和不去游乐场的人数
count_dict_cloud = {'前往':df[(df['天气']=='多云') & (df['是否前往游乐场']=='1')].shape[0], 
              '不前往':df[(df['天气']=='多云') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_cloud)
# 计算天气-多云 的信息熵
ent_cloud = calc_entropy(total_num_cloud, count_dict_cloud)
print('天气-多云 的信息熵为：%s' % ent_cloud)

{'不前往': 0, '前往': 4}
天气-多云 的信息熵为：0

# 天气为雨的总天数
total_num_rain = df[df['天气']=='雨'].shape[0]
# 天气为雨时，去游乐场和不去游乐场的人数
count_dict_rain = {'前往':df[(df['天气']=='雨') & (df['是否前往游乐场']=='1')].shape[0], 
              '不前往':df[(df['天气']=='雨') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_rain)
# 计算天气-雨 的信息熵
ent_rain = calc_entropy(total_num_rain, count_dict_rain)
print('天气-雨 的信息熵为：%s' % ent_rain)

{'不前往': 2, '前往': 3}
天气-雨 的信息熵为：0.971

计算天气状况的信息增益:
$$Gain(D,A)=E(D)-\sum_{i}^{n}\frac{|D_i|}{D}E(D)$$

其中，$A=“天气状况”$。于是天气状况这一气象特点的信息增益为： $$Gain(D,天气)=0.940-（\frac{5}{14}×0.971+\frac{4}{14}×0+\frac{5}{14}×0.971）=0.246$$

同理可以计算温度高低、湿度大小、风力强弱三个气象特点的信息增益。
通常情况下，某个分支的信息增益越大，则该分支对样本集划分所获得的“纯度”越大，信息不确定性减少的程度越大。

假设有 $K$ 个信息，其组成了集合样本 $D$ ，记第 $k$ 个信息发生的概率为$P_k(1≤k≤K)$。
这 $K$ 个信息的信息熵：
$$E(D)=-\sum_{k=1}^{K}p_k log_{2} p_k$$

需要指出：所有 $p_k$ 累加起来的和为1。

使用上面的公式计算信息增益。

# 信息增益
gain = entropy - (total_num_sun/total_num*ent_sun + 
                  total_num_cloud/total_num*ent_cloud + 
                  total_num_rain/total_num*ent_rain)
gain

0.2467285714285714

思考与练习¶

分别将天气状况、温度高低、湿度大小、风力强弱作为分支点来构建决策树，查看信息增益

# 温度 >26 的信息熵
total_num_temp_high = df[df['温度']=='>26'].shape[0]
count_dict_temp_high = {'前往':df[(df['温度']=='>26') & (df['是否前往游乐场']=='1')].shape[0], 
                   '不前往':df[(df['温度']=='>26') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_temp_high)
ent_temp_high = calc_entropy(total_num_temp_high, count_dict_temp_high)
print('温度 >26 的信息熵为：%s' % ent_temp_high)

# 温度 <=26 的信息熵
total_num_temp_low = df[df['温度']=='<=26'].shape[0]
count_dict_temp_low = {'前往':df[(df['温度']=='<=26') & (df['是否前往游乐场']=='1')].shape[0], 
                     '不前往':df[(df['温度']=='<=26') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_temp_low)
ent_temp_low = calc_entropy(total_num_temp_low, count_dict_temp_low)
print('温度 <=26 的信息熵为：%s' % ent_temp_low)

# 如果按照温度高低进行划分，则对应的信息增益为
gain = entropy - (total_num_temp_high/total_num*ent_temp_high + 
                  total_num_temp_low/total_num*ent_temp_low)
print('按照温度高低进行划分的信息增益为：%s' % gain)

{'不前往': 1, '前往': 2}
温度 >26 的信息熵为：0.9183
{'不前往': 4, '前往': 7}
温度 <=26 的信息熵为：0.9457
按照温度高低进行划分的信息增益为：0.0004714285714285671

# 湿度 >75 的信息熵
total_num_hum_high = df[df['湿度']=='>75'].shape[0]
count_dict_hum_high = {'前往':df[(df['湿度']=='>75') & (df['是否前往游乐场']=='1')].shape[0], 
                   '不前往':df[(df['湿度']=='>75') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_hum_high)
ent_hum_high = calc_entropy(total_num_hum_high, count_dict_hum_high)
print('湿度 >75 的信息熵为：%s' % ent_hum_high)

# 湿度 <=75 的信息熵
total_num_hum_low = df[df['湿度']=='<=75'].shape[0]
count_dict_hum_low = {'前往':df[(df['湿度']=='<=75') & (df['是否前往游乐场']=='1')].shape[0], 
                     '不前往':df[(df['湿度']=='<=75') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_hum_low)
ent_hum_low = calc_entropy(total_num_hum_low, count_dict_hum_low)
print('湿度 <=75 的信息熵为：%s' % ent_hum_low)

# 如果按照湿度高低进行划分，则对应的信息增益为
gain = entropy - (total_num_hum_high/total_num*ent_hum_high + 
                  total_num_hum_low/total_num*ent_hum_low)
print('按照湿度高低进行划分的信息增益为：%s' % gain)

{'不前往': 4, '前往': 5}
湿度 >75 的信息熵为：0.9911
{'不前往': 1, '前往': 4}
湿度 <=75 的信息熵为：0.7219
按照湿度高低进行划分的信息增益为：0.04534285714285702

# 有风 的信息熵
total_num_wind = df[df['是否有风']=='是'].shape[0]
count_dict_wind = {'前往':df[(df['是否有风']=='是') & (df['是否前往游乐场']=='1')].shape[0], 
              '不前往':df[(df['是否有风']=='是') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_wind)
ent_wind = calc_entropy(total_num_wind, count_dict_wind)
print('有风 的信息熵为：%s' % ent_wind)

# 无风 的信息熵
total_num_nowind = df[df['是否有风']=='否'].shape[0]
count_dict_nowind = {'前往':df[(df['是否有风']=='否') & (df['是否前往游乐场']=='1')].shape[0], 
              '不前往':df[(df['是否有风']=='否') & (df['是否前往游乐场']=='0')].shape[0]}
print(count_dict_nowind)
ent_nowind = calc_entropy(total_num_nowind, count_dict_nowind)
print('无风 的信息熵为：%s' % ent_nowind)

# 如果按照是否有风进行划分，则对应的信息增益为
gain = entropy - (total_num_wind/total_num*ent_wind + 
                  total_num_nowind/total_num*ent_nowind)
print('按照是否有风进行划分的信息增益为：%s' % gain)

{'不前往': 3, '前往': 3}
有风 的信息熵为：1.0
{'不前往': 2, '前往': 6}
无风 的信息熵为：0.8113
按照是否有风进行划分的信息增益为：0.04812857142857141

每朵鸢尾花有萼片长度、萼片宽度、花瓣长度、花瓣宽度四个特征。现在需要根据这四个特征将鸢尾花分为杂色鸢尾花、维吉尼亚鸢尾和山鸢尾三类，试构造决策树进行分类。

序号	萼片长度	萼片宽度	花瓣长度	花瓣宽度	种类
1	5.0	2.0	3.5	1.0	杂色鸢尾
2	6.0	2.2	5.0	1.5	维吉尼亚鸢尾
3	6.0	2.2	4.0	1.0	杂色鸢尾
4	6.2	2.2	4.5	1.5	杂色鸢尾
5	4.5	2.3	1.3	0.3	山鸢尾

观察上表中的五笔数据，我们可以看到杂色鸢尾和维吉尼亚鸢尾的花瓣宽度明显大于山鸢尾，所以可以通过判断花瓣宽度是否大于 0.7，来将山鸢尾区从其他两种鸢尾中区分出来。

同时，杂色鸢尾和维吉尼亚鸢尾的花瓣长度明显大于山鸢尾，所以也可以通过判断花瓣长度是否大于 2.4，来将山鸢尾区从其他两种鸢尾中区分出来。

然后我们观察到维吉尼亚鸢尾的花瓣长度明显大于杂色鸢尾，所以可以通过判断花瓣长度是否大于 4.75，来将杂色鸢尾和维吉尼亚鸢尾区分出来。

实际上是否如此呢？

上面的表格只是 Iris 数据集的一小部分，完整的数据集包含 150 个数据样本，分为 3 类，每类 50 个数据，每个数据包含 4 个属性。即花萼长度，花萼宽度，花瓣长度，花瓣宽度4个属性。

我们使用 sklearn 工具包来构建决策树模型，先导入数据集。

from sklearn.datasets import load_iris
# 加载数据集
iris = load_iris()
# 查看 label
print(list(iris.target_names))
# 查看 feature
print(iris.feature_names)

['setosa', 'versicolor', 'virginica']
['sepal length (cm)', 'sepal width (cm)', 'petal length (cm)', 'petal width (cm)']

setosa 是山鸢尾，versicolor是杂色鸢尾，virginica是维吉尼亚鸢尾。

sepal length， sepal width，petal length，petal width 分别是萼片长度，萼片宽度，花瓣长度，花瓣宽度。

然后进行训练集和测试集的切分。

from sklearn.model_selection import train_test_split
# 载入数据
X, y = load_iris(return_X_y=True)
# 切分训练集合测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.33, random_state=42)

接下来，我们在训练集数据上训练决策树模型。

from sklearn import tree
from sklearn.tree import DecisionTreeClassifier
# 初始化模型，可以调整 max_depth 来观察模型的表现
clf = tree.DecisionTreeClassifier(random_state=42, max_depth=2)
# 训练模型
clf = clf.fit(X_train, y_train)

我们可以使用 graphviz 包来展示构建好的决策树。

pip install graphviz

WARNING: The directory '/home/jovyan/.cache/pip/http' or its parent directory is not owned by the current user and the cache has been disabled. Please check the permissions and owner of that directory. If executing pip with sudo, you may want sudo's -H flag.
WARNING: The directory '/home/jovyan/.cache/pip' or its parent directory is not owned by the current user and caching wheels has been disabled. check the permissions and owner of that directory. If executing pip with sudo, you may want sudo's -H flag.
Looking in indexes: https://mirrors.ustc.edu.cn/pypi/web/simple
Collecting graphviz
  Downloading https://mirrors.tuna.tsinghua.edu.cn/pypi/web/packages/f5/74/dbed754c0abd63768d3a7a7b472da35b08ac442cf87d73d5850a6f32391e/graphviz-0.13.2-py2.py3-none-any.whl
Installing collected packages: graphviz
Successfully installed graphviz-0.13.2
WARNING: You are using pip version 19.1.1, however version 19.3.1 is available.
You should consider upgrading via the 'pip install --upgrade pip' command.
Note: you may need to restart the kernel to use updated packages.

import graphviz
feature_names = ['萼片长度','萼片宽度','花瓣长度','花瓣宽度']
target_names = ['山鸢尾', '杂色鸢尾', '维吉尼亚鸢尾']
# 可视化生成的决策树
dot_data = tree.export_graphviz(clf, out_file=None, 
                     feature_names=feature_names,  
                     class_names=target_names,  
                     filled=True, rounded=True,  
                     special_characters=True)  
graph = graphviz.Source(dot_data)  
graph

我们看模型在测试集上的表现

from sklearn.metrics import accuracy_score
y_test_predict = clf.predict(X_test)
accuracy_score(y_test,y_test_predict)

0.98

实践与体验¶

计算文章的信息熵

收集中英文对照的短文，在计算短文内中文单词和英文单词出现概率基础上，计算该两篇短文的信息熵，比较中文短文信息熵和英文短文信息熵的大小。

首先定义一个方法来辅助读取文件的内容。

def read_file(path):
    """
    读取某文件的内容
    :param path: 文件的路径
    :return: 文件的内容
    """
    contents = ""
    with open(path) as f:
        # 读取每一行的内容
        for line in f.readlines():
            contents += line
    return contents

使用上面定义的方法读取英文短文及其对应的中文短文。

# 读取英文短文
en_essay = read_file('essay3_en.txt')
# 读取中文短文
ch_essay = read_file('essay3_ch.txt')

处理文本，统计单词出现的概率，并计算信息熵。

from collections import Counter
import re


def cal_essay_entropy(essay, split_by=None):
    """
    计算文章的信息熵
    :param essay: 文章内容
    :param split_by: 切分方式，对于中文文章，不需传入，按字符切分，
                     对于英文文章，需传入空格字符来进行切分
    :return: 文章的信息熵
    """
    # 把英文全部转为小写
    essay = essay.lower()
    # 去除标点符号
    essay = re.sub(
        "[\f+\n+\r+\t+\v+\?\.\!\/_,$%^*(+\"\']+|[+——！，。？、~@#《》￥%……&*（）]", "",
        essay)
    # print(essay)
    # 把文本分割为词
    if split_by:
        word_list = essay.split(split_by)
    else:
        word_list = list(essay)
    # 统计总的单词数
    word_number = len(word_list)
    print('此文章共有 %s 个单词' % word_number)
    # 得到每个单词出现的次数
    word_counter = Counter(word_list)
    # print('每个单词出现的次数为：%s' % word_counter)
    # 使用信息熵公式计算信息熵
    ent = -sum([(p / word_number) * log(p / word_number, 2) for p in
                word_counter.values()])
    print('信息熵为：%.2f' % ent)
    return ent

ent = cal_essay_entropy(ch_essay)

此文章共有 1232 个单词
信息熵为：8.05

ent = cal_essay_entropy(en_essay, split_by = ' ')

此文章共有 652 个单词
信息熵为：7.77

	天气	温度	湿度	是否有风	是否前往游乐场
0	晴	>26	>75	否	0
1	晴	<=26	>75	是	0
2	多云	>26	>75	否	1
3	雨	<=26	>75	否	1
4	雨	<=26	>75	否	1
5	雨	<=26	<=75	是	0
6	多云	<=26	<=75	是	1
7	晴	<=26	>75	否	0
8	晴	<=26	<=75	否	1
9	雨	<=26	>75	否	1
10	晴	<=26	<=75	是	1
11	多云	<=26	>75	是	1
12	多云	>26	<=75	否	1
13	雨	<=26	>75	是	0

52 决策树.ipynb @736a5b8 — view markup · raw · history · blame

5.2 决策树¶

5.2.1 决策树分类概念¶

5.2.2 构建决策树¶

思考与练习¶

实践与体验¶