文章原创,最近更新：2018-08-20

本章节的主要内容是:
重点介绍项目案例1:判定鱼类和非鱼类测试算法：测试和存储分类器的代码。

1.决策树项目案例介绍:

项目案例1:

判定鱼类和非鱼类

项目概述:

• 根据以下 2 个特征，将动物分成两类：鱼类和非鱼类。
• 特征： 1. 不浮出水面是否可以生存 2. 是否有脚蹼

开发流程：

• 收集数据：可以使用任何方法
• 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化
• 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期
• 训练算法：构造树的数据结构
• 测试算法：使用决策树执行分类
• 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义

数据集介绍

2.代码汇总

2.1测试数据集

首先创建一个名为trees.py的文件,createDataSet()函数录入到trees.py文件.

from math import log
import operator

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    return dataSet, labels

2.2计算给定数据集的香农熵的函数

这段代码主要是计算给定数据集的熵,创建一个函数calcShannonEn()函数录入到trees.py文件.

def calcShannonEnt(dataSet):
    # 获取数据集dataSet列表的长度,表示计算参与训练的数据量
    numEntries=len(dataSet)
    # 新建一个空字典labelCounts，用以统计每个标签出现的次数,进而计算概率
    labelCounts={}
    for featVec in dataSet:
        # featVec[-1]获取了daatSet中每行最后一个数据，作为字典中的key（标签）
        currentLabel = featVec[-1]
        # 以currentLabel作为key加入到字典labelCounts.
        # 如果当前的键值不存在，则扩展字典并将当前键值加入字典。每个键值都记录了当前类别出现的次数。
        # 键值存在则则对应value+1,否则为0
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=0
        
        labelCounts[currentLabel] += 1
    # 对于 label 标签的占比，求出 label 标签的香农熵
    shannonEnt = 0.0 
    for key in labelCounts:
        # 计算分类概率prob=标签发生频率,labelCounts[key]除以数据集长度numEntries
        prob = float(labelCounts[key])/numEntries
        # 计算香农熵,以2为底求对数
        shannonEnt -=prob * log(prob,2)
    return shannonEnt

测试代码及其结果如下:

import trees

a, b = trees.createDataSet()

trees.calcShannonEnt(a)
Out[90]: 0.9709505944546686

2.3划分数据集的函数代码

这个函数的是作用是当我们按某个特征划分数据集时，把划分后剩下的元素抽取出来，形成一个新的子集，用于计算条件熵。

创建一个函数splitDataSet()函数录入到trees.py文件.

具体相关知识点,可参见:3-2节 决策树|划分数据集|机器学习实战-学习笔记

def splitDataSet(dataSet,axis,value):
    """
    splitDataSet(通过遍历dataSet数据集,求出index对应的column列的值为value的行)
    就是依据index列进行分类,如果index列的数据等于value的时候,就要index划分到我们创建的新的数据集中
    Args:
      dataSet:数据集                待划分的数据集
      axis:表示每一行的index列      特征的坐标，等于0，第0个特征为0或者1
      value:表示index列对应的value值 需要返回的特征的值
    Returns:
        index列为value的数据集[该数据集需要排除axis列]
    """
    retDataSet = []
    # index列为value的数据集[该数据集需要排除index列]
    # 判断index列的值是否等于value
    # 遍历数据集，将axis上的数据和value值进行对比
    for featVec in dataSet:
        # 如果待检测的特征axis和指定的特征value相等
        if featVec[axis] == value:
            # 从第0开始，一旦发现第axis符合要求，就将数据0-axis保存至reduceFeatVec
            reducedFeatVec =featVec[:axis]
            # 将指定的数据的axis+1位到末尾添加至reducedFeatVec，保持数据完整性
            reducedFeatVec.extend(featVec[axis+1:])
            # 收集结果值除掉index列的reducedFeatVec收据集添加到retDataSet数据集
            retDataSet.append(reducedFeatVec)
    return retDataSet

测试代码及其结果如下:

import trees
mydata,labels=trees.createDataSet()

