[人工智能]机器学习实战第三章

决策树

• 说明：本章节所有代码使用版本为Python3

优点：计算复杂度不高，输出结果易于理解，对中间值缺失不敏感，可以处理不相关特征数据
缺点：可能会产生过度匹配问题
适用数据类型：数值型和标称型

解释：
??标称型：标称型目标变量的结果只在有限目标集中取值，比如真与假(标称型目标变量主要用于分类)
??数值型（连续型）：数值型目标变量则可以从无限的数值集合中取值

??决策树经常用于解决处理分类问题，它的一个重要任务是为了理解数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集并从中提取出一系列规则，这些机器根据数据集创建规则的过程，就是机器学习的过程。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌人类专家。

决策树的构造

决策树的一般流程

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

一些决策树算法采用二分法划分数据，而这里使用ID3算法划分数据集，每一次划分数据集时只选取一个特征属性。

1、信息增益

??划分数据集的最大原则：将无序的数据变得有序。组织杂乱无章数据的一种方式就是使用信息论度量信息，量信息是量化处理信息的分支科学。我们可以在划分数据之前或之后使用信息量化度量信息的内容。
??划分数据之前之后信息发生的变化称之为信息增益，知道如何计算信息增益，就可以计算每一个特征值划分数据集获得信息增益，获得信息增益最高的特征就是最好的选择。
??集合信息的度量方式是香农熵或简称熵。熵定义信息的期望值。若待分类的事务可能划分在多个分类之中，则符号x_i的信息定义为：

$$l(x_i)=?lo{g}_{2}p(x_i)$$

??为了计算熵，需要计算所有类别所有可能包含的信息期望，通过下面公式得到：

$$?\sum _{i=1}^{n}p(x_i)lo{g}_{2}p(x_i)$$

??熵越高，混合的数据也就越多。得到熵之后，可以按照获取最大信息增益的方法划分数据集。

2、划分数据集

??分类算法除了需要测量信息熵，还需要划分数据集，度量划分数据的熵，以便判断当前是否正确的划分了数据集。我们对每一个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的方式。

3、递归构建决策树

??目前我们已经学习了冲数据集构造决策树所需的子功能模块。其工作原理是：

1. 得到原始数据集
2. 基于最好的属性值划分数据集，由于特征值可能有多于两个，因此可能存在大于两个分支的数据划分
3. 第一次划分后，数据将向下传递到树分支的下一个节点，在这个节点上，我们可以再次划分数据集
4. 最后采用递归的原则处理数据集

??递归结束的条件是：遍历完所有的数据集的属性，或者每个分支下的所有实例都具有相同的分类。若所有实例都具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然是属于叶子节点的分类。

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

# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    # 获取传来数据集的长度
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 获取数据每一行数据集的最后一个元素
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        # 如果最后一个数据的元素不在labelCounts集合中，则添加进去，值为0
        labelCounts[currentLabel] += 1
        # for循环中是为所有的可能分类创造字典
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # labelCounts[key]表示字典中key所对应的value值
        # prob计算出，每一个key所出现的概率
        shannonEnt -= prob*log(prob, 2)
        # 以2为底求对数，根据计算香农熵的公式得出的
    return shannonEnt

# 给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    # dataSet表示待划分的数据集，axis表示划分数据集的特征，value表示需要返回的特征值
    retDataSet = []
    # 创建list对象
    for featVec in dataSet:
        if featVec[axis] == value:
            # 将符合特征的数据抽取出来
            reducedFeatVec = featVec[:axis]
            # 指定特征之前的数据
            reducedFeatVec.extend(featVec[axis+1:])
            # 指定特征之后的数据，extend在已存在的列表中添加新的列表内容
            retDataSet.append(reducedFeatVec)
            # retDataSet相比于reducedFeatVec没有了特征数据
            # 注意extend与append的区别，extend是将每一个元素分别合并到列表中，而append是将一个列表当作一个元素合并到列表中
    return retDataSet
    # 返回符合要求的元素


