决策树系列————决策树基础

本文参考

决策树

决策树是一种基本的基本的回归和分类方法，本文主要讨论分类。

分类决策树

分类过程，表示基于特征对实例进行划分的过程，可认为是 if—then的集合，也可看做是定义在特征空间与分类空间上的条件概率分布。
决策树的构建通常包括三个步骤：特征选择、决策树的生成、决策树的剪枝

用决策树分类：从根节点开始，对实例的某一特征进行测试，根据测试结果将实例分配到其子节点，此时每个子节点对应着该特征的一个取值，如此递归的对实例进行测试并分配，直到到达叶节点，最后将实例分到叶节点的类中。

经验熵与条件熵

划分数据集的大原则是：将无序数据变得更加有序，但是各种方法都有各自的优缺点，信息论是量化处理信息的分支科学，在划分数据集前后信息发生的变化称为信息增益，获得信息增益最高的特征就是最好的选择，所以必须先学习如何计算信息增益，集合信息的度量方式称为香农熵，或者简称熵。

当熵中的概率由数据估计(特别是最大似然估计)得到时，所对应的熵称为经验熵(empirical entropy)。

信息增益

下图中的H（D）应为H（D|A）
数据集

计算集合中的熵的代码如下：

##决策树
from math import log
##构建数据集
def creatDataSet():
    # 数据集
    dataSet = [[0, 0, 0, 0, 'no'],
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    # 分类属性
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
    # 返回数据集和分类属性
    return dataSet, labels

##计算经验熵
def calcShannonEnt(dataSet):
    """
    计算数据集中的经验熵
    :param dataSet:  数据集
    :return: 返回经验熵
    """
    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 = (labelCounts[key])/numEntries
        shannonEnt -= prob*(log(prob,2))
    return shannonEnt

选择最好的特征进行划分

#计算信息增益
##选择最好的特征
def chooseBestFeatureToSplit(dataSet):
    """
    对每个特征计算信息增益
    返回最好的特征索引
    :param dataSet:
    :return:
    """
    baseEntropy= calcShannonEnt(dataSet)
    numFeatures = len(dataSet[0]) -1
    bestInfoGain  = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featureList = [example[i] for  example in dataSet]   #获取每个特征的取值
        uniqval = set(featureList)
        newEntropy = 0.0
        for value in uniqval:
            subSet = splitDataSet(dataSet,i,value)
            prob = float(len(subSet)) /len(dataSet)
            newEntropy+=prob * calcShannonEnt(subSet)
        infoGain = baseEntropy - newEntropy
        print("第 %s 个信息增益为%.3f" % (i,infoGain))
        if infoGain>bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
##划分数据集
def  splitDataSet(dataSet,axis,value):
    """
    :param dataSet:
    :param axis: 按第几个特征划分
    :param value: 特征值
    :return: 划分后的数据集
    """
    retSet =[]
    for feaVet in dataSet:
        if feaVet[axis] == value:
            tempVec = feaVet[:axis]
            tempVec.extend(feaVet[axis+1:])
            retSet.append(tempVec)
    return retSet

递归构造决策树

决策树的存储在这里采用的是字典的形式

##递归构建决策树
"""
程序完全遍历所有划分数据集的属性，(没有属性可用)
或者每个分支下的所有实例都具有相同的分类，（分支下所有的实例都属于同一个类别）
如果所有实例具有相同的分类，则得到一个叶子节点或者终止块，任何到达叶子节点的数据必然属于叶子节点的分类
"""
def majorityCnt(classList):
    """
函数说明：统计classList中出现次数最多的元素（类标签）
Parameters：
    classList：类标签列表
Returns：
    sortedClassCount[0][0]：出现次数最多的元素（类标签）
    """
    classCounts = {}
    for vec in classList:
        if vec not in classCounts.keys():
            classCounts[vec] =0
            classCounts[vec]+=1
    sortedClassCount = sorted(classCounts.items(),key = lambda item:item[1],reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels,featLabels):
    """
    函数说明：创建决策树
    Parameters:
        dataSet：训练数据集
        labels：分类属性标签
        featLabels：存储选择的最优特征标签
    Returns：
        myTree：决策树
    """
    ##取分类标签，
    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)

    ##选择最好的特征
    bestFeature = chooseBestFeatureToSplit(dataSet)
    #最有特征的标签
    bestFeatureLabel  = labels[bestFeature]
    featLabels.append(bestFeatureLabel)
    #根据最优特征构造树
    myTree = {bestFeatureLabel:{}}

    del(labels[bestFeature])

    featValues = [example[bestFeature] for example in dataSet]
    uniqVal = set(featValues)
    for value in uniqVal:
        myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataSet,bestFeature,value),labels,featLabels)  ##递归构建树
    return myTree

