Decision Tree In MNIST

发表于 | 分类于

Decision Tree In MNIST

决策树作为机器学习算法的基础算法之一，其优点是模型具有可读性，分类速度快。决策树的基本算法可以参考李航老师的《统计机器学习》,本文中的主要思路也是基于此。对于决策树而言，主要有三部分的工作需要实现，特征提取，决策树构造和决策树的剪枝。在特征提取部分，常用的是信息增益和信息增益比，分别对应于ID3和C4.5决策树算法；决策树的构造部分主要是利用递归的思想构建；本文中未涉及到决策树剪枝部分。

本文中实现的是利用信息增益进行特征提取的ID3决策树，主要需要提及的部分是关于树的节点构造的部分。树的节点中主要包含了节点类型，包括叶节点和内部节点，用于在预测过程中当预测到达叶节点时，返回所属类别；也包含了节点所属类别(只针对叶节点存在)；包含当前节点的最优切分位置(对于非叶节点存在)；以及切分位置取不同值所属的不同子树，用字典保存。

基本思路是：我们在函数中输入训练数据，训练标签，可切分维度集合和信息增益阈值。

  • 首先判断当前训练标签的类数，如果只有一类，我们将其设置为叶节点，节点类别取当前标签，然后返回；然后判断可切分维度的数量，如果不存在切分维度，则取当前训练标签中的最多那一类作为节点的类别，设置节点为叶节点返回；

  • 以上情况都不符合的情况下，我们遍历所有的切分点，找到信息增益最大的位置，提取出这一列的值；并根据这一列的不同取值所对应的标签得到下一步的训练数据、训练标签和切分维度集合用于构建子树，并将子树添加到当前树中。

  • 然后不断的递归调用即可
  • 其中在找到最大信息增益位置的最后需要判断和阈值的关系，在小于阈值的情况下，我们直接构建叶节点和所属类别返回。

代码如下：

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
import numpy as np
import math
import pandas as pd
from collections import Counter
# 容易混淆的是，feature是指用特征中的哪一维进行切分
# index是指当前还剩下可以用于切分的维数的集合
class Tree(object):
    def __init__(self, node_type, category=None, feature=None):
        self.node_type = node_type
        # 节点类型，分为内部节点和叶节点
        self.category = category
        # 如果是叶节点的情况，该值记录节点的所属类别
        self.feature = feature
        # 如果是内部节点，该值记录切分位置
        self.dic = {}
        # 用来保存切分点不同取值所对应的子树
    def add_tree(self, value, tree):
        self.dic[value] = tree
        # 将子树添加到当前树中
    def predict(self, index_list):
        if self.node_type == "lef":
            return self.category
        tree = self.dic[index_list[self.feature]]
        return tree.predict(index_list)
        # 预测给定特征的所属类别
def binary(data, threshold):
    """
    :param data: 需要二值化的数据
    :param threshold: 二值化的阈值
    :return: 二值化后的数据
    """
    data[data > threshold] = 255
    data[data <= threshold] = 0
    return data
def calculate_entropy(x):
    """
    :param x: 待计算的特征向量
    :return: 返回特征向量的熵
    """
    catogory_list = set(x)
    ent = 0
    for catogory in catogory_list:
        probability = x[x == catogory].shape[0] / x.shape[0]
        ent = ent + probability * math.log2(probability)
    return -1 * ent
def conditonal_entropy(x, y):
    """
    :param x: 条件特征向量
    :param y: 标签特征向量
    :return: 返回条件熵
    """
    catogory_list = set(x)
    conditional_ent = 0
    for catogory in catogory_list:
        sub_set = y[x == catogory]
        conditional_ent += (sub_set.shape[0] / x.shape[0]) * calculate_entropy(sub_set)
    return conditional_ent
def information_gain(x, y):
    """
    :return: 返回信息增益
    """
    return calculate_entropy(y) - conditonal_entropy(x, y)
def recursive_train(train_data, train_label, index, threashold):
    """
    :param train_data: 训练数据
    :param train_label: 训练的标签
    :param index: 特征的索引列表
    :param threashold: 阈值
    :return: 决策树头结点
    """
    most_common = Counter(train_label).most_common(1)
    # 得到标签中出现最多的类别
    max_infor_gain = 0
    # 记录最大信息增益
    max_entropy_index = 0
    # 记录最大信息增益所属的列
    if len(set(train_label)) == 1:
        return Tree("lef", category=train_label[0])
    # 如果当前标签只有一类的情况
    if len(index) == 0:
        return Tree("lef", category=most_common[0][0])
    # 如果没有可以继续切分的特征
    for col in index:
        condition_data = train_data[:, col]
        current_gain = information_gain(condition_data, train_label)
        # 找到每个切分点计算信息增益
        if current_gain > max_infor_gain:
            max_infor_gain = current_gain
            max_entropy_index = col
        # 找到最大的信息增益和其对应的列
    if max_infor_gain < threashold:
        return Tree("lef", category=most_common[0][0])
    # 如果小于阈值，直接返回叶节点，类别取出现最多的那个标签
    tree = Tree("internal", feature=max_entropy_index)
    # 构建树，节点类型为内部节点，切分点最大信息增益切分
    max_feature_list = train_data[:, max_entropy_index]
    # 提取出用于切分的那一列
    feature_value_list = set(max_feature_list)
    # 找到切分列中的不同取值列表
    next_index = list(filter(lambda x: x != max_entropy_index, index))
    # 得到子树的切分列表
    for value in feature_value_list:
        next_train_set = train_data[max_feature_list == value]
        # 得到子树的训练集
        next_train_label = train_label[max_feature_list == value]
        # 子树的训练标签
        next_tree = recursive_train(next_train_set, next_train_label, next_index, threashold)
        # 得到子树
        tree.add_tree(value, next_tree)
        # 将子树按照不同的切分值添加到当前树中
    return tree
if __name__ == '__main__':
    raw_path = r'F:\work and learn\ML\dataset\MNIST\train.csv'
    # 原始数据
    test_path = r'F:\work and learn\ML\dataset\MNIST\test.csv'
    # 训练数据
    index = [i for i in range(784)]
    # 初始的切分标签列表
    raw_data = np.loadtxt(raw_path, delimiter=',', skiprows=1)
    label = raw_data[:, 0]
    data = raw_data[:, 1:]
    # 得到标签和训练数据
    data = binary(data, 100)
    tree = recursive_train(data, label, index, 0.1)
    # 二值化后进行训练
    test_data = np.loadtxt(test_path, delimiter=',', skiprows=1)
    test_data = binary(test_data, 100)
    # 得到测试数据，并进行二值化
    result = []
    for i in range(test_data.shape[0]):
        print(i)
        result.append(tree.predict(test_data[i]))
    # 对于每个训练数据进行预测其所属类别
    index = [i for i in range(1, 28001)]
    res = pd.DataFrame(index, columns=['ImageId'])
    res['Label'] = result
    res.to_csv(r"C:\Users\PC\Desktop\result.csv", index=False)
    # 保存结果

对于本文中所实现的决策树在MNIST上的分类结果在Kaggle平台上测试结果为85.07%左右，相比于KNN，其分类效果要差不少，但是所需要的计算时间较少于KNN算法。