机器学习实战—决策树

决策树原理：通过一系列数据，最后给出分类结果，使用不熟悉的数据集合，从中提取出一系列规则。
决策树的主要优势在于数据形式非常容易理解
一、决策树的构建：
构造决策树时，第一个问题是当前数据集上哪个特征在划分数据分类时起决定性作用。
信息量的度量=信息不确定性的多少，变量的不确定性越大，熵越大，把它搞清楚所需的信息就越大。熵是信息的期望值。
划分数据集的大原则是：将无序的数据有序化，划分数据集之前之后的信息发生的变化成为信息增益，那么选择的划分特征就是在计算每个特征值划分数据集所获的信息增益中最大的特征。
计算给定数据集的熵（即没有进行特征划分之前的香农熵）：

#计算数据集的信息熵，以一种特征作为计算信息熵的基准（一种特征中会有多少分类）
#函数输入为数据集，输出为该信息的信息熵数值
def calShannonEnt(dataSet):
    #获取数据集实例个数
    numOsample = len(dataSet)
    #定义字典，存储该信息在数据集中出现的次数
    mesCounts = {}
    #遍历整个数据集，计算mesCounts中的value值
    for oneSample in dataSet:
        #如果字典中没有对应特征值作为的key值，则在字典中加入该key值，并且初始化value值为0
        #获取标签值
        label = oneSample[-1]
        if label not in mesCounts.keys():
            mesCounts[label] = 0
        mesCounts[label] += 1
    #计算香农熵
    #此处for循环遍历字典中的key值
    shannonEnt = 0.0
    for key in mesCounts:
        pro = (float)(mesCounts[key])/numOsample
        shannonEnt -= pro*log(pro,2)
    return shannonEnt

注：分类越多，不确定性越大，信息熵就越大

二、划分数据集
对每个特征划分数据集的结果计算一次信息熵，然后判断按照哪个特征划分数据集是最好的划分方式。
按照给定特征划分数据集：

#基于特定的特征信息进行数据集划分，对应于决策树中由父节点到子节点划分的过程
#输入参数为需要划分的数据集；此次的划分特征索引；划分特征的特定值
def splitDataSet(dataSet,splitFeatureIndex,spFeatrueValue):
    #定义返回集合列表
    retDataSet = []
    #遍历数据集，抽取符合特征的数据向量
    for lineVec in dataSet:
        if lineVec[splitFeatureIndex] == spFeatrueValue:
            reduceDataVec = lineVec[:splitFeatureIndex]
            reduceDataVec.extend(lineVec[splitFeatureIndex+1:])
            retDataSet.append(reduceDataVec)
    return retDataSet

注：返回特征集中不含有判定特征一列，因为在下次划分数据集时此特征值已经没有信息价值，在下次划分数据集事件中此特征值信息已处于已知状态，无意义。

信息增益：划分后的信息熵减去划分前的信息熵

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

#选择最好的特征信息划分，输入为整个数据集合（包含标签列），输出为最好划分特征索引值
def chooseBestFeatureIndex(dataSet):
    # 先计算没有划分数据集之前的信息熵，用来之后计算信息增益
    # 信息熵会在划分数据集之后降低，因为划分数据集使得信息的不确定性减少
    #获取数据集中特征数量
    numFeature = len(dataSet[0]) - 1
    noSplitScore = calShannonEnt(dataSet)
    #定义划分数据集后的新的信息熵和最优划分特征索引
    gainScore = 0.0
    bestFeatrueIndex = -1
    #遍历整个数据集，对数据集进行划分，并计算根据特定特征进行数据集划分的信息熵
    for i in range(numFeature):
        splitedScore = 0.0
        #获取整个数据集中第i列的特征值,valueList为列表
        valueList = [sample[i] for sample in dataSet]
        #确保特征值中的数据值唯一，将列表集合化
        equalValueSet = set(valueList)
        #遍历特征值唯一的集合，对相应下特征值划分数据集计算信息熵，并最后计算此特征划分的信息熵之和
        for value in equalValueSet:
            #获取到该value值划分的数据集，计算划分到此数据集的概率
            subDataSet = splitDataSet(dataSet,i,value)
            pro = float(len(subDataSet))/len(dataSet)
            #划分特征的信息熵等于各个子集的信息熵之和，calShannonEnt(subDataSet)函数计算的是一个集合的信息熵
            splitedScore += pro*calShannonEnt(subDataSet)
        getDevScore = noSplitScore - splitedScore
        if(getDevScore > gainScore ):
            gainScore = getDevScore
            bestFeatrueIndex = i
    return bestFeatrueIndex

