机器学习笔记十五之决策树、信息熵

这篇笔记我们来看看机器学习中一个重要的非参数学习算法，决策树。

什么是决策树

yENvMjq.jpg!web

上图是一个向银行申请信用卡的示例，图中的树状图展示了申请人需要在银行过几道关卡后才能成功申请到一张信用卡的流程图。在图中树状图的根节点是申请人输入的信息，叶子节点是银行作出的决策，也就相当于是对申请者输入信息作出的分类决策。从第一个根节点到最后一个叶子节点经过的根节点数量称为树状图的深度（depth）。上图示例中的树状图从第一个根节点 申请人是否办理过信用卡 ，到最后一个 发放信用卡 叶子节点共经过了三个根节点，所以深度为3。那么像这样使用树状图对输入信息一步步分类的方式就称为决策树方式。

我们再来看一个问题，上图中每一个根节点的输入信息都可以用是或否来做判断分类，但是机器学习的样本数据都是数字，那么此时如果做判断呢？我们先来使用Scikit Learn中提供的决策树直观的看一下通过决策树对样本数据的分类过程和分类结果。

# 我们使用Scikit Learn提供的鸢尾花数据集
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

# 为了绘图方便，我们只使用鸢尾花数据的后两个特征
iris = datasets.load_iris()
X = iris.data[:, 2:]
y = iris.target

# 将样本点绘制出来
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()

QZFzu2Y.jpg!web

# 引入Scikit Learn中的决策树分类器
from sklearn.tree import DecisionTreeClassifier

# max_depth参数是决策树深度，criterion参数这里我们先不用管
dt_clf = DecisionTreeClassifier(max_depth=2, criterion="entropy")
dt_clf.fit(X, y)

def plot_decision_boundary(model, axis):
	# meshgrid函数用两个坐标轴上的点在平面上画格，返回坐标矩阵
	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),
	)
	# ravel()方法将高维数组降为一维数组，c_[]将两个数组以列的形式拼接起来，形成矩阵
	X_grid_matrix = np.c_[X0.ravel(), X1.ravel()]
	
	# 通过训练好的逻辑回归模型，预测平面上这些点的分类
	y_predict = model.predict(X_grid_matrix)
	y_predict_matrix = y_predict.reshape(X0.shape)
	
	# 设置色彩表
	from matplotlib.colors import ListedColormap
	my_colormap = ListedColormap(['#EF9A9A', '#40E0D0', '#FFFF00'])
	
	# 绘制等高线，并且填充等高区域的颜色
	plt.contourf(X0, X1, y_predict_matrix, linewidth=5, cmap=my_colormap)

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()

quQrqmn.jpg!web

从决策边界图中可以看到决策树分类器将鸢尾花的数据较好的进行的归类区分。那么再回到刚才的问题，那就是在对样本数据进行决策树分类时，根节点是怎么做判断的呢？

我们仔细看上图，假设我们将横轴表示的特征记为$x$，纵轴表示的特征记为$y$，那么红色的区域就是$x<2.4$的区域，所以第一个根节点就直接可定义为$x$是否小于2.4，既样本数据的某一个特征数值是否小于2.4，如果小于2.4，那么将该样本点判定为蓝色分类的点。

然后再来看纵轴，观察可得，$y=1.8$是蓝色和黄色区域的分界点，所以可将$y<1.8$作为第二层的根节点，如果样本数据的另一个特征数值小于1.8，则判定为黄色分类的点，大于1.8则判定为绿色分类的点。那么此时的决策树为：

za2yqau.jpg!web

也就是决策树在对样本数据分类时，会先选定一个维度，或者说一个特征，再选定和这个维度想对应阈值构成一个根节点，既判断条件。

通过上面的示例，大家应该什么是决策树有了直观的了解，并且也能看出来决策树的一些特点：

决策树算法是非参数学习算法。
决策树算法可以解决分类问题。
决策树算法可以天然解决多分类问题。
决策树算法处理样本数据的结果具有非常好的可解释性。

