機(jī)器學(xué)習(xí)之決策樹(shù)ID3(python實(shí)現(xiàn))

機(jī)器學(xué)習(xí)中，決策樹(shù)是一個(gè)預(yù)測(cè)模型；代表對(duì)象屬性和對(duì)象值之間的一種映射關(guān)系。樹(shù)中每個(gè)節(jié)點(diǎn)表示某個(gè)對(duì)象，而每個(gè)分叉表示某個(gè)可能的屬性，每個(gè)葉子節(jié)點(diǎn)則對(duì)應(yīng)從根節(jié)點(diǎn)到該葉子節(jié)點(diǎn)所經(jīng)歷的路徑所表示的對(duì)象的值。決策樹(shù)只有單一輸出，若想要復(fù)數(shù)輸出，可以建立獨(dú)立的決策樹(shù)以處理不同輸入。
數(shù)據(jù)挖掘中常用到?jīng)Q策樹(shù)，可以用于分析數(shù)據(jù)，也可以用于預(yù)測(cè)。

簡(jiǎn)單理解

image.png

如上圖，
前兩個(gè)是屬性，可以記為['no surfacing','flippers']。則可以簡(jiǎn)單的構(gòu)建決策樹(shù)如下：
image.png

根據(jù)兩個(gè)屬性可以判斷是否屬于魚(yú)類。

那么首先決定選擇哪個(gè)屬性作為最開(kāi)始的分類？最簡(jiǎn)單的是ID3。改進(jìn)的C4.5， CART后面再進(jìn)行了解。

決策樹(shù)和ID3

決策樹(shù)與樹(shù)結(jié)構(gòu)類似，具有樹(shù)形結(jié)構(gòu)。每個(gè)內(nèi)部節(jié)點(diǎn)表示一個(gè)屬性的測(cè)試，每個(gè)分支代表一個(gè)測(cè)試輸出，每個(gè)葉子節(jié)點(diǎn)代表一種類別。如上圖一樣。
分類樹(shù)（決策樹(shù)）常用于機(jī)器學(xué)習(xí)的分類，是一種監(jiān)督學(xué)習(xí)方法。由樹(shù)的分支對(duì)該類型的對(duì)象依靠屬性進(jìn)行分類。每個(gè)決策樹(shù)可以依靠對(duì)源數(shù)據(jù)庫(kù)分割進(jìn)行數(shù)據(jù)測(cè)試，遞歸修剪樹(shù)。知道一個(gè)單獨(dú)的類被應(yīng)用于某一分支，不能進(jìn)行分割，遞歸完成。
特點(diǎn)：

  • 多層次的決策樹(shù)形式易于理解。
  • 只適用于標(biāo)稱行數(shù)據(jù)，連續(xù)性數(shù)據(jù)處理的不好。

ID3算法

上面介紹，怎么在一系列屬性中首先選擇哪個(gè)屬性進(jìn)行分類。簡(jiǎn)單理解，如果哪個(gè)屬性比較混亂，直接就可以得到所屬類別。比如上面屬性水下是否可以生存，不能生存的可以分類為 不是魚(yú)。
那么怎么去量化，得到這個(gè)屬性呢？
ID3算法的核心是信息墑，通過(guò)計(jì)算每個(gè)屬性的信息增益，認(rèn)為增益高的是好屬性，易于分類。每次劃分選取信息增益最高的屬性作為劃分標(biāo)準(zhǔn)，進(jìn)行重復(fù)，直至生成一個(gè)能完美分類訓(xùn)練樣歷的決策樹(shù)。

image.png

上面信息增益的算法不是很好理解，后面看代碼很容易。

ID3算法和決策樹(shù)的流程

  1. 數(shù)據(jù)準(zhǔn)備：需要對(duì)數(shù)值型數(shù)據(jù)進(jìn)行離散化
  2. ID3算法構(gòu)建決策樹(shù)：
  • 如果數(shù)據(jù)類別完全相同，則停止劃分。
  • 否則，繼續(xù)劃分：
    • 計(jì)算信息墑和信息增益來(lái)選擇最好的數(shù)據(jù)集劃分方法
    • 劃分?jǐn)?shù)據(jù)集
    • 創(chuàng)建分支節(jié)點(diǎn)
    • 對(duì)每個(gè)分支進(jìn)行判定類別相同。相同停止劃分，不同則按照上述方法進(jìn)行劃分。

python代碼實(shí)現(xiàn)

利用上面例子創(chuàng)建數(shù)據(jù)集

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

計(jì)算信息墑,對(duì)應(yīng)第一個(gè)公式

def calcShannonEnt(dataSet):
    numEntries = len(dataSet)
    # 為分類創(chuàng)建字典
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts.setdefault(currentLabel, 0)
        labelCounts[currentLabel] += 1

    # 計(jì)算香農(nóng)墑
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / numEntries
        shannonEnt += prob * math.log2(1 / prob)
    return shannonEnt

計(jì)算最大信息增益(公式2)， 劃分?jǐn)?shù)據(jù)集。

# 定義按照某個(gè)特征進(jìn)行劃分的函數(shù) splitDataSet
# 輸入三個(gè)變量（帶劃分?jǐn)?shù)據(jù)集， 特征，分類值)
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]
            reduceFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reduceFeatVec)
    return retDataSet  #返回不含劃分特征的子集

