## 一、基于ID3算法手动构建决策树，并通过Matplotlib进行可视化

\begin{aligned} & Gain(D, 年龄) = 0.083 \\ & Gain(D, 工作)=0.324 \\ & Gain(D, 房子)=0.420 \\ & Gain(D, 信用)=0.363 \end{aligned}

\begin{aligned} & Gain(D_1, 年龄) = 0.251 \\ & Gain(D_1, 工作)=0.918 \\ & Gain(D_1, 信用)=0.474 \end{aligned}

{"房子": {
"1": "Y",
"0"：{"工作": {
"1": "Y",
"0": "N"
}}
}}

"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建训数据集
"""
def establish_data():
data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息，前面几项代表属性特征，最后一项表示是否放款
[0, 0, 0, 1, 'N'],
[0, 1, 0, 1, 'Y'],
[0, 1, 1, 0, 'Y'],
[0, 0, 0, 0, 'N'],
[1, 0, 0, 0, 'N'],
[1, 0, 0, 1, 'N'],
[1, 1, 1, 1, 'Y'],
[1, 0, 1, 2, 'Y'],
[1, 0, 1, 2, 'Y'],
[2, 0, 1, 2, 'Y'],
[2, 0, 1, 1, 'Y'],
[2, 1, 0, 1, 'Y'],
[2, 1, 0, 2, 'Y'],
[2, 0, 0, 0, 'N']]
labels = ["年纪", "工作", "房子", "信用"]
return np.array(data), labels

"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：找出对应属性特征值的样本，比如找出所有年纪为青年的样本数据集
"""
def handle_data(data, axis, value):
result_data = list()
for item in data:
if item[axis] == value:
reduced_data = item[: axis].tolist()
reduced_data.extend(item[axis + 1:])
result_data.append(reduced_data)
return result_data

"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建决策树
"""
def establish_decision_tree(data, labels, feat_labels):
cat_list = [item[-1] for item in data]
if (cat_list.count(cat_list[0]) == len(cat_list)): return cat_list[0]   # 数据集中的类别只有一种
best_feature_index = calc_information_gain(data)    # 通过信息增益优先选取最好的属性特征
best_label = labels[best_feature_index]   # 属性特征对应的标签内容
# feat_labels表示已选取的属性；新建一个决策树节点；将属性标签列表中删除已选取的属性
feat_labels.append(best_label); decision_tree = {best_label: dict()}; del(labels[best_feature_index])
feature_values = [item[best_feature_index] for item in data]
unique_values = set(feature_values)      # 获取最优属性对应值的set集合
for value in unique_values:
sub_label = labels[:]
decision_tree[best_label][value] = establish_decision_tree(np.array(handle_data(data, best_feature_index, value)), sub_label, feat_labels)
return decision_tree

import numpy as np
import pandas as pd
np.__version__
pd.__version__
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建训数据集
"""
def establish_data():
data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息，前面几项代表属性特征，最后一项表示是否放款
[0, 0, 0, 1, 'N'],
[0, 1, 0, 1, 'Y'],
[0, 1, 1, 0, 'Y'],
[0, 0, 0, 0, 'N'],
[1, 0, 0, 0, 'N'],
[1, 0, 0, 1, 'N'],
[1, 1, 1, 1, 'Y'],
[1, 0, 1, 2, 'Y'],
[1, 0, 1, 2, 'Y'],
[2, 0, 1, 2, 'Y'],
[2, 0, 1, 1, 'Y'],
[2, 1, 0, 1, 'Y'],
[2, 1, 0, 2, 'Y'],
[2, 0, 0, 0, 'N']]
labels = ["年纪", "工作", "房子", "信用"]
return np.array(data), labels
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：计算信息熵
"""
def calc_information_entropy(data):
data_number, _ = data.shape
information_entropy = 0
for item in pd.DataFrame(data).groupby(_ - 1):
proportion = item[1].shape[0] / data_number
information_entropy += - proportion * np.log2(proportion)
return information_entropy
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：找出对应属性特征值的样本，比如找出所有年纪为青年的样本数据集
"""
def handle_data(data, axis, value):
result_data = list()
for item in data:
if item[axis] == value:
reduced_data = item[: axis].tolist()
reduced_data.extend(item[axis + 1:])
result_data.append(reduced_data)
return result_data
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：计算最大的信息增益，并输出其所对应的特征索引
"""
def calc_information_gain(data):
feature_number = data.shape[1] - 1                    # 属性特征的数量
base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和对应的特征索引
for index in range(feature_number):
feat_list = [item[index] for item in data]
feat_set = set(feat_list)
new_entropy = 0.0
for set_item in feat_set:                         # 计算属性特征划分后的信息增益
sub_data = handle_data(data, index, set_item)
proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
new_entropy += proportion * calc_information_entropy(np.array(sub_data))
temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
print("第%d个属性特征所对应的的增益为%.3f" % (index + 1, temp_information_gain))            # 输出每个特征的信息增益
if (temp_information_gain > max_information_gain):
max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益，确定的最大的信息增益对应的索引
return best_feature
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建决策树
"""
def establish_decision_tree(data, labels, feat_labels):
cat_list = [item[-1] for item in data]
if (cat_list.count(cat_list[0]) == len(cat_list)): return cat_list[0]   # 数据集中的类别只有一种
best_feature_index = calc_information_gain(data)    # 通过信息增益优先选取最好的属性特征
best_label = labels[best_feature_index]   # 属性特征对应的标签内容
# feat_labels表示已选取的属性；新建一个决策树节点；将属性标签列表中删除已选取的属性
feat_labels.append(best_label); decision_tree = {best_label: dict()}; del(labels[best_feature_index])
feature_values = [item[best_feature_index] for item in data]
unique_values = set(feature_values)      # 获取最优属性对应值的set集合
for value in unique_values:
sub_label = labels[:]
decision_tree[best_label][value] = establish_decision_tree(np.array(handle_data(data, best_feature_index, value)), sub_label, feat_labels)
return decision_tree
if __name__ == "__main__":
data, labels = establish_data()
print(establish_decision_tree(data, labels, list()))

