決策樹

計(jì)算香農(nóng)熵

def calcShannonEnt(dataSet):
    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.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2)
    return shannonEnt

建一組假數(shù)據(jù)

def createDataSet():
    dataSet = [[1, 1, 'yes'],
               [1, 1, 'yes'],
               [1, 0, 'no'],
               [0, 1, 'no'],
               [0, 1, 'no']]
    labels = ['no surfacing', 'flippers']
    return dataSet, labels

劃分?jǐn)?shù)據(jù)集

def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        #如果featVec第axis+1項(xiàng)的值等于需匹配的value
        if featVec[axis] == value:
            #featVec中不包含第axis+1項(xiàng)的剩余部分
            print 'axis: %d, value: %d, featVec:' % (axis, value), featVec
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

尋找最好的劃分方式

def chooseBestFeatureToSplit(dataSet):
    # 特征值的數(shù)量，不包含第三項(xiàng)標(biāo)簽
    numFeatures = len(dataSet[0]) - 1
    bestEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    for i in range(numFeatures):
        # 列出所有第i+1項(xiàng)的值作為一個(gè)列表
        featList = [example[i] for example in dataSet]
        # 列表中的值去重創(chuàng)建集合
        uniqueVals = set(featList)
        newEntropy = 0.0
        for value in uniqueVals:
            #找到劃分后的子集
            subDataSet = splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            print 'subDataSet:',subDataSet,'\nlen(subDataSet):',len(subDataSet),', prob:',prob
            #將所有value的熵相加
            newEntropy += prob * calcShannonEnt(subDataSet)
            print "i: %d, value: %d, newEntropy: %f\n" % (i,value,newEntropy)
        # 信息增益就是熵的減少
        infoGain = bestEntropy - newEntropy
        print "i: %d, bestEntropy:%f, infoGain(bestEntropy - newEntropy): %f\n" % (i,bestEntropy,infoGain)
        if(infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

尋找最多數(shù)的標(biāo)簽

def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount

創(chuàng)建決策樹

def createTree(dataSet,labels):
    # 取標(biāo)簽列表
    classList = [example[-1] for example in dataSet]
    print '\nclassList',classList
    # 如果classList中第一個(gè)元素的數(shù)量與總元素?cái)?shù)量相同，即classList中的元素均為相同元素
    if classList.count(classList[0]) == len(classList):
        print 'oh！classList[0]',classList[0],'classList.count(classList[0])',classList.count(classList[0]),'len(classList)',len(classList)
        # myTree[bestFeatLabel][value] = return的classlist[0]
        return classList[0]
    # 如果最優(yōu)解也無法完全將分類劃分的話，返回出現(xiàn)最多的類別
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)
    # 尋找最好的劃分方式
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 獲取最好的劃分方式對應(yīng)的實(shí)際劃分標(biāo)簽
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    # 在標(biāo)簽中去掉最好的劃分方式對應(yīng)的標(biāo)簽
    del(labels[bestFeat])
    # 最好的劃分方式包含的所有值
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    print 'uniqueVals', uniqueVals
    for value in uniqueVals:
        subLabels = labels[:]
        # 遞歸調(diào)用本函數(shù)
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
        print 'bestFeatLabel',bestFeatLabel,'value',value,'本次myTree', myTree
    return myTree

使用文本注解繪制節(jié)點(diǎn)樹

新建treePlottter.py

# -*- 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):
    # nodeTxt文本注解, centerPt終點(diǎn)坐標(biāo), parentPt起點(diǎn)坐標(biāo), nodeType文本框樣式
    # 創(chuàng)建一個(gè)描述 annotate(s, xy, xytext=None, xycoords='data',textcoords='data', arrowprops=None, **kwargs)
    # s : 描述的文本
    # xy、xytext: 起點(diǎn)及終點(diǎn)坐標(biāo)
    # xycoords 、textcoords : 給定坐標(biāo)系，axes fraction(0,0是)軸域左下角，(1,1)是軸域右上角。data為使用軸域數(shù)據(jù)坐標(biāo)系
    # arrowstyle : 箭頭樣式'->'指向標(biāo)注點(diǎn) '<-'指向標(biāo)注內(nèi)容
    createPlot.ax1.annotate(nodeTxt, xy = parentPt, xycoords = 'axes fraction', xytext = centerPt, textcoords = 'axes fraction', va = 'center', ha = 'center', bbox = nodeType, arrowprops = arrow_args)

