[数据结构与算法] 决策树----对天气和自身状态是否适合去运动做出预测

---------------------------------------------------------------------------------------------------------------------------------
前言

提示：通过自建数据集，创建决策树对天气和身体状态是否适合去运动进行预测。

一、决策树原理

????????决策树是一个预测判别模型。它代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，每个分支路径代表某个可能的属性值，每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。.决策树是从训练数据中学习得出一个树状模型，通过做出一系列决策(选择)来对数据进行划分,这类似于针对一系列问题进行选择。决策树的决策过程就是从根节点开始,测试待分类项中对应的特征属性,并按照其值选择输出分支，直到叶子结点，将叶子结点存放的类别作为决策结果。属于监督学习算法，属性选择的度量是决策树的关键。

决策树由结点和有向边组成。结点有两种类型：内部结点和叶节点。内部结点表示一个特征或属性，叶节点表示一个分类结果。
例如:根据声音和头发判断一个人的性别。

测试员A：先根据头发判断，再根据声音判断，头发长、声音粗为男生，头发长、声音细为女生；头发短、声音粗为男生，头发短、声音细为女生；于是得到如下决策树。

测试员B：首先判断声音，声音细是女生，声音粗、头发短是男生，声音粗、头发长是女生。得到如下决策树：

?这时我们发现两种决策树都可以用来判断，但是哪种最优呢?这就要度量那个特征获得的收益最高，就将他作为最佳划分特征。

二、实验过程

2.1.最优决策属性的选择

2.1.1信息熵

划分数据集的大原则是：将无序的数据变得有序。如果我们能测量数据的复杂度，对比按

?“信息熵”是度量样本集合纯度最常用的一种指标，假定当前样本集合D中第k类样本所占的比例为pk (K=1, 2, ..., |y|)

，则D的信息熵定义为：?

Ent(D)的值越小，则D的纯度越高

? 计算信息熵时约定：若p = 0，则plog2p=0

? Ent(D)的最小值为0，最大值为log2|y|

??计算信息熵的代码如下：

2.1.2信息增益（代表算法:ID3）

信息增益表示两个信息熵的差值。信息增益计算如下：

在上例中，属性A1对样本集D进行划分所得的信息增益为：

Gain(D,A1) = H(D) -?[H(D|A1=青年)*5/15+H(D|A1=中年)*5/15+H(D|A1=老年)*5/15]?

=0.971-（0.971*0.33+0.971*0.33+0.7219*0.33）= 0.093

?2.1.3信息增益率（代表算法:C4.5）

信息增益对可取值数目较多的属性有所偏好，他十分偏向于拥有更多选择的决策属性（如果我们将数据编号拿来也作为决策属性毫无疑问他将作为第一优先级的决策属性）这也导致了部分情况下决策树正确率受到了影响，那么学者又提出了一个新的数据划分方法–信息增益率（Gain?ratio）。也就是是在原有信息增益的情况下我们多考虑一个对于属性内部也计算一次信息熵。

?属性a的可能取值数目越多（即V越大），则IV(a)的值通常就越大。

?在上例中，年龄（青年，中年，老年）

?IV(年龄，v=3) =? -（5/15*log5/15+5/15*log5/15+5/15*log5/15）

Gain_ratio(D,年龄) = Gain(D,年龄) / IV(年龄，v=3)

增益率准则对可取值数目较少的属性有所偏好，取信息增益率最高的属性作为划分属性

def calcShannonEnt1(dataSet, method = 'none'):
    numEntries = len(dataSet)
    labelCount = {}
    for feature in dataSet:
        if method =='prob': #当参数为prob时转而计算信息增益率
            label =  feature
        else:
            label = feature[-1]
        if label not in labelCount.keys():
            labelCount[label]=1
        else:
            labelCount[label]+=1
    shannonEnt = 0.0
    for key in labelCount:
        numLabels = labelCount[key]
        prob = numLabels/numEntries
        shannonEnt -= prob*(log(prob,2))
    return shannonEnt
#信息增益率
def chooseBestFeatureToSplit2(dataSet): #使用信息增益率进行划分数据集
    numFeatures = len(dataSet[0]) -1 #最后一个位置的特征不算
    baseEntropy = calcShannonEnt(dataSet) #计算数据集的总信息熵
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        newEntropyProb = calcShannonEnt1(featList, method='prob') #计算内部信息增益率
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            # 通过不同的特征值划分数据子集
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob *calcGini(subDataSet)
        newEntropy  = newEntropy*newEntropyProb
        infoGain = baseEntropy - newEntropy #计算每个信息值的信息增益
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature #返回信息增益的最佳索引

