机器学习（二）：决策树之ID3

我会带着你远行 2022-05-23 05:15 246阅读 0赞

文中的代码和数据集下载地址：  
[https://github.com/TimePickerWang/MachineLearningInAction][https_github.com_TimePickerWang_MachineLearningInAction]

介绍决策树之前先介绍两个信息论里的概念：熵和信息增益。  
1.熵：代表了信息的混乱程度。也就是说熵越高，混合的数据越多，越无序。熵的计算方式如下（其中p(xi)  p ( x i ) 是样本为某一类别的概率。）：

H=−∑ni=1p(xi)log2p(xi)  H = − ∑ i = 1 n p ( x i ) l o g 2 p ( x i )

2.信息增益：信息增益可以理解为熵的减少或者说是数据无序度的减少。在划分数据时。为了使划分后数据的熵减少，我们需要选择信息增益最高的特征来划分数据。

决策树的创建过程描述如下，记为creatBranch()方法：

检测数据中的每个样本是否属于同一类别
        如果是，返回类标签
        否则执行以下步骤：
            选择信息增益最高的特征
            划分数据集
            创建分支节点
                对于划分后的每个子集调用creatBranch()进行递归操作
            返回分支节点

下面直接上计算熵的代码：

from math import log
    
    ''' 计算香农熵 Input: data_set: 需要计算熵的m个样本，每个样本向量的最后一列是类别 Output:香农熵的值 '''
    def calc_shannonEnt(data_set):
        m = len(data_set)
        lable_counts = {}
        for featVec in data_set:
            current_lable = featVec[-1]
            lable_counts[current_lable] = lable_counts.get(current_lable, 0) + 1
        shannon_ent = 0
        for key in lable_counts:
            prob = float(lable_counts[key])/m
            shannon_ent -= prob * log(prob, 2)
        return shannon_ent

为了方便计算熵，以上代码用一个字典记录了样本中数据的类别及其出现的次数。传入的数据是一个样本集，每个样本看成一个向量，样本向量的最后一列是该样本所属的类别。

ID3在每次划分数据时，会根据获得信息增益最大的特征来划分数据。并且在每次划分数据后，会删除该特征。然后把剩下的数据作为创建子树的数据重新进行划分，直到所有特征划分完毕。以下代码是通过某一特征来划分数据集，返回的是划分后的数据集：

''' 划分数据集 Input: data_set: 待划分的数据集 axis：划分数据集的特征 value：需要返回的特征的值 Output:划分后的数据集 '''
    def split_dataSet(data_set, axis, value):
        ret_data_set = []
        for feat_vec in data_set:
            if feat_vec[axis] == value:
                reduced_feat_vec = feat_vec[:axis]
                reduced_feat_vec += feat_vec[axis+1:]
                ret_data_set.append(reduced_feat_vec)
        return ret_data_set

为了直观感受以下，假设有如下数据集调用了split\_dataSet()方法：

data_set = [[0, 1, 0, 0, 'yes'],
                [1, 1, 0, 0, 'yes'],
                [0, 1, 1, 0, 'yes'],
                [0, 0, 1, 0, 'yes'],
                [1, 0, 0, 0, 'yes'],
                [0, 0, 1, 0, 'yes'],
                [0, 0, 0, 0, 'no'],
                [1, 1, 1, 1, 'no'],
                [0, 0, 0, 1, 'no'],
                [0, 1, 1, 1, 'no'],
                [0, 1, 0, 1, 'no']]
    
    split_dataSet(data_set, 1, 0)

此时的返回如下：

![这里写图片描述][70]

可以看出返回的是原数据集中第2个特征为0，并把第二个特征删除后的数据。

知道了熵的计算方式和划分数据的方式，接下来需要通过获得信息增益最高的特征来划分数据了。代码如下：

''' Input: data_set: 待划分的数据集 Output:划分结果最好（划分后信息增益最高）的特征索引 '''
    def choose_best_feature_to_split(data_set):
        feature_num = len(data_set[0]) - 1  # 特征的个数
        m = len(data_set)  # 样本数
        base_entropy = calc_shannonEnt(data_set)  # 经验熵
        best_info_gain = 0.0  # 最好的信息增益值
        best_feature = -1  # 划分后信息增益最高的特征索引值
        for i in range(feature_num):
            # 数据集中所有第i个特征的值存到feat_list中
            feat_list = [example[i] for example in data_set]
            unique_feat = set(feat_list)
            new_entropy = 0.0  # 条件熵
            for feature in unique_feat:
                # 根据第i个特征划分数据
                sub_data_set = split_dataSet(data_set, i, feature)
                prob = len(sub_data_set)/m
                new_entropy += prob * calc_shannonEnt(sub_data_set)
            info_gain = base_entropy - new_entropy
            if info_gain > best_info_gain:
                best_info_gain = info_gain
                best_feature = i
        return best_feature

以上代码仅仅进行了一次数据的划分。首先计算了一下数据划分前的熵，然后遍历数据集的每一个特征，通过某一特征的所有可能取值调用split\_dataSet()方法来划分数据，并计算划分数据后的熵之和。将划分数据前后的两个熵香减即是信息增益，用变量best\_feature保存获得信息增益最大时划分特征的索引，在遍历完所有特征后返回，此时best\_feature的值即是划分数据最好的方式。

要创建一颗决策树，仅仅进行一次划分是不够的，我们需要用完所有的特征。但如果我们用完所有的特征后，数据的类标签依然存在多个，这时我们需要结合kNN中多数表决的方式确定某一样本的类别。多数表决的方式如下：

''' Input: class_list: 分类名称的列表 Output:通过投票机制，返回出现次数最多的分类名称 '''
    def majority_label(class_list):
        class_count = {}
        for vote in class_list:
            class_count[vote] = class_count.get(vote, 0) + 1
        sorted_class_count = sorted(class_count.items(), key=lambda item: item[1], reverse=True)
        return sorted_class_count[0][0]

上述方法传入的是一个类别向量（也就是数据集中最后一列值组成的向量），是一个行向量。对sorted()方法不了解的可以看我另一篇博客[一：细说python3中sort和sorted][python3_sort_sorted]。最后，我们就可以用之前的代码来创建决策树了，创建树的代码如下：

''' Input: data_set: 待划分的数据集 labels:标签列表 Output:表示决策树结构的字典 '''
    def creat_tree(data_set, labels):
        class_list = [example[-1] for example in data_set]
        # 若所有的类标签完全相同，直接返回该类标签
        if class_list.count(class_list[0]) == len(class_list):
            return class_list[0]
        # 若使用完所有特征仍不能将数据划分成包含唯一类别的分组，则通过投票机制选出现次数最多的类别作为返回
        if len(data_set[0]) == 1:
            return majority_label(class_list)
        best_feature = choose_best_feature_to_split(data_set)
        best_feature_label = labels[best_feature]
        my_tree = {best_feature_label: {}}
        del labels[best_feature]
        feature_values = [example[best_feature] for example in data_set]
        unique_feature = set(feature_values)
        for value in unique_feature:
            sub_lables = labels[:]
            my_tree[best_feature_label][value] = creat_tree(
                split_dataSet(data_set, best_feature, value), sub_lables)
        return my_tree

以上代码中，用字典来保存树的所有信息。划分数据最好方式的特征索引用变量best\_feature来保存，然后通过该特征的所有来划分数据，创建子树。该方法的放回有两种情况：1.最后的类标签。2.保存子树信息的字典。

好了，接下来通过一些简单的测试数据来试试该算法，测试数据如下：

def test_fun():
        data_set = [[0, 1, 0, 0, 'yes'],
                    [1, 1, 0, 0, 'yes'],
                    [0, 1, 1, 0, 'yes'],
                    [0, 0, 1, 0, 'yes'],
                    [1, 0, 0, 0, 'yes'],
                    [0, 0, 1, 0, 'yes'],
                    [0, 0, 0, 0, 'no'],
                    [1, 1, 1, 1, 'no'],
                    [0, 0, 0, 1, 'no'],
                    [0, 1, 1, 1, 'no'],
                    [0, 1, 0, 1, 'no']]
        labels = ["have care", "have house", "have money", "have wife"]
        tree = creat_tree(data_set, labels[:])
        print(tree)

输出的结果如下：  
![这里写图片描述][70 1]

该结果是一颗如下图所示的树：  
![这里写图片描述][70 2]

决策树的一大优点就是我们可以把树结构序列化之后保存起来，这样在分类数据时就不用每次都计算来建造树了，序列化和反序列化的代码如下：

import pickle
    
    ''' Input: input_tree: 表示决策树结构的字典 filename: 需要存储的文件名 '''
    # 将字典类型的树结构序列化后存储在文件中
    def store_tree(input_tree, filename = "./testTree.txt"):
        fw = open(filename, 'wb')  # 以二进制格式打开一个文件只用于写入。
        pickle.dump(input_tree, fw)
        fw.close()
    
    
    ''' Input: filename: 需要读取的文件名 Output: 决策树字典 '''
    def grab_tree(filename = "./testTree.txt"):
        fr = open(filename, "rb")
        return pickle.load(fr)

需要注意的是，这里序列化和反序列化都需要用二进制格式打开文件，这里书上的代码有问题。这里文件的路径默认为当前路径下的testTree.txt文件。

当跟新数据进行分时的代码如下：

''' Input: input_tree: 表示决策树结构的字典 feat_labels: 标签列表 test_vec：待测试的向量 Output:分类结果 '''
    def classify(input_tree, feat_labels, test_vec):
        first_fect = list(input_tree.keys())[0]
        second_dict = input_tree[first_fect]
        feat_index = feat_labels.index(first_fect)
        for key in second_dict.keys():
            if test_vec[feat_index] == key:
                if type(second_dict[key]).__name__ == 'dict':
                    class_lable = classify(second_dict[key], feat_labels, test_vec)
                else:
                    class_lable = second_dict[key]
        return class_lable

这也是一个递归的函数，需要判断某一结点是叶子结点函数子树。如果是子树，则该结点的类型为字典类型。

好了， 现在我们将以上测试数据先保存起来，然后通过反序列化，直接通过保存好的决策树树来根新样本分类。代码如下：

# 分类测试数据
    def classify_test_data():
        tree = grab_tree()
        test_vec1 = [1, 0, 1, 0]
        test_vec2 = [0, 1, 0, 1]
        labels = ["has care", "has house", "has money", "has wife"]
        print("分类结果：" + classify(tree, labels, test_vec1))
        print("分类结果：" + classify(tree, labels, test_vec2))
    
    classify_test_data()

最后结果如下：

![这里写图片描述][70 3]

在书上还提到了将决策树的结构画出来，这里不做议论，书中还有一个预测隐形眼镜类型的例子，其数据集和代码我在开始已经放出来了，可以去下载，顺便点个星星支持一下，^\_^。

[https_github.com_TimePickerWang_MachineLearningInAction]: https://github.com/TimePickerWang/MachineLearningInAction
[70]: /images/20220523/e85a2fad9f694115bb6db25c678f85b1.png
[python3_sort_sorted]: https://blog.csdn.net/wang454592297/article/details/79887218
[70 1]: /images/20220523/312b0de270534078867727525895de9f.png
[70 2]: /images/20220523/51ea4b4525424f3f9c6fa4aa7f87c514.png
[70 3]: /images/20220523/5db4c0f0bad9475496bd6e21e34af730.png