#  定義按照最大信息增益劃分?jǐn)?shù)據(jù)的函數(shù)
def chooseBestFeatureToSplit(dataSet):
    numFeature = len(dataSet[0]) - 1
    print(numFeature)
    baseEntropy = calcShannonEnt(dataSet)
    bestInforGain = 0
    bestFeature = -1

    for i in range(numFeature):
        featList = [number[i] for number in dataSet] #得到某個(gè)特征下所有值
        uniqualVals = set(featList) #set無(wú)重復(fù)的屬性特征值
        newEntrogy = 0

        #求和
        for value in uniqualVals:
            subDataSet = splitDataSet(dataSet, i, value)
            prob = len(subDataSet) / float(len(dataSet)) #即p(t)
            newEntrogy += prob * calcShannonEnt(subDataSet) #對(duì)各子集求香農(nóng)墑

        infoGain = baseEntropy - newEntrogy #計(jì)算信息增益
        print(infoGain)

        # 最大信息增益
        if infoGain > bestInforGain:
            bestInforGain = infoGain
            bestFeature = i
    return bestFeature

簡(jiǎn)單測(cè)試：

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    r = chooseBestFeatureToSplit(dataSet)
    print(r)
# 輸出
# 2
# 0.41997309402197514
# 0.17095059445466865
# 0

如上，可以看到共有兩個(gè)屬性['no surfacing','flippers']和其信息增益，因此選擇較大的特征(下標(biāo)0)對(duì)數(shù)據(jù)集進(jìn)行劃分(見(jiàn)開(kāi)始圖)，重復(fù)步驟，知道只剩下一個(gè)類別。

創(chuàng)建決策樹(shù)構(gòu)造函數(shù)

# 投票表決代碼
def majorityCnt(classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount.setdefault(vote, 0)
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=lambda i:i[1], reverse=True)
    return sortedClassCount[0][0]

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # print(dataSet)
    # print(classList)
    # 類別相同，停止劃分
    if classList.count(classList[0]) == len(classList):
        return classList[0]

    # 判斷是否遍歷完所有的特征,是，返回個(gè)數(shù)最多的類別
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    #按照信息增益最高選擇分類特征屬性
    bestFeat = chooseBestFeatureToSplit(dataSet) #分類編號(hào)
    bestFeatLabel = labels[bestFeat]  #該特征的label
    myTree = {bestFeatLabel: {}}
    del (labels[bestFeat]) #移除該label

    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLabels = labels[:]  #子集合
        #構(gòu)建數(shù)據(jù)的子集合，并進(jìn)行遞歸
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

代碼里面有注視，嘗試去理解每一步的執(zhí)行，對(duì)決策樹(shù)有一個(gè)基本的了解。

if __name__ == '__main__':
    dataSet, labels = createDataSet()
    r = chooseBestFeatureToSplit(dataSet)
    # print(r)
    myTree = createTree(dataSet, labels)
    print(myTree)
#  --> {'no sufacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}

可以看到輸出結(jié)果是一個(gè)嵌套的字典，手動(dòng)可以畫(huà)出決策樹(shù)，與開(kāi)頭的圖相吻合。

將決策樹(shù)用于分類

構(gòu)建決策樹(shù)分類函數(shù)：

def classify(inputTree, featLabels, testVec):
    """
    :param inputTree: 決策樹(shù)
    :param featLabels: 屬性特征標(biāo)簽
    :param testVec: 測(cè)試數(shù)據(jù)
    :return: 所屬分類
    """
    firstStr = list(inputTree.keys())[0] #樹(shù)的第一個(gè)屬性
    sendDict = inputTree[firstStr]

    featIndex = featLabels.index(firstStr)
    classLabel = None
    for key in sendDict.keys():

        if testVec[featIndex] == key:
            if type(sendDict[key]).__name__ == 'dict':
                classLabel = classify(sendDict[key], featLabels, testVec)
            else:
                classLabel = sendDict[key]
    return classLabel

可以看到函數(shù)分別根據(jù)屬性值對(duì)測(cè)試數(shù)據(jù)進(jìn)行一步一步分類，直至到葉子節(jié)點(diǎn)，得到正確的分類。

另外，可以將決策樹(shù)進(jìn)行存儲(chǔ)，與kNN不一樣的是，決策樹(shù)構(gòu)造好不用重復(fù)計(jì)算，下次可以直接使用.

def storeTree(inputTree,filename):
    import pickle
    fw=open(filename,'wb') #pickle默認(rèn)方式是二進(jìn)制，需要制定'wb'
    pickle.dump(inputTree,fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr=open(filename,'rb')#需要制定'rb'，以byte形式讀取
    return pickle.load(fr)

完整決策樹(shù)代碼請(qǐng)查看github：
github:decision_tree

總結(jié)

  • 決策樹(shù)： ID3， C4.5， CART
  • 信息論：信息墑，信息增益
  • python對(duì)象存儲(chǔ)

參考資料：
機(jī)器學(xué)習(xí)之決策樹(shù)(ID3)算法與Python實(shí)現(xiàn)

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容