[人工智能]机器学习-----决策树

一 决策树简介

你是否玩过二十个问题的游戏，游戏的规则很简单：参与游戏的一方在脑海里想某个事物，其他参与者向他提问题，只允许提20个问题，问题的答案也只能用对或错回答。问问题的人通过推断分解，逐步缩小待猜测事物的范围。或者是酒桌上的猜数游戏，游戏规则有点类似，参与游戏的一方在脑海里想一个固定的数值，需要在固定的范围内，其他参与者进行猜测，他会先给出猜测的正确与否，如果正确直接喝酒，如果错误，就在下一个参与者开始之前给出新的猜数范围，逐步缩小待猜测事物的范围。

决策树的工作原理与上面两个游戏类似，用户输入一系列数据，然后给出游戏的答案。我们经常使用决策树处理分类问题，近来的调查表明决策树也是最经常使用的数据挖掘算法。它之所以如此流行，一个很重要的原因就是不需要了解机器学习的知识，就能搞明白决策树是如何工作的。

如果以前没有接触过决策树，也完全不用担心，它的概念非常简单。通过简单的图形就可以了解其工作原理，图3-1所示的流程图就是一个决策树，长方形代表 判断模块（decision block），椭圆形代表 终止模块（terminating block），表示已经得出结论，可以终止运行。从 判断模块 引出的左右箭头称作 分支（branch），它可以到达另一个判断模块或者终止模块。

上面构造的是一个假想的邮件分类系统， 首先它检测发送邮件域名地址：

如果地址为myEmployer.com，则将其放在分类“无聊时需要阅读的邮件”中。
如果邮件不是来自这个域名，则检查邮件内容里是否包含单词曲棍球。
如果包含则将邮件归类到“需要及时处理的朋友邮件”。
如果不包含则将邮件归类到“无需阅读的垃圾邮件”。
第二章介绍的k-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，在这些机器根据数据集创建规则时，就是 机器学习 的过程。

二 决策树的构造

1.决策树的优缺点

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

2.决策树的一般流程

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

3.信息增益

划分数据集的大原则是：将无序的数据变得更加有序

在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择 。

在可以评测哪种数据划分方式就是最好的数据划分之前，必须学习如何计算信息增益。集合信息的度量方式称为香农熵 或者简称为熵 。
代码实现

def calcShannonEnt(dataSet):
    # 返回数据集的行数
    numEntries = len(dataSet)
    # 保存每个标签(Label)出现次数的字典
    labelCounts = {}
    # 对每组特征向量进行统计
    for featVec in dataSet:
        # 提取标签(Label)信息
        currentLabel = featVec[-1]
        # 如果标签(Label)没有放入统计次数的字典，添加进去
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        # Label计数
        labelCounts[currentLabel] += 1
    # 香农熵
    shannonEnt = 0.0
    # 计算香农熵
    for key in labelCounts:
        # 选择该标签(Label)的概率
        prob = float(labelCounts[key])/numEntries
        # 利用公式计算香农熵
        shannonEnt -= prob * log(prob, 2)
    # 返回香农熵
    return shannonEnt
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

4 划分数据集

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

def splitDataSet(dataSet, axis, value):
    # 创建返回的数据集列表
    retDataSet = []
    # 遍历数据集
    for featVec in dataSet:
        if featVec[axis] == value:
            # 去掉axis特征
            reducedFeatVec = featVec[:axis]
            # 将符合条件的添加到返回的数据集
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    # 返回划分后的数据集
    return retDataSet

5 递归构建决策树

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

递归结束的条件：程序遍历完所有划分数据集的属性，或者每个分支下的所有实例都具有相同的分类。如果所有实例具有相同的分类，则得到一个叶子节点或者终止块。任何到达叶子节点的数据必然属于叶子节点的分类。如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时我们需要决定如何定义该叶子节点，在这种情况下，我们通常会采用多数表决的方法决定该叶子节点的分类。
代码实现

#多数表决
def majorityCnt(classList):
    classCount = {}
    # 统计classList中每个元素出现的次数
    for vote in classList:
        if vote not in classCount.keys():classCount[vote] = 0
        classCount[vote] += 1
    # 根据字典的值降序排序
    sortedClassCount = sorted(classCount.items(), key = operator.itemgetter(1), reverse = True)
    # 返回classList中出现次数最多的元素
    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]
    # 遍历完所有特征时返回出现次数最多的类标签
    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
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

三 绘制树形图

1 代码实现

