《机器学习实战》第2个算法是决策树。本来觉得该算法没什么，因为决策树原理很简单，实践也不复杂。仔细一看，原来它还包含自动构建较优的决策树，并绘制决策树。

决策树同样是一个分类算法。其概念和原理都比较简单，看下图就明白了。

根据不同的特征进行判断，可以很快得到结果。比较适合对数值型和标称型的数据分类。

再看看决策树的一般流程，就可以开始我们的实例讲解。

1）收集数据：可以使用任何方法

2）准备数据：树构造算法只使用于标称型数据，因此数值型数据必须离散化

3）分析数据：可以使用任何方法。构造树完成之后，还需检查图形是否符合预期的效果

4）训练算法：构造树的数据结构

5）测试算法：计算错误率

6）使用算法

这里需要说明一下，决策树算法划分数据有不少方法。书中采用ID3算法(我刚开始也不知道这是什么鬼)。

第1、2步，我们就直接略过，采用书中的数据：

根据前面两个特征：不浮出水面是否可以生存、是否有脚蹼，判断是否属于鱼类。

当然，这里的特征可以更多。

第3步，我们要分析这些数据，尝试构造决策树。

该实例有两个特征，我们要采用哪个特征作为第1个判断的标准，即判断决策的顺序应当如何才比较合适。

这个判断的顺序很重要，直接影响到运算的效率和准确性。

当然，该问题也有方法处理。

我们采用香农熵的方法确定顺序。在划分数据集（即确定顺序）前后信息会发送变化，该变化称为信息增益。

每次划分获得信息增益最高的特征就是最好的选择。

别问我香农熵计算原理是什么。我自己也只懂得怎么用，原理还不太懂。

创建一个文件tree.py，先创建该实例测试数据：

#coding:utf-8

def create_dataset():
    """创建测试数据集"""
    dataset = [
            [1,1,'yes'],
            [1,1,'yes'],
            [1,0,'no'],
            [0,1,'no'],
            [0,1,'no'],
        ]
    labels = ['no surfacing', 'filppers']
    return dataset, labels

其中，dataset每个元素都是一个3元素的列表。第1个元素对应第1个特征（no surfacing：无浮出水面），第2个元素对应第2个特征（flippers：有脚蹼）。第3个元素是该数据的分类，是否为鱼类。

接下来，需要确认判断顺序。利用香农熵确认顺序的方法如下。

再比较 base-entropy1 和 base-entropy2 的大小。取差值最大的特征，则是增益最多的。

若还有第3个，第4个特征。则需要再增益最大的结果继续判断下去，直到确定全部顺序。

确定一个数据集下，哪个特征最优的代码如下：

# -*- coding: utf-8 -*-
from math import log

#计算香农熵(dataset，每行最后一个值是类名)
def _calc_entropy(dataset):
    num = len(dataset)
    label_count = {}

    for vect in dataset:
        label = vect[-1]
        label_count[label] = label_count.get(label, 0.) +1

    entropy = 0.
    for key,value in label_count.items():
        prob = value/num #出现的概率
        entropy -= prob * log(prob, 2)
    return entropy

#划分数据集，剔除某一列的数据
def _filter_dataset(dataset, axis, value):
    re_dataset = []
    for vect in dataset:
        if vect[axis] == value:
            reduced_vect = vect[:axis] + vect[axis+1:] #移除元素
            re_dataset.append(reduced_vect)
    return re_dataset

#获取最好的划分方式
def best_split(dataset):
    axis_num = len(dataset[0]) - 1 #特征个数
    base_entropy = _calc_entropy(dataset)
    base_len = float(len(dataset))

    best_info_gain = 0.
    best_feature = -1

    for i in range(axis_num):
        feat_list = [x[i] for x in dataset] #特征值列表
        feat_list = set(feat_list) #去重

        new_entropy = 0.
        for value in feat_list:
            sub_dataset = _filter_dataset(dataset, i, value)
            prob = len(sub_dataset)/base_len #比例
            new_entropy += prob * _calc_entropy(sub_dataset)
        
        #计算信息增益，并对比找到增益最多的特征
        info_gain = base_entropy - new_entropy
        if info_gain > best_info_gain:
            best_info_gain = info_gain
            best_feature = i
    return best_feature

确定全部特征顺序，即可确定整个决策树，添加创建树的代码：

#返回最多数量的类别
def _majority_cnt(class_list):
    class_count={}
    for vote in class_list:
        class_count[vote] = class_count.get(vote,0)+1
    return max(class_count.iteritems(), key = lambda x:x[1])[0]

#创建树
def create_tree(dataset, labels):
    class_list = [x[-1] for x in dataset] #获取每条数据的类别
    #若类别一样，就停止分类
    if class_list.count(class_list[0]) == len(class_list):
        return class_list[0]
    #若无数据，则返回最多数量的类别？
    if len(dataset[0]) == 1:
        return _majority_cnt(class_list)

    #获取第1个分类特征
    best_feat_axis = best_split(dataset)
    best_feat_label = labels[best_feat_axis]

    mytree = {best_feat_label:{}}
    del(labels[best_feat_axis])

    #获取剩下的特征顺序
    feat_values = [x[best_feat_axis] for x in dataset]
    unique_vals = set(feat_values)
    for value in unique_vals:
        #复制一个标签集
        sub_labels = labels[:] 
        #递归处理
        mytree[best_feat_label][value] = create_tree(_filter_dataset(dataset, best_feat_axis, value), sub_labels)
    return mytree

再加一段测试代码，运行一下：

if __name__ == '__main__':
    dataset, labels = create_dataset()
    mytree = create_tree(dataset,labels[:])

    print(mytree)

得到如下图结果。

该决策树是一个字典，入口只有一个特征判断。特征判断内容为键名，键值是结果字典。该字典键名是判断分支，键值是判断结果。判断结果只有两种情况：1、分类；2、下一个判断条件。

该决策树看起来不直观，下个博文写如何画决策树以及如何保存该树结构。

可以先使用一些数据测试一下。写一个方法使用该决策树：

#利用决策树分类 classify(tree, labels, [1,0])
def classify(tree, labels, vect):
    sub_key = tree.keys()[0]
    sub_dict = tree[sub_key]

    index = labels.index(sub_key) #获取特征所在的位置
    value = sub_dict[vect[index]] #获取树对应的值

    #判断对应位置下的类别，若该类别是字典，则继续递归
    if isinstance(value, dict):
        class_label = classify(value, labels, vect)
    else:
        class_label = value
    return class_label

在__name__部分加入测试代码：

#测试
test_vects = [[0,0],[0,1],[1,0],[1,1]]
for vect in test_vects:
    result = classify(mytree, labels, vect)
    print('%s:%s' % (vect, result))

测试结果如下：

该分类结果和训练集的结果一致。下篇博文讲如何绘制决策树以及保存决策树。

点击查看相关目录。

上一篇：机器学习05：绘制决策树

下一篇：我的网站搭建(第42天) 添加公告和打赏

相关专题： 机器学习实战