决策树代码详解——真正地一行一行来解读_决策树代码复杂吗

因为决策树代码构建有点复杂，整体贴上来会显得有点难懂，所以我们在这里将从每个函数开始一点一点进行讲解，最后把这些函数按顺序复制到程序里就能运行：

首先是第一个函数：生成数据集。

def createDataSet():
    dataSet = [[1, 1, 1, 'yes'],
               [1, 0, 1, 'yes'],
               [1, 0, 2, 'no'],
               [0, 1, 2, 'no'],
               [0, 1, 2, 'no'],
               [1, 1, 2, 'yes'],
               [0, 0, 2, 'yes'],
               [0, 1, 0, 'no'],
               ]
    labels = ['ddddd','fffff','sssss']
    #change to discrete values
    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[currentLabel] += 1
    shannonEnt = 0.0
    for key in labelCounts:  # 计算信息熵
        prob = float(labelCounts[key]) / numEntries
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt
'
运行
运行

我们来分析一下这个函数。首先它输入一个数据集，就用上面的函数返回的dataSet就好了。

然后我们先计算出样本数，并采用中括号构建一个字典。

然后遍历每个样本，featVec[-1]表示每个样本中的数据的最后一个数据的值，也就是分类用的类别，在我们的数据集里分别是yes和no。如果该类别在字典里没有，则说明是一个新类别，然后我们就让字典包含该类别。然后数值+1。

在我们的例子中，我们先读到第一个数据 [1, 1, 1, 'yes'],此时字典还是空的，所以我们把yes放入字典里，然后yes的值+1。

紧接着我们读到第二个数据：[1, 0, 1, 'yes']，然后发现字典里已经有该类别的值了，所以字典里的数值+1.

然后读到第三个数据：[1, 0, 2, 'no'],发现字典里没有'no'，所以字典里生成新的类别，并+1。

等都读取完以后，建立一个变量shannonEnt，表示香农能量熵。

在该for循环中，遍历字典里所有的类别（该例子只有yes和no两个类别），然后计算香农能量熵。

之后我们可以打印测试一下：

myDat,labels=createDataSet()
shannonEnt=calcShannonEnt(myDat)
print(shannonEnt)

输出1.0

然后是第三个函数：划分子数据集。

# 划分数据集，axis:按第几个属性划分，value:要返回的子集对应的属性值
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    featVec = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
'
运行
运行

在我们构建决策树需要进行进一步分类时，我们需要用到该函数。

该函数的意义是根据用于分类的标签生成子数据集。

举个例子：假如我们输入的是之前建立的dataSet：splitDataSet(DataSet,0,1)

    dataSet = [[1, 1, 1, 'yes'],
               [1, 0, 1, 'yes'],
               [1, 0, 2, 'no'],
               [0, 1, 2, 'no'],
               [0, 1, 2, 'no'],
               [1, 1, 2, 'yes'],
               [0, 0, 2, 'yes'],
               [0, 1, 0, 'no'],
               ]

之后在for中，我们判段dataSet里面的每个样本数据的第0个特征的值，如果是1，就保留，保留的方式是把该特征去掉，用剩下的特征加分类值构成一个子样本数据，如果是0，就不用管。

在dataSet中，第一个样本数据的第0个特征是1，符合，所以去掉该特征然后生成子样本[ 1, 1, 'yes']。

第二个样本数据的第0个特征是1，符合，所以去掉该特征然后生成子样本[ 0, 1, 'yes']

遍历完整个dataSet以后，就得到了根据特征值划分的子空间，打印一下：

asa = splitDataSet(myDat, 0, 1)
print(asa)

打印结果：

[[1, 1, 'yes'], [1, 1, 'yes'], [0, 2, 'no'], [1, 2, 'yes']]
'
运行
运行

然后是第四个函数：选择最好的数据集划分方式

def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1  # 属性的个数。 -1是因为最后一个是分类的标签
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):  # 对每个属性记录信息增益
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)  # 该属性的取值集合
        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
'
运行
运行

输入数据集然后寻找最好的划分方式，返回值代表最好的用来划分的特征。待会测试的时候输入dataSet为上一个函数生成的子数据集，即 [[1, 1, 'yes'], [1, 1, 'yes'], [0, 2, 'no'], [1, 2, 'yes']] 。

现在详细解释一下这个函数：

dataSet[0]代表第一个样本，即[1, 1, 'yes']，长度为3, 3-1=2，表示该样本的特征数。

然后计算出香农熵。

定义增益初始为0.0，然后初始的特征坐标为-1。

之后用i来把样本的特征遍历一遍。这里只有两个特征。

