决策树

决策树定义

• 概念：决策树可以近似于一个流程图，长方形代表判断模块，椭圆形代表终止模块，表示已经得出结论，可以终止运行。从判断模块引出的左右箭头称作分支，它可以到达另一个判断模块或者终止模块。

  
  决策树

• 优点：计算复杂度不高，输出结果易于理解，对中间值的缺失不敏感，可以处理不相关特征数据

• 缺点：可能会产生过度匹配问题

• 应用难点：很难确定特征

• 适用数据类型：数值型和标称型

• 如何创建树的分支？

Function createBranch():
检测数据集中的每个子集是否属于同一分类
    If so return 类标签;
    Else
        寻找划分数据集的最好特征
        划分数据集
        创建分支节点
            for 每个划分的子集
                调用函数createBranch()并增加返回结果到分支节点中
        return 分支节点

• 信息增益：划分数据之前之后的变化称为信息增益，通过计算每个特征值划分数据集获得的信息增益，获得信息增益最高的特征就是最好的选择。香农提出的了熵用于计算信息增益，信息增益=原来的熵-变化后的熵
• 信息的定义：l(xi)=-log2p(xi),p(xi)表示选择xi类别的概率
• 熵：信息的期望值，计算一个样本集合中的数据是纯洁的还是不纯洁的，公式(n是分类的数目)：

H=-\sum_{i=1}^{n}p(x_i)log_2p(x_i)

决策树的程序实现

• 计算给定数据集的香农熵的实现代码：

from math import log
def calcShannonEnt(dataset):
    numEntries = len(dataset)
    labelCounts ={}
    # 求出各个类别的样本总数，用来计算p(xi)
    for featVec in dataset:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    shannoEnt = 0.0
    #利用公式计算熵
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannoEnt -= prob*log(prob,2)
    return shannoEnt

• 信息熵、信息增益与信息增益率的区别
• 划分数据集：对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式：

#按照给定特征划分数据集
#extend() 函数用于在列表末尾一次性追加另一个序列中的多个值
#输入：待划分的数据集，划分数据集的特征，需要返回的特征的值
#a[i:j]:表示取从第i+1位到第j个元素
def splitDataSet(dataSet,axis,value):
    retDataSet =[]
    for featVec in dataSet:
        if featVec[axis] == value:
            # 从数据元组去掉该特征值
            reduceFeatVec =featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

• 选择最好的数据集划分方法

#选择最好的数据集划分方式
def chooseBestFeatureToSplit(dataSet):
    #计算列数得到特征数
    numFeatures = len(dataSet) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeatures = -1
    for i in range(numFeatures):
        #循环取出dataset的元组，然后取出元组中的第i列的所有取值
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        #计算每个特征的所有特征值作为划分子节点时的熵
        for values 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
            bestFeatures = i
    return bestFeatures

• 数据具有多个标签时如何处理？
  • 采用多数表决的方法决定该子节点的分类

#当出现多个类标签结果时，采用投票表决的方法决定最终类标签
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=0
        classCount[vote] += 1
        sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(i),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):
        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

• 使用前面构造好的算法得到决策树，对测试数据执行分类：

#使用决策树执行分类
#输入：决策树，特征表，测试数据
def classify(inputTree, feaLabels, testVec):
    #取出第一个键值，即根
    firstStr = inputTree.keys()[0]
    #获得根对应的子节点
    secondDict = inputTree[firstStr]
    #找到第一个键值在实际数据存储中的列位置
    featIndex = feaLabels.index(firstStr)
    for key in secondDict.keys():
        #找到下一步要到达的节点
        if testVec[featIndex]==key:
            if type(secondDict[key])._name_== 'dict':
                classLabel=classify(secondDict[key],feaLabels,testVec)
            else:
                classLabel=secondDict[key]
    return classLabel

• 如何存储决策树？使用pickle包，pickle提供了一个简单的持久化功能。可以将对象以文件的形式存放在磁盘上。

def storeTree(inputTree, filename):
    import pickle
    fw = open(filename, 'w')
    pickle.dump(inputTree, fw)
    fw.close()


def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)