第3章 決策樹

決策樹首頁

決策樹 概述

決策樹（Decision Tree）算法主要用來處理分類問題，是最經(jīng)常使用的數(shù)據(jù)挖掘算法之一。

決策樹 場(chǎng)景

一個(gè)叫做 "二十個(gè)問題" 的游戲，游戲的規(guī)則很簡(jiǎn)單：參與游戲的一方在腦海中想某個(gè)事物，其他參與者向他提問，只允許提 20 個(gè)問題，問題的答案也只能用對(duì)或錯(cuò)回答。問問題的人通過推斷分解，逐步縮小待猜測(cè)事物的范圍，最后得到游戲的答案。

一個(gè)郵件分類系統(tǒng)，大致工作流程如下：

決策樹-流程圖.jpg

首先檢測(cè)發(fā)送郵件域名地址。如果地址為 myEmployer.com, 則將其放在分類 "無聊時(shí)需要閱讀的郵件"中。
如果郵件不是來自這個(gè)域名，則檢測(cè)郵件內(nèi)容里是否包含單詞 "曲棍球" , 如果包含則將郵件歸類到 "需要及時(shí)處理的朋友郵件", 
如果不包含則將郵件歸類到 "無需閱讀的垃圾郵件" 。

決策樹 原理

決策樹 須知概念

信息熵 & 信息增益

熵：
熵（entropy）指的是體系的混亂的程度，在不同的學(xué)科中也有引申出的更為具體的定義，是各領(lǐng)域十分重要的參量。

信息熵（香農(nóng)熵）：
是一種信息的度量方式，表示信息的混亂程度，也就是說：信息越有序，信息熵越低。例如：火柴有序放在火柴盒里，熵值很低，相反，熵值很高。

信息增益：
在劃分?jǐn)?shù)據(jù)集前后信息發(fā)生的變化稱為信息增益。

決策樹 工作原理

如何構(gòu)造一個(gè)決策樹?

我們使用 createBranch() 方法，如下所示：

檢測(cè)數(shù)據(jù)集中的所有數(shù)據(jù)的分類標(biāo)簽是否相同:
    If so return 類標(biāo)簽
    Else:
        尋找劃分?jǐn)?shù)據(jù)集的最好特征（劃分之后信息熵最小，也就是信息增益最大的特征）
        劃分?jǐn)?shù)據(jù)集
        創(chuàng)建分支節(jié)點(diǎn)
            for 每個(gè)劃分的子集
                調(diào)用函數(shù) createBranch （創(chuàng)建分支的函數(shù)）并增加返回結(jié)果到分支節(jié)點(diǎn)中
        return 分支節(jié)點(diǎn)

決策樹 開發(fā)流程

收集數(shù)據(jù)：可以使用任何方法。
準(zhǔn)備數(shù)據(jù)：樹構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)，因此數(shù)值型數(shù)據(jù)必須離散化。
分析數(shù)據(jù)：可以使用任何方法，構(gòu)造樹完成之后，我們應(yīng)該檢查圖形是否符合預(yù)期。
訓(xùn)練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)。
測(cè)試算法：使用經(jīng)驗(yàn)樹計(jì)算錯(cuò)誤率。（經(jīng)驗(yàn)樹沒有搜索到較好的資料，有興趣的同學(xué)可以來補(bǔ)充）
使用算法：此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義。

決策樹 算法特點(diǎn)

優(yōu)點(diǎn)：計(jì)算復(fù)雜度不高，輸出結(jié)果易于理解，對(duì)中間值的缺失不敏感，可以處理不相關(guān)特征數(shù)據(jù)。
缺點(diǎn)：可能會(huì)產(chǎn)生過度匹配問題。
適用數(shù)據(jù)類型：數(shù)值型和標(biāo)稱型。

決策樹 項(xiàng)目案例

項(xiàng)目案例1: 判定魚類和非魚類

項(xiàng)目概述

