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

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

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

H=−∑ni=1p(xi)log2p(xi)$H=-\sum _{i=1}^{n}p(x_i)lo{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)

此时的返回如下：

可以看出返回的是原数据集中第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。最后，我们就可以用之前的代码来创建决策树了，创建树的代码如下：

'''
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)

输出的结果如下：

该结果是一颗如下图所示的树：

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

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()

最后结果如下：

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