使用决策树进行分类

至此已经根据数据集生成了决策树：{‘有自己的房子’: {0: {‘有工作’: {0: ‘no’, 1: ‘yes’}}, 1: ‘yes’}}
依靠训练数据构造了决策树之后，我们可以将它用于实际数据的分类。在执行数据分类时，需要决策树以及用于构造树的标签向量。然后，程序比较测试数据与决策树上的数值，递归执行该过程直到进入叶子结点；最后将测试数据定义为叶子结点所属的类型。在构建决策树的代码，可以看到，有个featLabels参数。它是用来干什么的？它就是用来记录各个分类结点的，在用决策树做预测的时候，我们按顺序输入需要的分类结点的属性值即可。举个例子，比如我用上述已经训练好的决策树做分类，那么我只需要提供这个人是否有房子，是否有工作这两个信息即可，无需提供冗余的信息。

##用决策树进行分类
    """
    使用决策树进行分类
Parameters：
    inputTree；已经生成的决策树
    featLabels：存储选择的最优特征标签
    testVec：测试数据列表，顺序对应最优特征标签
Returns：
    classLabel：分类结果
    """
def classify(inputTree,featLabels,testVec):

    firstStr = next(iter(inputTree))
    secondDic = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    print(firstStr,":",testVec[featIndex])
    for key in secondDic.keys():
        if testVec[featIndex] == key:
            if type(secondDic[key]).__name__ =='dict':
                classlabel = classify(secondDic[key],featLabels,testVec)
            else:
                classlabel = secondDic[key]
    return classlabel

决策树的存储与载入

采用pickle模块序列化对象

##决策树的存储与载入，使用pickled.dump()和pickle.load()
import pickle
def storeTree(inputTree,filename):
    with open(filename,'wb') as fw:
        pickle.dump(inputTree,fw)
def loadTree(filename):
    fr = open(filename, 'rb')
    return pickle.load(fr)

决策树的剪枝

决策树的剪枝简单来说，就是控制决策树的叶子节点的数量，避免决策树过于复杂，产生过拟合。

常用决策树算法（ID3 C4.5 CART）

简单粗暴来说，ID3 使用信息增益作为选择特征的准则；C4.5 使用信息增益比作为选择特征的准则；CART 使用 Gini 指数作为选择特征的准则。

一、ID3
熵表示的是数据中包含的信息量大小。熵越小，数据的纯度越高，也就是说数据越趋于一致，这是我们希望的划分之后每个子节点的样子。

信息增益 = 划分前熵 - 划分后熵。信息增益越大，则意味着使用属性 a 来进行划分所获得的 “纯度提升” 越大 **。也就是说，用属性 a 来划分训练集，得到的结果中纯度比较高。

ID3 仅仅适用于二分类问题。ID3 仅仅能够处理离散属性。

二、C4.5

C4.5 克服了 ID3 仅仅能够处理离散属性的问题，以及信息增益偏向选择取值较多特征的问题，使用信息增益比来选择特征。信息增益比 = 信息增益 / 划分前熵 选择信息增益比最大的作为最优特征。

