決策樹定義

• 概念：決策樹可以近似于一個流程圖，長方形代表判斷模塊，橢圓形代表終止模塊，表示已經(jīng)得出結(jié)論，可以終止運行。從判斷模塊引出的左右箭頭稱作分支，它可以到達另一個判斷模塊或者終止模塊。

  
  
  決策樹

• 優(yōu)點：計算復雜度不高，輸出結(jié)果易于理解，對中間值的缺失不敏感，可以處理不相關特征數(shù)據(jù)

• 缺點：可能會產(chǎn)生過度匹配問題

• 應用難點：很難確定特征

• 適用數(shù)據(jù)類型：數(shù)值型和標稱型

• 如何創(chuàng)建樹的分支？

Function createBranch():
檢測數(shù)據(jù)集中的每個子集是否屬于同一分類
    If so return 類標簽;
    Else
        尋找劃分數(shù)據(jù)集的最好特征
        劃分數(shù)據(jù)集
        創(chuàng)建分支節(jié)點
            for 每個劃分的子集
                調(diào)用函數(shù)createBranch()并增加返回結(jié)果到分支節(jié)點中
        return 分支節(jié)點

• 信息增益：劃分數(shù)據(jù)之前之后的變化稱為信息增益，通過計算每個特征值劃分數(shù)據(jù)集獲得的信息增益，獲得信息增益最高的特征就是最好的選擇。香農(nóng)提出的了熵用于計算信息增益，信息增益=原來的熵-變化后的熵
• 信息的定義：l(xi)=-log2p(xi),p(xi)表示選擇xi類別的概率
• 熵：信息的期望值，計算一個樣本集合中的數(shù)據(jù)是純潔的還是不純潔的，公式(n是分類的數(shù)目)：

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

決策樹的程序?qū)崿F(xiàn)

• 計算給定數(shù)據(jù)集的香農(nóng)熵的實現(xiàn)代碼：

from math import log
def calcShannonEnt(dataset):
    numEntries = len(dataset)
    labelCounts ={}
    # 求出各個類別的樣本總數(shù)，用來計算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

• 信息熵、信息增益與信息增益率的區(qū)別
• 劃分數(shù)據(jù)集：對每個特征劃分數(shù)據(jù)集的結(jié)果計算一次信息熵，然后判斷按照哪個特征劃分數(shù)據(jù)集是最好的劃分方式：

#按照給定特征劃分數(shù)據(jù)集
#extend() 函數(shù)用于在列表末尾一次性追加另一個序列中的多個值
#輸入：待劃分的數(shù)據(jù)集，劃分數(shù)據(jù)集的特征，需要返回的特征的值
#a[i:j]:表示取從第i+1位到第j個元素
def splitDataSet(dataSet,axis,value):
    retDataSet =[]
    for featVec in dataSet:
        if featVec[axis] == value:
            # 從數(shù)據(jù)元組去掉該特征值
            reduceFeatVec =featVec[:axis]
            reduceFeatVec.extend(featVec[axis+1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

• 選擇最好的數(shù)據(jù)集劃分方法

#選擇最好的數(shù)據(jù)集劃分方式
def chooseBestFeatureToSplit(dataSet):
    #計算列數(shù)得到特征數(shù)
    numFeatures = len(dataSet) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeatures = -1
    for i in range(numFeatures):
        #循環(huán)取出dataset的元組，然后取出元組中的第i列的所有取值
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        #計算每個特征的所有特征值作為劃分子節(jié)點時的熵
        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

• 數(shù)據(jù)具有多個標簽時如何處理？
  • 采用多數(shù)表決的方法決定該子節(jié)點的分類

#當出現(xiàn)多個類標簽結(jié)果時，采用投票表決的方法決定最終類標簽
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]

• 構(gòu)建決策樹：

#創(chuàng)建樹的函數(shù)代碼
def createTree(dataSet, labels):
    classList=[example[-1]  for example in dataSet]
    #觀察當前分組的分類標簽是否一致
    if(classList.count(classList[0])==len(classList)):
        return classList[0]
    #特征已經(jīng)遍歷完
    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

• 使用前面構(gòu)造好的算法得到?jīng)Q策樹，對測試數(shù)據(jù)執(zhí)行分類：

#使用決策樹執(zhí)行分類
#輸入：決策樹，特征表，測試數(shù)據(jù)
def classify(inputTree, feaLabels, testVec):
    #取出第一個鍵值，即根
    firstStr = inputTree.keys()[0]
    #獲得根對應的子節(jié)點
    secondDict = inputTree[firstStr]
    #找到第一個鍵值在實際數(shù)據(jù)存儲中的列位置
    featIndex = feaLabels.index(firstStr)
    for key in secondDict.keys():
        #找到下一步要到達的節(jié)點
        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)