决策树的构造

决策树的构造

你是否玩过⼆⼗个问题的游戏， 游戏的规则很简单： 参与游戏的⼀⽅在脑海⾥想某个事物， 其他参与者向他提问题， 只允许提20个问题， 问题的答案也只能⽤对或错回答。 问问题的⼈通过推断分解， 逐步缩⼩待猜测事物的范围。

决策树的⼯作原理与20个问题类似， ⽤户输⼊⼀系列数据， 然后给出游戏的答案

image

决策树的优缺点

优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据。
缺点：可能会产生过度匹配问题。
适用数据类型：数值型和标称型。

决策树的一般流程

(1) 收集数据：可以使用任何方法。
(2) 准备数据：树构造算法只适用于标称型数据，因此数值型数据必须离散化。
(3) 分析数据：可以使用任何方法，构造树完成之后，我们应该检查图形是否符合预期。
(4) 训练算法：构造树的数据结构。
(5) 测试算法：使用经验树计算错误率。
(6) 使用算法：此步骤可以适用于任何监督学习算法，而使用决策树可以更好地理解数据的内在含义。

相关公式

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为

其中p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：

其中n是分类的数目

创建数据

image

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing','flippers']
    #change to discrete values
    return dataSet, labels

dataSet:
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
labels:
['no surfacing', 'flippers']

计算给定数据集的香农熵

from math import log
import operator

# 计算给定数据集的香农熵
def calcShannonEnt(dataSet):
     #计算数据集的输入个数  
    numEntries = len(dataSet) 
    #[]列表,{}元字典,()元组  
    # 创建存储标签的元字典 
    #创建⼀个数据字典， 它的键值是最后⼀列的数值
    labelCounts = {} 
    #对数据集dataSet中的每一行featVec进行循环遍历  
    for featVec in dataSet: #the the number of unique elements and their occurance
        # currentLabels为featVec的最后一个元素  
        currentLabel = featVec[-1] #创建⼀个数据字典， 它的键值是最后⼀列的数值
         # 如果标签currentLabels不在元字典对应的key中  
        if currentLabel not in labelCounts.keys(): 
            # 将标签currentLabels放到字典中作为key，并将值赋为0  
            labelCounts[currentLabel] = 0
            # 将currentLabels对应的值加1  
        labelCounts[currentLabel] += 1
    # 定义香农熵shannonEnt
    shannonEnt = 0.0
    # 遍历元字典labelCounts中的key，即标签
    for key in labelCounts:
        # 计算每一个标签出现的频率，即概率
        prob = float(labelCounts[key])/numEntries
        # 根据信息熵公式计算每个标签信息熵并累加到shannonEnt上
        shannonEnt -= prob * log(prob,2) #log base 2
     # 返回求得的整个标签对应的信息熵
    return shannonEnt

运行的结果

>>> reload(trees.py)
>>> myDat,labels=trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.calcShannonEnt(myDat)
0.97095059445466858

对运行结果的分析

#dataSet:
#[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

def calcShannonEnt(dataSet):  
    numEntries = len(dataSet) #numEntries: 5
    labelCounts = {} 
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys(): 
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    #labelCounts : <class 'dict'>: {'no': 3, 'yes': 2}
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries 
        shannonEnt -= prob * log(prob,2) 
        #'yes'; prob = 0.6; shannonEnt = 0.44217935649972373
        #'no'; prob = 0.4; shannoEnt = 0.9709505944546686
    return shannonEnt #0.9709505944546686

熵越⾼， 则混合的数据也越多