# 选择最好的数据划分方式
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]
        # 获取第i个特征所有的取值，example存放每一个数组，example[i]是数组的第i个元素
        uniqueVals = set(featList)
        # 创建唯一的分类标签，featList是一类特征是一个数组
        newEntropy = 0.0
        for value in uniqueVals:
            # 根据第i个特征划分数据并计算划分后的熵
            subDataSet = splitDataSet(dataSet, i, value)
            # 根据第i个特征划分数据集，得到符合要求的数据集
            prob = len(subDataSet)/float(len(dataSet))
            # 计算subDataSet中数据出现的概率
            newEntropy += prob*calcShannonEnt(subDataSet)
            # 计算新熵值calcShannonEnt计算当前特征香农熵
        infoGain = baseEntropy-newEntropy
        # 计算信息增益的熵，即当前唯一特征的熵之和
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            # 信息上增益减少（数据无序性减少），则为最好的信息增益
            bestFeature = i
            # 将最好特征划分的索引值返回
    return bestFeature

# 多数表决法定义叶子节点的分类
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote in classCount.keys():
            classCount[vote] = 0
        classCount += 1
    # 将没有出现的key加入到字典中，并设置为0，当遇到时加一
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    # sorted(对象，排序值，reverse=True/False)，reverse默认值为False，表示正序，reverse=True表示倒序（降序）。
    # 按照每个key的值对每对key，value进行降序排序，operator.itemgetter(1)：得到item中的第二个位置的值。
    # 使用iteritems()这个函数得到字典中的所有元素。sortedClassCount[0][0]是按照分类个数最多的元素的那个类。
    return sortedClassCount[0][0]


# 创建树的函数
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 获取类别，取出最后一列
    if classList.count(classList[0]) == len(classList):
        # 终止条件之一：所有数据的类别的都相同，则停止划分
        return classList[0]
    # count()统计表中的所有的记录数
    if len(dataSet[0]) == 1:
        # 终止条件之二：特征用完仍不能将数据集划分为只包含唯一类别的分组，返回出现次数最多的。
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 选择最好的数据划分方式
    bestFeatLabel = labels[bestFeat]
    # 获取对应的标签
    myTree = {bestFeatLabel: {}}
    # myTree是要返回的结果，所以要用字典来存储树
    del(labels[bestFeat])
    # 删除最佳特征值
    featValues = [example[bestFeat] for example in dataSet]
    # 因为上面已经找出了最佳特征值并删除了，所以还要找出新的最佳特征向量对应的所有特征值
    uniqueVals = set(featValues)
    # 创建集合，目的是除去重复数据
    for value in uniqueVals:
        subLabels = labels[:]
        # 相当于是复制了类标签
        myTree[bestFeatLabel][value] = createTree(
            splitDataSet(dataSet, bestFeat, value), subLabels)
        # 在数据集上递归调用只到找出所有的结果
    return myTree


dataSet, labels = createDataSet()
re = createTree(dataSet, labels)
print(re)

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

??决策树的主要优点是直观易于理解，若不能将其直观地表示出来，就无法发挥其优势

1、Matplotlib注解

??Matplotlib提供了非常有用的注解工具annotations，它可以在数据图形上添加文本注解，注解通常用于解释数据内容。

2、构造注解树

??我们必须知道有多少个叶子结点，以便可以正确的确定x轴的长度；还学要知道树的层数以便可以正确的确定y的高度

3、完整代码示例

import matplotlib.pyplot as plt


plt.rcParams['font.sans-serif'] = ['SimHei']
plt.rcParams['axes.unicode_minus'] = False
# matplotlib画图中中文显示会有问题，需要这两行设置默认字体

decisionNode = dict(boxstyle='sawtooth', fc='0.8')
# 决策节点的属性，boxstyle为文本框的类型，sawtooth是锯齿形，fc是边框线粗细
leafNode = dict(boxstyle='round4', fc='0.8')
# 决策树叶子节点的属性，round4是方框的样式
arrow_args = dict(arrowstyle='<-')
# 箭头的属性

# 绘制节点
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt, xycoords='axes fraction',
                            xytext=centerPt, va='center', ha='center', bbox=nodeType, arrowprops=arrow_args)
    # nodeTxt为要显示的文本，centerPt为文本的中心点，parentPt为箭头指向文本的点，xy是箭头尖的坐标，xytext设置注释内容显示的中心位置
    # xycoords和textcoords是坐标xy与xytext的说明（按轴坐标），若textcoords=None，则默认textcoords与xycoords相同，若都未设置，默认为data
    # va/ha设置节点框中文字的位置，va为纵向取值为(u'top', u'bottom', u'center', u'baseline')，ha为横向取值为(u'center', u'right', u'left')