{'房子': {'1': 'Y', '0': {'工作': {'1': 'Y', '0': 'N'}}}}

import numpy as np
import pandas as pd
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建训数据集
"""
def establish_data():
data = [[0, 0, 0, 0, 'N'],         # 样本数据集相关信息，前面几项代表属性特征，最后一项表示是否放款
[0, 0, 0, 1, 'N'],
[0, 1, 0, 1, 'Y'],
[0, 1, 1, 0, 'Y'],
[0, 0, 0, 0, 'N'],
[1, 0, 0, 0, 'N'],
[1, 0, 0, 1, 'N'],
[1, 1, 1, 1, 'Y'],
[1, 0, 1, 2, 'Y'],
[1, 0, 1, 2, 'Y'],
[2, 0, 1, 2, 'Y'],
[2, 0, 1, 1, 'Y'],
[2, 1, 0, 1, 'Y'],
[2, 1, 0, 2, 'Y'],
[2, 0, 0, 0, 'N']]
labels = ["年纪", "工作", "房子", "信用"]
return np.array(data), labels
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：计算信息熵
"""
def calc_information_entropy(data):
data_number, _ = data.shape
information_entropy = 0
for item in pd.DataFrame(data).groupby(_ - 1):
proportion = item[1].shape[0] / data_number
information_entropy += - proportion * np.log2(proportion)
return information_entropy
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：找出对应属性特征值的样本，比如找出所有年纪为青年的样本数据集
"""
def handle_data(data, axis, value):
result_data = list()
for item in data:
if item[axis] == value:
reduced_data = item[: axis].tolist()
reduced_data.extend(item[axis + 1:])
result_data.append(reduced_data)
return result_data
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：计算最大的信息增益，并输出其所对应的特征索引
"""
def calc_information_gain(data):
feature_number = data.shape[1] - 1                    # 属性特征的数量
base_entropy = calc_information_entropy(data)                 # 计算总体数据集的信息熵
max_information_gain, best_feature = 0.0, -1                 # 初始化最大信息增益和对应的特征索引
for index in range(feature_number):
feat_list = [item[index] for item in data]
feat_set = set(feat_list)
new_entropy = 0.0
for set_item in feat_set:                         # 计算属性特征划分后的信息增益
sub_data = handle_data(data, index, set_item)
proportion = len(sub_data) / float(data.shape[0])           # 计算子集的比例
new_entropy += proportion * calc_information_entropy(np.array(sub_data))
temp_information_gain = base_entropy - new_entropy                     # 计算信息增益
print("第%d个属性特征所对应的的增益为%.3f" % (index + 1, temp_information_gain))            # 输出每个特征的信息增益
if (temp_information_gain > max_information_gain):
max_information_gain, best_feature = temp_information_gain, index       # 更新信息增益，确定的最大的信息增益对应的索引
return best_feature
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建决策树
"""
def establish_decision_tree(data, labels, feat_labels):
cat_list = [item[-1] for item in data]
if (cat_list.count(cat_list[0]) == len(cat_list)): return cat_list[0]   # 数据集中的类别只有一种
best_feature_index = calc_information_gain(data)    # 通过信息增益优先选取最好的属性特征
best_label = labels[best_feature_index]   # 属性特征对应的标签内容
# feat_labels表示已选取的属性；新建一个决策树节点；将属性标签列表中删除已选取的属性
feat_labels.append(best_label); decision_tree = {best_label: dict()}; del(labels[best_feature_index])
feature_values = [item[best_feature_index] for item in data]
unique_values = set(feature_values)      # 获取最优属性对应值的set集合
for value in unique_values:
sub_label = labels[:]
decision_tree[best_label][value] = establish_decision_tree(np.array(handle_data(data, best_feature_index, value)), sub_label, feat_labels)
return decision_tree
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：统计决策树当中的叶子节点数目，以及决策树的深度
"""
def get_leaf_number_and_tree_depth(decision_tree):
leaf_number, first_key, tree_depth = 0, next(iter(decision_tree)), 0; second_dict = decision_tree[first_key]
for key in second_dict.keys():
if type(second_dict.get(key)).__name__ == "dict":
temp_number, temp_depth = get_leaf_number_and_tree_depth(second_dict[key])
leaf_number, curr_depth = leaf_number + temp_number, 1 + temp_depth
else: leaf_number += 1; curr_depth = 1
if curr_depth > tree_depth: tree_depth = curr_depth
return leaf_number, tree_depth
from matplotlib.font_manager import FontProperties
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：绘制节点
"""
def plot_node(node_text, center_pt, parent_pt, node_type):
arrow_args = dict(arrowstyle = "<-")
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)    # 设置字体
create_plot.ax1.annotate(node_text, xy=parent_pt,  xycoords='axes fraction',
xytext=center_pt, textcoords='axes fraction',
va="center", ha="center", bbox=node_type, arrowprops=arrow_args, FontProperties=font)
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：标注有向边的值
"""
def tag_text(cntr_pt, parent_pt, node_text):
x_mid = (parent_pt[0] - cntr_pt[0]) / 2.0 + cntr_pt[0]
y_mid = (parent_pt[1] - cntr_pt[1]) / 2.0 + cntr_pt[1]
create_plot.ax1.text(x_mid, y_mid, node_text, va="center", ha="center", rotation=30)
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：绘制决策树
"""
def plot_tree(decision_tree, parent_pt, node_text):
decision_node = dict(boxstyle="sawtooth", fc="0.8")
leaf_node = dict(boxstyle = "round4", fc = "0.8")
leaf_number, tree_depth = get_leaf_number_and_tree_depth(decision_tree)
first_key = next(iter(decision_tree))
cntr_pt = (plot_tree.xOff + (1.0 + float(leaf_number)) / 2.0 / plot_tree.totalW, plot_tree.yOff)
tag_text(cntr_pt, parent_pt, node_text); plot_node(first_key, cntr_pt, parent_pt, decision_node)
second_dict = decision_tree[first_key]
plot_tree.yOff = plot_tree.yOff - 1.0 / plot_tree.totalD
for key in second_dict.keys():
if type(second_dict[key]).__name__ == 'dict': plot_tree(second_dict[key], cntr_pt, str(key))
else:
plot_tree.xOff = plot_tree.xOff + 1.0 / plot_tree.totalW
plot_node(second_dict[key], (plot_tree.xOff, plot_tree.yOff), cntr_pt, leaf_node)
tag_text((plot_tree.xOff, plot_tree.yOff), cntr_pt, str(key))
plot_tree.yOff = plot_tree.yOff + 1.0 / plot_tree.totalD
from matplotlib import pyplot as plt
"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：创建决策树
"""
def create_plot(in_tree):
fig = plt.figure(1, facecolor = "white")
fig.clf()
axprops = dict(xticks = [], yticks = [])
create_plot.ax1 = plt.subplot(111, frameon = False, **axprops)
leaf_number, tree_depth = get_leaf_number_and_tree_depth(in_tree)
plot_tree.totalW, plot_tree.totalD = float(leaf_number), float(tree_depth)
plot_tree.xOff = -0.5 / plot_tree.totalW; plot_tree.yOff = 1.0
plot_tree(in_tree, (0.5,1.0), '')
plt.show()