了解了决策树后，那么问题来了，对于决策树来说核心的工作是确定根节点，那么这个根节点该如何确定呢？在哪个维度做划分？某个维度在哪个值上做划分？我们往后看。

信息熵

这一节我们先来看看什么是信息熵。其实信息熵的概念很简单， 熵在信息论中代表随机变量不确定的度量 。

熵越大，数据的不确定性越高。
熵越小，数据的不确定性越低。

信息熵的公式

上面解释了信息熵的定义，那么这一小节我们使用信息熵的公式来解释它的定义。

$$H = - \sum_{i=1}^k p_i log(p_i)$$

上面的公式就是香农提出的信息熵的公式。逐个解释一下：

假如一组数据有k类信息，那么每一个信息所占的比例就是$p_i$。比如鸢尾花数据包含三种鸢尾花的数据，那么每种鸢尾花所占的比例就是$\frac 1 3$，那么$p_1$、$p_2$、$p_3$就分别为$\frac 1 3$。
因为$p_i$只可能是小于1的，所以$log(p_i)$始终是负数。所以需要在公式最前面加负号，让整个熵的值大于0。

我们来举几个例子看一下，首先用鸢尾花的例子，三种鸢尾花各占$\frac 1 3$：

$$\{\frac 1 3,\frac 1 3,\frac 1 3\}$$

那么代入信息熵的公式可得：

$$H=-\frac 1 3 log(\frac 1 3)-\frac 1 3log(\frac 1 3)-\frac 1 3log(\frac 1 3)=1.0986$$

再来看一个例子：

$$\{\frac 1 {10},\frac 2 {10},\frac 7 {10}\}$$

代入公式可得：

$$H=-\frac 1 {10} log(\frac 1 {10})-\frac 2 {10}log(\frac 2 {10})-\frac 7 {10}log(\frac 7 {10})=0.8018$$

从上面两个例子可以看出，第二个例子的信息熵比一个例子的小，那么意味着第二个示例的数据不确定性要低于第一个示例的数据。其实从数据中也能看出，其中有一类信息占全部信息的$\frac 7 {10}$，所以大多数据是能确定在某一类中的，故而不确定性低。而第一个示例中每类信息都占了全部信息的$\frac 1 3$，所以数据不能很明确的确定是哪类，故而不确定性高。

再来看一个极端的例子，$\{1,0,0\}$，将其代入信息熵公式后得到的值是0。因为整个数据中就一种类型的数据，所以不确定性达到了最低，既信息熵的最小值为0。

信息熵曲线

这一小节我们在Jupyter Notebook中将信息熵的曲线绘制出来再让大家感性的理解一下。假设一组信息中有两个类别，那么当一个类别所占比例为$x$时，另一个类别的所占比例肯定是$1-x$，将其代入信息熵的公式展开后可得：

$$H=-xlog(x)-(1-x)log(1-x)$$

下面我们用代码来绘制一下这个曲线：

import numpy as np
import matplotlib.pyplot as plt

def entropy(p):
	return -p * np.log(p) - (1-p) * np.log(1-p)

# 构建不同的比例，这里避免log(0)的计算，所以要避免p=0和1-p=0
x = np.linspace(0.01, 0.99, 200)

# 将不同比例和不同信息熵的值绘制出来
plt.plot(x, entropy(x))
plt.show()

FjIJ3aR.jpg!web

从图中可以看到，曲线是以横轴0.5为中心的抛物线。当比例$x$为0.5时，纵轴达到最大值，也就是信息熵达到了最大值，表示此时变量不确定性最大。因为两个类别各以0.5的比例出现，很难确定是哪个类型，所以不确定性大。

当以0.5为中心向两边延展后，可以看到信息熵在逐渐减小，意味着不确定性在减小。因为此时要么有一个比例在减小，要么有一个比例在增大。这两种情况都可以表明其中一种类别的比例在增大，所以更容易确定是哪种类别，故而不确定性减小。

使用信息熵寻找最优划分

之前我们有带着两个问题进入到了信息熵小节。那么这一节就来解答这两个问题：