?2.1.4基尼指数（代表算法:C4.5）

分类问题中，假设D有K个类，样本点属于第k类的概率为Pk, 则概率分布的基尼值定义为:

?反映了随机抽取两个样本，其类别标记不一致的概率。

?Gini(D)越小，数据集D的纯度越高；

?给定数据集D，属性a的基尼指数定义为：

基尼指数反映得是分支内任意两个样本分类不一致得情况，所以基尼指数越小，分类越纯，所以我们选择基尼指数最小的属性作为最优划分属性

?在上例中，计算年龄的基尼指数：总样本数D=15，

?年龄=青年时，样本数为5，false:3,? agree：2? ? ------>?gini1= 1-[(3/5)^2+(2/5)^2]?

?年龄=中年时，样本数为5，false:2,? agree：3? ? ------>?gini2= 1-[(2/5)^2+(3/5)^2]?

?年龄=老年时，样本数为5，false:1,? agree：4? ? ------>?gini3= 1-[(1/5)^2+(4/5)^2]?

? gini(年龄) = 5/15 gini1 + 5/15 gini2 +5/15*gini3

?通过基尼指数来划分数据属性的代码：

????????

#基尼指数
def calcGini(dataset):
    feature = [example[-1] for example in dataset]
    uniqueFeat = set(feature)
    sumProb =0.0
    for feat in uniqueFeat:
        prob = feature.count(feat)/len(uniqueFeat)
        sumProb += prob*prob
    sumProb = 1-sumProb
    return sumProb
def chooseBestFeatureToSplit3(dataSet): #使用基尼系数进行划分数据集
    numFeatures = len(dataSet[0]) -1 #最后一个位置的特征不算
    bestInfoGain = np.Inf
    bestFeature = 0.0
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            # 通过不同的特征值划分数据子集
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob *calcGini(subDataSet)
        infoGain = newEntropy
        if(infoGain < bestInfoGain): # 选择最小的基尼系数作为划分依据
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature #返回决策属性的最佳索引

2.2 准备数据集

自己编的一些数据，存储在.xlsx文件中，有六个属性标签：天气，温度，适度，风况，场地，心情好坏，如下：

用于验证决策树的预测数据：

对读入数据进行处理的代码：

import pandas as pd
    myData = pd.read_excel('D:\python\RRJ\pycharm项目\pythonProject1\digits\TestData2.xlsx',header = None)
    print(myData.head())
    myData = np.array(myData).tolist()
    for d in myData:
        for i in range(len(d)):
            d[i] = d[i].strip()
    print(myData)
    Labels = ['天气', '温度', '湿度', '风况', '场地','心情好坏']

2.3 创建决策树?

#创建决策树
def createTree(dataSet,labels):
    '''
    函数说明：创建决策树
    :param dataSet: 训练数据集
    :param labels: 分类属性标签
    :return:
    '''
    #取分类标签
    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)                 #遍历完所有特征时返回出现次数最多的类标签
    bestFeat = chooseBestFeatureToSplit(dataSet)      #选择最优特征
    bestFeatLabel = labels[bestFeat]                  #最优特征的类标签
    myTree = {bestFeatLabel:{}}                       #根据最有特征的标签生成树
    #del(labels[bestFeat])                            #删除已经使用特征标签
    #得到训练集中所有最优特征的属性值
    featValues = [example[bestFeat] for example in dataSet]
    #去掉重复的属性值
    uniqueVals = set(featValues)
    #遍历特征，创建决策树
    for value in uniqueVals:
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels)
    return myTree

2.4 保存和读取决策树

构造决策树是很耗时的任务，尤其是数据集很大的时候，将会耗费大量的计算时间，因此为了节省时间，在每次执行分类时调用已创建决策树，用如下代码保存：


#存储决策树
'''
:param inputTree:已经生成的决策树 
:param filename: 决策树的存储文件名
'''
def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'wb')
    pickle.dump(inputTree, fw)
    fw.close()
#读取决策树
def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)  #决策树字典

2.5 绘制决策树

#绘制决策树
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif']=['SimHei']

decisionNode = dict(boxstyle="sawtooth", fc="0.8")   #设置结点格式
leafNode = dict(boxstyle="round4", fc="0.8")         #设置叶节点格式
arrow_args = dict(arrowstyle="<-")                   #设置箭头格式