注：valueList = [sample[i] for sample in dataSet] 一句在大循环中，所以一次大循环中此句中的内层循环会循环完。

三、递归构建决策树：
工作原理：得到原始数据集，然后基于最好的属性划分数据集，第一次划分后，数据将被向下传递到树分支的下个节点，递归结束的条件是：程序遍历完所有划分集的属性，或者每个分支下所有实例都具有相同的分类。
如果数据集已经处理了所有属性，但是类标签依然不是唯一的，此时需要根据投票策略决定该叶子节点。

#当特征值列表中值不唯一时采用投票机制返回数量较多的值，传入参数为特征值列表
def voteToDecision(classList):
    classCountSet = {}
    for one in classList:
        if one not in classCountSet.keys():
            classCountSet[one] = 0
        classCountSet[one] += 1
    sortedCountSet = sorted(classCountSet.items(),key=operator.itemgetter[1],reverse=True)
    return sortedCountSet[0][0]

创建树：

#构建树
def createTree(dataSet,labels):
    classList = [sample[-1] for sample in dataSet]
    #递归停止的两个条件
    #1.最终属性值列表类相同，直接返回分类值
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    #2.属性都遍历的情况下，不能直接得出分类，则投票返回分类标签
    if len(dataSet[0]) == 1:
        return voteToDecision(classList)
    #开始创建树
    #获取最佳划分特征
    bestFIndex = chooseBestFeatureIndex(dataSet)
    bestLabel = labels[bestFIndex]
    # 树的存储结构为字典
    myTree = {bestLabel: {}}
    del(labels[bestFIndex])
    #获取当前特征的唯一set集
    valueList = [sample[bestFIndex] for sample in dataSet]
    equalValueSet = set(valueList)
    for value in equalValueSet:
        newLabels = labels[:]
        #递归创建树
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFIndex,value),newLabels)
    return myTree

注：递归建树的两个递归停止条件：1.所有的类标签完全相同，直接返回该类标签
2.使用完了所有特征，仍然不能将数据集划分为包含唯一类别的分组（此处使用投票策略），使用字典数据嵌套结构存储整棵树

四、使用Matplotlib注解绘制树形图
使用文本注解绘制节点：

# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt

#定义文本框格式和箭头格式
decisionNode = dict(boxstyle="sawtooth",fc="0.8")
leafNode = dict(boxstyle="round4",fc="0.8")
arrow_args = dict(arrowstyle="<-")

#使用文本注解绘制树节点
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)
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)

def plotTree(myTree,parentPt,nodeTxt):
    numLeafs = getNumLeaf(myTree)
    depth = getDepthTree(myTree)
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstStr = keyList[0]
    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):
    fig = plt.figure(1,facecolor='white')
    fig.clf()
    axprops = dict(xticks=[],yticks=[])
    createPlot.ax1 = plt.subplot(111, frameon=False,**axprops)
    # plotNode("decisionNode",(0.5,0.1),(0.1,0.5),decisionNode)
    # plotNode("leafNode",(0.8,0.1),(0.3,0.8),leafNode)
    plotTree.totalW = float(getNumLeaf(inTree))
    plotTree.totalD = float(getDepthTree(inTree))
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree,(0.5,1.0),'')
    plt.show()

五、构造注解树：
获取叶节点的数目和树的层数：

#绘制决策树时需要知道树叶节点的个数和树的深度
#获取树的叶子个数
def getNumLeaf(myTree):
    numLeaf = 0
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstKey = keyList[0]
    secDict = myTree[firstKey]
    #如果该节点为字典，此节点为判断节点，需要向下递归调用，如果不是字典，则说明该节点是叶子节点
    for key in secDict.keys():
        if type(secDict[key]).__name__=='dict':
            numLeaf += getNumLeaf(secDict[key])
        else:
            #叶子节点数目累加
            numLeaf += 1
    return numLeaf

#获取树的深度
def getDepthTree(myTree):
    maxDepth = 0
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstKey = keyList[0]
    secDict = myTree[firstKey]
    #如果该节点为字典，此节点为判断节点，需要向下递归调用，如果不是字典，则说明该节点是叶子节点
    for key in secDict.keys():
        if type(secDict[key]).__name__=='dict':
            thisDepth =1 + getDepthTree(secDict[key])
        else:
            thisDepth = 1
    if(thisDepth>maxDepth):
        maxDepth = thisDepth
    return maxDepth

绘制一颗完整的树：

