决策树学习总结

决策树的工作原理

     决策树的工作原理简单来说就是通过一系列的判断语句来判定一个样本的类别，具体表现为树形结构，树中的节点(终节点除外)表示一个特征，特征节点的一条出边代表该特征的一种取值，而终节点代表样本可能隶属的类别。决策树分类的过程就是从决策树根节点依次走到终节点的过程。

如何设计决策树

    决策树的工作原理并不难理解，决策树的主要问题在于如何设计一棵合理的决策树。

    决策树进行分类时的每一节点上都要对某一属性值进行判断，对于多个可选属性，决策树在各个节点上的该选择哪一个属性？    

    对于一个节点上的属性，若有多个取值，如何设计该节点的出边？（是每个取值作为一条出边，还是几个取值作为一条出边？）

    以上两个问题总结起来是选择每个节点最佳属性度量问题，它包括两个方面：选择一个节点上的属性 和 划分该属性的取值，这两者都可以通过划分后的数据集中数据的纯度来确定，纯度越高意味着我们选择的的属性度量越好。

    纯度大小可以由“信息熵”或“Gini值”来衡量，两者的定义分别如下：

信息熵：

 Gini值： Gini

    具体来说，我们在确定决策树的节点属性度量时，并不是单纯的考虑划分后的数据集的纯度，而是将划分后的数据集与划分前的数据作比较，看数据集的纯度提升了多少，“纯度提升”可由三个可选指标来衡量：信息增益、信息增益率以及Gini指数，它们分别对应不同的决策树：ID3决策树、C4.5决策树和CART决策树。三个纯度提升衡量指标定义如下：

信息增益：

信息增益率：            

Gini指数：

    以上三个指标中，信息增益和信息增益率越大越好，而Gini指数越小越好。

    对于具有连续值的属性来说，我们应该取该属性的取值区间作为分类的判断条件，取值区间的选取也遵从纯度提升最大的原则，具体操作如下：

        上述内容解决了如何生成决策树的一个节点的问题，设计决策树时另一个问题是什么时候停止决策树的生长。由于决策树在生成过程中是一条路径一条路径的生长的，所以这个问题具体来说就是什么时候停止一条路径的生长，去生成下一条路径。

           有三种情况会导致决策树的生长停止：

                （1）某一属性划分后得到的数据集中的数据已经属于同一类，不需要再划分

                （2）某条路径生长过程中，所有属性都已使用过得到的数据集中仍然包含不同类别的数据。

                （3）某条路径生长过程中，在使用某一属性划分后得到空的数据集

            在上述三种情况下，我们停止决策树生长时的操作如下：

               第（1）种情况下，直接将该属性划分的到的数据集作为终节点即可。

                综上所述，一棵决策树的生成伪代码如下：

        如上所示，决策树的生成过程是一个递归生成节点的过程。为方便理解，这里的节点看作几个元素的集合，它包括以下几个部分：属性，分支，属性按各分支划分后的各个数据子集。其中属性指的是当前最佳属性，分支对应着当前最佳属性的不同取值。当前结点划分后得到的数据子集会作为生成下一个节点（如果需要生成）的输入，也就是作为被下一个节点划分的数据集。

        每生成一个节点，都要进行三次判断（对应上面的三条if语句），看当前的决策树是否满足了前面所说的三种停止生长的情况，首先对上面一个节点传过来的数据集以及未使用的的属性集进行判断，看是否满足前面（1），（2）所说的停止条件，若不满足为该节点生成一条分支，得到由该分支划分得到的一个数据子集，对该子集判断它是否满足（3）所说的停止条件，若不满足递归生成下一个节点。上面的伪代码中14行的语句是递归调用函数本身，它控制决策树的深度生长，9行对每一个节点属性的每种取值进行遍历，控制决策树同一节点不同分支的生长，即决策树的宽度生长。由上可见，决策树的生成是一个深度优先搜索的过程。

        注：决策树的生长过程中，每个属性只能使用一次，即每个属性只能用来生成一个节点，对于连续取值的属性，该属性值划分成的每个取值区间只能用来生成一个节点。

        用Python实现一颗简单的决策树可参考博客：https://blog.csdn.net/csqazwsxedc/article/details/65697652

        该博客中的代码复制到下面，加了一些注释：

