决策树算法及实践

参考书籍《机器学习实战》

决策树算法概述

K-近邻算法可以完成很多分类任务，但是它最大的缺点就是无法给出数据的内在含义，决策树的主要优势就在于数据形式非常容易理解。

决策树算法能够读取数据集合，构建类似于图3-1的决策树。决策树很多任务都是为了数据中所蕴含的知识信息，因此决策树可以使用不熟悉的数据集合，并从中提取出一系列规则，机器学习算法最终将使用这些机器从数据集中创造的规则。专家系统中经常使用决策树，而且决策树给出结果往往可以匹敌在当前领域具有几十年工作经验的人类专家。

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

一些决策树算法采用二分法划分数据，本书并不采用这种方法。如果依据某个属性划分数据将会产生4个可能的值，我们将把数据划分成四块，并创建四个不同的分支。每次划分数据集时我们只选取一个特征属性，如果训练集中存在20个特征，第一次我们选择哪个特征作为划分的参考属性呢？

表3-1的数据包含5个海洋动物，特征包括：不浮出水面是否可以生存，以及是否有脚蹼。我们可以将这些动物分成两类：鱼类和非鱼类。现在我们想要决定依据第一个特征还是第二个特征划分数据。在回答这个问题之前，我们必须采用量化的方法判断如何划分数据。

信息増益
划分数据集的大原则是：将无序的数据变得更加有序。我们可以使用多种方法划分数据集，但是每种方法都有各自的优缺点。组织杂乱无章数据的一种方法就是使用信息论度量信息，信息论是量化处理信息的分支科学。我们可以在划分数据之前使用信息论量化度量信息的内容。
在划分数据集之前之后信息发生的变化称为信息增益，知道如何计算信息增益，我们就可以计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为：其中p(xi)是选择该分类的概率。

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

使用Python实现决策树算法

创建文件Tree.py

#coding:utf-8
from math import log
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)#数据集总数   #数据集格式为{条件1，条件2...，分类结果}
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]#得到分类结果
        if currentLabel not in labelCounts.keys():#新的分类
            labelCounts[currentLabel] = 0#记录分类
            labelCounts[currentLabel] += 1#该分类总数+1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries#信息值
        shannonEnt -= prob * log(prob,2)#熵
    return shannonEnt

测试输出数据集及输出熵的计算结果

得到熵之后，我们就可以按照获取最大信息增益的方法划分数据集

划分数据集
上节我们学习了如何度量数据集的无序程度，分类算法除了需要测量信息熵，还需要划分数据集，度量花费数据集的熵，以便判断当前是否正确地划分了数据集。我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。想象一个分布在二维空间的数据散点图，需要在数据之间划条线，将它们分成两部分，我们应该按照x轴还是y轴划线呢？答案就是本节讲述的内容。要划分数据集，打开文本编辑器，在Tree.py文件中添加下列的代码：

def splitDataSet(dataSet,axis,value):#划分数据集
    retDataSet = []#生成新的list
    for featVec in dataSet:
        if featVec[axis] == value:#满足条件则把该条数据提取出来
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet#返回新的数据集

按照不同条件划分测试：

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

---

选择最好的数据集划分方式

在Tree.py中添加如下代码：

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个特征值
        uniqueVals = set(featList)#得到第i个特征的所有非重复值
        newEntropy = 0.0
        for value in uniqueVals:#计算按照第i个特征按照所有非重复值划分时包含的信息熵
            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

chooseBestFeatureToSplit函数返回结果告诉我们应该按照哪一个特征划分包含的信息最大，结果为0（第一个特征）：

那么这个划分结果是否有意义呢？如果我们按照第一个特征划分数据集，第一个特征为1的海洋生物有两个鱼类，一个非鱼类；另一个分组则全部属于非鱼类。如果按照第二个特征划分，则第一个分组有两个鱼类，两个非鱼类；另一个分组有一个非鱼类。显然按照第一个特征划分更好。

递归构建决策树

之前的步骤我们已经能够按照最好的属性划分数据集，由于特征可能多于两个，选择一个特征后应该从剩下的特征继续选择最好的划分特征，直到所有特征都被考虑在内，因此我们可以采用递归的原则处理数据集。参见图3-2

如果数据集已经处理了所有的属性，但是类标签依然不是唯一的，此时我们采用多数表决的方法决定其标签。
在Tree.py中添加如下代码：

import operator
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote]+=1
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]

为了创建树，在Tree.py中添加如下代码：

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]#得到label标签
    if classList.count(classList[0])==len(classList):#所有标签都是一样的，直接返回
        return classList[0]
    if len(dataSet[0]) == 1:#所有特征遍历1次
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#最好划分特征
    bestFeatLabel = labels[bestFeat]#该特征对应的标签
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])#从labels中删除该特征
    featValues = [example[bestFeat] for example in dataSet]#在dataSet中得到该特征的所有值
    uniqueVals = set(featValues)#得到该特征的不重复值
    for value in uniqueVals:
        subLabels = labels[:]#除去该特征后还剩余的其他特征
        #将剩余特征写作当前特征的子树
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

以递归的方式创建，每一次判断一个特征，将剩余特征做为该特征的分支，直到所有特征遍历完；若有不能决断的标签则按多数表决决定。
决策树建立完成后输出测试：

树的图形化显示：略

测试和存储分类器

之前主要内容为如何创建决策树，本节将使用决策树构建分类器。
在Tree.py中添加分类代码：

def classify(inputTree,featLabels,testVec):
    firstStr = 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

虽然树中划分好了特征分类的结构，但是计算机并不知道特征在特征分组中的位置，例如'no surfacing'在测试数据中到底是在第一个位置还是第2个位置？所以分类器的第一步是判断出各个特征在源数据中的位置，之后再遍历整棵树，找到测试数据的对应标签。

可以看到对输入的数据，决策树能做出正确的判断，即使是训练数据没有的组合，也能作出相应判断。

决策树的存储

构建决策树是一个很耗时的任务，如果数据量较大，会花费更多时间。而不同于KNN算法，决策树的好处是能够使用创建好的决策树解决分类问题，我们可以在创建好树后保存在本地磁盘，方便下次使用。
在Tree.py中添加如下代码：

def storeTree(inputTree,filename):
    import pickle
    fw = open(filename,'w')
    pickle.dump(inputTree,fw)
    fw.close
def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

之后在test.py中运行一次Tree.storeTree()，就可以使用Tree.grabTree()读取决策树了