#构建树
def createTree(dataSet,labels):
    classList = [sample[-1] for sample in dataSet]
    #递归停止的两个条件
    #1.最终属性值列表类相同，直接返回分类值
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    #2.属性都遍历的情况下，不能直接得出分类，则投票返回分类标签
    if len(dataSet[0]) == 1:
        return voteToDecision(classList)
    #开始创建树
    #获取最佳划分特征
    bestFIndex = chooseBestFeatureIndex(dataSet)
    bestLabel = labels[bestFIndex]
    # 树的存储结构为字典
    myTree = {bestLabel: {}}
    del(labels[bestFIndex])
    #获取当前特征的唯一set集
    valueList = [sample[bestFIndex] for sample in dataSet]
    equalValueSet = set(valueList)
    for value in equalValueSet:
        newLabels = labels[:]
        #递归创建树
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFIndex,value),newLabels)
    return myTree

六、测试和存储分类器
利用决策树执行数据分类和存储分类器
1.使用决策树的分类函数：

#使用决策树创建分类函数
#输入决策树，标签向量，测试数据
def classify(inputTree,labelsVec,testVec):
    keyList = []
    for item in inputTree.keys():
        keyList.append(item)
    firstKey = keyList[0]
    secDict = inputTree[firstKey]
    labelIndex = labelsVec.index(firstKey)
    # 遍历决策树，将测试数据与决策树上的节点进行比较
    # 如果是判断节点，则递归调用，直到到叶子节点，得到测试数据的分类
    for key in secDict.keys():
        #比较测试数据与决策树上的值，如果满足要求，则递归分类
        if testVec[labelIndex] == key:
            if type(secDict[key]).__name__ == 'dict':
                classLabel = classify(secDict[key],labelsVec,testVec)
            else:
                classLabel = secDict[key]
    return classLabel

注：python2.x和python3.x在dict.keys()函数中的返回值不同，python2.x此函数返回key值列表，但是python3.x该函数返回的是key值的迭代器。

2.狗杂决策树很耗时，所以使用pickle模块将决策树对象存储在文件中，在需要使用时再次读取出来即可。
使用pickle模块存储决策树：

#将分类树存储在磁盘上
def store_tree(input_tree,filename):
    import pickle
    #以二进制写方式打开文件，否则会报错
    fp = open(filename, 'wb')
    #将分类器以二进制形式存储在文件中
    pickle.dump(input_tree, fp)
    fp.close()

#引用以存储好的树结构
def grab_tree(filename):
    import pickle
    #以二进制读方式打开文件
    fp = open(filename,'rb')
    #加载文件中存储的分类器
    return pickle.load(fp)

示例：使用决策树预测隐形眼镜类型
注：隐形眼镜数据集可在网上下载，数据及文件内容如下所示：

数据特征标签为：age,prescript,astigmatic,tearRate
隐形眼镜类型包括：硬材质，软材质，不适合佩戴隐形眼镜
注：函数都保存在一个.py文件中，文件中的函数就是上面所列出的所有函数，通过文件中的main函数调用，main函数如下：

#决策树分类算法：ID3
if __name__ == "__main__":
    # dataSet, labelVec = createDataSet()
    # print("dataSet:\n",dataSet)
    # print("labelVec:\n",labelVec)
    # shannonEnt = calShannonEnt(dataSet)
    # print("shannonEnt of label:",shannonEnt)
    # index = 0
    # value = 1
    # retDataSet = splitDataSet(dataSet,index,value)
    # print("splitedDataSet(base featrue_%d):\n"%(index),retDataSet)
    # bestFeatrueIndex = chooseBestFeatureIndex(dataSet)
    # print("bestFeatrueIndex:",bestFeatrueIndex)
    # myTree = createTree(dataSet,labelVec)
    # print("树结构：",myTree)
    # myTree = retrive_tree(0)
    # print(myTree)
    # classLabel1= classify(myTree,labelVec,[1,0])
    # classLabel2 = classify(myTree, labelVec, [1,1])
    # print("classLabel_0:%s\nclassLabel_1:%s"%(classLabel1,classLabel2))
    # store_tree(myTree,'my_tree.txt')
    # myTree = grab_tree('my_tree.txt')
    # print("my_tree:",myTree)
    #打开文件
    fp = open("lenses.txt")
    #逐行遍历文件内容，每行数据去除空格后按tab键分割，获得数据集
    splitDataList = [sample.strip().split('\t')  for sample in fp.readlines()]
    #创建标签向量
    labelsVec = ['age','prescript','astigmatic','tearRate']
    #训练算法（即根据训练数据创建决策树）
    my_tree = createTree(splitDataList,labelsVec)
    createPlot(my_tree)

注：注释掉的代码都是用来测试之前写的函数的，此次的决策树算法使用的时ID3算法，即特征数目在每次划分数据集后减少。ID3算法无法直接处理数值型数据，所以有数值型数据时需要将连续数值离散化为若干区间。