def createPlot():
    fig = plt.figure(1, facecolor = 'white')
    fig.clf()
    createPlot.ax1 = plt.subplot(111, frameon = False)
    plotNode(U'決策節(jié)點(diǎn)', (0.5, 0.1), (0.1, 0.5), decisionNode)
    plotNode(U'葉節(jié)點(diǎn)', (0.8, 0.1), (0.3, 0.8), leafNode)
    plt.show()

獲取葉節(jié)點(diǎn)的數(shù)目和樹的層數(shù)

def getNumLeafs(myTree):
  # 獲取葉子節(jié)點(diǎn)數(shù)
    numLeafs = 0
    firstStr = myTree.keys()[0]
    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):
  # 獲取層數(shù)
    maxDepth = 0
    firstStr = myTree.keys()[0]
    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

def retrieveTree(i):
    # 一組假數(shù)據(jù)，方便使用
    listOfTrees =[{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}},
                  {'no surfacing': {0: 'no', 1: {'flippers': {0: {'head': {0: 'no', 1: 'yes'}}, 1: 'no'}}}}
                  ]
    return listOfTrees[i]

繪制樹形圖

def plotTree(myTree, parentPt, nodeTxt):
    numLeafs = getNumLeafs(myTree)
    depth = getTreeDepth(myTree)
    firstStr = myTree.keys()[0]
    cntrPt = (plotTree.xOff + (1.0 + float(numLeafs)) / 2.0 / plotTree.totalW, plotTree.yOff)
    print '1 plotTree.xOff', plotTree.xOff, 'plotTree.yOff', plotTree.yOff, 'cntrPt', cntrPt, 'parentPt', parentPt
    plotMidText(cntrPt, parentPt, nodeTxt)
    print '\tmidText "%s" drawn,' % nodeTxt, '起點(diǎn)',parentPt,', 終點(diǎn)',cntrPt
    plotNode(firstStr, cntrPt, parentPt, decisionNode)
    print '\tdecisionNode "%s" drawn,' % firstStr, '起點(diǎn)',parentPt,', 終點(diǎn)',cntrPt
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - 1.0 / plotTree.totalD
    print '2 plotTree.xOff', plotTree.xOff, 'plotTree.yOff', plotTree.yOff
    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
            print '3 plotTree.xOff', plotTree.xOff, 'plotTree.yOff', plotTree.yOff
            plotNode(secondDict[key], (plotTree.xOff, plotTree.yOff), cntrPt, leafNode)
            print '\tleafNode "%s" drawn,' % secondDict[key], '起點(diǎn) (',plotTree.xOff, plotTree.yOff,'), 終點(diǎn)',cntrPt
            plotMidText((plotTree.xOff, plotTree.yOff), cntrPt, str(key))
    plotTree.yOff = plotTree.yOff + 1.0 / plotTree.totalD
    print '4 plotTree.xOff', plotTree.xOff, 'plotTree.yOff', plotTree.yOff

def createPlot(inTree):
    fig = plt.figure(1, facecolor = 'white')
    fig.clf()
    axprops = dict(xticks = [], yticks = [])
    createPlot.ax1 = plt.subplot(111, frameon = False, **axprops)
    plotTree.totalW = float(getNumLeafs(inTree))
    plotTree.totalD = float(getTreeDepth(inTree))
    plotTree.xOff = -0.5/plotTree.totalW
    plotTree.yOff = 1.0
    plotTree(inTree, (0.5,1.0), '')
    plt.show()

使用決策樹執(zhí)行分類

def classify(inputTree, featLabels, testVec):
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index(firstStr)
    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]
    return classLabel

決策樹的存儲(chǔ)

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)

應(yīng)用：預(yù)測隱形眼鏡類型