决策树每个节点在哪个维度做划分？
某个维度在哪个值上做划分？

那么我们要做的事情就是找到一个维度和一个阈值，使得通过该维度和阈值划分后的信息熵最低，此时这个划分才是最好的划分。

用大白话解释一下就是，我们在所有数据中寻找到信息熵最低的维度和阈值，然后将数据划分为多个部分，再寻找划分后每部分信息熵最低的维度和阈值，继续划分下去，最终形成完整的决策树。这一节就来看看如何使用信息熵寻找最优划分。

划分函数

我们先定义一个划分函数，也就是相当于构建决策树根节点的作用：

import numpy as np

# 四个参数分别为样本特征数据、样本目标数据、维度、阈值
def split(X, y, d, v):
	# 划分后左侧和右侧的索引数组
	index_l = (X[:, d] <= v)
	index_r = (X[:, d] > v)
	return X[index_l], X[index_r], y[index_l], y[index_r]

举个例子来看看上面的划分函数：

# 构建一个五行四列的样本数据
X = np.linspace(1, 10, 20)
X = X.reshape(5, 4)
y = 2 * X + 3

X
# 结果
array([[  1.        ,   1.47368421,   1.94736842,   2.42105263],
	   [  2.89473684,   3.36842105,   3.84210526,   4.31578947],
	   [  4.78947368,   5.26315789,   5.73684211,   6.21052632],
	   [  6.68421053,   7.15789474,   7.63157895,   8.10526316],
	   [  8.57894737,   9.05263158,   9.52631579,  10.        ]])

# 期望以第1个维度，既第1列特征为划分维度，以5为划分阈值
X_l, X_r, y_l, y_r = split(X, y, 1, 5)

X_l
# 结果
array([[ 1.        ,  1.47368421,  1.94736842,  2.42105263],
	   [ 2.89473684,  3.36842105,  3.84210526,  4.31578947]])

# 如果以第0个维度，既第0列特征为划分维度，以5为划分阈值，那么X_l为三行四列矩阵，因为第0列的第三行值也小于5
X_l, X_r, y_l, y_r = split(X, y, 0, 5)

X_l
# 结果
array([[ 1.        ,  1.47368421,  1.94736842,  2.42105263],
	   [ 2.89473684,  3.36842105,  3.84210526,  4.31578947],
	   [ 4.78947368,  5.26315789,  5.73684211,  6.21052632]])

计算信息熵函数

然后定义计算信息熵的函数：

from collections import Counter
from math import log
# 计算信息熵时不关心样本特征，只关心样本目标数据的类别和每个类别的数量
def entropy(y):
	# 使用Counter生成字典，key为y的值，value为等于该值的元素数量
	counter_y = Counter(y)
	entropy_result = 0
	for num in counter_y.values():
		p = num / len(y)
		# 将所有类别的占比加起来，得到信息熵
		entropy_result += -p * log(p)
		
	return entropy_result

举个例子验证一下：

test_y = np.array([0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3])
test_y1 = np.array([0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1])

# test_y信息熵应该比较大，因为有4种类别
entropy(test_y)
# 结果
1.3421257227487469

# test_y1信息熵应该比较小，因为有2种类别
entropy(test_y1)
# 结果
0.5982695885852573

寻找维度和阈值函数

最后我们来定义寻找最优信息熵、维度、阈值的函数，该函数的最基本思路就是遍历样本数据的每个维度，对该维度中每两个相邻的值求均值作为阈值，然后求出信息熵，最终找到最小的信息熵，此时计算出该信息熵的维度和阈值既是最优维度和最优阈值：