根據(jù)以下 2 個(gè)特征，將動(dòng)物分成兩類：魚類和非魚類。

特征：

1. 不浮出水面是否可以生存
2. 是否有腳蹼

開發(fā)流程

收集數(shù)據(jù)：可以使用任何方法
準(zhǔn)備數(shù)據(jù)：樹構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)，因此數(shù)值型數(shù)據(jù)必須離散化
分析數(shù)據(jù)：可以使用任何方法，構(gòu)造樹完成之后，我們應(yīng)該檢查圖形是否符合預(yù)期
訓(xùn)練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)
測(cè)試算法：使用決策樹執(zhí)行分類
使用算法：此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義

收集數(shù)據(jù)：可以使用任何方法

![Uploading 熵的計(jì)算公式_445544.jpg . . .]

海洋生物數(shù)據(jù).png

我們利用 createDataSet() 函數(shù)輸入數(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

準(zhǔn)備數(shù)據(jù)：樹構(gòu)造算法只適用于標(biāo)稱型數(shù)據(jù)，因此數(shù)值型數(shù)據(jù)必須離散化

此處，由于我們輸入的數(shù)據(jù)本身就是離散化數(shù)據(jù)，所以這一步就省略了。

分析數(shù)據(jù)：可以使用任何方法，構(gòu)造樹完成之后，我們應(yīng)該檢查圖形是否符合預(yù)期

熵的計(jì)算公式.jpg

計(jì)算給定數(shù)據(jù)集的香農(nóng)熵的函數(shù)

def calcShannonEnt(dataSet):
    # 求list的長(zhǎng)度，表示計(jì)算參與訓(xùn)練的數(shù)據(jù)量
    numEntries = len(dataSet)
    # 計(jì)算分類標(biāo)簽label出現(xiàn)的次數(shù)
    labelCounts = {}
    # the the number of unique elements and their occurance
    for featVec in dataSet:
        # 將當(dāng)前實(shí)例的標(biāo)簽存儲(chǔ)，即每一行數(shù)據(jù)的最后一個(gè)數(shù)據(jù)代表的是標(biāo)簽
        currentLabel = featVec[-1]
        # 為所有可能的分類創(chuàng)建字典，如果當(dāng)前的鍵值不存在，則擴(kuò)展字典并將當(dāng)前鍵值加入字典。每個(gè)鍵值都記錄了當(dāng)前類別出現(xiàn)的次數(shù)。
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1

    # 對(duì)于 label 標(biāo)簽的占比，求出 label 標(biāo)簽的香農(nóng)熵
    shannonEnt = 0.0
    for key in labelCounts:
        # 使用所有類標(biāo)簽的發(fā)生頻率計(jì)算類別出現(xiàn)的概率。
        prob = float(labelCounts[key])/numEntries
        # 計(jì)算香農(nóng)熵，以 2 為底求對(duì)數(shù)
        shannonEnt -= prob * log(prob, 2)
    return shannonEnt

按照給定特征劃分?jǐn)?shù)據(jù)集

將指定特征的特征值等于 value 的行剩下列作為子數(shù)據(jù)集。

