機器學習筆記3-id3算法決策樹程式解析

from math import log

import operator

import treePlotter

import pickle

def calcShannoEnt(dataSet):

    '''

    根據一個給定的資料集求香農熵,這裡開始沒搞懂,後來複習了一下資訊論與編碼總算是搞明白了

    例如這個資料集,我們需要了解的資訊是"是否為水生生物",而描述一個資訊的資訊量的大小是取決于他的不确定度(即這個資訊出現的機率)

    為什麼這麼了解,例如,一個生物是水生生物的機率為2/5,即不确定度為2/5,那麼當我們知道這個動物屬于水生生物時,2/5的不确定度就被消除了,可以了解為消除的不确定度就是我們獲得的資訊

    一個資訊所含有的資訊量我們用自資訊量來衡量,它的

    計算公式是I = -log('一事件出現的機率',2),其中2代表對數以2為底,比如這裡我們假設是水生生物的機率為2/5,不是水生生物的機率為3/5,那麼他們的資訊量分别為-log(2/5,2),-log(3/5,2)

    熵(這本書上說得是香農熵)其實就是資訊的平均不确定度,數值上等于平均資訊量,即當我們知道一個動物是水生生物或者不是水生生物所獲得的平均資訊量,計算公式為

    某事件的機率*某事件的自資訊量求和,例如是否為水生生物的熵為(2/5)*(-log(2/5,2))+(3/5)*(-log(3/5,2))

    資訊增益在網上查閱了一些資料也能了解了

    例如我們要判斷在一群人中一個人的性别是男是女,判斷成功的機率為1/2,是男是女事件分别對應的自資訊量為1,平均資訊量為0.5

    而人有如下特點1:是否有喉結,2:頭發長短

    當我們用特征值1,即有無喉結來劃分這一群人,資料集就被我們劃分成了兩波人,有喉結的人和無喉結的人

    當我們在有喉結的人中判斷是男人還是女人的時候,判斷成功的機率為1,自資訊量和平均資訊量都是0

    資訊增益就等于未劃分之前的平均資訊量-劃分之後的平均資訊量

    簡單了解,資訊增益就是我們用一個特征(有無喉結)将一個資料集(人類)劃分之後,對我們判斷某一事物(男人還是女人)的幫助是多大

    比如有無喉結和頭發長短,基本上有喉結的肯定是男人,而長頭發的不一定肯定是女人,那麼有無喉結的特征對我們判斷性别的資訊增益就比頭發長短要大

    '''

    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

def splitDataSet(dataSet,axis,value):

    '''

    根據給定的資料集,劃分資料集的特征,特征的傳回值來劃分資料集

    '''

    returnSet = []

    for featVec in dataSet:

        if featVec[axis] == value:

            reducedFeatVec = featVec[:axis]

            reducedFeatVec.extend(featVec[axis+1:])

            returnSet.append(reducedFeatVec)

    return returnSet

def createTestSet():

    dataSet = [[1,1,'yes'],

               [1,1,'yes'],

               [1,0,'no' ],

               [0,1,'no' ],

               [0,1,'no' ]]

    labels = ['no surfacing','flippers']

    return dataSet,labels

def chooseBestFeatureToSplit(dataSet):

    '''

    選擇最好的劃分特征,即最大的資訊增益

    '''

    numFeatures = len(dataSet[0]) - 1

    baseEntropy = calcShannoEnt(dataSet)

    bestInfoGain = 0.0

    bestFeature = -1

    for i in range(numFeatures):

        featList = [example[i] for example in dataSet]

        #value去重

        uniqueVals = set(featList)

        newEntropy = 0.0

        for value in uniqueVals:

            subDataSet = splitDataSet(dataSet,i,value)

            prob = len(subDataSet)/float(len(dataSet))

            newEntropy += prob * calcShannoEnt(subDataSet)

        infoGain = baseEntropy - newEntropy

        if infoGain > bestInfoGain:

            bestInfoGain = infoGain

            bestFeature = i

    return bestFeature

def majorityCnt(classList):

    '''

    在一個清單中傳回最多的值

    '''

    classCount = {}

    for vote in classList:

        if vote not in classCount.keys():

            classCount[vote] = 0

        classCount[vote] += 1

    sortedClassCount = sorted(classCount.item(),key = operator.itemgetter(1),reverse = True)

    return sortedClassCount[0][0]