#获取决策树叶子结点数目
def getNumLeafs(myTree):
    '''
    函数说明：获取叶子结点数目
    :param myTree: 决策树
    :return: 决策树叶子结点数目
    '''
    numLeafs = 0                                     #初始化叶子结点
    #firstStr = myTree.keys()[0]
    firstStr = next(iter(myTree))                    #获取结点属性
    secondDict = myTree[firstStr]                    #获取下一组字典
    for key in secondDict.keys():
        #测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
        if type(secondDict[key]).__name__=='dict':
            numLeafs += getNumLeafs(secondDict[key])
        else:   numLeafs +=1
    return numLeafs

#获取决策树的深度
def getTreeDepth(myTree):
    '''
    函数说明：获取决策树的深度
    :param myTree:决策树
    :return:决策树层数
    '''
    maxDepth = 0                              #初始化决策树层数
    firstStr = next(iter(myTree))
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__=='dict':
            thisDepth = 1 + getTreeDepth(secondDict[key])
        else:   thisDepth = 1
        if thisDepth > maxDepth:
            maxDepth = thisDepth              #更新树的层数
    return maxDepth

#绘制结点
'''
    函数说明：绘制结点
    :param nodeTxt: 结点名
    :param centerPt: 文本位置
    :param parentPt: 标注的箭头位置
    :param nodeType: 结点格式
    '''
def plotNode(nodeTxt, centerPt, parentPt, nodeType):
    createPlot.ax1.annotate(nodeTxt, xy=parentPt,  xycoords='axes fraction',
        xytext=centerPt, textcoords='axes fraction',
        va="center", ha="center", bbox=nodeType, arrowprops=arrow_args)

#标注有向边属性值
'''
    函数说明：标注有向边属性值
    :param cntrPt,parentPt: 用于计算标注位置
    :param txtString: 标注的内容
    '''
def plotMidText(cntrPt, parentPt, txtString):
    xMid = (parentPt[0]-cntrPt[0])/2.0 + cntrPt[0]
    yMid = (parentPt[1]-cntrPt[1])/2.0 + cntrPt[1]
    createPlot.ax1.text(xMid, yMid, txtString, va="center", ha="center", rotation=30)

#
'''
    函数说明：绘制决策树
    :param myTree: 决策树(字典)
    :param parentPt: 标注的内容
    :param nodeTxt: 结点名
'''
def plotTree(myTree, parentPt, nodeTxt):
    #获取决策树叶结点数目，决定了树的宽度
    numLeafs = getNumLeafs(myTree)
    #获取决策树层数
    depth = getTreeDepth(myTree)
    #获取下一个字典
    firstStr = next(iter(myTree))
    #中心位置
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs))/2.0/plotTree.totalW, plotTree.yOff)
    #标注有向边属性值
    plotMidText(cntrPt, parentPt, nodeTxt)
    #绘制结点
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    #下一个字典，继续绘制子结点
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0/plotTree.totalD
    for key in secondDict.keys():
        # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
        if type(secondDict[key]).__name__=='dict':
            #不是叶子结点，递归调用继续绘制
            plotTree(secondDict[key],cntrPt,str(key))
        else:      #是叶子结点则进行绘制，标注有向边
            plotTree.xOff = plotTree.xOff + 1.0/plotTree.totalW
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0/plotTree.totalD

#创建绘制面板
def createPlot(inTree):
    '''
    函数说明：创建绘制面板
    :param inTree: 决策树(字典)
    '''
    fig = plt.figure(1, facecolor='white')            #创建fig
    fig.clf()                                         #清空fig
    axprops = dict(xticks=[], yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False, **axprops)     #去掉x,y轴
    plotTree.totalW = float(getNumLeafs(inTree))      #决策树叶子结点数目
    plotTree.totalD = float(getTreeDepth(inTree))     #决策树层数
    plotTree.xOff = -0.5/plotTree.totalW; plotTree.yOff = 1.0;   #x偏移
    plotTree(inTree, (0.5,1.0), '')                   #绘制决策树
    plt.show()

2.6 使用决策树进行分类

分类函数：

