机器学习篇 | 决策树介绍
决策树（Decision Tree）是一种简单但是广泛使用的分类器。通过训练数据构建决策树，可以高效的对未知的数据进行分类。
决策数有两大优点:
- 决策树模型可以读性好，具有描述性，有助于人工分析；
- 效率高，决策树只需要一次构建，反复使用，每一次预测的最大计算次数不超过决策树的深度。
决策树的基本流程
如上所示， 在基于递归模式的划分属性过程中， 在遇到以下三种情况会阻止递归的向下传递:
- 当前样本同属于一个类别，此时无需继续划分
- 当前属性集为空，无法继续划分属性。（此时用含有样本数最多的一个类别作为该划分的最终分类类型）
- 当前属性集为空，则无需划分
划分属性算法
属性划分算法帮助我们基于训练样本集选择一个基于样本特征最优的属性分类方案， 帮助我们基于样本特征简单的将样本分类。 常见的划分方式有基于信息熵的ID3与C4.5算法，基于基尼指数的CART算法。
信息熵
信息熵是度量样本集合纯度最常用的一种指标, 假定当前样本集合 $D$ 中第 $k$ 类样本所占比例为 $p_k(k=1,2,…,y)$ ,则 $D$ 的信息熵定义为 :
\[Ent(D) = - \sum_{k=1}^{y}p_k \log_2{p_k}\]$Ent(D)$ 的值越小，则 $D$ 的纯度越高
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def information_entropy(X:np, Y:np) -> float :
"""
信息熵
:param X:
:param Y:
:return:
"""
sample_count = len(Y)
ent = 0.0
for target in np.unique(Y):
target_sample_count = len(Y[Y == target])
target_probabili = target_sample_count / sample_count
ent += ((target_probabili) * -math.log(target_probabili, 2))
return ent
基尼值
基尼值来度量数据集 $D$ 的纯度的算法表示:
\[Gini(D) = \sum_{k=1}^{y}\sum_{j \neq k}p_{k}p_{j} = 1 - \sum_{k=1}^{y}p_{k}^{2}\]直观来说，$Gini(D)$ 反映了从数据集 $D$ 中随机抽取两个样本，其类别标记不一致的概率。 因此, $Gini(D)$ 越小， 则数据集 $D$ 的纯度越高。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def gini_index(X:np, Y:np) -> float :
"""
基尼基数
:param X:
:param Y:
:return:
"""
sample_count = len(Y)
gini = 1
for target in np.unique(Y) :
sample_target_count = len(Y[Y == target])
sample_target_ratio = sample_target_count / sample_count
gini = gini - sample_target_ratio ** 2
return gini
基于信息增益的 ID3 算法
ID3 使用信息增益为准则来选择划分属性。
对于样本集 $D$ , 如果基于属性 $a$ 来划分，将样本集 $D$ 划分为 $V$ 类，每个子样本集为 $D^{v}, (v=1,2,…V)$.
则样本集 $D$ 对于属性 $a$ 划分 的信息增益为 :
\[Gain(D,a) = Ent(D) - \sum_{v=1}^{V} \frac{D^v}{D} Ent(D^v)\]一般而言，信息增益越大，则意味着使用属性 $a$ 来进行划分所获得的纯度提升越大。
因此对于信息增益的选择方式，我们选择信息增益最大属性来划分 $a_* = arg \max Gain(D,a)$
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
def ID3(X:np, Y:np) -> tuple :
"""
ID3 算法， 使用信息增益
:param X:
:param Y:
:return:
"""
feature_num = X.shape[1]
# sample_info_ent = information_entropy(X, Y) # 计算信息熵
min_info_ent = math.inf
min_item = 0
min_feature_cut = 0
for feature_item in range(feature_num) :
feature_sample_unique = np.sort(np.unique(X[:, feature_item]))
for feature_item_index in range(len(feature_sample_unique) -1):
feature_item_cut = (feature_sample_unique[feature_item_index] + feature_sample_unique[feature_item_index + 1])/2
x1 = X[X[:, feature_item] < feature_item_cut]
y1 = Y[X[:, feature_item] < feature_item_cut]
pa_sample_1 = len(y1) / len(Y)
ent1 = information_entropy(x1, y1)
x2 = X[X[:, feature_item] > feature_item_cut]
y2 = Y[X[:, feature_item] > feature_item_cut]
pa_sample_2 = len(y2) / len(Y)
ent2 = information_entropy(x2, y2)
gain = pa_sample_1 * ent1 + pa_sample_2 * ent2
if gain < min_info_ent :
min_info_ent = gain
min_item = feature_item
min_feature_cut = feature_item_cut
return min_item, min_feature_cut
基于信息增益率的 C4.5 算法
信息增益准则对取值数目较多的属性有所偏好，为减少这种偏好可能带来的不利影响， C4.5 算法不直接使用信息增益， 而是使用信息增益率来选择最优划分属性。
信息增益率的公式为 :
\[Gain\_ratio(D,a) = \frac{Gain(D,a)}{IV(a)}\]其中
\[IV(a) = - \sum_{v=1}^{V} \frac{D^v}{D}\log_{2}\frac{D^v}{D}\]增益率对取值数目较少的属性会有所偏好，因此， C4.5算法并不是直接选择增益率最大的候选划分属性，而是是用了一个启发式: 先从候选划分属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
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
def C4_5(X:np, Y:np) -> tuple :
"""
C4.5 信息增益率算法
为了逻辑简单直接选择增益率最高的
:param X:
:param Y:
:return:
"""
feature_num = X.shape[1]
sample_info_ent = information_entropy(X, Y) # 计算信息熵
max_gain_ratio = 0
max_item = 0
max_feature_cut = 0
for feature_item in range(feature_num):
feature_sample_unique = np.sort(np.unique(X[:, feature_item]))
for feature_item_index in range(len(feature_sample_unique) - 1):
feature_item_cut = (feature_sample_unique[feature_item_index] + feature_sample_unique[
feature_item_index + 1]) / 2
x1 = X[X[:, feature_item] < feature_item_cut]
y1 = Y[X[:, feature_item] < feature_item_cut]
pa_sample_1 = len(y1) / len(Y)
info_ent1 = information_entropy(x1, y1)
x2 = X[X[:, feature_item] > feature_item_cut]
y2 = Y[X[:, feature_item] > feature_item_cut]
pa_sample_2 = len(y2) / len(Y)
info_ent2 = information_entropy(x2, y2)
gain = sample_info_ent - (pa_sample_1 * info_ent1 + pa_sample_2 * info_ent2)
iv = - math.log(pa_sample_1, 2) - math.log(pa_sample_2, 2)
gain_ratio = gain / iv
if gain_ratio > max_gain_ratio:
max_gain_ratio = gain_ratio
max_item = feature_item
max_feature_cut = feature_item_cut
return max_item, max_feature_cut
基于基尼指数的 CART 算法
CART决策树使用基尼指数来选择划分属性, 对应属性 $a$ 的基尼指数定义为 :
于是， 我们在候选属性 $a$ 中，选择那个使得划分后基尼指数最小的属性最为最优划分属性， 即 $a_* = arg \max Gini_index(D,a)$
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
def CART(X:np, Y:np) -> tuple :
"""
基于基尼基数的 CART 决策树
:param X:
:param Y:
:return:
"""
feature_count = X.shape[1]
min_gini_value = math.inf
min_feature_item = 0
min_feature_cut = 0
for feature_item in range(feature_count) :
feature_item_unique_value = np.sort(np.unique(X[:, feature_item]))
for feature_item_index in range(len(feature_item_unique_value) -1) :
feature_item_value_cut = (feature_item_unique_value[feature_item_index] + feature_item_unique_value[feature_item_index+1]) / 2
x1 = X[X[:, feature_item] < feature_item_value_cut]
y1 = Y[X[:, feature_item] < feature_item_value_cut]
pa_sample_1 = len(y1) / len(Y)
info_ent1 = gini_index(x1, y1)
x2 = X[X[:, feature_item] > feature_item_value_cut]
y2 = Y[X[:, feature_item] > feature_item_value_cut]
pa_sample_2 = len(y2) / len(Y)
info_ent2 = gini_index(x2, y2)
gini_index_value = pa_sample_1 * info_ent1 + pa_sample_2 * info_ent2
if gini_index_value < min_gini_value :
min_gini_value = gini_index_value
min_feature_item = feature_item
min_feature_cut = feature_item_value_cut
return min_feature_item, min_feature_cut
模型处理
离散特征与连续特征的处理方式
对于离散属性
如果属性A为离散性属性， 如西瓜样本集的色泽属性， 其属性特征值可以枚举 : 青绿, 乌黑, 浅白
因为离散属性的属性个数确定，所以可以基于属性枚举进行划分， 将属性值相同的样本作为一个分类样本。
因为样本划分后对于属性A来说，每个子样本的属性相同， 则后续属性A不参与分类
对于连续属性
由于属性的特征值不在有限，因此不能直接根据连续属性的可取值来对节点进行划分。
对于这种情况一般采用二分法来对连续属性进行处理。
具体的方法为:
- 对于给定样本集 $D$ 和连续属性 $a$ , 假定 $a$ 在 $D$ 上出现了 $n$ 个不同取值， 将这些值从小到大进行排序，记为 $ \lbrace a^{1}, a^{2}, …, a^{n} \rbrace $
- 选择划分点 $t$ 将 $D$ 划分为两部分 $D_{t}^{-}$ 和 $D_{t}^{+}$。 其中 $D_{t}^{-}$ 包含那些在属性 $a$ 上取值小于 $t$ 的样本集， $D_{t}^{+}$ 包含那些在属性 $a$ 上取值大于 $t$ 的样本集
- t 取值为 $T_a = \lbrace \frac{a^{i} + a^{i+1}}{2} | 1 \leq i \leq n-1 \rbrace $
- 带入算法选择最优的位置进行划分
与离散属性不同，连续属性进行划分以后， 还可以作为后代节点的属性划分
剪枝技术防止过拟合
剪枝是决策树学习算法对付过拟合的主要手段。在决策树学习中，为了尽可能正确分类训练样本，节点划分过程将不断重复，有时会造成决策树分支过多， 这时就可能因训练样本学得太好了，以至于吧训练集资深的一些特点当做所有数据都具有的一般性质而导致过拟合。
因此，可通过主动去掉一些分支来降低过拟合的风险。
为了决策树剪枝， 首先要将样本集划分为训练样本与测试样本， 例如采用留出法划分 :
预剪枝
预剪枝是在构建决策树过程中进行剪枝， 在每次选择一个划分属性时， 首先判断划分前后在测试数据集的误差大小:
如果属性不划分时(使用类别最多的样本作为改属性对应的类别)在测试集的错误率 大于 属性划分后在测试集的错误率，则进行改属性划分
如果属性不划分时(使用类别最多的样本作为改属性对应的类别)在测试集的错误率 小于 属性划分后在测试集的错误率, 则放弃划分
- 预剪枝使得决策树的很多分支都没有展开， 这不仅降低了过拟合的风险，还显著减少了决策树的训练时间开销和测试时间开销。
- 有些分支的当前划分虽然不能提升泛化性能， 甚至可能导致泛化性能下降，但是在其基础上进行的后续划分却有可能导致性能的显著提升，预剪枝的基于”贪心”的本质禁止了这些分支展开，给预剪枝决策树带来了
欠拟合的风险。
后剪枝
后剪枝是在决策树训练完成后合并分支的手段。
后剪枝从下到上在测试集比较节点的泛化能力， 对于其分支拆分后泛化能力下降者进行合并
- 一般情况下，后剪枝的欠拟合风险很小
- 泛化能力往往优于预剪枝
- 后剪枝时间开销要比预剪枝要大的多
说明
- 代码采用特征为连续属性莺尾花样本集
- 参考 [周志华-机器学习]