mydata
Out[111]: [[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

trees.splitDataSet(mydata,0,1)
Out[112]: [[1, 'maybe'], [1, 'yes'], [0, 'no']]

2.4选择最好的数据集划分方式的函数代码

接下来我们将遍历整个数据集，循环计算香农熵和 splitDataSet（）函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式.

创建一个函数chooseBestFeatTopSplit()函数录入到trees.py文件.

具体相关知识点,可参见:3-3节 决策树|选择最好的数据集划分方式|机器学习实战-学习笔记

def chooseBestFeatTopSplit(dataSet):
    """chooseBestFeatureToSplit(选择最好的特征)

    Args:
        dataSet 数据集
    Returns:
        bestFeature 最优的特征列
    """
    # 求第一行有多少列的 Feature, 减去1,是因为最后一列是label列
    numFeatures = len(dataSet[0])-1
    # 计算没有经过划分的数据的香农熵
    baseEntropy = calcShannonEnt(dataSet) 
    # 最优的信息增益值
    bestInfoGain = 0.0
    #最优的Featurn编号
    bestFeature = -1
    for i in range(numFeatures): 
        # 创建唯一的分类标签列表，获取第i个的所有特征（信息元纵排列！）
        featList = [example[i] for example in dataSet]
        """
        print(featList)结果为
        [1, 1, 1, 0, 0]
        [1, 1, 0, 1, 1]
        """
        # 使用set集，排除featList中的重复标签，得到唯一分类的集合
        uniqueVals = set(featList)
        """
        print(uniqueVals)结果为
        {0, 1}
        {0, 1}
        """
        newEntropy = 0.0
         # 遍历当次uniqueVals中所有的标签value（这里是0，1）
        for value in uniqueVals: 
            # 对第i个数据划分数据集, 返回所有包含i的数据（已排除第i个特征）
            subDataSet = splitDataSet(dataSet, i, value)
            """
            print(subDataSet)结果为
            [[1, 'no'], [1, 'no']]
            [[1, 'yes'], [1, 'yes'], [0, 'no']]
            [[1, 'no']]
            [[1, 'yes'], [1, 'yes'], [0, 'no'], [0, 'no']]
            """        
            # 计算包含个i的数据占总数据的百分比
            prob = len(subDataSet)/float(len(dataSet))
            """
            print(prob)结果为
            0.4
            0.6
            0.2
            0.8
            """
            # 计算新的香农熵，不断进行迭代，这个计算过程仅在包含指定特征标签子集中进行
            newEntropy += prob * calcShannonEnt(subDataSet) 
            """
            print(calcShannonEnt(subDataSet))
            0.0
            0.9182958340544896
            0.0
            1.0
        
            print(newEntropy)结果为
            0.0
            0.5509775004326937
            0.0
            0.8
            """
            
            # 计算信息增益
            infoGain = baseEntropy - newEntropy
            # 如果信息增益大于最优增益，即新增益newEntropy越小，信息增益越大，分类也就更优（分类越简单越好）
            """
            print(infoGain)结果为
            0.4199730940219749
            0.17095059445466854
            """
            
            if (infoGain > bestInfoGain): 
                # 更新信息增益 
                bestInfoGain = infoGain
                # 确定最优增益的特征索引
                bestFeature = i 
                # 更新信息增益
        # 返回最优增益的索引
        return bestFeature 

测试代码及其 结果如下:

import trees
myDat,labels=trees.createDataSet()

myDat
Out[182]: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

trees.chooseBestFeatTopSplit(myDat)
Out[183]: 0

2.5 递归构建决策树

创建分别函数majorityCnt()以及createTree()录入到trees.py文件.

具体相关知识点,可参见:3-4节 决策树|递归构建决策树|机器学习实战-学习笔记

2.5.1筛选出现次数最多的分类标签名称
如果数据集已经处理了所有的属性,但是类标签依然不是唯一的,此时我们需要决定如何定义该叶子节点,在这种情况下,我们通常会采用多数表决的方法决定该叶子节点的分类.

#筛选出现次数最多的分类标签名称
def majorityCnt(classList):
    """
    majorityCnt(筛选出现次数最多的分类标签名称)

    Args:
        classList 类别标签的列表
    Returns:
        sortedClassCount[0][0] 出现次数最多的分类标签名称
        
    假设classList=['yes', 'yes', 'no', 'no', 'no']    
    """
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():classCount[vote]= 0
        classCount[vote] += 1
        """
        print(classCount[vote])的结果为:
        {'yes': 1}
        {'yes': 2}
        {'yes': 2, 'no': 1}
        {'yes': 2, 'no': 2}
        {'yes': 2, 'no': 3}
        """
    sortedClassCount =sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    """
    print(sortedClassCount)的结果为:
    [('no', 3), ('yes', 2)]
    """
    return sortedClassCount[0][0]

测试代码及其结果如下:

import trees
classList=['yes', 'yes', 'no', 'no', 'no']

majorityCnt(classList)
Out[45]: 'no'

2.5.2递归构建决策树
决策树是一个递归算法，伪代码如下：

def createBranch():
    检测数据集中的所有数据的分类标签是否相同:
        If so return 类标签
        Else:
            寻找划分数据集的最好特征（划分之后信息熵最小，也就是信息增益最大的特征）
            划分数据集
            创建分支节点
                for 每个划分的子集
                    调用函数 createBranch （创建分支的函数）并增加返回结果到分支节点中
            return 分支节点

决策树一般使用递归的方法生成。

• 编写递归函数有一个好习惯，就是先考虑结束条件。生成决策树结束的条件有两个：其一是划分的数据都属于一个类，其二是所有的特征都已经使用了。在第二种结束情况中，划分的数据有可能不全属于一个类，这个时候需要根据多数表决准则确定这个子数据集的分类。

• 在非结束的条件下，首先选择出信息增益最大的特征，然后根据其分类。分类开始时，记录分类的特征到决策树中，然后在特征标签集中删除该特征，表示已经使用过该特征。根据选中的特征将数据集分为若干个子数据集，然后将子数据集作为参数递归创建决策树，最终生成一棵完整的决策树

 # 创建树的函数代码       
def createTree(dataSet, labels):
    """
    createTree(创建树)

    Args:
        dataSet 数据集
        labels  标签列表:标签列表包含了数据集中所有特征的标签。最后代码遍历当前选择
    Returns:
        myTree 标签树:特征包含的所有属性值，在每个数据集划分上递归待用函数createTree()，
        得到的返回值将被插入到字典变量myTree中，因此函数终止执行时，字典中将会嵌套很多代
        表叶子节点信息的字典数据。
    """
    #取得dataSet的最后一列数据保存在列表classList中
    classList = [example[-1] for example in dataSet]
    #如果classList中的第一个值在classList中的总数等于长度,也就是说classList中所有的值都一样
    #也就等价于当所有的类别只有一个时停止
    if classList.count(classList[0])==len(classList):
        return classList[0]
    #当数据集中没有特征可分时也停止
    if len(dataSet[0])==1:
        #通过majorityCnt()函数返回列表中最多的分类
        return majorityCnt(classList)
    #通过chooseBestFeatTopSplit()函数选出划分数据集最佳的特症
    bestFeat = chooseBestFeatTopSplit(dataSet) 
    #最佳特征名 = 特征名列表中下标为bestFeat的元素
    bestFeatLabel=labels[bestFeat]
    # 构造树的根节点，多级字典的形式展现树，类似多层json结构
    myTree={bestFeatLabel:{}}
    # 删除del列表labels中的最佳特征(就在labels变量上操作)
    del(labels[bestFeat])
    #取出所有训练样本最佳特征的值形成一个list
    featValues = [example[bestFeat] for example in dataSet]
    # 通过set函数将featValues列表变成集合,去掉重复的值
    uniqueVals = set(featValues)
    for value in uniqueVals:
        #复制类标签并将其存储在新列表subLabels中
        subLabels = labels[:] 
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

测试代码及其结果如下:

import trees
myDat,labels=createDataSet()
myTree =createTree(myDat,labels)

myTree
Out[55]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

2.6使用文本注解绘制树节点的函数代码

将以下代码录入到treePlotter.py文件.

具体相关知识点,可参见:3-5节 决策树|使用文本注解绘制树节点|机器学习实战-学习笔记

《机器学习实战》书中，该部分的代码有些混乱。重新构造了代码，创建一个类。其中，绘制最基本的树节点是如下代码：

#导入matplotlib的pyplot绘图模块并命名为plt
import matplotlib.pyplot as plt

# boxstyle是文本框类型,fc是边框粗细,sawtooth是锯齿形
decisionNode = dict(boxstyle="sawtooth",fc="0.8")
leafNode = dict(boxstyle="round4",fc="0.8")

# arrowprops: 通过arrowstyle表明箭头的风格或种类。
arrow_args=dict(arrowstyle="<-")

# annotate 注释的意思
#plotNode()函数绘制带箭头的注解,sub_ax:使用figure命令来产生子图, node_text：节点的文字标注,start_pt：箭头起点位置（上一节点位置）,end_pt:箭头结束位置, node_type：节点属性   
def plot_node(sub_ax, node_text, start_pt, end_pt, node_type):
    sub_ax.annotate(node_text,
        xy = end_pt, xycoords='axes fraction', 
        xytext = start_pt, textcoords='axes fraction',
        va='center', ha='center', bbox=node_type, arrowprops=arrow_args)

if __name__ == '__main__':
    fig = plt.figure(1, facecolor='white')
    #清空绘图区
    fig.clf()
    axprops = dict(xticks=[], yticks=[]) #去掉坐标轴
    sub_ax = plt.subplot(111, frameon=False, **axprops)
    #绘制节点
    plot_node(sub_ax, 'a decision node', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plot_node(sub_ax, 'a leaf node', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

输出结果如下:

2.7测试算法：使用决策树执行分类代码

依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于决策树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。

创建一个函数classify()录入到trees.py文件.

具体相关知识点,可参见:3-6节 决策树|测试和存储分类器|机器学习实战-学习笔记

def classify(inputTree, featLabels, testVec):
    # 因为并不知道按特征分类的先后顺序，所以要写一个分类器
    """classify(给输入的节点，进行分类)

    Args:
        inputTree  是输入的决策树对象
        featLabels Feature是我们要预测的特征值的label，如：['throat','mustache']
        testVec    是要预测的特征值向量，如[0,0]
    Returns:
        classLabel 分类的结果值，需要映射label才能知道名称
    """
    # 存储决策树第一个节点
    firstStr=list(inputTree.keys())[0]
    """
    myTree={'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
    labels=['no surfacing', 'flippers']
    
    print(firstStr)的结果为:
    'no surfacing'
    """
    # 将第一个节点的值存到secondDict字典中
    secondDict = inputTree[firstStr]
    """
    print(secondDict)的结果为:
    {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}
    """
    # 判断根节点名称获取根节点在label中的先后顺序，这样就知道输入的testVec怎么开始对照树来做分类
    featIndex = featLabels.index(firstStr)
    """
    print(featIndex)的结果为:
    0
    """
    for key in secondDict.keys():
        """
        print(secondDict.keys())的结果为:
        dict_keys([0, 1])
        """
        if testVec[featIndex]==key:
            # 判断分枝是否结束:判断secondDict[key]是否是dict类型,如果是就递归，不是就输出当前键值为结果
            if type(secondDict[key]).__name__ == 'dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]
    return classLabel

测试代码以及结果如下:

import trees
myDat, labels = trees.createDataSet()
myTree = trees.createTree(myDat, labels[:])

Out[35]:  trees.classify(myTree, labels, [1, 0])
'no'
Out[36]:  trees.classify(myTree, labels, [1, 1])
'yes'

2.8使用算法：决策树的存储

可以使用Python模块pickle序列化对象，参见下面的程序。序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。

创建分别函数storeTree()/grabTree()录入到trees.py文件.

具体相关知识点,可参见:3-6节 决策树|测试和存储分类器|机器学习实战-学习笔记

def storeTree(inputTree,filename):
    import pickle
    # wb二进制写模式
    fw = open(filename,"wb")
    pickle.dump(inputTree,fw)
    fw.close()
    
def grabTree(filename):
    import pickle
    # rb二进制文件读取
    fr=open(filename,"rb")
    return pickle.load(fr)

测试代码以及结果如下:

import trees
myDat, labels = trees.createDataSet()
myTree = trees.createTree(myDat, labels[:])

storeTree(myTree,'classifierStorage.txt')
grabTree('classifierStorage.txt')
Out[51]: {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}