# ---------更新之前代码（start）---------
# def createPlot():
#     fig = plt.figure(1, facecolor='white')
#     # 创建一个画布，画布背景为白色
#     fig.clf()
#     # Clear figure清除所有轴，但是窗口打开，这样它可以被重复使用。
#     createPlot.ax1 = plt.subplot(111, frameon=False)
#     # createPlot.ax1为全局变量，绘制图像的句柄，subplot为定义了一个绘图，111表示figure中的图有1行1列，即1个，最后的1代表第一个图
#     # frameon表示是否绘制坐标轴矩形
#     plotNode('决策节点', (0.5, 0.1), (0.1, 0.5), decisionNode)
#     plotNode('叶节点', (0.8, 0.1), (0.3, 0.8), leafNode)
#     plt.show()
# ---------更新之前代码（end）---------

# ---------更新之后代码（start）---------

# 计算父节点和子节点的中间位置，并在父子节点间填充文本信息
def plotMidText(cntrPt, parentPt, txtString):
    # cntrPt文本中心点，parentPt指向文本中心的点，txtString填充的信息
    xMid = (parentPt[0]-cntrPt[0])/2.0+cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0+cntrPt[1]
    # 确定在指向线上显示出txtString的位置（xMid，yMid）
    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)
    # plotTree.totalW用来存储全局树的宽度，
    plotMidText(cntrPt, parentPt, nodeTxt)
    # 填充节点之间的文本
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    # 绘制节点
    sceondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff-1.0/plotTree.totalD
    # 因从上往下画，所以需要依次递减y的坐标值，plotTree.totalD表示存储树的深度
    for key in sceondDict.keys():
        if type(sceondDict[key]).__name__ == 'dict':
            plotTree(sceondDict[key], cntrPt, str(key))
            # 若节点还是字典，则还继续递归，直到不是词典结束
        else:
            plotTree.xOff = plotTree.xOff+1.0/plotTree.totalW
            # 确定决策树的下一个节点位置的x轴坐标，每个叶子节点占据的空间长度是1/plotTree.totalW
            plotNode(sceondDict[key], (plotTree.xOff,
                     plotTree.yOff), cntrPt, leafNode)
            # 绘制出节点
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
            # 计算父节点和子节点的中间位置，并在父子节点间填充文本信息
    plotTree.yOff = plotTree.yOff+1.0/plotTree.totalD
# https://blog.csdn.net/jin690734932/article/details/80183043或https://www.cnblogs.com/fantasy01/p/4595902.html
# 主要用来解释Y轴坐标的确定问题（难点☆☆☆☆☆）

# 创建决策树主函数
def createPlot(inTree):
    fig = plt.figure(1, facecolor='white')
    # 创建一个画布，画布背景为白色
    fig.clf()
    # Clear figure清除所有轴，但是窗口打开，这样它可以被重复使用。
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    plotTree.totalW = float(getNumLeafs(inTree))
    # 获取树的宽度
    plotTree.totalD = float(getTreeDepth(inTree))
    # 获取树的深度（高度）
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    # 使用plotTree.xOff、plotTree.yOff作为全局变量，追踪已经绘制的节点位置，以及放置下一个节点的恰当位置
    plotTree(inTree, (0.5, 1.0), '')
    plt.show()
# ---------更新之后代码（end）---------


# 获取叶子节点的数目
def getNumLeafs(myTree):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    # 找到输入的第一个元素，第一个关键词为划分数据集类别的标签
    secondDict = myTree[firstStr]
    # 得到字典中firstStr所对应的值
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            # 测试数据是否为字典形式
            numLeafs += getNumLeafs(secondDict[key])
            # 子节点也为字典，则也是判断结点，需要递归获取子节点数
        else:
            numLeafs += 1
            # 若不是字典则为叶子节点
    return numLeafs

# 获取树的深度
def getTreeDepth(myTree):
    maxDepth = 0
    firstStr = list(myTree.keys())[0]
    # 找到输入的第一个元素，第一个关键词为划分数据集类别的标签
    secondDict = myTree[firstStr]
    # 得到字典中firstStr所对应的值
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            # 测试数据是否为字典形式
            thisDepth = 1+getTreeDepth(secondDict[key])
            # 若是字典则深度加一，并使用递归继续遍历，直到不是字典形式
        else:
            thisDepth = 1
            # 否则深度为一
        if thisDepth > maxDepth:
            maxDepth = thisDepth
    return maxDepth
    # 返回最大的深度值

