这一章分为三部分：

• 决策树的构造方法
• 测试和存储分类器
• 使用matplotlib画出决策树结构

1. 决策树的构造

根据数据集构建树的过程就是决策树算法的学习过程。那么该如何构造树呢？根据数据的特征来划分数据集，以构造树。

在构造决策树时，我们需要解决的第一个问题是，当前数据集上哪个特征在划分数据分类时起决定性作用(即根据该特征来划分效果最好，效果的评价在后面讲)。为了找到决定性的特征，划分出最好的结果，我们必须评估每个特征。找到最佳特征后，原始数据集就被划分为几个数据子集。这些数据子集会分布在第一个决策点(就是选取的那个特征)的所有分支上。如果某个分支下的数据属于同一类型，则无需进一步对数据集进行分割。否则，需要在数据子集上重复进行划分数据集的过程。

书中使用的是ID3算法来划分数据集，每次使用一个特征来划分数据，如果该属性有4个可能的值，就把数据划分为4份。所以，要求特征的取值为离散值。

按照下面顺序讲解：

• 数据集的熵
• 按给定特征划分数据集
• 使用信息增益来选择最好的划分方式
• 递归构造决策树

1.1 数据集的熵

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

而信息熵可以用于评价信息的有序程度。

这一节讲的是要通过信息增益来选择待划分的特征。关于熵和信息增益的概念可以看这里、这里、这里、这里还有这里。如果根据某一特征划分数据集的信息增益最大，那么就使用该特征。

首先需要计算原始数据集的熵，再计算根据某一特征划分后的子集的条件熵。熵-条件熵就的到了信息增益，即划分后数据稳定了多少，稳定的越多，划分的效果就越好。

下面代码用于求给定数据集的熵：

from math import log
# 计算给定数据集的熵
# dataSet为二维列表，[[feature1,feature2,...,label],...]形式
def calcShannonEnt(dataSet):
    # 数据的个数
    numEntries = len(dataSet)
    labelCounts = {}
    # 统计各label出现的次数，也就是每一类有多少数据
    for featVec in dataSet:
        currentLabel = featVec[-1]
        labelCounts[currentLabel] = labelCounts.get(currentLabel, 0) + 1
        
    shannonEnt = 0.0
    # 计算整个数据集的熵
    for value in labelCounts.values():
        # 某一类在整个数据集中出现的概率
        prob = float(value) / numEntries
        # 求熵的公式
        shannonEnt -= prob * log(prob,2)
    return shannonEnt

1.2 按给定特征划分数据集

在求条件熵之前需要先根据某一特征划分完数据，下面代码完成这一操作：

# 按照给定特征划分数据集
# dataSet为二维列表，[[feature1,feature2,...,label],...]形式，待划分数据集
# axis为划分特征索引
# 如果特征取值为value则将该数据划分出来。
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            # 注意这里将数据的特征featVec[axis]去掉后，
            # 再将数据加入新的集合
            reducedFeatVec = featVec[:axis]
            # 这里注意不能使用append
            reducedFeatVec.extend(featVec[axis+1:])
            # 此时reducedFeatVec为去掉特征后的数据
            # 将其加入子集
            retDataSet.append(reducedFeatVec)
    # 返回的子集中的数据都是本身具有值为value的特征featVec[axis]
    return retDataSet

1.3 使用信息增益来选择最好的划分方式

下面的代码重复使用所有的特征来划分数据，并计算每一次划分后的信息增益，找到使划分后信息增益最大的那个特征。

# 选择最好的数据集划分方式(特征)
# dataSet为二维列表，[[feature1,feature2,...,label],...]形式，待划分数据集
# 最好的划分方式也就是使数据集更为有序，熵值也就越低
def chooseBestFeatureToSplit(dataSet):
    # 得到feature的个数
    numFeatures = len(dataSet[0]) - 1
    # 计算初始数据集的熵
    baseEntropy = calcShannonEnt(dataSet)
    
    # 记录最大信息增益和对应的特征索引
    bestInfoGain = 0.0; bestFeature = -1
    # 按各个feature来迭代划分数据集，找到使信息增益最多的那个划分
    for i in range(numFeatures):
        # 将所有数据的第i个feature存入list中
        featureList = [example[i] for example in dataSet]
        # 仅保留唯一feature值，划分的数据子集数也就是len(uniqueVals)
        # 就是得到数据集中该特征的所有取值。
        uniqueVals = set(featureList)
        # 用于计算子集条件熵
        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

1.4 递归构造决策树

既然是使用递归，那么首先就需要确定停止条件，这里有两个停止条件对应两种情况：

• 每个分支下的所有实例都具有相同的分类，即该子集中的所有实例都属于一个类别了，此时不需要再继续划分，直接返回该类别。
• 如果已经对所有的特征进行划分了，这时仍然不能区分一些实例，即这些实例的特征值都相同，但却有着不同的分类。此时采用多数表决来决定该子集或该分支的类别。

下面代码用于完成多数表决的功能：

"""
输入的是集合中所有实例的类别，也就是之前dataSet的最后一列
"""
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        classCount[vote] = classCount.get(vote, 0) + 1
    sortedClassCount = sorted(classCount.items(), 
                       key=operator.itemgetter(1), 
                       reverse=True)
    return sortedClassCount