#4.决策树
from math import log
import operator

def calcShannonEnt(dataSet):  # 计算数据的熵(entropy)
    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
    for key in labelCounts:
        prob=float(labelCounts[key])/numEntries # 计算单个类的熵值
        shannonEnt-=prob*log(prob,2) # 累加每个类的熵值
    return shannonEnt

def createDataSet1():    # 创造示例数据
    dataSet = [['长', '粗', '男'],
               ['短', '粗', '男'],
               ['短', '粗', '男'],
               ['长', '细', '女'],
               ['短', '细', '女'],
               ['短', '粗', '女'],
               ['长', '粗', '女'],
               ['长', '粗', '女']]
    labels = ['头发','声音']  #两个特征
    return dataSet,labels

def splitDataSet(dataSet,axis,value): # 按某个特征分类后的数据
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis]==value:
            reducedFeatVec =featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):  # 选择最优的分类特征
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)  # 原始的熵
    bestInfoGain = 0
    bestFeature = -1
    for i in range(numFeatures): #i表示第i个特征
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value)
            prob =len(subDataSet)/float(len(dataSet))
            newEntropy +=prob*calcShannonEnt(subDataSet)  # 按特征分类后的熵
        infoGain = baseEntropy - newEntropy  # 原始熵与按特征分类后的熵的差值
        if (infoGain>bestInfoGain):   # 若按某特征划分后，熵值减少的最大，则次特征为最优分类特征
            bestInfoGain=infoGain
            bestFeature = i
    return bestFeature

def majorityCnt(classList):    #按分类后类别数量排序，比如：最后分类为2男1女，则判定为男；
    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]

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:#随着决策树的生长，可用的分类属性越来越少（后面涉及到属性的删除），
                            #数据集中每一条数据的长度也在减少，最后只剩类别一项，长度为1，即属性集为空        
        return majorityCnt(classList)#满足前叙条件，返回该数据集中较多的类别（终节点）
    bestFeat=chooseBestFeatureToSplit(dataSet) #选择最优特征，函数返回值为当前最优特征在特征集中的索引
    bestFeatLabel=labels[bestFeat]#根据索引取最优特征
    myTree={bestFeatLabel:{}} #分类结果以字典形式保存，创建一个节点
    del(labels[bestFeat])#lables是特征集合，删除当前最优特征
    featValues=[example[bestFeat] for example in dataSet]#取接收的数据集中所有数据的当前最优特征的值
    uniqueVals=set(featValues)#对于最优特征的每一个值，从最优特征节点生成与该取值对应的分支
    for value in uniqueVals: #对于uniquelVals(最优特征的可能取值)的for循环实现决策树横向生长
        subLabels=labels[:]#前面删除当前最优特征后的特征集，作为下一级节点的可选特征集
        myTree[bestFeatLabel][value]=createTree(splitDataSet\
                            (dataSet,bestFeat,value),subLabels)#递归调用createTree函数本身，返回结果交给myTree字典保存，该字典中，一个键（key：bestFeatLabel）
                                                               #表示一个决策树节点(一个特征)，一个值（value）表示一个决策树节点的一条分支（特征的一个取值）。
                                                               #接收的返回的sub_myTree，字典的最外层键就是下一层的节点，实现决策树的深度生长
                #splitDataSet函数对于当前数据集（DataSet）,返回满足当前最优特征当前取值（labels[bestFeat]=value）的数据子集,该数据子集作为下一级
                #creatTree函数所要处理的数据集。subLabels:前面删除当前最优特征后的特征集，作为下一级节点的可选特征集.
    return myTree


if __name__=='__main__':
    dataSet, labels=createDataSet1()  # 创造示列数据
    print(createTree(dataSet, labels))  # 输出决策树模型结果

        输出结果如下：

{'声音': {'细': '女', '粗': {'头发': {'短': '男', '长': '女'}}}}

后续待更新... ...

参考文献：周志华-《机器学习》

                   Pang-Ning Tan, Michal Steinbach, Vipin Kumar-《数据挖掘导论》（中文版）

注：本文图片全部来自周志华-《机器学习》第四章