if __name__ == "__main__":
data, labels = establish_data()
decision_tree = establish_decision_tree(data, labels, list())
print(decision_tree)
print("决策树的叶子节点数和深度：", get_leaf_number_and_tree_depth(decision_tree))
create_plot(decision_tree)

get_leaf_number_and_tree_depth 主要用于统计决策树当中的叶子节点数目，以及决策树的深度。选取 key 对应的 value ，判断 value 是否为一个字典类型，否的话说明是一个叶子节点，是的话说明非叶子节点，不同情况做不同处理
plot_node 方法用于绘制节点，这里设置了font类型是在windows下的，如果是linux则需要额外设置
tag_text 用于标注有向边的属性值，在这里主要是用1和0来进行标注，1代表对属性的肯定，0表示否定
plot_tree 遍历绘制决策树，在这里需要调用前面所定义的几个方法

## 二、基于已经构建好的决策树进行分类预测

"""
Author: Taoye
微信公众号: 玩世不恭的Coder
Explain：通过决策树模型对测试数据进行分类
"""
def classify(decision_tree, best_feature_labels, test_data):
first_node = next(iter(decision_tree))
second_dict = decision_tree[first_node]
feat_index = best_feature_labels.index(first_node)
for key in second_dict.keys():
if int(test_data[feat_index]) == int(key):
if type(second_dict[key]).__name__ == "dict":   # 为字典说明还没到叶子节点
result_label = classify(second_dict[key], best_feature_labels, test_data)
else: result_label = second_dict[key]
return result_label