C4.5 处理连续特征是先将特征取值排序，以连续两个值中间值作为划分标准。尝试每一种划分，并计算修正后的信息增益，选择信息增益最大的分裂点作为该属性的分裂点。

三、CART

CART 与 ID3，C4.5 不同之处在于 CART 生成的树必须是二叉树。也就是说，无论是回归还是分类问题，无论特征是离散的还是连续的，无论属性取值有多个还是两个，内部节点只能根据属性值进行二分。

CART 的全称是分类与回归树。从这个名字中就应该知道，CART 既可以用于分类问题，也可以用于回归问题。

回归树中，使用平方误差最小化准则来选择特征并进行划分。每一个叶子节点给出的预测值，是划分到该叶子节点的所有样本目标值的均值，这样只是在给定划分的情况下最小化了平方误差。

要确定最优化分，还需要遍历所有属性，以及其所有的取值来分别尝试划分并计算在此种划分情况下的最小平方误差，选取最小的作为此次划分的依据。由于回归树生成使用平方误差最小化准则，所以又叫做最小二乘回归树。

分类树种，使用 Gini 指数最小化准则来选择特征并进行划分；

Gini 指数表示集合的不确定性，或者是不纯度。基尼指数越大，集合不确定性越高，不纯度也越大。这一点和熵类似。另一种理解基尼指数的思路是，基尼指数是为了最小化误分类的概率。

信息增益 vs 信息增益比

之所以引入了信息增益比，是由于信息增益的一个缺点。那就是：信息增益总是偏向于选择取值较多的属性。信息增益比在此基础上增加了一个罚项，解决了这个问题。

Gini 指数 vs 熵

既然这两个都可以表示数据的不确定性，不纯度。那么这两个有什么区别那？

Gini 指数的计算不需要对数运算，更加高效；
Gini 指数更偏向于连续属性，熵更偏向于离散属性。

使用sklearn构建决策树

官方网站

完整代码