#使用决策树的分类函数
'''
函数说明:使用决策树分类
:param inputTree: 已经生成的决策树
:param featLabels: 存储选择的最优特征
:param testVec: 测试数据列表，顺序对应最优特征标签
:return: 分类结果
'''
def classify(inputTree,featLabels,testVec):
    #firstStr = next(iter(inputTree))            #获取决策树结点
    firstStr = list(inputTree.keys())[0]
    #print(firstStr)
    secondDict = inputTree[firstStr]            #下一个字典
    featIndex = featLabels.index(firstStr)      #获取存储选择的最优特征标签的索引
    classLabel = -1
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            # 测试该结点是否为字典，如果不是字典，代表此结点为叶子结点
            if type(secondDict[key]).__name__=='dict':
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    # 标记classLabel为-1当循环过后若仍然为-1，表示未找到该数据对应的节点则我们返回他兄弟节点出现次数最多的类别
    if classLabel == -1:
        return getLeafBestCls(inputTree)

    else:
        return classLabel

#求该节点下所有叶子节点的列表
def getLeafscls(myTree, clsList):
    numLeafs = 0
    firstStr = list(myTree.keys())[0]
    secondDict = myTree[firstStr]
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            clsList =getLeafscls(secondDict[key],clsList)
        else:
            clsList.append(secondDict[key])
    return clsList

#返回出现次数最多的类别
def getLeafBestCls(myTree):
    clsList = []
    resultList = getLeafscls(myTree,clsList)
    return max(resultList,key = resultList.count)

2.7 创建的决策树结果

主程序:

if __name__ == '__main__':
    '''
    myDat,labels = createDataSet()
    print(myDat)
    print(labels)
    print("原始数据信息香农熵为：",end=' ')
    print(calcShannonEnt(myDat))
    print("最好的数据划分的特征索引值：",end=' ')
    print(chooseBestFeatureToSplit(myDat))
    #myTree = treesPlotter.retrieveTree(0)
    myTree = createTree(myDat,labels)
    treesPlotter.createPlot(myTree)             #没有坐标轴标签
    #myTree['no surfacing'][3] = 'maybe'
    print(myTree)
    treesPlotter.createPlot(myTree)
    print('测试分类结果为：',end='')
    #print(classify(myTree,labels,['晴天','中温','中湿','无风']))
    '''
    import pandas as pd
    myData = pd.read_excel('D:\python\RRJ\pycharm项目\pythonProject1\digits\TestData2.xlsx',header = None)
    print(myData.head())
    myData = np.array(myData).tolist()
    for d in myData:
        for i in range(len(d)):
            d[i] = d[i].strip()
    print(myData)
    Labels = ['天气', '温度', '湿度', '风况', '场地','心情好坏']
    myTree = createTree(myData, Labels)
    storeTree(storeTree, 'saveTree.txt')  #将决策树存储进入txt文件
    treesPlotter.createPlot(myTree)
    print("预测结果:")
    print(classify(myTree, Labels, ['多云', '中温', '中湿', '无风', '室内','心情好']))

    dataSet2 = [['晴朗', '高温', '高湿', '无风', '室外', '心情好'],
                ['晴朗', '中温', '高湿', '有风', '室外', '心情好'],
                ['晴朗', '高温', '低湿', '无风', '室内', '心情差'],
                ['阴天', '中温', '高湿', '无风', '室内', '心情好'],
                ['阴天', '低温', '低湿', '有风', '室外', '心情差'],
                ['阴天', '低温', '高湿', '有风', '室外', '心情差'],
                ['雨天', '低温', '中湿', '有风', '室外', '心情好'],
                ['雨天', '中温', '低湿', '有风', '室内', '心情好'],
                ['多云', '中温', '高湿', '有风', '室外', '心情差'],
                ['多云', '中温', '低湿', '无风', '室外', '心情差']]

    for dataVet in dataSet2:
       print(classify(myTree,Labels,dataSet2))

用信息增益创建的决策树

预测结果：

对比预测数据的正确率：40%

用信息增益率创建的决策树

用基尼指数创建的决策树

预测结果正确率都是40%，可见决策树创建存在问题，通过用书上提供简单数据测试发现是我数据集的问题，数据集由于是自己编的存在太多主观性，一致决策结果一半false。?

导入网上下载的莺尾花数据进行测试：

信息增益预测结果：

正确率：4/15*100%=28.6%

信息增益率，基尼指数预测结果上同：所以是代码编写出现问题，需要进一步改进。

总结

在这次实验中由于是自己编的数据集所以使实验结果不理想，无法比较信息增益，信息增益率，基尼指数三种划分方式的对数据划分的优劣，以及比较得出哪种方式更适合用来建决策树。

信息增益准则对可取值数目较多的特征有所偏好，类似"编号”的特征其信息增益接近于1;

只能用于处理离散分布的特征;，没有考虑缺失值。