def createTree(dataSet,labels):

    '''

    建構決策樹

    決策樹遞歸過程:開始一直無法了解疊代過程中有一個if-return語句,如果直接滿足條件不是直接會退出程式嗎?

    在網上找到一個非常好的答案幫我解決了這個問題,一句話就是return之前需要将程式運作完畢,例如如下函數

        def fact(n):

          if n==1:

            return 1

          return n * fact(n - 1)

    疊代過程如下:

        ===> fact(5)

        ===> 5 * fact(4)

        ===> 5 * (4 * fact(3))

        ===> 5 * (4 * (3 * fact(2)))

        ===> 5 * (4 * (3 * (2 * fact(1))))

    在return之前,n * fact(n - 1)必須要計算完畢

    本程式中的createTree(dataSet,labels)函數與之類似,在return之前,myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)必須計算完畢

    設dataSet為create為:

    [[1,1,'yes'],    lebels為['no surfacing','flippers']

     [1,1,'yes'],

     [1,0,'no' ],

     [0,1,'no' ],

     [0,1,'no' ]]

    第一次疊代有兩個分支1:MyTree['no surfacing'][0] = createTree([[1,'no'],[1,'no'])

                        2:MyTree['no surfacing'][1] = createTree([[1,'yes'],[1,'yes'],[0,'no'])

    分支1進入一次疊代直接滿足條件classList.count(classList[0]) == len(classList),直接等于'no'

    分支2進入一次疊代後有兩個分支2_1:MyTree['no surfacing'][1]['flippers'][0] = createTree([['no']])

                                 2_1:MyTree['no surfacing'][1]['flippers'][1] = createTree([['yes'],['yes]])

    2_1,2_2滿足第一條語,2_1傳回'no',2_2傳回'yes',最後計算結果

    MyTree['no surfacing'][0] = 'no'

    MyTree['no surfacing'][1]['flippers'][0] = 'no'

    MyTree['no surfacing'][1]['flippers'][1] = 'yes'

    即{'no surfacing'{0:'no',1:{'flippers':{0:'no',1:'yes'}}}}

    '''

    #dataSet的'yes' or 'no'集合,在本書中的測試例子中第一次疊代時classList = ['yes','yes','no','no']

    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,featLabels,testVec):

    '''

    利用決策樹對給定的特征值的對象進行分類

    '''

    #樹的一号決策點,測試決策樹中是'no surfacing'

    firstStr = list(inputTree.keys())[0]

    #測試決策樹中是{0:'no',1:{'flippers':{0:'no',1:'yes'}}}

    secoundDict = inputTree[firstStr]

    #傳回'no sufacing'在标簽清單中的位置

    featIndex = featLabels.index(firstStr)

    #進入循環,如果到達葉節點,傳回分類,如果沒有到達,疊代

    for key in secoundDict.keys():

        if testVec[featIndex] == key:

            if type(secoundDict[key]).__name__ == 'dict':

                classLabel = classify(secoundDict[key],featLabels,testVec)

            else:classLabel = secoundDict[key]

    return classLabel

def storeTree(inputTree,filename):

    '''

    用于将構造好的決策樹存儲到檔案中

    '''

    fw = open(filename,'wb')

    pickle.dump(inputTree,fw)

    fw.close()

def grabTree(filename):

    '''

    用于擷取檔案中存儲的決策樹

    '''

    fr = open(filename,'rb')

    return pickle.load(fr)

def test():

    fr = open('f:\\lenses.txt')

    lenses = [inst.strip().split('\t') for inst in fr.readlines()]

    print(lenses)

    lenselabels = ['age','prescript','astigmatic','tearRate']

    lenseTree = createTree(lenses,lenselabels)

    print(lenseTree)

if __name__ == '__main__':

    test()

'''

決策樹很好的比對了實驗資料,但是比對選項可能太多了,我們将這種問題稱為過度比對

為了減少過度比對,可以裁剪決策樹,去掉一些不必要的葉子節點,如果葉子節點隻能增加

少許資訊,可以删除該節點

決策樹就像帶有終止子產品的流程圖,終止塊表示分類結果,處理資料集時

首先要測量集合中資料的熵

然後選擇最優方案劃分資料集,直到資料集中的所有資料屬于同一分類

'''