前言
在上一小节中介绍了一个新指标：信息熵。通过信息熵可以计算当前数据的不确定度。构建决策树时，初始状态下，根节点拥有全部的数据集。在根节点的基础上，根据划分后左右两个节点中的数据计算得到的信息熵最低为指标，找到一个合适的维度以及在这个维度上的一个阈值，然后根据找到的维度以及对应的阈值将在根节点中的全部数据集划分成两个部分，两个部分的数据分别对应两个不同的节点。对于两个新节点，再以同样的方式分别对两个新节点进行同样的划分，这个过程递归下去就形成了决策树。本小节主要通过代码来模拟使用信息熵作为指标的划分方式。
sklearn中的决策树
回顾使用 sklearn 中封装好的决策树对鸢尾花数据集进行训练，通过绘制训练好的决策树的决策边界来更加直观的可视化在各个节点上划分的维度以及对应的阈值。
使用 sklearn.datasets 模块中的 load_iris 方法加载鸢尾花数据集，为了方便可视化，只选取鸢尾花数据集的最后两个特征。
代码语言：javascript复制In[1]: from sklearn import datasets
iris = datasets.load_iris()
# 只选取petal length和petal width两个特征
X = iris.data[:, 2:]
y = iris.target
有了数据集，可以在 sklearn.tree 中导入 DecisionTreeClassifier 决策树分类器。在实例化决策树分类器时，指定两个参数：
- max_depth: 决策树的最大深度，深度越大，模型越容易过拟合；
- criterion: 决策树的划分标准，其中
entropy为信息熵，gini为基尼系数；
In[2]: from sklearn.tree import DecisionTreeClassifier
dt_clf = DecisionTreeClassifier(max_depth=2,
criterion="entropy",
random_state=42)
dt_clf.fit(X, y)
Out[2]: DecisionTreeClassifier(class_weight=None,
criterion='entropy', max_depth=2,
max_features=None, max_leaf_nodes=None,
min_impurity_decrease=0.0, min_impurity_split=None,
min_samples_leaf=1, min_samples_split=2,
min_weight_fraction_leaf=0.0, presort=False, random_state=None,
splitter='best')
训练好了决策树，接下来可以使用 plot_decision_boundary 方法来绘制决策边界，与此同时将只包含后两个特征的原始数据集也绘制出来。
代码语言：javascript复制In[4]: import numpy as np
import matplotlib.pyplot as plt
# 绘制不规则决策边界
def plot_decision_boundary(model, axis):
'''
model: 训练好的模型
axis: 横纵坐标轴的范围，[x_start, x_end, y_start, y_end ]
'''
x0, x1 = np.meshgrid(
np.linspace(axis[0], axis[1],
int((axis[1] - axis[0]) * 100)).reshape(-1, 1),
np.linspace(axis[2], axis[3],
int((axis[3] - axis[2]) * 100)).reshape(-1, 1)
)
X_new = np.c_[x0.ravel(), x1.ravel()]
y_predict = model.predict(X_new)
zz = y_predict.reshape(x0.shape)
from matplotlib.colors import ListedColormap
custom_cmap = ListedColormap(['#EF9A9A','#FFF59D','#90CAF9'])
plt.contourf(x0, x1, zz, linewidth=5, cmap=custom_cmap)
In[5]: plot_decision_boundary(dt_clf, axis=[0.5, 7.5, 0, 3])
plt.scatter(X[y==0,0], X[y==0,1])
plt.scatter(X[y==1,0], X[y==1,1])
plt.scatter(X[y==2,0], X[y==2,1])
plt.show()
通过绘制好的决策边界可以大致看出决策树的构建过程：
- 根节点中有全部数据集；
- 第一次将根节点中的全部数据集按照第 0 个维度上的 2.45 这个值进行划分：
- 将第 0 个维度的特征值小于等于 2.45 的数据划分到左节点中
- 将第 0 个维度的特征值大于 2.45 的数据划分到右节点中
- 由于左节点中只有蓝色类别的数据，此时左节点中的数据不确定度最低，即信息熵为 0，因为不需要再次进行划分；
- 第二次将右节点中的全部数据集按照第 1 个维度上的 1.75 这个值进行划分：
- 将第 1 个维度的特征值小于等于 1.75 的数据划分到左节点中
- 将第 1 个维度的特征值大于 1.75 的数据划分到右节点中
模拟使用信息熵进行划分
接下来将模拟使用信息熵理论对鸢尾花数据集进行划分，并将划分结果与前面使用 sklearn 封装好的决策树的划分结果进行比对，看看两种划分结果是否一致？
- 创建 split(X, y, d, value) 函数，作用：按照特征维度 d 上的 value 值对数据集 (X, y) 进行划分
split 函数有四个参数：X 表示数据集的特征，y 表示数据集的类别标签，d 表示进行划分的特征维度，value 表示在特征维度 d 上进行划分的阈值。
代码语言：javascript复制In[6]: def split(X, y, d, value):
index_a = (X[:, d] <= value)
index_b = (X[:, d] > value)
return X[index_a], X[index_b], y[index_a], y[index_b]
「split 函数的任务并不是寻找特征维度 d 以及在特征维度 d 上的阈值 value，而是假设已经知道了划分的 d 和 value 值的情况下对数据集进行划分。」 划分的方式非常简单，将数据集中的每个样本点的第 d 个特征维度的值与阈值 value 进行比较，其中 index_a 变量是条件小于等于 value 值的布尔数组，而 index_b 变量是条件大于 value 值的布尔数组，最后通过 index_a 和 index_b 两个布尔数组将传入的数据集划分成两个部分，对应左右两个节点分支。
- 创建 entropy(y) 函数，作用：根据类别标签计算信息熵
entropy 函数有一个参数：y 表示数据集的类别标签。类别标签 y 中包含了数据集的具体类别，通过类别标签 y 可以看出数据集中一共有多少个类别以及每个类别所包含的样本数，知道了这些已知条件就可以计算信息熵。
代码语言：javascript复制In[7]: from collections import Counter
from math import log
def entropy(y):
counter = Counter(y)
res = 0.0
for num in counter.values():
p = num / len(y)
res = -p * log(p)
return res
在 entropy 函数中使用 collections 包下的 Counter 模块可以将类别标签 y 转换为包含键值信息的数据对，其中键为具体的类别，而对应的值为具体类别的个数 (比如1:50，类别1样本为50个)。接下来只需要迭代计算每一个类别所占的比例，就可以套用计算信息熵的公式得到信息熵的值。由于这里的 p 仅仅是一个数字，因此只需要使用 math 模块下的 log 函数即可。
- 创建 try_split(X, y) 函数，作用：根据数据集 (X, y) 寻找最优的信息熵以及对应的特征维度 d 以及在特征维度 d 上的阈值 value
try_split 函数有一个参数：X 表示数据集的特征，y 表示数据集的类别标签。
代码语言：javascript复制In[7]: def try_split(X, y):
# 初始化最优信息熵为正无穷
best_entropy = float('inf')
# 初始化最优维度以及对应阈值为-1
best_d, best_v = -1, -1
# 遍历样本中每一个特征维度
for d in range(X.shape[1]):
# 将所有样本点按照特征维度d的值进行排序
sorted_index = np.argsort(X[:,d])
# 遍历样本点
for i in range(1, len(X)):
# 相邻的两个数据在第d个特征维度上的特征值不相等
if X[sorted_index[i], d] != X[sorted_index[i-1], d]:
# 取两个数据在第d个维度上特征值的平均值作为候选阈值
value = (X[sorted_index[i], d] X[sorted_index[i-1], d])/2
# 使用split函数按照特征维度d上的value值对数据集进行划分
X_l, X_r, y_l, y_r = split(X, y, d, value)
# 计算当前节点的信息熵
p_l, p_r = len(X_l) / len(X), len(X_r) / len(X)
e = p_l * entropy(y_l) p_r * entropy(y_r)
if e < best_entropy:
best_entropy, best_d, best_v = e, d, value
return best_entropy, best_d, best_v
try_split 函数是最为核心的部分。每一次尝试都是再找使得信息熵最小的划分方式，因此定义 best_entropy 变量并将其初始化为正无穷。每次找到最小的信息熵都会有一个对应的特征维度以及特征维度上的阈值，因此定义了最优的特征维度 best_d 以及特征维度上的阈值 best_v，并都将其初始化为 -1。
接下来的事情比较简单，本质就是遍历样本中的所有特征维度 (X.shape[1])，对于每一个特征维度都需要确定划分的阈值。可选的阈值为每两个样本点在 d 这个特征维度上的平均值，所以对所有样本点在 d 这个特征维度上进行排序。使用 argsort 对样本点进行排序，argsort 函数返回排序后的索引。
遍历每一个样本点，此时开始遍历从 1 开始而不是从 0 开始，因为每次找的都是 i-1 和 i 这两个样本点在特征维度 d 上的平均值 (当然也可以从0开始，则改为range(0, len(X) - 1))。「如果 X[sorted_index[i], d] 和 X[sorted_index[i-1], d] 这两个值不相等的话，就可以将候选阈值 value 定义为相邻的两个样本点在特征维度 d 上的平均值。」
使用 split 函数按照特征维度 d 以及候选的阈值 value 对数据集进行划分，返回 (X_l, y_l) 和 (X_r, y_r) 两个部分。分别计算两个部分的信息熵，并进行累加作为当前节点的信息熵。
经过双重循环之后，找到了让信息熵减低的划分方式。最优的信息熵为 best_entropy，对应划分的特征维度为 best_d，特征维度下的阈值为 best_v。
完成了 try_split 这个核心函数，接下来可以将整个鸢尾花数据集传入到 try_split 函数中，try_split 函数会返回结果存入 best_entropy、best_d 和 best_v 三个变量中。
代码语言：javascript复制 In[8]: best_entropy, best_d, best_v = try_split(X, y)
print("best_entropy =", best_entropy)
print("best_d =", best_d)
print("best_v =", best_v)
Out[8]: best_entropy = 0.46209812037329684
best_d = 0
best_v = 2.45
「对整个鸢尾花数据集的最佳划分位置在第 0 个特征维度上且阈值为 2.45，划分后的信息熵变成了 0.693 左右，与前面使用 sklearn 封装好的决策树的划分结果一致。」
有了信息熵最小时的特征维度 best_d 以及对应特征维度上的阈值 best_v，接下来就可以调用 split 函数将全部鸢尾花数据集按照 best_d 以及 best_v 划分为两个部分。
代码语言：javascript复制In[9]: X1_l, X1_r, y1_l, y1_r = split(X, y, best_d, best_v)
(X1_l, y1_l) 为在 best_d 特征维度上小于等于 best_v 的数据集合，为了方便将其称为左分支。(X1_r, y1_r) 为在 best_d 特征维度上大于 best_v 的数据集合，为了方便将其称为右分支。
调用 entropy 函数计算左右两个分支上数据的信息熵。
代码语言：javascript复制 In[10]: print("划分为左部分的数据的信息熵：",
entropy(y1_l))
Out[10]: 划分为左部分的数据的信息熵： 0.0
In[11]: print("划分为右部分的数据的信息熵：",
entropy(y1_r))
Out[11]: 划分为右部分的数据的信息熵： 0.6931471805599453
左分支的信息熵为 0.0，这是因为划分后的左分支中包含同一类别的全部数据 (sklearn中绘制决策树的决策边界中蓝色的样本点)，因此不需要继续进行划分。右分支的信息熵为 0.69，信息熵的值比较大，并且还没有达到划分最大的深度，可以继续进行划分。
由于右分支的信息熵为 0.69，因此可以继续进行划分，将右分支的全部数据传入 try_split 函数中，try_split 函数返回结果存入 best_entropy2、best_d2 和 best_v2 三个变量中。
代码语言：javascript复制 In[12]: best_entropy2, best_d2, best_v2 = try_split(X1_r, y1_r)
print("best_entropy =", best_entropy2)
print("best_d =", best_d2)
print("best_v =", best_v2)
Out[12]: best_entropy = 0.2147644654371359
best_d = 1
best_v = 1.75
「对右分支的所有数据的最佳划分位置在第 1 个特征维度上且阈值为 1.75，划分后的信息熵变成了 0.21 左右，与前面使用 sklearn 封装好的决策树的划分结果一致。」
有了信息熵最小时的特征维度 best_d2 以及对应特征维度上的阈值 best_v2，接下来就可以调用 split 函数将右分支的全部数据按照 best_d2 以及 best_v2 划分为两个部分。
代码语言：javascript复制In[13]: X2_l, X2_r, y2_l, y2_r = split(X1_r, y1_r, best_d2, best_v2)
(X2_l, y2_l) 为在 best_d2 特征维度上小于等于 best_v2 的数据集合，为了方便将其称为右-左分支。(X2_r, y2_r) 为在 best_d2 特征维度上大于 best_v2 的数据集合，为了方便将其称为右-右分支。
调用 entropy 函数计算左右两个分支上数据的信息熵。
代码语言：javascript复制 In[10]: print("划分为左部分的数据的信息熵：",
entropy(y2_l))
Out[10]: 划分为左部分的数据的信息熵：0.30849545083110386
In[11]: print("划分为右部分的数据的信息熵：",
entropy(y2_r))
Out[11]: 划分为右部分的数据的信息熵：0.10473243910508653
右-左分支的信息熵大概为 0.30，右-右分支的信息熵大概为 0.10。第二次对右分支的全部数据集划分得到的右-左分支和右-右分支上的信息熵都没有降到 0，因此还可以继续进行划分，但是为了和前面 sklearn 中使用决策树时指定的 max_depth 最大深度为 2 一致，这里不再继续进行划分。
References：
- Python3入门机器学习 经典算法与应用: https://coding.imooc.com/class/chapter/169.html#Anchor