def splitDataSet(dataSet, index, value):
    """splitDataSet(通過遍歷dataSet數(shù)據(jù)集，求出index對(duì)應(yīng)的colnum列的值為value的行)
        就是依據(jù)index列進(jìn)行分類，如果index列的數(shù)據(jù)等于 value的時(shí)候，就要將 index 劃分到我們創(chuàng)建的新的數(shù)據(jù)集中
    Args:
        dataSet 數(shù)據(jù)集                 待劃分的數(shù)據(jù)集
        index 表示每一行的index列        劃分?jǐn)?shù)據(jù)集的特征
        value 表示index列對(duì)應(yīng)的value值   需要返回的特征的值。
    Returns:
        index列為value的數(shù)據(jù)集【該數(shù)據(jù)集需要排除index列】
    """
    retDataSet = []
    for featVec in dataSet: 
        # index列為value的數(shù)據(jù)集【該數(shù)據(jù)集需要排除index列】
        # 判斷index列的值是否為value
        if featVec[index] == value:
            # chop out index used for splitting
            # [:index]表示前index行，即若 index 為2，就是取 featVec 的前 index 行
            reducedFeatVec = featVec[:index]
            '''
            請(qǐng)百度查詢一下： extend和append的區(qū)別
            list.append(object) 向列表中添加一個(gè)對(duì)象object
            list.extend(sequence) 把一個(gè)序列seq的內(nèi)容添加到列表中
            1、使用append的時(shí)候，是將new_media看作一個(gè)對(duì)象，整體打包添加到music_media對(duì)象中。
            2、使用extend的時(shí)候，是將new_media看作一個(gè)序列，將這個(gè)序列和music_media序列合并，并放在其后面。
            result = []
            result.extend([1,2,3])
            print result
            result.append([4,5,6])
            print result
            result.extend([7,8,9])
            print result
            結(jié)果：
            [1, 2, 3]
            [1, 2, 3, [4, 5, 6]]
            [1, 2, 3, [4, 5, 6], 7, 8, 9]
            '''
            reducedFeatVec.extend(featVec[index+1:])
            # [index+1:]表示從跳過 index 的 index+1行，取接下來的數(shù)據(jù)
            # 收集結(jié)果值 index列為value的行【該行需要排除index列】
            retDataSet.append(reducedFeatVec)
    return retDataSet

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

def chooseBestFeatureToSplit(dataSet):
    """chooseBestFeatureToSplit(選擇最好的特征)

    Args:
        dataSet 數(shù)據(jù)集
    Returns:
        bestFeature 最優(yōu)的特征列
    """
    # 求第一行有多少列的 Feature, 最后一列是label列嘛
    numFeatures = len(dataSet[0]) - 1
    # 數(shù)據(jù)集的原始信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # 最優(yōu)的信息增益值, 和最優(yōu)的Featurn編號(hào)
    bestInfoGain, bestFeature = 0.0, -1
    # iterate over all the features
    for i in range(numFeatures):
        # create a list of all the examples of this feature
        # 獲取對(duì)應(yīng)的feature下的所有數(shù)據(jù)
        featList = [example[i] for example in dataSet]
        # get a set of unique values
        # 獲取剔重后的集合，使用set對(duì)list數(shù)據(jù)進(jìn)行去重
        uniqueVals = set(featList)
        # 創(chuàng)建一個(gè)臨時(shí)的信息熵
        newEntropy = 0.0
        # 遍歷某一列的value集合，計(jì)算該列的信息熵 
        # 遍歷當(dāng)前特征中的所有唯一屬性值，對(duì)每個(gè)唯一屬性值劃分一次數(shù)據(jù)集，計(jì)算數(shù)據(jù)集的新熵值，并對(duì)所有唯一特征值得到的熵求和。
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, i, value)
            # 計(jì)算概率
            prob = len(subDataSet)/float(len(dataSet))
            # 計(jì)算信息熵
            newEntropy += prob * calcShannonEnt(subDataSet)
        # gain[信息增益]: 劃分?jǐn)?shù)據(jù)集前后的信息變化， 獲取信息熵最大的值
        # 信息增益是熵的減少或者是數(shù)據(jù)無序度的減少。最后，比較所有特征中的信息增益，返回最好特征劃分的索引值。
        infoGain = baseEntropy - newEntropy
        print 'infoGain=', infoGain, 'bestFeature=', i, baseEntropy, newEntropy
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

問：上面的 newEntropy 為什么是根據(jù)子集計(jì)算的呢？
答：因?yàn)槲覀冊(cè)诟鶕?jù)一個(gè)特征計(jì)算香農(nóng)熵的時(shí)候，該特征的分類值是相同，這個(gè)特征這個(gè)分類的香農(nóng)熵為 0；
這就是為什么計(jì)算新的香農(nóng)熵的時(shí)候使用的是子集。