递归的过程是，在createTree()中先判断是否符合停止条件，符合则返回类别，否则，进行下面的迭代过程：对于某一集合，通过函数chooseBestFeatureToSplit(dataSet)找到使划分后信息增益最大的那个特征，对于该集合中该特征的n个取值，循环划分该集合(循环的次数即为n)，在每次循环中使用splitDataSet(dataSet, axis, value)根据该特征的取值进行一次划分得到一个子集(共有n个子集)，然后再调用createTree()函数对该子集进行迭代划分。这样就相当于最先找到一个叶节点，之后返回再找到相邻的叶节点。假设根节点的度为5，那么先完成第一个分支的构建，之后再完成下一分支。。。。。

下面为创建树的代码：

# dataSet为二维列表，[[feature1,feature2,...,label],...]形式，待划分数据集
# labels为所有的特征名，也就是dataSet[i,:-1]各个列的名字
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]
    # 将该特征作为当前根节点来构建子树
    # 结构是多层嵌套的字典。
    # 如果key的value是类标签，则是叶节点
    # 若果是另一个字典，则是一个判断节点
    myTree = {bestFeatLabel:{}}
    # 下面就是根据该特征划分，该特征已经使用，将其从特征列表中删除，注意这里的删除是对原始labels中操作了
    del(labels[bestFeat])
    # 得到当前数据集中该特征的所有取值
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    # 根据特征取值来划分数据集，由于在循环中递归调用了本函数
    # 这样就会不断进行划分的过程，直到完全分完该数据集
    for value in uniqueVals:
        subLabels = labels[:]
        newDataSet = splitDataSet(dataSet, bestFeat, value)
        myTree[bestFeatLabel][value] = createTree(newDataSet, subLabels)
    return(myTree)

可见代码中使用深层嵌套的字典来代表树的结构。字典中有两种key，特征名称和该特征的取值。只有一种value，即类别。

下面代码构建一个简单的树：

# 一个简单的数据集
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

myDat,labels = createDataSet()
# 构建树
createTree(myDat, labels)
"""
结果为(缩进一下方便看)：
{'no surfacing': {0: 'no', 
                  1: {'flippers': {0: 'no', 
                                   1: 'yes'}}}}
"""

2. 测试和存储分类器

使用构造好的树来对新实例进行分类。这里还是使用递归操作来查找类别：

# 使用决策树进行分类，还是递归操作
# inputTree为createTree()返回的树
# featLabels为各特征按顺序组成的列表，用于得到某一特征的索引
# testVec为待分类实例
def classify(inputTree, featLabels, testVec):
    # 传入的inputTree一定是个树或子树
    # 所以firstStr一定为某一特征名
    firstStr = list(inputTree.keys())[0]
    # 得到该特征的分支，secondDict.keys()为该特征的各个取值
    secondDict = inputTree[firstStr]
    # 该特征在特征列表中的索引
    featIndex = featLabels.index(firstStr)
    # key为该特征的各个取值
    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

上面代码有一个bug，如果输入实例的某一特征值在训练集中没有出现过，则代码会产生错误。修改如下：

# 使用决策树进行分类，还是递归操作
# inputTree为createTree()返回的树
# featLabels为各特征按顺序组成的列表，用于得到某一特征的索引
# testVec为待分类实例
def classify(inputTree, featLabels, testVec):
    # 传入的inputTree一定是个树或子树
    # 所以firstStr一定为某一特征名
    firstStr = list(inputTree.keys())[0]
    # 得到该特征的分支，secondDict.keys()为该特征的各个取值
    secondDict = inputTree[firstStr]
    # 该特征在特征列表中的索引
    featIndex = featLabels.index(firstStr)
    
    # 如果输入实例的对应特征的值在secondDict.keys()中，说明其可能属于该子集下的某一类别
    if testVec[featIndex] in secondDict.keys():
        # 如果该分支下面还有分支，则进行迭代
        if type(secondDict[testVec[featIndex]]).__name__ == 'dict':
            classLabel = classify(secondDict[testVec[featIndex]], featLabels, testVec)
        # 如果下面已经没有分支了，说明找到了对应的类别
        else:
            classLabel = secondDict[testVec[featIndex]]
    # 如果输入实例的该特征的值不存在于树中，则返回没有该类
    else:
        classLabel = 'no class'
    # 返回所属类别
    return classLabel

代码测试如下：

>>> myDat,labels = createDataSet()
>>> classify(myTree, labels, [1,2])
'no class'
>>> classify(myTree, labels, [1,0])
'no'
>>> classify(myTree, labels, [1,1])
'yes'

分类器的存储就是将树字典有pickle序列化存储，很简单。关于python中序列化操作的简介可看这里。

本章介绍的决策树算法有很多的缺点，如对输入数据的过拟合，ID3算法无法处理数值型数据。在后面的章节中会介绍决策树的裁剪和CART算法来改正这些问题。

3. 使用matplotlib画出决策树结构

待续。。。。。。

4. 参考

关于决策树比较详细的总结在这里。