## 三、构建好的决策树模型应当如何保存和读取？

import pickle
with open("DecisionTreeModel.txt", "wb") as f:
pickle.dump(decision_tree, f)           # 保存决策树模型
f = open("DecisionTreeModel.txt", "rb")
decision_tree = pickle.load(f)             # 加载决策树模型

## 四、通过鸢尾花（Iris）数据集，使用Sklearn构建决策树

criterion ：属性选取的标准，默认采用的是 gini ，也可以自行选择 entropygini 是基尼值， entropy 是信息熵，这两个我们在上篇文章中已经讲到过了
splitter ：特征划分节点的选择标准，默认是best，可以设置为random。默认的”best”适合样本量不大的时候，而如果样本数据量非常大，此时决策树构建推荐”random”。
max_depth ：决策树最大深度，默认是None。 需要注意一点的是，该深度是不包含根节点的。 一般来说，数据少或者特征少的时候可以不管这个值。如果模型样本量多，特征也多的情况下，推荐限制这个最大深度，具体的取值取决于数据的分布。
max_features ：划分时考虑的最大特征数，默认是None。一般来说，如果样本特征数不多，比如小于50，我们用默认的”None”就可以了，如果特征数非常多，我们可以灵活使用其他取值来控制划分时考虑的最大特征数，以控制决策树的生成时间。用到的时候查看下文档即可。
min_samples_split ：内部节点再划分所需最小样本数，默认为2。意思就是说，比如我们某个属性对应样本数目小于 min_samples_split ，即使它满足优先选取条件，依然会被剔除掉。
min_samples_leaf ：叶子节点最少样本数，默认是1。这个 值限制了叶子节点最少的样本数，如果某叶子节点数目小于样本数，则会和兄弟节点一起被剪枝。叶结点需要最少的样本数，也就是最后到叶结点，需要多少个样本才能算一个叶结点 。如果设置为1，哪怕这个类别只有1个样本，决策树也会构建出来。
max_leaf_nodes ：最大叶子节点数，默认是None。通过限制最大叶子节点数，可以防止过拟合。如果加了限制，算法会建立在最大叶子节点数内最优的决策树。如果特征不多，可以不考虑这个值，但是如果特征分成多的话，可以加以限制，具体的值可以通过交叉验证得到。
random_state ：随机数种子，默认是None。如果没有设置随机数，随机出来的数与当前系统时间有关，每个时刻都是不同的。如果设置了随机数种子，那幺相同随机数种子，不同时刻产生的随机数也是相同的。