訓(xùn)練算法：構(gòu)造樹的數(shù)據(jù)結(jié)構(gòu)

創(chuàng)建樹的函數(shù)代碼如下：

def createTree(dataSet, labels):
    classList = [example[-1] for example in dataSet]
    # 如果數(shù)據(jù)集的最后一列的第一個(gè)值出現(xiàn)的次數(shù)=整個(gè)集合的數(shù)量，也就說只有一個(gè)類別，就只直接返回結(jié)果就行
    # 第一個(gè)停止條件：所有的類標(biāo)簽完全相同，則直接返回該類標(biāo)簽。
    # count() 函數(shù)是統(tǒng)計(jì)括號(hào)中的值在list中出現(xiàn)的次數(shù)
    if classList.count(classList[0]) == len(classList):
        return classList[0]
    # 如果數(shù)據(jù)集只有1列，那么最初出現(xiàn)label次數(shù)最多的一類，作為結(jié)果
    # 第二個(gè)停止條件：使用完了所有特征，仍然不能將數(shù)據(jù)集劃分成僅包含唯一類別的分組。
    if len(dataSet[0]) == 1:
        return majorityCnt(classList)

    # 選擇最優(yōu)的列，得到最優(yōu)列對(duì)應(yīng)的label含義
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 獲取label的名稱
    bestFeatLabel = labels[bestFeat]
    # 初始化myTree
    myTree = {bestFeatLabel: {}}
    # 注：labels列表是可變對(duì)象，在PYTHON函數(shù)中作為參數(shù)時(shí)傳址引用，能夠被全局修改
    # 所以這行代碼導(dǎo)致函數(shù)外的同名變量被刪除了元素，造成例句無法執(zhí)行，提示'no surfacing' is not in list
    del(labels[bestFeat])
    # 取出最優(yōu)列，然后它的branch做分類
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        # 求出剩余的標(biāo)簽label
        subLabels = labels[:]
        # 遍歷當(dāng)前選擇特征包含的所有屬性值，在每個(gè)數(shù)據(jù)集劃分上遞歸調(diào)用函數(shù)createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
        # print 'myTree', value, myTree
    return myTree

測(cè)試算法：使用決策樹執(zhí)行分類

def classify(inputTree, featLabels, testVec):
    """classify(給輸入的節(jié)點(diǎn)，進(jìn)行分類)

    Args:
        inputTree  決策樹模型
        featLabels Feature標(biāo)簽對(duì)應(yīng)的名稱
        testVec    測(cè)試輸入的數(shù)據(jù)
    Returns:
        classLabel 分類的結(jié)果值，需要映射label才能知道名稱
    """
    # 獲取tree的根節(jié)點(diǎn)對(duì)于的key值
    firstStr = inputTree.keys()[0]
    # 通過key得到根節(jié)點(diǎn)對(duì)應(yīng)的value
    secondDict = inputTree[firstStr]
    # 判斷根節(jié)點(diǎn)名稱獲取根節(jié)點(diǎn)在label中的先后順序，這樣就知道輸入的testVec怎么開始對(duì)照樹來做分類
    featIndex = featLabels.index(firstStr)
    # 測(cè)試數(shù)據(jù)，找到根節(jié)點(diǎn)對(duì)應(yīng)的label位置，也就知道從輸入的數(shù)據(jù)的第幾位來開始分類
    key = testVec[featIndex]
    valueOfFeat = secondDict[key]
    print '+++', firstStr, 'xxx', secondDict, '---', key, '>>>', valueOfFeat
    # 判斷分枝是否結(jié)束: 判斷valueOfFeat是否是dict類型
    if isinstance(valueOfFeat, dict):
        classLabel = classify(valueOfFeat, featLabels, testVec)
    else:
        classLabel = valueOfFeat
    return classLabel

