基本概念

決策樹(shù)是分類(lèi)算法。

數(shù)據(jù)類(lèi)型：數(shù)值型和標(biāo)稱(chēng)型。因?yàn)闃?gòu)造算法只適用于標(biāo)稱(chēng)型，所以數(shù)值型數(shù)據(jù)必須離散化。

工作原理

利用香濃熵找到信息增益***的特征，按照信息增益***的特征劃分?jǐn)?shù)據(jù)，如此反復(fù)，讓無(wú)序的數(shù)據(jù)變的更加有序。使用ID3算法構(gòu)建樹(shù)結(jié)構(gòu)。當(dāng)傳入一個(gè)新數(shù)據(jù)時(shí)，按照數(shù)據(jù)找到對(duì)應(yīng)樹(shù)節(jié)點(diǎn)，直到***沒(méi)有葉子節(jié)點(diǎn)時(shí)，完成分類(lèi)。

樣例

不浮出水面是否可以生存? 是否有腳蹼? 是否是魚(yú)類(lèi)?

通過(guò)“不浮出水面是否可以生存”和“是否有腳蹼”這兩個(gè)特征來(lái)判斷是否是魚(yú)類(lèi)。構(gòu)建一個(gè)簡(jiǎn)單決策樹(shù)，如果得到一個(gè)新的生物，可以用此來(lái)判斷是否是魚(yú)類(lèi)。

樣例代碼

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 

香農(nóng)熵公式

如果待分類(lèi)的事務(wù)可能劃分在多個(gè)分類(lèi)之中，則符號(hào)Xi的信息定義為：

其中P(Xi)是選擇該分類(lèi)的概率

為了計(jì)算熵，需要計(jì)算所有類(lèi)別所有可能值包含的信息期望值總和，公式為：

其中n是分類(lèi)的數(shù)目

香農(nóng)熵算法

def calcShannonEnt(dataSet):   
    # 選擇該分類(lèi)的概率 就是每個(gè)類(lèi)型/總個(gè)數(shù) 
    # 總數(shù)，多少行數(shù)據(jù) 
    numEntries = len(dataSet) 
    labelCounts = {} 
    # 取到的每個(gè)類(lèi)型個(gè)數(shù) 
    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: 
        # 得到選擇該分類(lèi)的概率 
        prob = float(labelCounts[key])/numEntries 
        # 按照公式 
        shannonEnt -= prob * log(prob,2) #log base 2 
    return shannonEnt 

按照香農(nóng)熵劃分?jǐn)?shù)據(jù)

除了需要測(cè)量信息熵，還需要?jiǎng)澐謹(jǐn)?shù)據(jù)集，度量花費(fèi)數(shù)據(jù)集的熵，以便判斷當(dāng)前是否正確劃分。 循環(huán)計(jì)算香濃熵和splitDataSet()，找到***的特征劃分方式。

def splitDataSet(dataSet, axis, value):   
    # 這個(gè)算法返回axis下標(biāo)之外的列 
    retDataSet = [] 
    for featVec in dataSet: 
        if featVec[axis] == value: 
            reducedFeatVec = featVec[:axis]     #chop out axis used for splitting 
            reducedFeatVec.extend(featVec[axis+1:]) 
            retDataSet.append(reducedFeatVec) 
    return retDataSet 
 
def chooseBestFeatureToSplit(dataSet):   
    # 先取***一列，用在標(biāo)簽結(jié)果：是魚(yú)或不是魚(yú)。 
    numFeatures = len(dataSet[0]) - 1 
    # 原始香濃熵 
    baseEntropy = calcShannonEnt(dataSet) 
 
    bestInfoGain = 0.0; bestFeature = -1 
    # 遍歷所有的特征 
    for i in range(numFeatures): 
        # 創(chuàng)建一個(gè)列表包含這個(gè)特征的所有值 
        featList = [example[i] for example in dataSet] 
        # 利用set去重 
        uniqueVals = set(featList) 
        newEntropy = 0.0 
        # 計(jì)算該特征所包含類(lèi)型的香濃熵之和 
        for value in uniqueVals: 
            subDataSet = splitDataSet(dataSet, i, value) 
            prob = len(subDataSet)/float(len(dataSet)) 
            newEntropy += prob * calcShannonEnt(subDataSet) 
        # 得到信息增益 
        infoGain = baseEntropy - newEntropy 
        # 取***的信息增益，并記錄下標(biāo) 
        if (infoGain > bestInfoGain): 
            bestInfoGain = infoGain 
            bestFeature = i 
    # 返回下標(biāo) 
    return bestFeature 

