0%

决策树

1、决策树(Decision Tree)

决策树(decision tree)是一类常见的机器学习方法,就如同它的名字一般,训练过程类似一个树形结构,树上的每个非叶子节点都是 某种属性测试,每个分支代表了对该属性测试的输出,而叶子节点存储的就是决策结果根节点代表样本全集)。

上述概念性的语句可能会比较晦涩,不过决策树的思想体现在日常生活中的方方面面,下图应该可以给你一个较为直观的感受。

未命名文件 (1)

上图简化了==大概是==谈恋爱时的决策思路,第一印象外貌,这部分的比重应该是比较大的,可以筛选掉大部分的人,从而降低信息熵(信息熵又是什么?),而后可能虽然没有那么帅气,但在相识一段时间后,发现其学富五车或是被其他什么因素吸引了,也会萌生谈恋爱的想法。如果在彻底观察下来后,结果都不尽人意,那就只能递出好人卡了。

显然,决策树的创建过程应该是一个递归的过程(可能用迭代实现吧),它会一直采用深度遍历的方式进行属性测试,只有在当前节点中所包含的样本都属于同一类别时才会导致递归返回(正常情况下不会这么做)。

2、信息熵(Entropy)

不过,人可以通过某些经验得出一系列的 属性测试,计算机可不行。那么决策树是如何进行 属性测试,又是如何判断该测试的好坏呢?这就要提出由大名鼎鼎的香农提出的香农定理(计网DNA错乱),其实是他老人家在1948年提出的 信息熵 的概念。

简单来说信息熵可以反映某件事不确定的程度,信息熵越高,那我们说这件事就越不确定;反之,信息熵越低,那这件事就越确定。信息熵为0,代表我们完全了解这件事,不确定性为0。下面是信息熵的数学公式。
$$
\begin{gather*}
entropy = -\sum\limits_{i=1}^kp_ilog(p_i)
\end{gather*}
$$
如果是二分类的话,又可以写成
$$
\begin{gather*}
entropy = -plog(p)-(1-p)log(1-p)
\end{gather*}
$$
下面是二分类信息熵的函数图像,这里 log 是以 2 为底的,神经网络中一般都是以 e 为底,不过就按我愚见,底数到底取什么值并没有什么太大关系(可能会方便后续数据处理),毕竟函数的性质不会发生改变,包括极值点的位置(横坐标),对称性等,只要能保证在一个系统(程序)中保证统一方便比较就行。

如下图,信息熵的函数图像会比较类似于二次函数抛物线的图像,定义域 (0,1),注意 log 真数要大于 0,但可以利用极限思想得出两个端点值都为 0。整个函数图像在 x = 0.5 除取的最大值,也就是说在二分类的问题下,50% 是不确定性最大的,这也非常好理解, 50% 不会偏向于任意一个类别,我们只能靠猜来得出答案。如果这个概率偏大一点或偏小一点,那么就肯定会偏向于某一类别,不确定性就没有那么大了。

image

现在再回到计算机应该如何评估 属性测试,信息熵就是它的评估指标。我们希望在每次 属性测试 的信息熵都要尽量的低,也就是尽可能地将不同的类别区分开来。而如何得到这个最好的 属性测试 呢?只需要暴力枚举所有特征,根据特征值进行分类就行了,下面是代码的实现。

3、基尼系数(Gini)

另外,除了信息熵函数,还可以用基尼系数来量化不确定性程度。
$$
\begin{gather*}
gini = 1-\sum\limits_{i=1}^kp_i^2
\end{gather*}
$$
同样地,这里也给出二分类下的基尼系数表达式。
$$
\begin{gather*}
gini = 1-p^2-(1-p)^2=-2(p^2-p)
\end{gather*}
$$
图像如下,橙色的是 gini,绿色的是 entropy,二者的函数的性态非常相似(单调性,对称性,凹凸性,极值点等),因此二者都非常适合描述事物的不确定性程度。

而由于信息熵函数有取对数的操作,比较影响计算效率,因此基尼系数也被 sklearn 中决策树的实现选为默认标准。

image

4、特性(propety)

测试集选用的是 sklearn 中自带的月亮函数 make_moons,样本分布如下。

image

先调用库中的决策树类,对该月亮样本进行拟合,然后我们可以绘制其决策边界。

由于决策树天然地容易过拟合(随随便便就能在训练集上获得非常高的预测率),因此在构建模型的时候 sklearn 也是提供了非常多的超参数来控制这个问题。

下图是没设置超参数的情况,决策树会特别容易收到异常值的影响,会为了拟合单独一个或几个点导致其决策边界奇形怪状的。

image

下图将树的最高高度限制在了 2。

image

通过上述两张图可以发现一个比较有意思的事情,决策树的决策边界是横平竖直的,这也是归于他较为独特的训练方法(根据特征值划分左右两份),因此它不可能能拟合出来一条斜线或是曲线(只能拟合出类似楼梯状的决策边界)!

5、代码(Coding)

关于决策树,我这里只实现了部分功能,有关递归建树和预测的代码都没写(不大会)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
# 计算信息熵
def getEntropy(y):
n = len(y)
counter = Counter(y)
entropy = 0.
for value in counter.values():
p = value / n
entropy -= p * np.log(p)
return entropy

# d - dimension
# v - value
# 根据特征值将样本划分成大于该特征值或小于等于该特征值的两部分
def split(X, y, d, v):
l_idx = X[:, d] <= v
r_idx = X[:, d] > v
return X[l_idx], X[r_idx], y[l_idx], y[r_idx]

# 划分样本
def decision(X, y):
best_e = float("inf")
best_d = -1
best_v = -1

# 遍历所有特征
for d in range(X.shape[1]):
X_d = X[:, d]
sorted_idx = np.argsort(X_d)
# 遍历特征中所有值,并以此划分样本,寻求最低的信息熵
for i in range(len(y) - 1):
mid = (X_d[i] + X_d[i+1]) / 2
X_l, X_r, yl, yr = split(X, y, d, mid)
entropy = len(yl) / len(y) * getEntropy(yl) + len(yr) / len(y) * getEntropy(yr)
if entropy < best_e:
best_e = entropy
best_d = d
best_v = mid

return best_e, best_d, best_v

# 可视化决策边界
def plot_decision_boundary(model, axis):

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, cmap=custom_cmap)

测试一下,我的代码实现和 sklearn 实现的结果是否有差异。数据还是用得前面的月亮样本。

image

第一次划分在了 特征1,值为 0.27,也就是下图中红线的位置。

image

image

第一次划分后,整个样本就变成上下两部分,后续在分别对这上下两部分再各进行一次划分。可以发现啊,运行的结果都是在x轴上进行了划分,值分别为 -0.681.24,和上图的决策边界也基本一致。

image