决策树算法的理解及实现决策树算法的理解及实现

本文基本复制原文来源：http://www.cnblogs.com/lliuye/p/9008901.html，我个人认为已经非常详细了，所有理论基本来自周志华《机器学习》的决策树章节！

我主要是将该博客提供的源码进行了实践与大量注解，以便读者更容易理解。而为了读者方便理解，我将注解提供在源码内。经过源码注解，我已将作者小错误

classCount+=1改成classCount[value]+=1。我将代码附在原理后面，你可以通过debug形式解读代码等，因为代码已经是可以直接运行的，希望对学习机器学习的

决策树算法有帮助。

1. 决策树

决策树（decision tree）是一种基本的分类与回归方法（本文主要是描述分类方法），是基于树结构进行决策的，可以将其认为是if-then规则的集合。一般的，一棵决策树包含一个根节点、若干内部节点和若干叶节点。其中根节点包含所有样本点，内部节点作为划分节点（属性测试），叶节点对应于决策结果。

用决策树进行分类，是从根节点开始，对实例的某一特征进行测试，根据测试结果，将实例分配到其子节点，若该子节点仍为划分节点，则继续进行判断与分配，直至将实例分到叶节点的类中。

若对以上描述不太明白，可以结合以下图进行理解。

根据以上决策树，现在给你一个实例：{色泽：青绿，根蒂：稍蜷，敲声：清脆，纹理：清晰，脐部：稍凹，触感：光滑}，来判断该瓜是否是好瓜。其过程是：脐部（稍凹）–>根蒂（稍蜷）–>色泽（青绿）–>好瓜。

以上是由决策树来进行分类的过程。而决策树的学习（构建）通常是一个递归地选择最优特征的过程。那么构建决策树时如何选择特征作为划分点（即选择哪个特征作为根节点或者选择哪个特征作为非叶子节点）？当训练数据量大、特征数量较多时构建的决策树可能很庞大，这样的决策树用来分类是否好？

由这些问题我们可以知道，构建决策树的三个要点：
（1）特征选择
（2）决策树的生成
（3）决策树修剪

2. ID3算法

基于ID3算法的决策树构建，其选择特征的准则是信息增益。信息增益（information gain）表示得知特征

2.1 熵（Entropy）

熵是度量样本集合纯度最常用的一种指标，它是信息的期望值。我们首先了解一下什么是信息。由《机器学习实战》中定义：

如果待分类的事务可能划分在多个分类之中，则符号（特征）
$l (k) = - log 2 p (k)$

其中

而熵计算的是所有类别所有可能值包含的信息期望值，其公式为：

E n t (D) = - \sum k = 1 N p (k) log 2 p (k)

其中

（1）对于最终分类（是否为好瓜），计算其信息熵：
由上表可看出，一共有17个样本，属于好瓜的有8个样本，坏瓜的有9个样本，因此其熵为：