>>> myDat[0][-1]='maybe'
>>> myDat
[[1, 1, 'maybe'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']
>>> trees.calcShannonEnt(myDat)
1.3709505944546687

按照给定特征划分数据集

我们将对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。想象一个分布在二维空间的数据散点图，需要在数据之间划条线，将它们分成两部分

# 按照给定特征划分数据集
# dataSet数据集，axis是对应的要分割数据的列，value是要分割的列按哪个值分割，即找到含有该值的数据
def splitDataSet(dataSet, axis, value): #三个输入参数：待划分的数据集、划分数据集的特征、需要返回的特征的值
    # 定义要返回的数据集
    retDataSet = []
    # 遍历数据集中的每个特征，即输入数据
    for featVec in dataSet:#我们要遍历数据集中的每个元素，一旦发现符合要求的值，则将其添加到新创建的列表中
        # 如果列标签对应的值为value，则将该条(行)数据加入到retDataSet中
        if featVec[axis] == value: #在if语句中，程序将符合特征的数据抽取出来
            # 取featVec的0-axis个数据，不包括axis，放到reducedFeatVec中
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting
            # 取featVec的axis+1到最后的数据，放到reducedFeatVec的后面
            reducedFeatVec.extend(featVec[axis+1:])
            # 将reducedFeatVec添加到分割后的数据集retDataSet中，同时reducedFeatVec，retDataSet中没有了axis列的数据
            retDataSet.append(reducedFeatVec)
    # 返回分割后的数据集
    return retDataSet

append函数用法

>>> a=[1,2,3]
>>> b=[4,5,6]
>>> a.append(b)
>>> a
[1, 2, 3, [4, 5, 6]]

extend函数用法

>>> a=[1,2,3]
>>> a.extend(b)
>>> a
[1, 2, 3, 4, 5, 6]

运行的结果

>>> reload(trees)
<module 'trees' from 'trees.pyc'>
>>> myDat,labels=trees.createDataSet()
>>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
>>> trees.splitDataSet(myDat,0,1) [[1, 'yes'], [1, 'yes'], [0, 'no']]
>>> trees.splitDataSet(myDat,0,0) [[1, 'no'], [1, 'no']]

运行结果分析

#dataSet = <class 'list'>: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
#axis = 0
#value = 1
def splitDataSet(dataSet, axis, value): 
    retDataSet = []
    #第一次循环过程
    for featVec in dataSet: #featVec = <class 'list'>: [1, 1, 'yes']
        if featVec[axis] == value: #featVec[0]=1 == value
            reducedFeatVec = featVec[:axis]   
            reducedFeatVec.extend(featVec[axis+1:]) #reducedFeatVec: <class 'list'>: [1, 'yes']          
            retDataSet.append(reducedFeatVec)#retDataSet: <class 'list'>: [[1, 'yes']]
    return retDataSet #[[1, 'yes'], [1, 'yes'], [0, 'no']]

将featVec[0]=1的特征都提取出来,即不浮出水面也能生存判断为是海洋生物

选择最好的数据集划分方式

接下来我们将遍历整个数据集，循环计算香农熵和splitDataSet()函数，找到最好的特征划分方式。熵计算将会告诉我们如何划分数据集是最好的数据组织方式。

信息增益是熵的减少或者是数据无序度的减少，大家肯定对于将熵用于度量数据无序度的减少更容易理解。最后，比较所有特征中的信息增益，返回最好特征划分的索引值

def chooseBestFeatureToSplit(dataSet):
    # 获取特征的数目，从0开始，dataSet[0]是一条数据
    numFeatures = len(dataSet[0]) - 1      #the last column is used for the labels
    # numFeatures=2
    # 计算数据集当前的信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # baseEntropy = 0.9709505944546686
    # 定义最大的信息增益
    bestInfoGain = 0.0
    # 定义分割后信息增益最大的特征
    bestFeature = -1
    # 遍历特征，即所有的列，计算每一列分割后的信息增益，找出信息增益最大的列
    for i in range(numFeatures):        #iterate over all the features
        # 取出第i列特征赋给featList
        featList = [example[i] for example in dataSet]#create a list of all the examples of this feature
        # 将特征对应的值放到一个集合中，使得特征列的数据具有唯一性
        uniqueVals = set(featList)       #get a set of unique values
        # 定义分割后的信息熵
        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     #calculate the info gain; ie reduction in entropy
        # 如果分割后信息增益大于最好的信息增益
        if (infoGain > bestInfoGain):       #compare this to the best gain so far
            # 将当前的分割的信息增益赋值为最好信息增益
            bestInfoGain = infoGain         #if better than current best, set to best
            # 分割的最好特征列赋为i
            bestFeature = i
    # 返回分割后信息增益最大的特征列
    return bestFeature                      #returns an integer

运行结果

>>> reload(trees)
<module 'trees' from 'trees.py'>
>>> myDat,labels=trees.createDataSet()
>>> trees.chooseBestFeatureToSplit(myDat)
0>
>> myDat
[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]

代码运⾏结果告诉我们， 第0个特征是最好的⽤于划分数据集的特征。

运行结果分析

#dataSet:<class 'list'>: [[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1    # numFeatures: 2
    baseEntropy = calcShannonEnt(dataSet) #baseEntropy: 0.9709505944546686
    bestInfoGain = 0.0; bestFeature = -1 # bestInfoGain: 0.0; bestFeature: -1
    #第一次循环,取第一列的数值 1 1 1 0 0 
    for i in range(numFeatures):       
        featList = [example[i] for example in dataSet]#featList: <class 'list'>: [1, 1, 1, 0, 0]
        uniqueVals = set(featList) #uniqueVals: <class 'set'>: {0, 1}  
        newEntropy = 0.0 #newEntropy: 0.0
        #第一次循环 value=0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)#subDataSet: <class 'list'>: [[1, 'no'], [1, 'no']] 即第一个特征值为0的
            prob = len(subDataSet)/float(len(dataSet)) #prob: 0.4
            newEntropy += prob * calcShannonEnt(subDataSet)     
        infoGain = baseEntropy - newEntropy  #infoGain: 0.4199730940219749  
        if (infoGain > bestInfoGain):      
            bestInfoGain = infoGain        
            bestFeature = i
    return bestFeature                    

递归构建决策树

遍历标签

⽬前我们已经学习了从数据集构造决策树算法所需要的⼦功能模块， 其⼯作原理如下： 得到原始数据集， 然后基于最好的属性值划分数据集， 由于特征值可能多于两个， 因此可能存在⼤于两个分⽀的数据集划分。 第⼀次划分之后， 数据将被向下传递到树分⽀的下⼀个节点， 在这个节点上， 我们可以再次划分数据。 因此我们可以采⽤递归的原则处理数据集。

递归结束的条件是： 程序遍历完所有划分数据集的属性， 或者每个分⽀下的所有实例都具有相同的分类。

# 该函数使用分类名称的列表，然后创建键值为classList中唯一值的数据字典，
# 字典对象存储了classList中每个类标签出现的频率，最后利用operator操作键值排序字典，
# 并返回出现次数最多的分类名称。
# 对类标签进行投票 ，找标签数目最多的标签
def majorityCnt(classList):
    # 定义标签元字典，key为标签，value为标签的数目
    classCount={}
    # 遍历所有标签
    for vote in classList:
        # 如果标签不在元字典对应的key中
        if vote not in classCount.keys():
            # 将标签放到字典中作为key，并将值赋为0
            classCount[vote] = 0
        # 对应标签的数目加1
        classCount[vote] += 1
    # 对所有标签按数目排序  
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)
    # 返回数目最多的标签  
    return sortedClassCount[0][0]

运行结果

myDat,labels=createDataSet()
classList = [example[-1] for example in myDat]
print(majorityCnt(classList)) #no

创建树的函数代码

[图片上传失败...(image-173488-1564800012201)]

# 创建决策树
def createTree(dataSet,labels):
    # 将dataSet的最后一列数据(标签)取出赋给classList，classList存储的是标签列
    classList = [example[-1] for example in dataSet]

    # 判断是否所有的列的标签都一致
    if classList.count(classList[0]) == len(classList):
        # 直接返回标签列的第一个数据
        return classList[0]#stop splitting when all of the classes are equal

    # 判断dataSet是否只有一条数据
    if len(dataSet[0]) == 1: #stop splitting when there are no more features in dataSet
        # 返回标签列数据最多的标签
        return majorityCnt(classList)
    # 选择一个使数据集分割后最大的特征列的索引
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 找到最好的标签
    bestFeatLabel = labels[bestFeat]
    # 定义决策树，key为bestFeatLabel，value为空
    myTree = {bestFeatLabel:{}}
    # 删除labels[bestFeat]对应的元素
    del(labels[bestFeat])
    # 取出dataSet中bestFeat列的所有值
    featValues = [example[bestFeat] for example in dataSet]
    # 将特征对应的值放到一个集合中，使得特征列的数据具有唯一性
    uniqueVals = set(featValues)
    # 遍历uniqueVals中的值
    for value in uniqueVals:
        # 子标签subLabels为labels删除bestFeat标签后剩余的标签
        subLabels = labels[:]       #copy all of labels, so trees don't mess up existing labels
        # myTree为key为bestFeatLabel时的决策树
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    # 返回决策树
    return myTree

运行结果{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

myDat,labels=createDataSet()
myTree = createTree(myDat,labels)
print(myTree) #{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

运行结果分析

#dataSet:
#[[1, 1, 'yes'], [1, 1, 'yes'], [1, 0, 'no'], [0, 1, 'no'], [0, 1, 'no']]
#labels:
#['no surfacing', 'flippers']

def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet]# classList: <class 'list'>: ['yes', 'yes', 'no', 'no', 'no']
    if classList.count(classList[0]) == len(classList): 
        return classList[0]
    if len(dataSet[0]) == 1: 
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#bestFeat: 0
    bestFeatLabel = labels[bestFeat]#bestFeatLabel: 'no surfacing'
    myTree = {bestFeatLabel:{}}#myTree: <class 'dict'>: {'no surfacing': {}}
    del(labels[bestFeat])#删除后'no surfacing' labels变成: <class 'list'>: ['flippers']
    featValues = [example[bestFeat] for example in dataSet]#featValues: <class 'list'>: [1, 1, 1, 0, 0]
    uniqueVals = set(featValues)# uniqueVals: <class 'set'>: {0, 1}
    #第一次循环 value=0
    for value in uniqueVals:
        subLabels = labels[:]#subLabels: <class 'list'>: ['flippers']
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)#myTree: <class 'dict'>: {'no surfacing': {0: 'no'}}
    return myTree