决策树的构造和源码分析

野性酷女 2021-12-01 13:12 265阅读 0赞

### 决策树的原理 ###

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

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

![aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZrbDRvbnpqMzB0dDBnbGFkOC5qcGc][]

### 决策树的优缺点 ###

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

### 决策树的一般流程 ###

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

### 相关公式 ###

熵定义为信息的期望值，在明晰这个概念之前，我们必须知道信息的定义。如果待分类的事务可能划分在多个分类之中，则符号xi的信息定义为  
 l ( x i ) = − log ⁡ 2 p ( x i )  l\\left(x\_\{i\}\\right)=-\\log \_\{2\} p\\left(x\_\{i\}\\right) l(xi)=−log2p(xi)  
其中p(xi)是选择该分类的概率。

为了计算熵，我们需要计算所有类别所有可能值包含的信息期望值，通过下面的公式得到：  
 H = − ∑ i = 1 n p ( x i ) log ⁡ 2 p ( x i ) H=-\\sum\_\{i=1\}^\{n\} p\\left(x\_\{i\}\\right) \\log \_\{2\} p\\left(x\_\{i\}\\right) H=−∑i=1np(xi)log2p(xi)  
其中n是分类的数目

### 创建数据 ###

![aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZqYnI1Nm1qMzB4NjA5ZTc1Ni5qcGc][]

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

#### 创建树的函数代码 ####

\[外链图片转存失败(img-UaM8JxBz-1563609434744)(C:\\Users\\SilentY\\AppData\\Roaming\\Typora\\typora-user-images\\1562728501183.png)\]

# 创建决策树
    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

[aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZrbDRvbnpqMzB0dDBnbGFkOC5qcGc]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZrbDRvbnpqMzB0dDBnbGFkOC5qcGc
[aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZqYnI1Nm1qMzB4NjA5ZTc1Ni5qcGc]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly93czEuc2luYWltZy5jbi9sYXJnZS8wMDZReW4yUWx5MWc1NTZqYnI1Nm1qMzB4NjA5ZTc1Ni5qcGc