【机器学习实战】－－第三章决策树

可参考博客：https://blog.csdn.net/cxjoker/article/details/79501887

完整代码如下：

trees.py

from math import log
import operator
import treePlotter
import pickle


def calcShannonEnt(dataSet):
    numEntries = len(dataSet)  # 数据集中实例的总数
    labelCounts = {}  # 创建一个数据字典，它的键值是最后一列的数值
    for featVec in dataSet:
        currentLabel = featVec[-1]  # 当前的标签是最后一列的数值
        if currentLabel not in labelCounts.keys():  # 如果当前键值不在字典里，则扩展字典并将当前键值加入字典
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1  # 每个键值都记录了当前类别出现的次数
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries  # 使用所有类标签的发生频率计算类别出现的概率，并用此概率计算香浓熵
        shannonEnt -= prob * log(prob, 2)  # log默认以e为底，这里是以2为底
    return shannonEnt


def creatDataSet():
    dataSet = [[1,1,‘yes‘],[1,1,‘yes‘],[1,0,‘no‘],[0,1,‘no‘],[0,1,‘no‘]]  # 特征的值和类别标签
    labels = [‘no surfacing‘, ‘flippers‘]  # 特征的名称
    return dataSet, labels


def splitDataSet(dataSet, axis, value):
    ‘‘‘
    :param dataSet:待划分的数据集
    :param axis: 划分数据集的特征
    :param value: 特征的值
    :return: 由特征划分好的数据集
    ‘‘‘
    retDatSet = []
    for featVec in dataSet:  # 遍历整个数据集的实例样本
        if featVec[axis] == value:
            # 如果实例特征的值与要求的值相等则将其添加到新创建的列表中，
            # 计算熵时仅根据label出现的概率进行计算，和新列表中保存下来的特征无关
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDatSet.append(reducedFeatVec)  # 划分后的新列表
    return retDatSet


def chooseBestFeaturetoSplit(dataSet):
    # 实现选取特征，划分数据集，计算得出最好的划分数据集的特征
    numFeatures = len(dataSet[0]) - 1  # 当前数据集包含的特征数量
    baseEntropy = calcShannonEnt(dataSet)   # 计算整个数据集的原始香浓熵
    bestInfoGain = 0.0; bestFeature = -1
    for i in range(numFeatures):  # 遍历数据集中的所有特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)  # 集合（set）是一个无序的不重复元素序列。去掉重复元素
        # 集合数据类型与列表类型相似，不同之处在于集合类型中的每个值互不相同。
        # 从列表中创建集合是Python语言得到列表中唯一元素值的最快方法。
        newEntropy = 0.0
        for value in uniqueVals:  # 遍历当前特征中的所有唯一属性值
            subDataSet = splitDataSet(dataSet, i, value)  # 对每个唯一属性值划分一次数据集
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
            # 对划分后的新数据集计算香浓熵并对所有唯一特征值得到的熵求和
        infoGain = baseEntropy - newEntropy  # 信息增益是熵的减少或者是数据无序度的减少
        if(infoGain > bestInfoGain):  # 比较所有特征中的信息增益，返回最好特征划分的索引值
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature


def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1  # 字典对象存储classList中每个类标签出现的频率
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 使用operator操作键值排序字典，并返回出现次数最多的分类名称
    return sortedClassCount[0][0]