# 寻找最优信息熵
def try_split(X, y):
	
	# 最优信息熵初始取无穷大
	best_entropy = float('inf')
	# 最优维度和最优阈值，初始值为-1
	best_d, best_v = -1, -1
	
	# 对样本特征数据的每个维度，既每个特征进行搜索
	for d in range(X.shape[1]):
		# 在d这个维度上，将每两个样本点中间的值作为阈值
		# 对样本数据在d这个维度上进行排序，返回排序索引
		sorted_index = np.argsort(X[:, d])
		# 遍历每行样本数据，注意从第一行开始，因为需要用上一行的值和该行的值求均值
		for row in range(1, len(X)):
			# 如果两个值相等，那么均值无法区分这两个值，所以忽略这种情况
			if X[sorted_index[row-1], d] != X[sorted_index[row], d]:
				v = (X[sorted_index[row-1], d] + X[sorted_index[row], d]) / 2
				# 使用split()函数做划分
				X_l, X_r, y_l, y_r = split(X, y, d, v)
				# 求划分后两部分的信息熵
				e = entropy(y_l) + entropy(y_r)
				# 保存最优信息熵、维度、阈值
				if e < best_entropy:
					best_entropy, best_d, best_v = e, d, v
					
	return best_entropy, best_d, best_v

我们同样使用鸢尾花的数据进行验证，在验证之前，我们先将之前通过Scikit Learn的决策树求出的鸢尾花决策边界的图贴出来，做以对比：

quQrqmn.jpg!web

from sklearn import datasets
iris = datasets.load_iris()
X = iris.data[:, 2:]
y = iris.target

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)

# 结果
best_entropy =  0.6931471805599453
best_d =  0
best_v =  2.45

此时样本数据的第一个根节点的判断条件就求出来了，从上面的决策边界图中可以看到，第一次划分确实是从第0个维度，既横轴开始，以2.4左右为阈值进行的。我们来看看通过这个根节点划分后的数据是什么样的：

X_l1, X_r1, y_l1, y_r1 = split(X, y, best_d, best_v)
entropy(y_l1)

# 结果
0.0

entropy(y_r1)

# 结果
0.6931471805599453

从上面结果可以看到，经过第一个根节点划分后，对左侧数据求信息熵的结果为0，说明左侧的数据现在只有一个类型了。从上图也可以清晰的看到，以横轴2.4往左的区域全部是蓝色的点。那么对右侧而言，它的信息熵是0.69，说明对右侧还可以继续划分：

best_entropy2, best_d2, best_v2 = try_split(X_r1, y_r1)
print("best_entropy2 = ", best_entropy2)
print("best_d2 = ", best_d2)
print("best_v2 = ", best_v2)

# 结果
best_entropy2 =  0.4132278899361904
best_d2 =  1
best_v2 =  1.75

第二次划分以第一个维度上的1.75为阈值进行，这和上图中的纵轴的划分界限基本是一致的。再来看看划分后的结果：

X_l2, X_r2, y_l2, y_r2 = split(X_r1, y_r1, best_d2, best_v2)
entropy(y_l2)

# 结果
0.30849545083110386

entropy(y_r2)

# 结果
0.10473243910508653

可以看到第二次划分后，两部分的信息熵都不为零，其实还可以对每部分再进行划分。不过在之前使用Scikit Learn的决策树划分时，我们将深度设为了2，所以就只划分到了目前的阶段，如果将深度设的更大的话，那么就会继续划分下去。在我们模拟寻找最优划分的过程中，就不再继续划分下去了，大家理解了划分过程就可以了。

申明：本文为慕课网 liuyubobobo 老师《Python3入门机器学习经典算法与应用》课程的学习笔记，未经允许不得转载。

什么是决策树

信息熵

信息熵的公式

信息熵曲线

使用信息熵寻找最优划分

划分函数

计算信息熵函数

寻找维度和阈值函数

Recommend

决策树-机器学习实战h5三公平台安装-jkajew的博客-51CTO博客

机器学习第一课：决策树学习概述与实现

机器学习：决策树

机器学习决策树算法实战——理论+详细的Python3代码实现

机器学习决策树算法实战：理论 + 详细的 Python 3 代码实现

机器学习A-Z～决策树与随机森林

机器学习回顾篇（8）：CART决策树算法

【白话机器学习】算法理论+实战之决策树

【机器学习】决策树

机器学习（十五）——决策树

About Joyk