E n t (D) = - \sum k = 1 2 p k log 2 p k = - (8 17 log 2 8 17 +

E n t (D 1) = - (3 6 log 2 3 6 + 3 6 log 2 3 6 ) = 1.000

E n t (D 2) = - (4 6 log 2 4 6 + 2 6 log 2 2 6 ) = 0.918

E n t (D 3) = - (1 5 log 2 1 5 + 4 5 log 2 4 5 ) = 0.722

2.2 信息增益（information gain）

信息增益，由《统计学习方法》中定义：

特征
$G a i n (D, a) = E n t (D) - E n t (D | a)$

其中特征
$E n t (D | a) = \sum i = 1 v | D i | | D | E n t ( D i )$

我们根据例子对其进行理解：
对于特征“色泽”，我们计算其信息增益，由2.1中，集合

G a i n (D, 色 泽) = E n t (D) - \sum i = 1 3 | D i | | D | E n t (

2.3 算法步骤

ID3算法递归地构建决策树，从根节点开始，对所有特征计算信息增益，选择信息增益最大的特征作为节点的特征，由该特征的不同取值建立子节点；再对子节点递归地调用以上方法构建决策树；知道所有特征的信息增益均很小或者没有特征可以选择为止。最后得到一个决策树。

在算法中（C4.5也是），有三种情形导致递归返回：

（1）当前节点包含的样本全属于同一类别，无需划分。
（2）当前属性集为空，或是所有样本在所有属性上取值相同，无法划分。（此时将所含样本最多的类别设置为该叶子节点类别）
（3）当前节点包含的样本集合为空，不能划分。（将其父节点中样本最多的类别设置为该叶子节点的类别）

输入：训练数据集

3. C4.5算法

实际上，信息增益准则对可取值书目较多的属性有所偏好，例如如果将前面表格中的第一列ID也作为特征的话，它的信息增益将达到最大值，而这样做显然不对，会造成过拟合。为了减少这种偏好可能带来的不利影响，C4.5算法中将采用信息增益比来进行特征的选择。信息增益比准则对可取值数目较少的属性有所偏好。接下来，我们首先对信息增益比进行介绍。

3.1 信息增益比（增益率）

信息增益比的定义为：

G a i n_r a t i o (D, a) = G a i n ( D , a ) I V ( a )

I V (a) = - \sum i = 1 v | D i | | D | log 2 | D i | | D |

I V (色 泽) = - (6 17 \times log 2 6 17 + 6 17 \times log 2 6 17 + 5 17 \times

3.2 算法步骤

C4.5算法同ID3算法过程相似，仅在选择特征时，使用信息增益比作为特征选择准则。

输入：训练数据集

4. 剪枝处理

针对于在第1部分提到的最后一个问题：当训练数据量大、特征数量较多时构建的决策树可能很庞大，这样的决策树用来分类是否好？答案是否定的。决策树是依据训练集进行构建的，当决策树过于庞大时，可能对训练集依赖过多，也就是对训练数据过度拟合。从训练数据集上看，拟合效果很好，但对于测试数据集或者新的实例来说，并不一定能够准确预测出其结果。因此，对于决策树的构建还需要最后一步—-即决策树的修剪。
决策树的修剪，也就是剪枝操作，主要分为两种：
（1）预剪枝（Pre-Pruning）
（2）后剪枝（Post-Pruning）
接下来我们将详细地介绍这两种剪枝方法。

4.1 预剪枝（Pre-Pruning）

预剪枝是指在决策树生成过程中，对每个节点在划分前先进行估计，若当前节点的划分不能带来决策树泛化性能的提升，则停止划分并将当前节点标记为叶节点。
我们使用例子进一步理解预剪枝的过程：
将本文开始的西瓜数据集表划分成两部分，一部分作为训练集用来构建决策树，一部分作为验证集用来进行决策树的剪枝。具体划分见下图：

使用ID3算法进行决策树的构建，即使用信息增益进行特征的选择。首先选择特征“脐部”作为决策树根节点，如何判断该节点是否需要剪枝，需要对剪枝前后验证集精度进行比较。由“脐部”这个特征将产生三个分支“凹陷”、“稍凹”、“平坦”，并认定其分支结果（可采用多数表决法，当分类数量相当时，任选一类即可），如下图：

查看验证集，若将“脐部”看做节点，并将其标记为“好瓜”，那么划分前的精度为：

同理我们“色泽”以及“根蒂”特征进行划分前后精度的计算。对于“色泽”，划分后的精度为

4.1 后剪枝（Post-Pruning）

后剪枝是指先从训练集生成一棵完整的决策树，然后自底向上地对非叶节点进行考察，若将该节点对应的子树替换为叶节点能带来决策能力的提升，则将该子树替换成叶节点。
我们使用例子进一步理解后剪枝的过程：
同样适用4.1中的划分数据集。针对已建立好的决策树，我们首先对“纹理”特征节点进行处理，判断其是否需要剪枝，见下图。

首先，使用整个决策树对验证集进行预测，并将其预测结果与真实结果进行对比，可得到如下结果（预测结果与真实结果相同，标记为“正确”，否则标记为“不正确”）：

{(4, 正 确), (5, 不 正 确), (8, 不 正 确), (9, 不

代码如下：

from math import log

import operator

# C4.5算法与ID3算法仅有细微差别，其差别与代码在注释中体现
# #-------------------------------------构造决策树-----------------------------------------
# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):
    \'\'\'
    :param dataSet: 样本第一维度是样本个数，最后一个维度是每个样本的类别
    :return: 计算出每个类别的香浓熵
    \'\'\'
    numEntries = len(dataSet)  # 计算样本个数
    labelCounts = {}  # 用来统计每个标签的个数，如有3类,0类4个，1类5个，3类32个，则{0:4,1:5,2:32}
    for featVec in dataSet:  # 遍历样本
        currentLabel = featVec[-1]  # currentLabel保存分类标签 数据集最后一个为类别
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannanEnt = 0.0
    # shannonEnt = -(求和)[p(xi)log(2,p(xi))]
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # 以2为底求对数
        shannanEnt -= prob * log(prob, 2)
    return shannanEnt

# 按照给定特征划分数据集
def splitDataSet(dataSet, axis, value):
    \'\'\'
    :param dataSet:  数据集
    :param axis: 想要删掉的列
    :param value: 判断axis列删掉的值是否等于value，否则不能删除。原因在于该
    chooseBestFeatureToSplit函数将每个列循环，而value将某列值循环，这样就可以排除
    axis列的值不再value中而删除了。
    :return: 返回一个axis列满足value值的新数据，如[array([21., 1., 61.]), array([ 17., 41., 1.]),
    \'\'\'
    # 将dataSet中满足dataSet[axis] = value的行进行保留，
    # retDataSet中存储了保留行中除了axis列之外的其它列
    retDataSet = []
    for featVec in dataSet:
        # 除掉featVec[axis]列的内容
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            # extend() 函数用于在列表末尾一次性追加另一个序列中的多个值（用新列表扩展原来的列表)
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

# 遍历数据集，循环计算香农熵和splitDataSet()函数，
# 找到最好的划分方式（计算所有特征的信息增益，并进行比较选出最优的特征）
def chooseBestFeatureToSplit(dataSet):
    \'\'\'
    该函数执行一次便可以选择一个最好的节点
    :param dataSet: 需要筛选节点时候的所有数据集和，
    行表示样本数，列最后一列表示最终分类，其它列为属性值，
    每个属性可能包含多个特征
    :return: 返回最好的节点序号，如第3列属性最好，便返回3.（0列属性也包含）
    \'\'\'
    # 计算总特征数，数据集最后一列为分类标签。dataSet[0]是指第一条数据
    numFeatures = len(dataSet[0]) - 1  # 排除最后一列的干扰
    # 按照分类标签计算香农熵
    # baseEntropy为经验熵H(D)
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeaature = -1
    # 创建唯一的feature取值列表（分别对每个feature进行），对每个唯一feature值划分一次数据集
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]  # 得到dataSet数据集中第i列所有值，集第i个属性
        uniqueVals = set(featList)  # 第i个属性不同特征的集合，排除相同的特征
        newEntropy = 0.0  # newEntropy为经验条件熵H(D|A)
        # 计算每种划分方式的信息熵，并求该feature熵和
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # subDataSet是feature[i]=value的所有条目的列表（不包含feature[i]）
            # len(subDataSet)表示feature[i]=value的条目总数
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob * calcShannonEnt(subDataSet)
            # (C4.5)分裂信息：splitInfo
            # splitInfo -= prob * log(prob, 2)
        # 信息增益：g(D,A) = H(D) - H(D|A)
        inforGain = baseEntropy - newEntropy
        # (C4.5)信息增益率
        # inforGainRate = inforGain / splitInfo
        if inforGain > bestInfoGain:
            bestInfoGain = inforGain
            bestFeaature = i
    return bestFeaature


def majorityCnt(classList):
    \'\'\'
    该函数是构建决策树停止条件之一，当数据集只剩下最后一列的标签时候，
    会出现多个标签，则“投票法”，将选择标签最多的一个为最终标签
    :param classList: 为最终标签类的一列
    :return: 返回一个最终标签
    \'\'\'
    classCount = {}  # 保存数据集classList每个类别的数量
    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)  # 默认为从小到大
    \'\'\'
    a = [1,2,3] 
    >>> b=operator.itemgetter(1)      //定义函数b，获取对象的第1个域的值
    >>> b(a) 
    2 
    >>> b=operator.itemgetter(1,0)   //定义函数b，获取对象的第1个域和第0个的值
    >>> b(a) 
    (2, 1) 
    \'\'\'
    return sortedClassCount[0][0]  # 返回数量最多类的名字

# 创建树的函数代码
def createTree(dataSet, labels):
    \'\'\'
    :param dataSet:  （m,n）表示m行n列，第0--（n-1）列表示属性，
    第n列表示每个样本的分类结果，属于哪一类。
    :param labels: 是属性对应的标签，如有3个属性分别为第0、1、2列，
    那标签应为[\'颜色\',\'纹理\',\'触感\']
    :return:函数返回的是myTree，则在myTree[bestFeatLabel][value]建立
    myTree = {bestFeatLabel: {}}，一直在myTree[bestFeatLabel][value]建立
    \'\'\'

    classList = [example[-1] for example in dataSet]  # 创建样本类别标签列表

    # 下面的代码用最终分类即标签判断是否停止循环
    if classList.count(classList[0]) == len(classList):  # 类别完全相同则停止继续划分
        # classList.count(classList[0])表示该列classList中第一名字的数量
        return classList[0]  # 返回最终的结果
    # 遍历完所有特征时，返回出现次数最多的类别（dataset中只剩下一列类别）
    if len(dataSet[0]) == 1:
        # 表示只剩下类别了，这里处理最后一个节点应该给最终标签是什么。
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)  # 得到dataSet数据集中最好的属性作为节点，为数字型式
    bestFeatLabel = labels[bestFeat]  # 该属性作为节点的名字
    myTree = {bestFeatLabel: {}}  # 建立最好的属性值为空
    del(labels[bestFeat])  # 删除该节点
    # 得到列表包含的所有属性值
    featValues = [example[bestFeat] for example in dataSet]  # 得到bestFeat列所有值
    uniqueVals = set(featValues)  # 得到bestFeat列的属性值
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] =\
            createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        #                       已经是新的数据集了              新的标签
    return myTree  # 返回值是myTree





# 简单测试数据集
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 classify(inputTree, featLabels, testVec):
    \'\'\'
    :param inputTree:  输入的是树的结构，以字典形式给出
    :param featLabels: 输入测试数据的属性，要有训练数据的属性
    :param testVec:  测试数据，直接为1列，只有属性没有最终的类
    :return:  返回了最终的分类属性
    \'\'\'
    firstStr = list(inputTree.keys())[0]  # 树的第一个节点的名字
    restDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)  # 得到树firstStr节点对应的属性
    \'\'\'
    若树为{\'no surfacing\': {0: \'no\', 1: {\'flippers\': {0: \'no\', 1: \'yes\'}}}}
    firstStr就是得到树的第一个节点的名字no surfacing
    restDict就是得到\'no surfacing\'的其它字典，形式为
    {\'no surfacing\': {0: \'no\', 1: {\'flippers\': {0: \'no\', 1: \'yes\'}}}}
    featIndex 在labels找到对应的标签
    \'\'\'
    for key in restDict.keys():
        if testVec[featIndex] == key:
            # testVec 测试数据集在featIndex下只有一个值
            if type(restDict[key]).__name__ == \'dict\':
                classLabel = classify(restDict[key], featLabels, testVec)
            else:
                classLabel = restDict[key]  # 因为这里只剩下该key键值的一个最终类
    return classLabel    # 返回了最终的分类属性



#-------------------------------------存储决策树-----------------------------------------

def storeTree(inputTree, filename):
    \'\'\'
    :param inputTree:  输入树的字典
    :param filename:  需要保存的文件路径
    \'\'\'
    import pickle
    # fw = open(filename, "w")
    fw = open(filename, "wb+")
    pickle.dump(inputTree, fw)
    fw.close()


def grabTree(filename):
    \'\'\'
    :param filename:  从文件中读取字典
    :return:
    \'\'\'
    import pickle
    fr = open(filename, "rb+")
    return pickle.load(fr)




# 代码实现的主函数
if __name__ == \'__main__\':
    # 构建训练数据集
    dataSet, labels = createDataSet()
    # 训练模型生成决策树
    decision_tree_dict = createTree(dataSet, labels)
    print(decision_tree_dict) # 打印决策树，为字典类型保存
    # 构建测试数据集
    featLabels=[\'no surfacing\',\'flippers\']
    testVec=[0,1]
    # 采用下面的分类函数，就可以对测试数据进行分类了
    test_result=classify(decision_tree_dict, featLabels, testVec)
    print(test_result)  # 打印最终测试结果

结果如下：

最后：本人仅仅对代码进行了改动与详细的注解，感谢下方博客作者的提供，若有所见解或异议可在下方评论，谢谢！
原文来源：http://www.cnblogs.com/lliuye/p/9008901.html

本文链接：https://www.cnblogs.com/tangjunjun/p/12327900.html

决策树算法的理解及实现决策树算法的理解及实现

1. 决策树