def createTree(dataSet, labels):
    ‘‘‘
    :param dataSet: 数据集
    :param labels:  标签列表
    :return:
    ‘‘‘
    classList = [example[-1] for example in dataSet]  # 创建classList的列表变量，包含了数据集的所有类标签
    if classList.count(classList[0]) == len(classList):
        # 递归函数的第一个停止条件是所有的类标签完全相同，则直接返回该类标签
        return classList[0]
    if len(dataSet[0]) == 1:
        # 第二个停止条件是使用完了所有特征，仍然不能将数据集划分成仅包含唯一类别的分组
        # 返回出现次数最多的类别作为返回值
        return majorityCnt(classList)
    bestFeat = chooseBestFeaturetoSplit(dataSet)  # 当前数据集选取的最好的特征
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}  # 使用字典存储树的信息
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]  # 得到数据集中最好的特征的值
    uniqueVals = set(featValues)
    for value in uniqueVals:  # 遍历当前选择特征包含的所有属性值
        subLabels = labels[:]  # 复制类标签，并将其存储在新列表变量subLabels中，
        # 为了保证每次调用函数createTree时不改变原始列表的内容，使用新变量subLabels代替原始列表
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat,value), subLabels)
        # 在每个数据集划分上递归调用函数createTree，得到的返回值将被插入到字典变量myTree中
    return myTree


def classify(inputTree, featLabels, testVec):
    firstStr = list(inputTree.keys())[0]  # 输入树的第一个特征名称
    secondDict = inputTree[firstStr]  # 第一个特征名称对应的字典
    featIndex = featLabels.index(firstStr)  # 第一个特征名称在特征中的索引
    # 将标签字符串转换为索引，使用index方法查找当前列表中第一个匹配firstStr变量的元素
    for key in secondDict.keys():
        if testVec[featIndex] == key:  # 比较testVec变量中的值与树节点的值
            if type(secondDict[key]).__name__ == ‘dict‘:
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel = secondDict[key]  # 如果到达叶子节点则返回当前节点的分类标签
    return classLabel


def storeTree(inputTree, filename):
    fw = open(filename, ‘wb‘)
    pickle.dump(inputTree, fw, 0)  # 为了避免保存的file乱码，在dump()里加上第三个参数，设为0(ASCII协议).
    fw.close()


def grabTree(filename):
    fr = open(filename, ‘rb‘)
    return pickle.load(fr)


if __name__ == ‘__main__‘:
    myDat, labels = creatDataSet()
    # myDat[0][-1] = ‘maybe‘
    # retDatSet = splitDataSet(myDat, 1, 0)
    # print(retDatSet)
    # ent = calcShannonEnt(myDat)
    # print(ent)
    # bestFeature = chooseBestFeaturetoSplit(myDat)
    # print(bestFeature)
    # myTree = createTree(myDat, labels)
    myTree = treePlotter.retrieveTree(0)
    # print(myTree)
    label_ = classify(myTree, labels, [1,0])
    print(label_)
    storeTree(myTree, ‘classifierStorage.txt‘)
    # print(grabTree(‘classifierStorage.txt‘))
    fr =open(‘../machinelearninginaction/Ch03/lenses.txt‘)
    lenses = [inst.strip().split(‘\t‘) for inst in fr.readlines()]
    lensesLabels = [‘age‘, ‘prescript‘, ‘astigmatic‘, ‘tearRate‘]
    lensesTree = createTree(lenses, lensesLabels)
    print(lensesTree)
    treePlotter.createPlot(lensesTree)

treePlotter.py

import matplotlib.pyplot as plt


#　使用文本注解绘制树节点
#　包含了边框的类型，边框线的粗细等
decisionNode = dict(boxstyle="sawtooth", fc="0.8")
# boxstyle为文本框的类型，sawtooth是锯齿形，fc是边框线粗细,pad指的是外边框锯齿形（圆形等）的大小
leafNode = dict(boxstyle="round4", fc="0.8")  # 定义决策树的叶子结点的描述属性 round4表示圆形
arrow_args = dict(arrowstyle="<-")  # 定义箭头属性
# 定义文本框和箭头格式