在每个特征里，首先用 [example[i] for example in dataSet] 提取所有样本第 i 个特征值的列表，此处我们假设正在第0个特征中，把每个样本的第0个特征分别提取出来，就生成了如下值：[1,1,0,1]。之后，通过uniqueVals = set(featList)可以把列表中不同的值都取出来。然后生成新的列表。这里一共就只有两个不同的特征值，一个是1，一个是0。

然后我们进行划分：遍历该特征所有不同的值，分别用该特征不同的值进行划分：subDataSet = splitDataSet(dataSet, i, value)，在该例子中我们划分出来的结果是：第0个特征为1时：[[1, 'yes'], [1, 'yes'], [2, 'yes']] ; 第0个特征为0时：[[2, 'no']]。在for循环里计算累加这种靠这种划分方式的熵。

之后再计算增益。找到按哪个特征进行划分增益最大。然后返回该划分方式的索引。

我们把上一个函数中输出的asa输入进去：

bestFeteTest = chooseBestFeatureToSplit(asa)
print(bestFeteTest)

打印结果为 0

我们研究一下这个结果：

如果根据第0个特征划分asa，则生成结果为：

第0个特征为1时：[[1, 'yes'], [1, 'yes'], [2, 'yes']] ; 第0个特征为0时：[[2, 'no']]

如果根据第1个特征划分asa，则生成结果为：

第1个特征为1时：[[1, 'yes'], [1, 'yes']] ; 第1个特征为2时：[[0, 'no'],[1, 'yes']]

显然根据第一个特征进行划分，结果是对半分的（每边都是2个），对半分的划分方式无序性更大，不如第一个划分方式。

然后是第五个函数：通过排序返回出现次数最多的类别

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(), #注意python3.x中要改成.items()函数
                              key=operator.itemgetter(1), reverse=True)
    return sortedClassCount[0][0]
'
运行
运行

这个函数有什么用呢？我们想象这样一种情况：因为每次我们划分数据的时候，都会用掉一个特征来进行划分。用掉的特征以后不会再使用了（因为用一个特征划分好以后，其每个子分支各自的该特征的值都是一样的）。假设在我们不断细分的过程中，发现所有的特征值都用完了，这时候该怎么办呢？很显然我们没法再继续下分了，所以需要返回当前类别，这个类别就用分到这个树枝的所有类别中比例最大的来代替，即假如分到该树枝的类别中有5个yes，2个no，最后我们就把它作为yes返回。

这种统计计数的方式还是靠创建字典来完成实现的。假设在for循环里统计的时候我们生成了这样的数据格式：{'no':2, 'yes':5}。然后用sorted函数对字典记录的每个类别的键值进行排序，排序完之后得到如下结果：[('yes', 5), ('no', 2)]。sortedClassCount[0][0]代表数量最大的那个类别值。

我们做个测试：

aks = ['yes','yes','no','yes','no','yes','yes']
majorityCnt(aks)

输出 

[('yes', 5), ('no', 2)]
'
运行
运行

至于为什么我们的输入是 ['yes','yes','no','yes','no','yes','yes']而不是 [['yes'],['yes'],['no'],['yes'],['no'],['yes'],['yes']]，下一个构建树的程序会首先提取最后一列：[example[-1] for example in dataSet]，提取出来的值是一个一维列表，而不再是二维列表了。后面还会再说。

最后一个函数：构建决策树。

终于到最后一个函数了。

# 递归构建决策树
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]
    uniqueValue = set(featValues)  # 该属性所有可能取值，也就是节点的分支
    for value in uniqueValue:  # 对每个分支，递归构建树
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(
            splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree
'
运行
运行

构建过程涉及递归操作。递归一般很难描述，这里想办法把递归的结构描述一下。

首先要注意我们在函数开头把最后面的类别读出开。然后用两个if判断，如果都是属于同一类别的，则直接将该类作为该树枝里的样本所代表的类。如果用于划分的特征都用完了，就直接把该类中数量最多的类别返回。

如果没有用完特征并且树枝里有许多别的类别，就继续处理：

构建一个树，采用最好的划分特征进行划分。删除该特征的列，然后对每个分支进行递归构建决策树。

至此，整个决策树的程序就构建好了。

我们运行验证一下：

print(createTree(myDat, labels))

打印结果为：

{'sssss': {0: 'no', 1: 'yes', 2: {'ddddd': {0: {'fffff': {0: 'yes', 1: 'no'}}, 1: {'fffff': {0: 'no', 1: 'yes'}}}}}}
'
运行
运行

勉强能看出来我们的分类方式。

下面将介绍如何把生成的决策树图表示出来。