數(shù)據(jù)集需要滿(mǎn)足一定的要求：

• 數(shù)據(jù)必須是一種有列表元素組成的列表。(二維數(shù)組)
• 所有列表元素必須有相同長(zhǎng)度。
• ***一列必須是當(dāng)前實(shí)例的標(biāo)簽。

遞歸構(gòu)建決策樹(shù)

多數(shù)表決算法

如果數(shù)據(jù)集已經(jīng)處理了所有屬性，但是類(lèi)標(biāo)簽依然不是唯一的，此時(shí)需要決定如何定義該葉子節(jié)點(diǎn)，在這種情況下，我們通常會(huì)采用多數(shù)表決決定該葉子節(jié)點(diǎn)。

import operator   
def majorityCnt(classList):   
    # 排序取出種類(lèi)最多的 
    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[0][0] 

構(gòu)建樹(shù)算法

def createTree(dataSet,labels):   
    # 取出結(jié)果 
    classList = [example[-1] for example in dataSet] 
    # 如果結(jié)果里的***個(gè)元素所代表的數(shù)據(jù)個(gè)數(shù)等于結(jié)果本身，說(shuō)明沒(méi)有其他分類(lèi)了 
    if classList.count(classList[0]) == len(classList):  
        return classList[0] 
    # 如果沒(méi)有更多數(shù)據(jù)了，超過(guò)一個(gè)才有分類(lèi)的意義 
    if len(dataSet[0]) == 1: 
        # 多數(shù)表決，返回出現(xiàn)次數(shù)最多的 
        return majorityCnt(classList) 
 
    # 選出最適合用于切分類(lèi)型的下標(biāo) 
    bestFeat = chooseBestFeatureToSplit(dataSet) 
    # 根據(jù)下標(biāo)取出標(biāo)簽 
    bestFeatLabel = labels[bestFeat] 
    # 構(gòu)建樹(shù) 
    myTree = {bestFeatLabel:{}} 
    # 刪除取出過(guò)的標(biāo)簽，避免重復(fù)計(jì)算 
    del(labels[bestFeat]) 
    featValues = [example[bestFeat] for example in dataSet] 
 
    # 利用set去重 
    uniqueVals = set(featValues) 
 
 
    for value in uniqueVals: 
        # 復(fù)制所有的子標(biāo)簽，因?yàn)槭且妙?lèi)型，以避免改變?cè)紭?biāo)簽數(shù)據(jù) 
        subLabels = labels[:] 
        # 遞歸的構(gòu)建樹(shù) 
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value),subLabels) 
    return myTree 

使用決策樹(shù)分類(lèi)

def classify(inputTree,featLabels,testVec):   
    firstStr = inputTree.keys()[0] 
    secondDict = inputTree[firstStr] 
    featIndex = featLabels.index(firstStr) 
    # print 'featIndex %s' % (featIndex) 
    key = testVec[featIndex] 
    # print 'key %s' % (key) 
    valueOfFeat = secondDict[key] 
    if isinstance(valueOfFeat, dict):  
        classLabel = classify(valueOfFeat, featLabels, testVec) 
    else: classLabel = valueOfFeat 
    return classLabel 
 
dataSet, labels = createDataSet()   
mytree = createTree(dataSet, labels[:]) #因?yàn)閮?nèi)部會(huì)刪除labels里的值所以用這樣copy一份   
print mytree   
# {'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}} 
print classify(mytree, labels, [0,1])   
no 

決策樹(shù)的存儲(chǔ)

構(gòu)造決策樹(shù)是耗時(shí)的任務(wù)，即使處理很小的數(shù)據(jù)集。所以我們可以使用構(gòu)造好的決策樹(shù)。

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ōu)點(diǎn)

• 計(jì)算復(fù)雜度不高
• 輸出結(jié)果易于理解
• 對(duì)中間值缺失不敏感
• 可以處理不相關(guān)特偵

缺點(diǎn)

• 可能產(chǎn)生過(guò)度匹配問(wèn)題