使用算法：此步驟可以適用于任何監(jiān)督學(xué)習(xí)算法，而使用決策樹可以更好地理解數(shù)據(jù)的內(nèi)在含義。

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/3.DecisionTree/DecisionTree.py

項(xiàng)目案例2: 使用決策樹預(yù)測(cè)隱形眼鏡類型

項(xiàng)目概述

隱形眼鏡類型包括硬材質(zhì)、軟材質(zhì)以及不適合佩戴隱形眼鏡。我們需要使用決策樹預(yù)測(cè)患者需要佩戴的隱形眼鏡類型。

開發(fā)流程

1. 收集數(shù)據(jù): 提供的文本文件。
2. 解析數(shù)據(jù): 解析 tab 鍵分隔的數(shù)據(jù)行
3. 分析數(shù)據(jù): 快速檢查數(shù)據(jù)，確保正確地解析數(shù)據(jù)內(nèi)容，使用 createPlot() 函數(shù)繪制最終的樹形圖。
4. 訓(xùn)練算法: 使用 createTree() 函數(shù)。
5. 測(cè)試算法: 編寫測(cè)試函數(shù)驗(yàn)證決策樹可以正確分類給定的數(shù)據(jù)實(shí)例。
6. 使用算法: 存儲(chǔ)樹的數(shù)據(jù)結(jié)構(gòu)，以便下次使用時(shí)無需重新構(gòu)造樹。

收集數(shù)據(jù)：提供的文本文件

文本文件數(shù)據(jù)格式如下：

young   myope   no  reduced no lenses
pre myope   no  reduced no lenses
presbyopic  myope   no  reduced no lenses

解析數(shù)據(jù)：解析 tab 鍵分隔的數(shù)據(jù)行

lecses = [inst.strip().split('\t') for inst in fr.readlines()]
lensesLabels = ['age', 'prescript', 'astigmatic', 'tearRate']

分析數(shù)據(jù)：快速檢查數(shù)據(jù)，確保正確地解析數(shù)據(jù)內(nèi)容，使用 createPlot() 函數(shù)繪制最終的樹形圖。

>>> treePlotter.createPlot(lensesTree)

訓(xùn)練算法：使用 createTree() 函數(shù)

>>> lensesTree = trees.createTree(lenses, lensesLabels)
>>> lensesTree
{'tearRate': {'reduced': 'no lenses', 'normal': {'astigmatic':{'yes':
{'prescript':{'hyper':{'age':{'pre':'no lenses', 'presbyopic':
'no lenses', 'young':'hard'}}, 'myope':'hard'}}, 'no':{'age':{'pre':
'soft', 'presbyopic':{'prescript': {'hyper':'soft', 'myope':
'no lenses'}}, 'young':'soft'}}}}}

測(cè)試算法: 編寫測(cè)試函數(shù)驗(yàn)證決策樹可以正確分類給定的數(shù)據(jù)實(shí)例。

使用算法: 存儲(chǔ)樹的數(shù)據(jù)結(jié)構(gòu)，以便下次使用時(shí)無需重新構(gòu)造樹。

使用 pickle 模塊存儲(chǔ)決策樹

def storeTree(inputTree, filename):
    impory pickle
    fw = open(filename, 'w')
    pickle.dump(inputTree, fw)
    fw.close()

def grabTree(filename):
    import pickle
    fr = open(filename)
    return pickle.load(fr)

完整代碼地址: https://github.com/apachecn/MachineLearning/blob/master/src/python/3.DecisionTree/DecisionTree.py

• 作者：片刻 小瑤
• GitHub地址: https://github.com/apachecn/MachineLearning
• 版權(quán)聲明：歡迎轉(zhuǎn)載學(xué)習(xí) => 請(qǐng)標(biāo)注信息來源于 ApacheCN