Python手撸机器学习系列（六）：决策树（附Python实现西瓜书决策树构建及剪枝代码）_利用决策树算法对西瓜数据集进行分类python 实现

决策树

根据划分方法不同可以分为ID3、CART、C4.5三种决策树

一、ID3决策树

1.1 信息熵

决策树算法的关键在于如何选择最优划分属性。一般而言，我们希望决策树的分支节点所包含的样本尽可能属于同一类别，即其纯度越高越好。

通常，使用信息熵（information entropy）来作为度量样本纯度的标准，计算公式为：
$$Ent(D)=-\sum _{k=1}^{|y|}{p}_{k}lo{g}_2{p}_k$$
其中$|y|$表示有几类，$p_k$表示第$k$类样本的占比

信息熵值越小，纯度则越高

举个例子：对于二分类，假设现在划分节点使得样本分类各占一半，则根据上述公式，信息熵为$Ent=-0.5\ast lo{g}_2(0.5)\ast 2=1.00$

而当划分节点使得样本按照91开分为2类时，根据上述公式，信息熵为$Ent=-0.1\ast lo{g}_2(0.1)\ast -0.9\ast lo{g}_2(0.9)=0.469$

根据我们的定义，$Ent$的值越小纯度越高，即当划分数据越倾向一类越好，当数据均分时纯度较低。

1.2 信息增益

对于某一个属性$a$而言，它有$V$个可能的取值 { a 1 , a 2 , . . . , a V } \{a^1,a^2,...,a^V\} {a1,a2,...,aV}，如果使用这个属性对数据进行划分，则会产生$V$个节点，其中第$v$个节点包含了原始数据集中所有在属性$a$上取值为$v$的样本（包括所有类别），记为$D^v$。我们可以先计算按照属性值$v$划分的信息熵，然后根据样本数量的不同给与不同的权重$|D^v|/|D|$，可计算出属性$a$对样本集$D$进行划分所获得的“信息增益”，用公式表述为：
$$Gain(D,a)=Ent(D)-\sum _{v=1}^V\frac{|D^v|}{|D|}Ent(D^v)$$
其中$|\cdot |$表示样本数量

很显然，这个公式表示使用属性$a$划分之后信息熵下降了多少，即纯度提升了多少。因此，我们可以使用信息增益作为决策树的划分属性选择。而ID3决策树就是以信息增益为准则来划分属性的。

1.3 数据集

使用数据集：周志华《机器学习》 第76页表4.1 西瓜数据集2.0，已经使用pandas处理为csv格式，请自取：

西瓜数据集（csv格式）：百度网盘 提取码：dy4c

1.3 ID3决策树基础代码实现

根据决策树算法，可知I3D决策树的算法流程如下：

1. 先根据最大信息增益选取一个特征作为根节点
2. 以根节点特征的取值作为分支递归生成节点，在递归中注意：
   • 每次取特征值时需要删除之前取过的数据
   • 当当前样本只有一类时，返回该类别作叶子结点，即分类结果
   • 当当前所有样本的特征值都一样时，选样本最多的类作为叶子结点
3. 使用测试特征测试决策树预测能力

以下为python代码实现：

import pandas as pd
import numpy as np

#计算信息熵
def cal_information_entropy(data):
    data_label = data.iloc[:,-1]
    label_class =data_label.value_counts() #总共有多少类
    Ent = 0
    for k in label_class.keys():
        p_k = label_class[k]/len(data_label)
        Ent += -p_k*np.log2(p_k)
    return Ent

#计算给定数据属性a的信息增益
def cal_information_gain(data, a):
    Ent = cal_information_entropy(data)
    feature_class = data[a].value_counts() #特征有多少种可能
    gain = 0
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        Ent_v = cal_information_entropy(data.loc[data[a] == v])
        gain += weight*Ent_v
    return Ent - gain

#获取标签最多的那一类
def get_most_label(data):
    data_label = data.iloc[:,-1]
    label_sort = data_label.value_counts(sort=True)
    return label_sort.keys()[0]

#挑选最优特征，即信息增益最大的特征
def get_best_feature(data):
    features = data.columns[:-1]
    res = {}
    for a in features:
        temp = cal_information_gain(data, a)
        res[a] = temp
    res = sorted(res.items(),key=lambda x:x[1],reverse=True)
    return res[0][0]

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列
def drop_exist_feature(data, best_feature):
    attr = pd.unique(data[best_feature])
    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
    return new_data