#获得叶节点的数目
def getNumLeafs(myTree):
    # 初始化叶子
    numLeafs = 0
    #python3中myTree.keys()返回的是dict_keys,不在是list,
    #所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
    firstStr = next(iter(myTree))
    # 获取下一组字典
    secondDict = myTree[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
    #python3中myTree.keys()返回的是dict_keys,不在是list,
    #所以不能使用myTree.keys()[0]的方法获取结点属性，可以使用list(myTree.keys())[0]
    firstStr = next(iter(myTree))
    # 获取下一个字典
    secondDict = myTree[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):
    """
    用于测试的预定义的树结构 
    """
    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]

//标注有向边属性值
def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]#计算标注位置
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

#绘制决策树
def plotTree(myTree, parentPt, nodeTxt):
    # 设置结点格式
    decisionNode = dict(boxstyle="sawtooth", fc="0.8")
    # 设置叶结点格式
    leafNode = dict(boxstyle="round4", fc="0.8")
    # 获取决策树叶结点数目，决定了树的宽度
    numLeafs = getNumLeafs(myTree)
    # 获取决策树层数
    depth = getTreeDepth(myTree)
    # 下个字典
    firstStr = next(iter(myTree))
    # 中心位置
    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]
    # y偏移
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    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):
    # 创建fig
    fig = plt.figure(1, facecolor='white')
    # 清空fig
    fig.clf()
    axprops = dict(xticks=[], yticks=[])
    # 去掉x、y轴
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)
    # 获取决策树叶结点数目
    plotTree.totalW = float(getNumLeafs(inTree))
    # 获取决策树层数
    plotTree.totalD = float(getTreeDepth(inTree))
    # x偏移
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;
    # 绘制决策树
    plotTree(inTree, (0.5,1.0), '')
    # 显示绘制结果
    plt.show()


#main
if __name__ == '__main__':
    myTree = retrieveTree(0)
    createPlot(myTree)

2 运行结果

四 测试和存储分类器

1.使用决策树执行分类

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

代码实现

def classify(inputTree, featLabels, testVec):
    # 获取决策树结点
    firstStr = next(iter(inputTree))
    # 下一个字典
    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

2.决策树的存储

构造决策树是很耗时的任务，即使处理很小的数据集，如前面的样本数据，也要花费几秒的时间，如果数据集很大，将会耗费很多计算时间。然而用创建好的决策树解决分类问题，则可以很快完成。因此，为了节省计算时间，最好能够在每次执行分类时调用已经构造好的决策树。

代码实现

def storeTree(inputTree, filename):
    with open(filename, 'wb') as fw:
        pickle.dump(inputTree, fw)
def grabTree(filename):
    fr = open(filename, 'rb')
    return pickle.load(fr)

五 实战：预测隐形眼镜类型

1.代码实现

import pandas as pd
import numpy as np
import matplotlib.pyplot as plt

from sklearn.preprocessing import LabelEncoder, OneHotEncoder
from sklearn.externals.six import StringIO
from sklearn import tree

if __name__ == '__main__':
    with open('lenses.txt', 'r') as fr:                               #加载文件
        lenses = [inst.strip().split('\t') for inst in fr.readlines()]#处理文件
    lenses_target = []                                                #提取每组数据的类别，保存在列表里
    for each in lenses:
        lenses_target.append(each[-1])
    print(lenses_target)

    lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']     #特征标签
    lenses_list = []                                                  #保存lenses数据的临时列表
    lenses_dict = {}                                                  #保存lenses数据的字典，用于生成pandas
    for each_label in lensesLabels:                                   #提取信息，生成字典
        for each in lenses:
            lenses_list.append(each[lensesLabels.index(each_label)])
        lenses_dict[each_label] = lenses_list
        lenses_list = []
    # print(lenses_dict)                                              #打印字典信息
    lenses_pd = pd.DataFrame(lenses_dict)                             #生成pandas.DataFrame
    # print(lenses_pd)                                                #打印pandas.DataFrame
    le = LabelEncoder()                                               #创建LabelEncoder()对象，用于序列化
    for col in lenses_pd.columns:                                     #序列化
        lenses_pd[col] = le.fit_transform(lenses_pd[col])
    # print(lenses_pd)                                                #打印编码信息

    clf = tree.DecisionTreeClassifier(max_depth = 4)                  #创建DecisionTreeClassifier()类
    # clf = clf.fit(lenses_pd.values.tolist(), lenses_target)         #使用数据，构建决策树
    tree.plot_tree(clf.fit(lenses_pd.values.tolist(), lenses_target), filled=True)
    plt.show()

2.运行结果