这一章分为三部分：
- 决策树的构造方法
- 测试和存储分类器
- 使用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. 参考
关于决策树比较详细的总结在这里。