#创建决策树
def create_tree(data):
    data_label = data.iloc[:,-1]
    if len(data_label.value_counts()) == 1: #只有一类
        return data_label.values[0]
    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果
        return get_most_label(data)
    best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征
    Tree = {best_feature:{}} #用字典形式存储决策树
    exist_vals = pd.unique(data[best_feature]) #当前数据下最佳特征的取值
    if len(exist_vals) != len(column_count[best_feature]): #如果特征的取值相比于原来的少了
        no_exist_attr = set(column_count[best_feature]) - set(exist_vals) #少的那些特征
        for no_feat in no_exist_attr:
            Tree[best_feature][no_feat] = get_most_label(data) #缺失的特征分类为当前类别最多的

    for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树
        Tree[best_feature][item[0]] = create_tree(item[1])
    return Tree

#{'纹理': {'清晰': {'根蒂': {'蜷缩': 1, '稍蜷': {'色泽': {'青绿': 1, '乌黑': {'触感': {'硬滑': 1, '软粘': 0}}}}, '硬挺': 0}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}
def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0]
    second_dict = Tree[first_feature]
    input_first = test_data.get(first_feature)
    input_value = second_dict[input_first]
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

if __name__ == '__main__':
    #读取数据
    data = pd.read_csv('西瓜数据集2.0.csv')

    #统计每个特征的取值情况作为全局变量
    column_count = dict([(ds, list(pd.unique(data[ds]))) for ds in data.iloc[:, :-1].columns])

    #创建决策树
    dicision_Tree = create_tree(data)
    print(dicision_Tree)
    #测试数据
    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
    result = predict(dicision_Tree,test_data_2)
    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93

最后得到的决策树模型，以字典形式存储：