import numpy as np
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeClassifier, plot_tree
class IrisDecisionTree:
"""
Explain：属性的初始化
Parameters:
n_classes： 鸢尾花的类别数
plot_colors: 不同类别花的颜色
plot_step： meshgrid网格的步长
"""
def __init__(self, n_classes, plot_colors, plot_step):
self.n_classes = n_classes
self.plot_colors = plot_colors
self.plot_step = plot_step

"""
"""
def establish_data(self):
return iris_info.data, iris_info.target, iris_info.feature_names, iris_info.target_names

"""
Explain：分类的可视化
"""
def show_result(self, x_data, y_label, feature_names, target_names):
# 选取两个属性来构建决策树，以方便可视化，其中列表内部元素代表属性对应的索引
for index, pair in enumerate([[0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, 3]]):
sub_x_data, sub_y_label = x_data[:, pair], y_label
clf = DecisionTreeClassifier().fit(sub_x_data, sub_y_label)   # 选取两个属性构建决策树
plt.subplot(2, 3, index + 1)
x_min, x_max = sub_x_data[:, 0].min() - 1, sub_x_data[:, 0].max() + 1   # 第一个属性
y_min, y_max = sub_x_data[:, 1].min() - 1, sub_x_data[:, 1].max() + 1   # 第二个属性
xx, yy = np.meshgrid(np.arange(x_min, x_max, self.plot_step), np.arange(y_min, y_max, self.plot_step))
Z = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)    # 预测meshgrid内部每个元素的分类
cs = plt.contourf(xx, yy, Z, cmap = plt.cm.RdYlBu)   # 绘制带有颜色的网格图
plt.xlabel(feature_names[pair[0]]); plt.ylabel(feature_names[pair[1]])     # 标注坐标轴标签
for i, color in zip(range(self.n_classes), self.plot_colors):
idx = np.where(sub_y_label == i)
plt.scatter(sub_x_data[idx, 0], sub_x_data[idx, 1], c=color, label=target_names[i],
cmap=plt.cm.RdYlBu, edgecolor='black', s=15)    # 绘制数据样本集的散点图

from matplotlib.font_manager import FontProperties
font = FontProperties(fname=r"c:\windows\fonts\simsun.ttc", size=14)    # 定义中文字体
plt.suptitle("通过决策树对鸢尾花数据进行可视化", fontproperties=font)
plt.axis("tight")
plt.figure()
clf = DecisionTreeClassifier().fit(x_data, y_label)     # 针对鸢尾花数据集的多重属性来构建决策树
plot_tree(clf, filled=True)
plt.show()

if __name__ == "__main__":
iris_decision_tree = IrisDecisionTree(3, "ryb", 0.02)
x_data, y_label, feature_names, target_names = iris_decision_tree.establish_data()
iris_decision_tree.show_result(x_data, y_label, feature_names, target_names)

graphviz 不能采用pip进行安装，采用anaconda安装的时候也会很慢，甚至多次尝试都可能安装失败，前几天帮同学安装就出现这种情况（windows下是这样的，linux环境下会很方便），所以这里我们采用直接通过 whl 文件来安装。

pip install graphviz‑0.15‑py3‑none‑any.whl

$sudo apt install graphviz # Ubuntu$ sudo apt install graphviz         # Debian

"""
Explain：通过graphviz实现决策树的可视化
"""
def show_result_by_graphviz(self, x_data, y_label):
clf = DecisionTreeClassifier().fit(x_data, y_label)
iris_dot_data = tree.export_graphviz(clf, out_file=None,
feature_names=iris.feature_names,
class_names=iris.target_names,
filled=True, rounded=True,
special_characters=True)
import graphviz
graph = graphviz.Source(iris_dot_data); graph.render("iris")

#### 参考资料：

[1] 《机器学习实战》：Peter Harrington 人民邮电出版社 [2] 《统计学习方法》：李航 第二版 清华大学出版社 [3] 《机器学习》：周志华 清华大学出版社

[4] Python Extension Packages： https://www.lfd.uci.edu/~gohlke/pythonlibs/#wordcloud

[5] sklearn.tree.DecisionTreeClassifier： https://scikit-learn.org/stable/modules/generated/sklearn.tree.DecisionTreeClassifier.html

[6] Graphviz官网： https://graphviz.org/