14.决策树的最终构建

前面是做了一轮决策，按照信息论的方式，对各特征做了分析，确定了能够带来最大信息增益（注意是熵减）的特征。但仅这一步是不够的，我们需要继续对叶子节点进行同样的操作，直到完成如下的目标：

[if !supportLists]1）[endif]程序遍历完所有划分数据集的属性；

[if !supportLists]2）[endif]每个分支下的所有实例都具有相同的分类；

如果程序已经遍历完所有划分数据集的属性，叶子节点下的实例仍然不具备相同的分类，那就采用多数表决的方法（有点像KNN）来决定该叶子节点的分类。

好，上代码。

def majorityCnt(classList):

    classCount={}

    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)

    return sortedClassCount[0][0]

如上代码就不逐行展开了，其实就是把一个数组中的标签项数一下数，然后找到哪一个标签出现的次数最多，和KNN中相关的排序方式类似。

我们再来看看，整棵树的遍历：

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 = labels[:]

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

    return myTree

代码一共16行。这段代码比较关键，而且不算太容易看懂，我们来逐行看一下：

def createTree(dataSet, labels):

#定义函数，dataSet实际上是带了标签值的数据集，labels其实是标签值的意义定义，详见前面的数据集定义

    classList = [example[-1] for example in dataSet]

#classList实际上就是标签值的数组，标签值位于数据集的最后一列

    if classList.count(classList[0]) == len(classList):

#这里做了一个判断，count方法的作用就是数出数组中某个元素值的个数，在这里就是对classList[0]做了计数，当它的数量等同于数组的长度时，说明这个数组里没有别的标签了，即已经分到了标签唯一的状态；按决策树叶子节点是否达到不可分的条件2，已经完成

        return classList[0]

#返回classList[0]，即当前叶子节点唯一的标签值

    if len(dataSet[0]) == 1:

        return majorityCnt(classList)

#如果dataSet的长度为1，那就等于是叶子节点中特征值只有1个，这个时候就满足了决策树叶子节点是否达到不可分的条件1，程序遍历完所有划分数据集的属性，这个时候我们要对叶子节点中的标签进行统计，通过多数表决的方法确定并返回这一分支的标签值。

    bestFeat = chooseBestFeatureToSplit(dataSet)

    bestFeatLabel = labels[bestFeat]

#如果不是上述的两种情况，即节点还可分，那么就用chooseBestFeatureToSplit方法找到最佳的特征项，并对节点进行分解。

    myTree = {bestFeatLabel:{}}

#建立一个字典myTree

    del(labels[bestFeat])

#删除已选出的特征

    featValues = [example[bestFeat] for example in dataSet]

#根据最佳特征的下标，从dataSet里取出相关特征的值的数组

    uniqueVals = set(featValues)

#去重，得到该数组中可能的值

    for value in uniqueVals:

#遍历所有可能的值

        subLabels = labels[:]

#复制出一个label数组，这个数组已经删掉了之前的最佳特征项

        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)

#根据最优的特征进行分叉，每一个分叉再去进行生成子树的递归操作（这是关键，通过递归遍历生成所有的子节点，并根据那两条要求确定是否终止并直接return）

    return myTree

#返回树（注意这里的返回，可能是一棵子树，因为是通过递归生成了整棵树，只有最开始的调用才是根节点）

好了，至此，这段代码结束。这段代码不算太容易看懂，原理好懂，但是算法理论要想跟代码联系在一起，还是挺复杂的。最终生成的树结构如下：

它是个什么呢？其实就是一开始的最优特征项是“no surfacing”，然后进行分叉，左边由于标签一致所以结束，右边进行再分叉，然后因为特征用完，结束。

一棵有意思的树。