{'纹理': {'清晰': {'根蒂': {'蜷缩': 1, '稍蜷': {'色泽': {'浅白': 1, '青绿': 1, '乌黑': {'触感': {'硬滑': 1, '软粘': 0}}}}, '硬挺': 0}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}

1
2

随后使用测试数据进行预测：

test_data_1 = {'色泽': '青绿','根蒂' : '蜷缩','敲声' :'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
1
2

预测结果分别为：坏瓜、好瓜

二、C4.5决策树

2.1 增益率

信息增益的缺点在于对取值数目较多的属性有所偏好，举个例子：

如果把上述数据集中的编号作为一组特征，在最开始划分根节点的时候进行计算信息增益会得到如下结果：

可以看到序号作为特征信息增益远超过其他特征，因为它有17中可能的取值，每一种取值只有一个样本，即纯度达到最大（计算一下便可得信息熵为0），特征的信息增益直接等于原始数据的信息熵$Ent（D）$达到最大。

很显然，这样的偏好是及其不合理的，“序号”这样的特征根本不能作为分类依据，为了减少这种偏好带来的负面影响，C4.5决策树算法不直接使用信息增益，而是使用增益率(gain ratio)来选择最优划分属性，用公式表述为：
$$Gain\_ration(D,a)=\frac{Gain(D,a)}{IV(a)}$$
其中，$Gain(D,a)$同上文中的信息增益，而
$$IV(a)=-\sum _{v=1}^V\frac{|D^v|}{|D|}lo{g}_2\frac{|D^v|}{|D|}$$
被称为特征$a$的固有值(intrinsic value)，属性$a$的取值越多，则$IV(a)$越大，则$Gain\_ration$越小，举例：

$a$有两个取值且各占一半时，$IV(a)=1$，$a$有四个取值且各占四分之一时，$IV(a)=2$

注意，显然增益率会对可取值数目较小的特征有偏好，为了避免这个问题，C4.5并不是直接使用增益率的大小进行划分特征，而是先从候选划分特征中找出信息增益高于平均水平的属性，再从中选择增益率最高的那个特征。

在使用信息率后，上述表格变为：

在信息增益排序中，仅“序号”和“纹理”两个特征高于平均水平，随后比较两者的增益率，“纹理”的增益率高于“序号”，则在遇到“序号”这种离谱的特征时，增益率算法还是能一定程度地选择正确的特征

2.2 C4.5决策树基础代码实现

基本上和ID3一样，只是特征选取部分需要修改

注意我们这里是基础实现，尚未涉及到剪枝，数据集同ID3

import pandas as pd
import numpy as np

#计算信息熵
def cal_information_entropy(data):
    data_label = data.iloc[:,-1]
    label_class =data_label.value_counts() #总共有多少类
    Ent = 0
    for k in label_class.keys():
        p_k = label_class[k]/len(data_label)
        Ent += -p_k*np.log2(p_k)
    return Ent

#计算给定数据属性a的信息增益
def cal_information_gain(data, a):
    Ent = cal_information_entropy(data)
    feature_class = data[a].value_counts() #特征有多少种可能
    gain = 0
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        Ent_v = cal_information_entropy(data.loc[data[a] == v])
        gain += weight*Ent_v
    return Ent - gain

def cal_gain_ratio(data , a):
    #先计算固有值intrinsic_value
    IV_a = 0
    feature_class = data[a].value_counts()  # 特征有多少种可能
    for v in feature_class.keys():
        weight = feature_class[v]/data.shape[0]
        IV_a += -weight*np.log2(weight)
    gain_ration = cal_information_gain(data,a)/IV_a
    return gain_ration

#获取标签最多的那一类
def get_most_label(data):
    data_label = data.iloc[:,-1]
    label_sort = data_label.value_counts(sort=True)
    return label_sort.keys()[0]

#挑选最优特征，即在信息增益大于平均水平的特征中选取增益率最高的特征
def get_best_feature(data):
    features = data.columns[:-1]
    res = {}
    for a in features:
        temp = cal_information_gain(data, a)
        gain_ration = cal_gain_ratio(data,a)
        res[a] = (temp,gain_ration)
    res = sorted(res.items(),key=lambda x:x[1][0],reverse=True) #按信息增益排名
    res_avg = sum([x[1][0] for x in res])/len(res) #信息增益平均水平
    good_res = [x for x in res if x[1][0] >= res_avg] #选取信息增益高于平均水平的特征
    result =sorted(good_res,key=lambda x:x[1][1],reverse=True) #将信息增益高的特征按照增益率进行排名
    return result[0][0] #返回高信息增益中增益率最大的特征

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列
def drop_exist_feature(data, best_feature):
    attr = pd.unique(data[best_feature])
    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
    return new_data

#创建决策树
def create_tree(data):
    data_label = data.iloc[:,-1]
    if len(data_label.value_counts()) == 1: #只有一类
        return data_label.values[0]
    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果
        return get_most_label(data)
    best_feature = get_best_feature(data) #根据信息增益得到的最优划分特征
    Tree = {best_feature:{}} #用字典形式存储决策树
    exist_vals = pd.unique(data[best_feature])  # 当前数据下最佳特征的取值
    if len(exist_vals) != len(column_count[best_feature]):  # 如果特征的取值相比于原来的少了
        no_exist_attr = set(column_count[best_feature]) - set(exist_vals)  # 少的那些特征
        for no_feat in no_exist_attr:
            Tree[best_feature][no_feat] = get_most_label(data)  # 缺失的特征分类为当前类别最多的
    for item in drop_exist_feature(data,best_feature): #根据特征值的不同递归创建决策树
        Tree[best_feature][item[0]] = create_tree(item[1])
    return Tree

def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0]
    second_dict = Tree[first_feature]
    input_first = test_data.get(first_feature)
    input_value = second_dict[input_first]
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

if __name__ == '__main__':
    #读取数据
    data = pd.read_csv('西瓜数据集2.0.csv')
    # 统计每个特征的取值情况作为全局变量
    column_count = dict([(ds, list(pd.unique(data[ds]))) for ds in data.iloc[:, :-1].columns])

    #创建决策树
    dicision_Tree = create_tree(data)
    print(dicision_Tree)
    #测试数据
    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
    result = predict(dicision_Tree,test_data_2)
    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

结果：

{'纹理': {'清晰': {'触感': {'硬滑': 1, '软粘': {'色泽': {'浅白': 0, '青绿': {'根蒂': {'蜷缩': 1, '稍蜷': 1, '硬挺': 0}}, '乌黑': 0}}}}, '稍糊': {'触感': {'软粘': 1, '硬滑': 0}}, '模糊': 0}}

1
2

三、CART决策树

3.1 基尼指数

CART决策树与前面两个都不同，它采用基尼指数划分属性，计算公式如下：
G i n i ( D ) = ∑ k = 1 ∣ y ∣ p k ( 1 − p k ) = 1 − ∑ k = 1 ∣ y ∣ p k 2

$$\begin{aligned} Gini(D) &= \displaystyle\sum_{k=1}^{|y|}p_k(1-p_k) \\&= 1-\displaystyle\sum_{k=1}^{|y|}p_k^2 \end{aligned}$$ Gini(D)​=k=1∑∣y∣​pk​(1−pk​)=1−k=1∑∣y∣​pk2​​
$|y|$表示类别个数

当做二分类时，公式可以简化为：
$$Gini(D)=2p(1-p)$$
从公式上来理解，基尼指数表示了在样本中随机抽两个样本，其类别不一样的概率，值越小说明一个类别明显多于另一个类别，纯度越高。

举个例子：当二分类样本对半分的时候，基尼指数为0.5，而样本46开的时候，基尼指数为0.48

当我们划分属性时，需要对基尼指数赋予不同的权重（与前面的信息增益样本权重一致），且需要寻找每个特征的每个取值的基尼系数，如计算A特征取值为a的基尼指数：
$$Gini\_index(D,A,a)=\frac{|D_1|}{|D|}Gini(D_1)+\frac{|D_2|}{|D|}Gini(D_2)$$
这里$D_1$和$D_2$指的是根据取值$v$对$D$的划分子集，即：

$D_1=｛(x,y)\in D|A(x)=a｝,D_2=D-D_1$

在划分属性时，选择划分后基尼指数最小的属性作为最优划分属性

2022.3.31更新：在之前的代码实现中，我犯了一个错误，现在修正如下：

首先CART是一棵二叉树，所以不能按照之前的决策树一样将每个特征的取值列举出来往下衍生，需要挑选一个基尼指数最小的取值作为最优切分点，这一点西瓜书并没有提到，详细可以看看《统计学习方法》第二版第84页的例子。详细点说就是需要单独计算每个特征的每个取值的基尼指数，先比较特征之间的基尼指数，再比较基尼指数最小的特征中各个取值的基尼指数，并作为最优切分点，其他取值并入一起。

3.2 CART决策树基础代码实现

数据集同ID3数据集
更新后的代码：

import pandas as pd
import numpy as np

#计算基尼指数
def gini(data):
    data_label = data.iloc[:, -1]
    label_num = data_label.value_counts() #有几类，每一类的数量
    res = 0
    for k in label_num.keys():
        p_k = label_num[k]/len(data_label)
        res += p_k ** 2
    return 1 - res

# 计算每个特征取值的基尼指数，找出最优切分点
def gini_index(data,a):
    feature_class = data[a].value_counts()
    res = []
    for feature in feature_class.keys():
        weight = feature_class[feature]/len(data)
        gini_value = gini(data.loc[data[a] == feature])
        res.append([feature, weight * gini_value])
    res = sorted(res, key = lambda x: x[-1])
    return res[0]

#获取标签最多的那一类
def get_most_label(data):
    data_label = data.iloc[:,-1]
    label_sort = data_label.value_counts(sort=True)
    return label_sort.keys()[0]

#挑选最优特征，即基尼指数最小的特征
def get_best_feature(data):
    features = data.columns[:-1]
    res = {}
    for a in features:
        temp = gini_index(data, a) #temp是列表，【feature_value, gini】
        res[a] = temp
    res = sorted(res.items(),key=lambda x:x[1][1])
    return res[0][0], res[0][1][0]

def drop_exist_feature(data, best_feature, value, type):
    attr = pd.unique(data[best_feature]) #表示特征所有取值的数组
    if type == 1: #使用特征==value的值进行划分
        new_data = [[value], data.loc[data[best_feature] == value]]
    else:
        new_data = [attr, data.loc[data[best_feature] != value]]
    new_data[1] = new_data[1].drop([best_feature], axis=1) #删除该特征
    return new_data

#创建决策树
def create_tree(data):
    data_label = data.iloc[:,-1]
    if len(data_label.value_counts()) == 1: #只有一类
        return data_label.values[0]
    if all(len(data[i].value_counts()) == 1 for i in data.iloc[:,:-1].columns): #所有数据的特征值一样，选样本最多的类作为分类结果
        return get_most_label(data)
    best_feature, best_feature_value = get_best_feature(data) #根据信息增益得到的最优划分特征
    Tree = {best_feature:{}} #用字典形式存储决策树

    Tree[best_feature][best_feature_value] = create_tree(drop_exist_feature(data, best_feature, best_feature_value, 1)[1])
    Tree[best_feature]['Others'] = create_tree(drop_exist_feature(data, best_feature, best_feature_value, 2)[1])
    return Tree

def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0] #第一个特征
    second_dict = Tree[first_feature] #第一个特征后面的字典
    input_first = test_data.get(first_feature) #预测输入的第一个特征值是多少
    input_value = second_dict[input_first] if input_first == list(second_dict.keys())[0] else second_dict['Others'] #预测输入对应的字典
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

if __name__ == '__main__':
    #读取数据
    data = pd.read_csv('data_word.csv')

    #创建决策树
    dicision_Tree = create_tree(data)
    print(dicision_Tree)
    #测试数据
    test_data_1 = {'色泽':'青绿','根蒂':'蜷缩','敲声':'浊响','纹理':'稍糊','脐部':'凹陷','触感':'硬滑'}
    test_data_2 = {'色泽': '乌黑', '根蒂': '稍蜷', '敲声': '浊响', '纹理': '清晰', '脐部': '凹陷', '触感': '硬滑'}
    result = predict(dicision_Tree,test_data_2)
    print('分类结果为'+'好瓜'if result == 1 else '坏瓜')
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

结果：

{'根蒂': {'硬挺': 0, 'Others': {'纹理': {'模糊': 0, 'Others': {'色泽': {'浅白': {'敲声': {'浊响': 1, 'Others': 0}}, 'Others': {'触感': {'软粘': 1, 'Others': {'脐部': {'稍凹': {'敲声': {'沉闷': 0, 'Others': 1}}, 'Others': {'敲声': {'沉闷': 1, 'Others': 1}}}}}}}}}}}}

1
2

修正后的决策树：

四、决策树剪枝

剪枝分为预剪枝（prepruning）和后剪枝（postpruning），预剪枝指在决策树生成过程中对每个节点先进行估计，如果划分能带来准确率上升则划分，否者不划分节点；后剪枝则是先使用训练集生成一棵决策树，再使用测试集对其节点进行评估，若将子树替换为叶子结点能带来准确率的提升则替换。

这一部分书上有较为详尽的图例，这里不再赘述

一般情况下，后剪枝的欠拟合风险小，泛化能力优于预剪枝，这里我们仅实现后剪枝。

为了保持和西瓜书上的决策树一致，我们直接输入书上的决策树进行剪枝。

注意这里有几个要点：

• 字典传入函数后在函数内进行修改，即使没有返回值原本的字典也会改变
• 在比较剪枝前后的准确率时，我们并不需要判断整棵树的预测情况，而是只需要判断当前节点为根节点的子树对于走到当前节点的部分测试集的预测情况，有点绕，读代码可能会更清晰
• 西瓜书对于后剪枝的定义为判断所有非叶子结点的剪枝预测情况，所以即使一个节点的子树已经判断剪枝或是没有剪枝，该节点都要再次判断。

剪枝数据集：和西瓜书一样，分为train和test
链接：百度网盘自取
提取码：pt8q

import pandas as pd
import numpy as np

##将数据转化为（属性值：数据）的元组形式返回，并删除之前的特征列
def drop_exist_feature(data, best_feature):
    attr = pd.unique(data[best_feature])
    new_data = [(nd, data[data[best_feature] == nd]) for nd in attr]
    new_data = [(n[0], n[1].drop([best_feature], axis=1)) for n in new_data]
    return new_data

# 预测单条数据
def predict(Tree , test_data):
    first_feature = list(Tree.keys())[0]
    second_dict = Tree[first_feature]
    input_first = test_data.get(first_feature)
    input_value = second_dict[input_first]
    if isinstance(input_value , dict): #判断分支还是不是字典
        class_label = predict(input_value, test_data)
    else:
        class_label = input_value
    return class_label

#测试很多案例，话返回准确率
def predict_more(Tree, test_data, test_label):
    cnt = 0
    #计算如果该节点不剪枝的准确率
    for i in range(len(test_data)):
        after_data = test_data.reset_index().loc[i].to_dict()
        pred = predict(Tree,  after_data)
        if pred == test_label[i]:
            cnt += 1
    return cnt / len(test_label)

#用于预测节点剪枝后的预测正确数
def equalNums(label, featPreLabel):
    res = 0
    for l in label:
        if l == featPreLabel:
            res += 1
    return res

# 后剪枝
def post_prunning(tree , test_data , test_label , names):
    newTree = tree.copy() #copy是浅拷贝
    names = np.asarray(names)
    # 取决策节点的名称 即特征的名称
    featName = list(tree.keys())[0]
    # 取特征的列
    featCol = np.argwhere(names == featName)[0][0]
    names = np.delete(names, [featCol]) #删掉使用过的特征
    newTree[featName] = tree[featName].copy() #取值
    featValueDict = newTree[featName] #当前特征下面的取值情况
    featPreLabel = featValueDict.pop("prun_label") #如果当前节点剪枝的话是什么标签，并删除_vpdl

    # 分割测试数据 如果有数据 则进行测试或递归调用:
    split_data = drop_exist_feature(test_data,featName) #删除该特征，按照该特征的取值重新划分数据
    split_data = dict(split_data)

    for featValue in featValueDict.keys(): #每个特征的值
        if type(featValueDict[featValue]) == dict: #如果下一层还是字典，说明还是子树

            split_data_feature = split_data[featValue] #特征某个取值的数据，如“脐部”特征值为“凹陷”的数据
            split_data_lable = split_data[featValue].iloc[:, -1].values
            # 递归到下一个节点
            newTree[featName][featValue] = post_prunning(featValueDict[featValue],split_data_feature,split_data_lable,split_data_feature.columns)

    # 根据准确率判断是否剪枝，注意这里的准确率是到达该节点数据预测正确的准确率，而不是整体数据集的准确率
    # 因为在修改当前节点时，走到其他节点的数据的预测结果是不变的，所以只需要计算走到当前节点的数据预测对了没有即可
    ratioPreDivision = equalNums(test_label, featPreLabel) / test_label.size #判断测试集的数据如果剪枝的准确率

    #计算如果该节点不剪枝的准确率
    ratioAfterDivision = predict_more(newTree, test_data, test_label)

    if ratioAfterDivision < ratioPreDivision:
        newTree = featPreLabel # 返回剪枝结果，其实也就是走到当前节点的数据最多的那一类

    return newTree

if __name__ == '__main__':
    #读取数据
    train_data = pd.read_csv('./train_data.csv')
    test_data = pd.read_csv('./test_data.csv')
    test_data_label = test_data.iloc[:, -1].values
    names = test_data.columns

    dicision_Tree = {"脐部": {"prun_label": 1
                                   , '凹陷': {'色泽':{"prun_label": 1, '青绿': 1, '乌黑': 1, '浅白': 0}}
                                   , '稍凹': {'根蒂':{"prun_label": 1
                                                  , '稍蜷': {'色泽': {"prun_label": 1
                                                                  , '青绿': 1
                                                                  , '乌黑': {'纹理': {"prun_label": 1
                                                                               , '稍糊': 1, '清晰': 0, '模糊': 1}}
                                                                  , '浅白': 1}}
                                                  , '蜷缩': 0
                                                  , '硬挺': 1}}
                                   , '平坦': 0}}
    print('剪枝前的决策树:')
    print(dicision_Tree)
    print('剪枝前的测试集准确率: {}'.format(predict_more(dicision_Tree, test_data, test_data_label)))

    print('-'*20  + '剪枝' + '-'*20)
    new_tree = post_prunning(dicision_Tree,test_data , test_data_label , names)
    print('剪枝后的决策树:')
    print(new_tree)
    print('剪枝后的测试集准确率: {}'.format(predict_more(new_tree, test_data, test_data_label)))
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

后剪枝结果，并对整体测试集数据进行预测：

剪枝后决策树不仅更加轻量，而且对于测试集的预测准确率从0.428提升到了0.714

与课本上后剪枝的决策树一致

与课本上后剪枝的决策树一致。

五、连续值决策树、缺失值决策树

已更新周志华《机器学习》中的连续值处理与缺失值处理部分，代码为我的另一篇博客 https://blog.csdn.net/qq_43601378/article/details/124050140?spm=1001.2014.3001.5501

六、参考文献及联系方式

参考文献：

李航《统计学习方法》

周志华《机器学习》

博客1： https://blog.csdn.net/ylhlly/article/details/93213633

博客2：https://www.bbsmax.com/A/gGdXyQA1z4/

如有问题欢迎评论区只出，也可邮件联系：

1759412770@qq.com