# 自己创建的决策树值
def retrieveTree(i):
    listOfTree = [{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}, {
        'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}},
        {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}, 3: 'maybe'}}]
    return listOfTree[i]

createPlot(retrieveTree(0))

测试和存储分类器

??主要内容是使用决策树构建分类器，并介绍实际应用中如何存储分类器

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

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

2、适用算法：决策树的存储

??为了节省更多的计算时间，最好能够在每次执行分类时调用已经构建好的决策树，需要使用python模块pickle序列化对象。序列化对象可以在磁盘上保存对象，并在需要的时候读取出来。

3、完整代码示例

from math import log
import operator
import pickle

# 自己创建简单的数据集
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

# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    # 获取传来数据集的长度
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        # 获取数据每一行数据集的最后一个元素
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        # 如果最后一个数据的元素不在labelCounts集合中，则添加进去，值为0
        labelCounts[currentLabel] += 1
        # for循环中是为所有的可能分类创造字典
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # labelCounts[key]表示字典中key所对应的value值
        # prob计算出，每一个key所出现的概率
        shannonEnt -= prob*log(prob, 2)
        # 以2为底求对数，根据计算香农熵的公式得出的
    return shannonEnt

# 给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    # dataSet表示待划分的数据集，axis表示划分数据集的特征，value表示需要返回的特征值
    retDataSet = []
    # 创建list对象
    for featVec in dataSet:
        if featVec[axis] == value:
            # 将符合特征的数据抽取出来
            reducedFeatVec = featVec[:axis]
            # 指定特征之前的数据
            reducedFeatVec.extend(featVec[axis+1:])
            # 指定特征之后的数据，extend在已存在的列表中添加新的列表内容
            retDataSet.append(reducedFeatVec)
            # retDataSet相比于reducedFeatVec没有了特征数据
            # 注意extend与append的区别，extend是将每一个元素分别合并到列表中，而append是将一个列表当作一个元素合并到列表中
    return retDataSet
    # 返回符合要求的元素


# 选择最好的数据划分方式
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]
        # 获取第i个特征所有的取值，example存放每一个数组，example[i]是数组的第i个元素
        uniqueVals = set(featList)
        # 创建唯一的分类标签，featList是一类特征是一个数组
        newEntropy = 0.0
        for value in uniqueVals:
            # 根据第i个特征划分数据并计算划分后的熵
            subDataSet = splitDataSet(dataSet, i, value)
            # 根据第i个特征划分数据集，得到符合要求的数据集
            prob = len(subDataSet)/float(len(dataSet))
            # 计算subDataSet中数据出现的概率
            newEntropy += prob*calcShannonEnt(subDataSet)
            # 计算新熵值calcShannonEnt计算当前特征香农熵
        infoGain = baseEntropy-newEntropy
        # 计算信息增益的熵，即当前唯一特征的熵之和
        if infoGain > bestInfoGain:
            bestInfoGain = infoGain
            # 信息上增益减少（数据无序性减少），则为最好的信息增益
            bestFeature = i
            # 将最好特征划分的索引值返回
    return bestFeature

# 多数表决法定义叶子节点的分类
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote in classCount.keys():
            classCount[vote] = 0
        classCount += 1
    # 将没有出现的key加入到字典中，并设置为0，当遇到时加一
    sortedClassCount = sorted(
        classCount.items(), key=operator.itemgetter(1), reverse=True)
    # sorted(对象，排序值，reverse=True/False)，reverse默认值为False，表示正序，reverse=True表示倒序（降序）。
    # 按照每个key的值对每对key，value进行降序排序，operator.itemgetter(1)：得到item中的第二个位置的值。
    # 使用iteritems()这个函数得到字典中的所有元素。sortedClassCount[0][0]是按照分类个数最多的元素的那个类。
    return sortedClassCount[0][0]

# 决策树分类函数
def classify(inputTree, featLabels, testVec):
    # testVec测试数据列表，顺序对应最优特征标签
    firstStr = list(inputTree.keys())[0]
    # 获取决策树的键的值
    secondDict = inputTree[firstStr]
    # 获取对应键的值
    featIndex = featLabels.index(firstStr)
    # 将标签字符串转换成索引
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            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')
    # 提示py3与py2不同，py2可使用'w'，而py3必须加上'wb'
    pickle.dump(inputTree, fw)
    fw.close()