##决策树
from math import log
##构建数据集
def creatDataSet():
    # 数据集
    dataSet = [[0, 0, 0, 0, 'no'],
               [0, 0, 0, 1, 'no'],
               [0, 1, 0, 1, 'yes'],
               [0, 1, 1, 0, 'yes'],
               [0, 0, 0, 0, 'no'],
               [1, 0, 0, 0, 'no'],
               [1, 0, 0, 1, 'no'],
               [1, 1, 1, 1, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [1, 0, 1, 2, 'yes'],
               [2, 0, 1, 2, 'yes'],
               [2, 0, 1, 1, 'yes'],
               [2, 1, 0, 1, 'yes'],
               [2, 1, 0, 2, 'yes'],
               [2, 0, 0, 0, 'no']]
    # 分类属性
    labels = ['年龄', '有工作', '有自己的房子', '信贷情况']
    # 返回数据集和分类属性
    return dataSet, labels

##计算经验熵
def calcShannonEnt(dataSet):
    """
    计算数据集中的经验熵
    :param dataSet:  数据集
    :return: 返回经验熵
    """
    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 = (labelCounts[key])/numEntries
        shannonEnt -= prob*(log(prob,2))
    return shannonEnt

#计算信息增益
##选择最好的特征
def chooseBestFeatureToSplit(dataSet):
    """
    对每个特征计算信息增益
    返回最好的特征索引
    :param dataSet:
    :return:
    """
    baseEntropy= calcShannonEnt(dataSet)
    numFeatures = len(dataSet[0]) -1
    bestInfoGain  = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featureList = [example[i] for  example in dataSet]   #获取每个特征的取值
        uniqval = set(featureList)
        newEntropy = 0.0
        for value in uniqval:
            subSet = splitDataSet(dataSet,i,value)
            prob = float(len(subSet)) /len(dataSet)
            newEntropy+=prob * calcShannonEnt(subSet)
        infoGain = baseEntropy - newEntropy
        print("第 %s 个信息增益为%.3f" % (i,infoGain))
        if infoGain>bestInfoGain:
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature
##划分数据集
def  splitDataSet(dataSet,axis,value):
    """
    :param dataSet:
    :param axis: 按第几个特征划分
    :param value: 特征值
    :return: 划分后的数据集
    """
    retSet =[]
    for feaVet in dataSet:
        if feaVet[axis] == value:
            tempVec = feaVet[:axis]
            tempVec.extend(feaVet[axis+1:])
            retSet.append(tempVec)
    return retSet

##递归构建决策树
"""
程序完全遍历所有划分数据集的属性，(没有属性可用)
或者每个分支下的所有实例都具有相同的分类，（分支下所有的实例都属于同一个类别）
如果所有实例具有相同的分类，则得到一个叶子节点或者终止块，任何到达叶子节点的数据必然属于叶子节点的分类
"""
def majorityCnt(classList):
    """
函数说明：统计classList中出现次数最多的元素（类标签）
Parameters：
    classList：类标签列表
Returns：
    sortedClassCount[0][0]：出现次数最多的元素（类标签）
    """
    classCounts = {}
    for vec in classList:
        if vec not in classCounts.keys():
            classCounts[vec] =0
            classCounts[vec]+=1
    sortedClassCount = sorted(classCounts.items(),key = lambda item:item[1],reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet,labels,featLabels):
    """
    函数说明：创建决策树
    Parameters:
        dataSet：训练数据集
        labels：分类属性标签
        featLabels：存储选择的最优特征标签
    Returns：
        myTree：决策树
    """
    ##取分类标签，
    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)

    ##选择最好的特征
    bestFeature = chooseBestFeatureToSplit(dataSet)
    #最有特征的标签
    bestFeatureLabel  = labels[bestFeature]
    featLabels.append(bestFeatureLabel)
    #根据最优特征构造树
    myTree = {bestFeatureLabel:{}}

    del(labels[bestFeature])

    featValues = [example[bestFeature] for example in dataSet]
    uniqVal = set(featValues)
    for value in uniqVal:
        myTree[bestFeatureLabel][value] = createTree(splitDataSet(dataSet,bestFeature,value),labels,featLabels)  ##递归构建树
    return myTree

##用决策树进行分类
    """
    使用决策树进行分类
Parameters：
    inputTree；已经生成的决策树
    featLabels：存储选择的最优特征标签
    testVec：测试数据列表，顺序对应最优特征标签
Returns：
    classLabel：分类结果
    """
def classify(inputTree,featLabels,testVec):

    firstStr = next(iter(inputTree))
    secondDic = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    print(firstStr,":",testVec[featIndex])
    for key in secondDic.keys():
        if testVec[featIndex] == key:
            if type(secondDic[key]).__name__ =='dict':
                classlabel = classify(secondDic[key],featLabels,testVec)
            else:
                classlabel = secondDic[key]
    return classlabel

##决策树的存储与载入，使用pickled.dump()和pickle.load()
import pickle
def storeTree(inputTree,filename):
    with open(filename,'wb') as fw:
        pickle.dump(inputTree,fw)
def loadTree(filename):
    fr = open(filename, 'rb')
    return pickle.load(fr)


if __name__ =="__main__":
    dataSet, labels = creatDataSet()
    print(dataSet)
    print(calcShannonEnt(dataSet))
    print("最优索引值：",chooseBestFeatureToSplit(dataSet))
    featLabels =[]
    myTree=createTree(dataSet,labels,featLabels)
    print(myTree)
    testVec = [0, 1]

    result = classify(myTree, featLabels, testVec)

    if result == 'yes':
        print('放贷')
    if result == 'no':
        print('不放贷')
    storeTree(myTree,"Mytree.txt")
    testTree = loadTree("Mytree.txt")
    print(testTree)
    print(featLabels)