机器学习实战 | 第3章 决策树

发表于   |   更新于 | 分类于 | | 阅读数
字数统计: 3.1k

决策树的一个重要任务是：为了数据中蕴含的知识信息。
决策树可以使用不熟悉的数据集合，并从中提取除一系列规则，在这些机器根据数据集创建规则时，就是机器学习的过程。

3.1 决策树的构造

  1. 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
    缺点：可能会产生过度匹配问题。
    适用数据类型：数值型和标称型。
  2. 在构造决策树时，我们需要解决的第一个问题是：当前数据集上哪个特征在划分数据分类时起决定性作用。
    为了找到决定性特征，划分出最好的结果，我们必须评估每个特征。
    完成测试之后，原始数据集就被划分为几个数据子集。
    这些数据子集会分布在第一个决策点的所有分支上。
    如果某分支上的数据属于同一类型，无需进一步对数据集进行分割。
    如果数据子集内的数据不属于同一类型，则需要重复划分数据子集。
    直到所有具有相同数据类型的数据均在一个数据子集内。
  3. 创建分支的伪代码函数createBranch()：
    创建分支的伪代码函数
  4. 决策树的一般流程：
    (1) 收集数据：可以使用任何方法。
    (2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
    (3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
    (4) 训练算法：构造树的数据结构。
    (5) 测试算法：使用经验树计算错误率。
    (6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据
    的内在含义。

3.1.1 信息增益

  1. 划分数据集的大原则：将无序的数据变得更加有序。
  2. 信息增益：划分数据集之前之后信息发生的变化。获得信息增益最高的特征就是最好的选择。
  3. 香农熵（熵）：集合信息的度量方式。
  4. 熵：定义为信息的期望值。
  5. 信息：符号xi的信息定义：
    信息
    其中p(xi)是选择该分类的概率。
  6. 信息熵：信息熵
    其中n是分类的数目。
  7. 基尼不纯度：度量集合无序程度的方法。简单的说就是从一个数据集中随机选取子项，度量其被错误分类到其他组里的概率。

程序清单3-1 计算给定数据集的香农熵

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
from math import log
from numpy import *
import operator
import matplotlib.pyplot as plt

# 为所有可能分类创建字典
def cal_entropy(data):
    entries_num = len(data)
    label_count = {}
    for vec in data:
        cur_label = vec[-1]
        label_count[cur_label] = label_count.get(cur_label,0)+1
    Entropy =0.0
    
    # 以2为底求对数
    for key in label_count:
        prob =float(label_count[key])/entries_num
        Entropy += prob*math.log(prob,2)
    return (0-Entropy)

# 定义自己的数据集
def createData():
    data = [[1,1,'yes'],[1,1,'yes'],[1,0,'no'],[0,1,'no'],[0,1,'no']]
    labels = ['no sufacing','flippers']
    return data,labels

执行：

1
2
3
4
5
6
7
8
>import trees
>myDat,labels = trees.createData()
>myDat
>trees.cal_entropy(myDat)
# 增加第三个名为maybe的分类，测试熵的变化：
>myDat[0][-1] = 'maybe'
>myDat
>trees.cal_entropy(myDat)

3.1.2 划分数据集

  1. 使用ID3算法划分数据集。
    三组参数：待划分的数据集、划分数据集的特征、需要返回的特征的值。

程序清单3-2 按照给定特征划分数据集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def Split_Data(dataset, axis, value):
    '''
    使用传入的axis以及value划分数据集
    axis代表在每个列表中的第X位，value为用来划分的特征值
    '''
    new_subset = []
    # 利用循环将不符合value的特征值划分入另一集合
    # 相当于将value单独提取出来（或作为叶节点）
    for vec in dataset:
        if vec[axis] == value:
            feature_split = vec[:axis]
            feature_split.extend(vec[axis + 1:])
            new_subset.append(feature_split)
    # extend将vec中的元素一一纳入feature_split
    # append则将feature_split作为列表结合进目标集合
            
    return new_subset

执行：

1
2
3
4
5
6
7
8
>import trees
>myDat,labels = trees.createData()
>myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>trees.split_data(myDat,0,1)
[[1, 'yes'], [1, 'yes'], [0, 'no']]
>trees.split_data(myDat,0,0)
[[1, 'no'], [1, 'no']]
Python语言不用考虑内存分配问题。Python语言在函数中传递的是列表的引用，在函        数内部对列表对象的修改，将会影响该列表对象的整个生存周期。为了消除这个不良影响，我们需要在函数的开始声明一个新列表对象。

程序清单3-3 选择最好的数据集划分方式

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
def Split_by_entropy(dataset):
	'''
    使用熵原则进行数据集划分
    @信息增益:info_gain = old -new
    @最优特征：best_feature
    @类别集合：uniVal
    '''
    feature_num = len(dataset[0]) - 1
    ent_old = cal_entropy(dataset)
    best_gain = 0.0
    best_feature = -1
    for i in range(feature_num):
        feature_list = [x[i] for x in dataset]
        # 将dataSet中的数据先按行依次放入x中，然后取得x中的x[i]元素，放入列表feature_list中
        uniVal = set(feature_list)
        ent_new = 0.0
        # 使用set剔除重复项，保留该特征对应的不同取值
        for value in uniVal:
            sub_set = split_data(dataset, i, value)
            prob = len(sub_set) / float(len(dataset))
            # 使用熵计算函数求出划分后的熵值
            ent_new += prob * (0 - cal_entropy(sub_set))

        # 由ent_old - ent_new选出划分对应的最优特征
        Info_gain = ent_old - ent_new
        if (Info_gain > best_gain):
            best_gain = Info_gain
            best_feature = i

    return best_feature

执行：

1
2
3
4
5
6
>import trees
>myDat,labels=trees.createData()
>trees.Split_by_entropy(myDat)
1
>myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

3.1.3 递归构建决策树

  1. 工作原理：得到原始数据集，然后基于最好的属性值划分数据集（由于特征值可能多余两个，因此可能存在大于两个分支的数据集划分）。第一次划分之后，数据被向下传递到树分支的下一个节点，在这个节点上，再次划分数据。递归进行。
    递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。
    如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用==多数表决==的方法决定该叶子节点的分类。

多数表决法：

1
2
3
4
5
6
7
8
9
10
11
12
def Majority_vote(classList):
    '''
    使用多数表决法：若集合中属于第K类的节点最多，则此分支集合划分为第K类
    '''
    classcount = {}
    for vote in classList:
        classcount[vote] = classcount.get(vote,0) + 1
    sorted_count = sorted(classcount.items(), key = operator.itemgetter(1),\
                          reverse = True)
    # 获取每一类出现的节点数（没出现默认为0）并进行排序
    # 返回最大项的KEY所对应的类别
    return sorted_count[0][0]

程序清单3-4 创建树的函数代码

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
def Create_Tree(dataset, labels):
    # 类别完全相同则停止继续划分
    classList = [x[-1] for x in dataset]
    if classList.count(classList[0]) == len(classList):
        return classList[0]

    # 遍历完所有特征值时返回出现次数最多的
    if len(dataset[0]) == 1:
        return Majority_vote(classList)
    best_feature = Split_by_entropy(dataset)
    best_labels = labels[best_feature]

    # 得到列表包含的所有属性值
    myTree = {best_labels: {}}
    # 此位置书上写的有误，书上为del(labels[bestFeat])
    # 相当于操作原始列表内容，导致原始列表内容发生改变
    # 按此运行程序，报错'no surfacing'is not in list
    # 以下代码已改正

    # 复制当前特征标签列表，防止改变原始列表的内容
    subLabels = labels[:]
    # 删除属性列表中当前分类数据集特征
    del (subLabels[best_feature])

    # 使用列表推导式生成该特征对应的列
    f_val = [x[best_feature] for x in dataset]
    uni_val = set(f_val)
    for value in uni_val:
        # 递归创建子树并返回
        myTree[best_labels][value] = Create_Tree(split_data(dataset \
                                                            , best_feature, value), subLabels)

    return myTree

执行：

1
2
3
4
5
>import trees
>myDat,labels = trees.createData()
>myTree = trees.Create_Tree(myDat,labels)
>myTree
{'flippers': {0: 'no', 1: {'no sufacing': {0: 'no', 1: 'yes'}}}}

3.2 在 Python 中使用 Matplotlib 注解绘制树形图

Matplotlib提供了一个注解工具==annotations==，非常有用，它可以在数据图形上添加文本注释。

程序清单3-5 使用文本注解绘制树节点

我们要知道：
1）有多少个叶节点，以便确定x轴的长度；
2）树有多少层，以便确定y轴的高度。

1
2
3
4
5
6
7
8
9
10
11
#定义文本框和箭头格式
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
# 创建字典。 boxstyle=”sawtooth” 表示注解框的边缘是波浪线，fc=”0.8” 是颜色深度
leafNode = dict(boxstyle="round4", fc="0.8")
arrow_args = dict(arrowstyle="<-") # 箭头样式

#绘制带箭头的注释
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
# centerPt:节点中心坐标  parentPt:起点坐标
     createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',xytext=centerPt, textcoords='axes fraction',va="center",ha="center", bbox=nodeType, arrowprops=arrow_args )
# 参考annotate说明文档

程序清单3-6 获取叶节点的数目和树的层数

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
def Num_of_leaf(myTree): 
    '''计算此树的叶子节点数目，输入为我们前面得到的树（字典）'''
    num_leaf = 0  # 初始化
    first_node = myTree.keys() 
    first_node = list(first_node)[0]  # 获得第一个key值（根节点） 'no surfacing'
    # python 3X 中： mytree.keys() 返回 :dict_keys([’ ‘])是类似于列表但又不是列表的东东，它是个字典的key值的一个视图（view），所以改写为本句方法。
    
    second_dict = myTree[first_node]  # 获得value值 {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}
    # Python3中使用LIST转换firstnode，原书使用[0]直接索引只能用于Python2
    # 对于树，每次判断value是否为字典，若为字典则进行递归，否则累加器+1
    
    for key in second_dict.keys():  # 键值：0 和 1
        if type(second_dict[key]).__name__ =='dict':  # 判断如果里面的一个value是否还是dict
            num_leaf += Num_of_leaf(second_dict[key])  # 递归调用
        else: num_leaf += 1
    return num_leaf


def Depth_of_tree(myTree):
    '''计算此树的总深度'''
    depth = 0
    first_node = myTree.keys()
    first_node = list(first_node)[0]
    second_dict = myTree[first_node]

    for key in second_dict.keys():
        if type(second_dict[key]).__name__ == 'dict':
            pri_depth = 1 + Depth_of_tree(second_dict[key])
        else:
            pri_depth = 1
        # 对于树，每次判断value是否为字典，若为字典则进行递归，否则计数器+1
        if pri_depth > depth: depth = pri_depth
    return depth
    
def retrieveTree(i):
    '''
   保存了树的测试数据
     '''
    listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},{'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}]
    return listOfTrees[i]

程序清单3-7 plotTree函数

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
def plotmidtext(cntrpt, parentpt, txtstring):
    '''作用是计算tree的中间位置
    cntrpt起始位置,parentpt终止位置,txtstring：文本标签信息
    (在两个节点之间的线上写上字)
    '''
    xmid = (parentpt[0] - cntrpt[0]) / 2.0 + cntrpt[0]
    # cntrPt 起点坐标 子节点坐标
    # parentPt 结束坐标 父节点坐标
    ymid = (parentpt[1] - cntrpt[1]) / 2.0 + cntrpt[1]  # 找到x和y的中间位置
    createPlot.ax1.text(xmid, ymid, txtstring)  # text() 的使用


def plottree(mytree, parentpt, nodetxt):  # 画树
    numleafs = Num_of_leaf(mytree)
    depth = Depth_of_tree(mytree)
    firststr = list(mytree.keys())[0]
    cntrpt = (plottree.xoff + (1.0 + float(numleafs)) / 2.0 / plottree.totalw, plottree.yoff)
    # 计算子节点的坐标
    plotmidtext(cntrpt, parentpt, nodetxt)  # 绘制线上的文字
    plotNode(firststr, cntrpt, parentpt, decisionNode)  # 绘制节点
    seconddict = mytree[firststr]
    plottree.yoff = plottree.yoff - 1.0 / plottree.totald
    # 每绘制一次图，将y的坐标减少1.0/plottree.totald，间接保证y坐标上深度的
    for key in seconddict.keys():
        if type(seconddict[key]).__name__ == 'dict':
            plottree(seconddict[key], cntrpt, str(key))
        else:
            plottree.xoff = plottree.xoff + 1.0 / plottree.totalw
            plotNode(seconddict[key], (plottree.xoff, plottree.yoff), cntrpt, leafNode)
            plotmidtext((plottree.xoff, plottree.yoff), cntrpt, str(key))
    plottree.yoff = plottree.yoff + 1.0 / plottree.totald

def createPlot(intree):
    # 类似于Matlab的figure，定义一个画布(暂且这么称呼吧)，背景为白色
    fig = plt.figure(1, facecolor='white')
    fig.clf()  # 把画布清空
    axprops = dict(xticks=[], yticks=[])
    # createPlot.ax1为全局变量，绘制图像的句柄，subplot为定义了一个绘图，
    # 111表示figure中的图有1行1列，即1个，最后的1代表第一个图
    # frameon表示是否绘制坐标轴矩形
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)

    plottree.totalw = float(Num_of_leaf(intree))
    plottree.totald = float(Depth_of_tree(intree))
    plottree.xoff = -0.6 / plottree.totalw;plottree.yoff = 1.2;
    plottree(intree, (0.5, 1.0), '')
    plt.show()

执行：

1
2
3
4
5
6
7
8
>import trees
Backend TkAgg is interactive backend. Turning interactive mode on. #???
>myTree=trees.retrieveTree(0)
>trees.createPlot(myTree)
>myTree['no surfacing'][3]='maybe'
>myTree
{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}, 3: 'maybe'}}
>trees.createPlot(myTree)

tree
为啥没有根节点呢？？

3.3 测试和存储分类器

使用决策树构建分类器，以及实际应用中如何存储分类器。

3.3.1 测试算法：使用决策树执行分类

我们一起来让这个世界有趣一点……ヽ(✿ﾟ▽ﾟ)ノ