# 从文件中读取树
def grabTree(filename):
    fr = open(filename, 'rb+')
    # 读取的时候必须是'b+'不然识别不了gbk
    return pickle.load(fr)

# 创建树的函数
def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 获取类别，取出最后一列
    if classList.count(classList[0]) == len(classList):
        # 终止条件之一：所有数据的类别的都相同，则停止划分
        return classList[0]
    # count()统计表中的所有的记录数
    if len(dataSet[0]) == 1:
        # 终止条件之二：特征用完仍不能将数据集划分为只包含唯一类别的分组，返回出现次数最多的。
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 选择最好的数据划分方式
    bestFeatLabel = labels[bestFeat]
    # 获取对应的标签
    myTree = {bestFeatLabel: {}}
    # myTree是要返回的结果，所以要用字典来存储树
    del(labels[bestFeat])
    # 删除最佳特征值
    featValues = [example[bestFeat] for example in dataSet]
    # 因为上面已经找出了最佳特征值并删除了，所以还要找出新的最佳特征向量对应的所有特征值
    uniqueVals = set(featValues)
    # 创建集合，目的是除去重复数据
    for value in uniqueVals:
        subLabels = labels[:]
        # 相当于是复制了类标签
        myTree[bestFeatLabel][value] = createTree(
            splitDataSet(dataSet, bestFeat, value), subLabels)
        # 在数据集上递归调用只到找出所有的结果
    return myTree


dataSet, labels = createDataSet()

listOfTree = [{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}, {
    'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}},
    {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}, 3: 'maybe'}}]

print(classify(listOfTree[0], labels, [1, 0]))
print(classify(listOfTree[0], labels, [1, 1]))

storeTree(dataSet, 'classifierStorage.txt')
print(grabTree('classifierStorage.txt'))

示例：使用决策树预测隐形眼镜的类型

使用决策树预测隐形眼镜类型的一般流程

1. 收集数据：提供文本文件
2. 准备数据：解析tab键分隔的数据行
3. 分析数据：快速检查数据，确保正确的解析数据内容，使用createPlot()函数绘制最终的树形图
4. 训练算法：适用上文采用的createTree
5. 测试算法：编写测试函数验证决策树可以正确分类给定的数据实例
6. 使用算法：存储树的数据结构，以便下次使用时无需重新构造树

完整代码示例

import P36
# P36为本文中第一个完整代码的名称，主要是调用了createTree()函数
import P43
# P43为本文中第二个完整代码的名称，主要是调用了createPlot函数

fr = open('lenses.txt')
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLables = ['age', 'prescript', 'astigmatic', 'tearRate']
lensesTree = P36.createTree(lenses, lensesLables)
print(lensesTree)
P43.createPlot(lensesTree)

注意 ：匹配选项过多会产生过度匹配，为了减少过度匹配可以采用裁剪决策树，去掉一些非必要的叶子结点。若叶子结点只能增加少许信息，则可以删除该节点将它并入到其他叶子结点中。

小结

??决策树分类器就像带有终止块的流程图，终止块表示分类结果。开始处理数据集时，需要测量数据中的不一致性，也就是熵，然后寻找最优方案划分数据集，直到数据集中所有数据属于同一分类。ID3算法可以用于划分标称型数据集。构建决策树时，通常采用递归的方法将数据集转化为决策树。

其中lenses.txt文件数据为：

young	myope	no	reduced	no lenses
young	myope	no	normal	soft
young	myope	yes	reduced	no lenses
young	myope	yes	normal	hard
young	hyper	no	reduced	no lenses
young	hyper	no	normal	soft
young	hyper	yes	reduced	no lenses
young	hyper	yes	normal	hard
pre	myope	no	reduced	no lenses
pre	myope	no	normal	soft
pre	myope	yes	reduced	no lenses
pre	myope	yes	normal	hard
pre	hyper	no	reduced	no lenses
pre	hyper	no	normal	soft
pre	hyper	yes	reduced	no lenses
pre	hyper	yes	normal	no lenses
presbyopic	myope	no	reduced	no lenses
presbyopic	myope	no	normal	no lenses
presbyopic	myope	yes	reduced	no lenses
presbyopic	myope	yes	normal	hard
presbyopic	hyper	no	reduced	no lenses
presbyopic	hyper	no	normal	soft
presbyopic	hyper	yes	reduced	no lenses
presbyopic	hyper	yes	normal	no lenses