def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    ‘‘‘
    annotate是关于一个数据点的文本
    :param nodeTxt: 要显示的文本
    :param centerPt: 文本的中心点,箭头所在的点
    :param parentPt: 指向文本的点
    :param nodeType: 输入的节点（边框）的形状
    :return:
    ‘‘‘
    ‘‘‘
    添加注释。第一个参数是注释的内容，xy设置箭头的起始坐标，xytext设置注释内容显示的起始位置，文本的位置坐标 
    arrowprops用来设置箭头，facecolor设置箭头的颜色  
    headlength 箭头的头的长度，headwidth 箭头的宽度，width 箭身的宽度  
    ‘‘‘
    # annotate的作用是添加注释，nodetxt是注释的内容，
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords=‘axes fraction‘, 29                             xytext=centerPt,textcoords=‘axes fraction‘, 30                             va=‘center‘,ha=‘center‘,bbox=nodeType,arrowprops=arrow_args)



‘‘‘
def createPlot():
    fig = plt.figure(1, facecolor=‘white‘)
    fig.clf()
    createPlot.ax1 = plt.subplot(111, frameon = False)
    plotNode(‘decisionNode‘, (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode(‘leafNode‘, (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()
‘‘‘


def plotMidText(cntrPt, parentPt, txtString):
    ‘‘‘
    作用是计算tree的中间位置
    :param cntrPt: 起始位置
    :param parentPt: 终止位置
    :param txtString: 文本标签信息
    :return:
    ‘‘‘
    xMid = (parentPt[0] - cntrPt[0])/2.0 + cntrPt[0]
    # 找到x和y的中间位置
    yMid = (parentPt[1] - cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString)


def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(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)  # 绘制节点
    sencodDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    # 每绘制一次图，将y的坐标减少1.0 / plottree.totalD，间接保证y坐标上的深度
    for key in sencodDict.keys():
        if type(sencodDict[key]).__name__ == ‘dict‘:
            plotTree(sencodDict[key], cntrPt, str(key))  # 如果不是叶子节点则递归调用plotTree函数
        else:
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(sencodDict[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):
    fig = plt.figure(1, facecolor=‘white‘)
    fig.clf()  # 把画布清空
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon = False, **axprops)
    # createPlot.ax1为全局变量，绘制图像的句柄，subplot为定义了一个绘图，
    # 111表示figure中的图有1行1列，即1个，最后的1代表第一个图
    # frameon表示是否绘制坐标轴矩形
    plotTree.totalW = float(getNumLeafs(inTree))  # 全局变量，存储树的宽度,用于计算放置判断节点的位置
    plotTree.totalD = float(getTreeDepth(inTree))  # 全局变量，存储树的深度
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    # 追踪已经绘制的节点位置，以及放置下一个节点的恰当位置
    plotTree(inTree, (0.5, 1.0), ‘‘)
    plt.show()

def getNumLeafs(myTree):
    # 遍历整棵树，累计叶子节点的个数(不包括中间的分支节点)，并返回该数值
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]  # 根据键值得到对应的值，即根据第一个特征分类的结果
    for key in secondDict.keys():  # 获取第二个小字典中的key
        if type(secondDict[key]).__name__ == ‘dict‘:  # 测试节点的数据类型是否为字典
            # 判断是否小字典中是否还包含新的字典（即新的分支）
            numLeafs += getNumLeafs(secondDict[key])
            # 包含的话进行递归从而继续循环获得新的分支所包含的叶节点的数量
        else:
            numLeafs += 1
            # 不包含的话就停止迭代并把现在的小字典加一表示这边有一个分支
    return numLeafs


def getTreeDepth(myTree):
    # 计算遍历过程中遇到判断节点的个数
    maxDepth = 0
    # print(myTree.keys())
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == ‘dict‘:
            thisDepth = 1 + getTreeDepth(secondDict[key])  # 递归调用几次就有几个返回值maxDepth
        else:
            thisDepth = 1  # 如果不是字典说明这是一个判断节点
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth


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]


if __name__ == ‘__main__‘:
    # createPlot()
    # print(retrieveTree(1))
    myTree = retrieveTree(0)
    myTree[‘no surfacing‘][3] = ‘maybe‘
    # print(getNumLeafs(myTree))
    # print(getTreeDepth(myTree))
    createPlot(myTree)

两个例子的决策树：