机器学习04:创建决策树

  • 发布时间:2017年1月23日 16:38
  • 作者:杨仕航

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


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

20170123/20170123093858623.png

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


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

1)收集数据:可以使用任何方法

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

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

4)训练算法:构造树的数据结构

5)测试算法:计算错误率

6)使用算法

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


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

20170123/20170123101444217.png

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

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


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

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

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

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

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

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

20170123/20170123104629518.png

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


创建一个文件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个元素是该数据的分类,是否为鱼类。


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

20170123/20170123145403513.png

再比较 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)

得到如下图结果。

20170123/20170123161806567.png

该决策树是一个字典,入口只有一个特征判断。特征判断内容为键名,键值是结果字典。该字典键名是判断分支,键值是判断结果。判断结果只有两种情况: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))

测试结果如下:

20170123/20170123163627386.png

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

点击查看相关目录

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

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

相关专题: 机器学习实战   

评论列表

1271787323@qq.com

1271787323@qq.com

😕

2018-06-01 18:20 回复

新的评论

清空

猜你喜欢

  • 猜测中,请稍等...