機器學習實戰—決策樹

決策樹原理：通過一系列資料，最後給出分類結果，使用不熟悉的資料集合，從中提取出一系列規則。

決策樹的主要優勢在于資料形式非常容易了解

一、決策樹的建構：

構造決策樹時，第一個問題是目前資料集上哪個特征在劃分資料分類時起決定性作用。

資訊量的度量=資訊不确定性的多少，變量的不确定性越大，熵越大，把它搞清楚所需的資訊就越大。熵是資訊的期望值。

劃分資料集的大原則是：将無序的資料有序化，劃分資料集之前之後的資訊發生的變化成為資訊增益，那麼選擇的劃分特征就是在計算每個特征值劃分資料集所獲的資訊增益中最大的特征。

計算給定資料集的熵（即沒有進行特征劃分之前的香農熵）：

#計算資料集的資訊熵，以一種特征作為計算資訊熵的基準（一種特征中會有多少分類）
#函數輸入為資料集，輸出為該資訊的資訊熵數值
def calShannonEnt(dataSet):
    #擷取資料集執行個體個數
    numOsample = len(dataSet)
    #定義字典，存儲該資訊在資料集中出現的次數
    mesCounts = {}
    #周遊整個資料集，計算mesCounts中的value值
    for oneSample in dataSet:
        #如果字典中沒有對應特征值作為的key值，則在字典中加入該key值，并且初始化value值為0
        #擷取标簽值
        label = oneSample[-]
        if label not in mesCounts.keys():
            mesCounts[label] = 
        mesCounts[label] += 
    #計算香農熵
    #此處for循環周遊字典中的key值
    shannonEnt = 
    for key in mesCounts:
        pro = (float)(mesCounts[key])/numOsample
        shannonEnt -= pro*log(pro,)
    return shannonEnt

注：分類越多，不确定性越大，資訊熵就越大

二、劃分資料集

對每個特征劃分資料集的結果計算一次資訊熵，然後判斷按照哪個特征劃分資料集是最好的劃分方式。

按照給定特征劃分資料集：

#基于特定的特征資訊進行資料集劃分，對應于決策樹中由父節點到子節點劃分的過程
#輸入參數為需要劃分的資料集；此次的劃分特征索引；劃分特征的特定值
def splitDataSet(dataSet,splitFeatureIndex,spFeatrueValue):
    #定義傳回集合清單
    retDataSet = []
    #周遊資料集，抽取符合特征的資料向量
    for lineVec in dataSet:
        if lineVec[splitFeatureIndex] == spFeatrueValue:
            reduceDataVec = lineVec[:splitFeatureIndex]
            reduceDataVec.extend(lineVec[splitFeatureIndex+:])
            retDataSet.append(reduceDataVec)
    return retDataSet

注：傳回特征集中不含有判定特征一列，因為在下次劃分資料集時此特征值已經沒有資訊價值，在下次劃分資料集事件中此特征值資訊已處于已知狀态，無意義。

資訊增益：劃分後的資訊熵減去劃分前的資訊熵

選擇最好的資料集劃分方式：

#選擇最好的特征資訊劃分，輸入為整個資料集合（包含标簽列），輸出為最好劃分特征索引值
def chooseBestFeatureIndex(dataSet):
    # 先計算沒有劃分資料集之前的資訊熵，用來之後計算資訊增益
    # 資訊熵會在劃分資料集之後降低，因為劃分資料集使得資訊的不确定性減少
    #擷取資料集中特征數量
    numFeature = len(dataSet[]) - 
    noSplitScore = calShannonEnt(dataSet)
    #定義劃分資料集後的新的資訊熵和最優劃分特征索引
    gainScore = 
    bestFeatrueIndex = -
    #周遊整個資料集，對資料集進行劃分，并計算根據特定特征進行資料集劃分的資訊熵
    for i in range(numFeature):
        splitedScore = 
        #擷取整個資料集中第i列的特征值,valueList為清單
        valueList = [sample[i] for sample in dataSet]
        #確定特征值中的資料值唯一，将清單集合化
        equalValueSet = set(valueList)
        #周遊特征值唯一的集合，對相應下特征值劃分資料集計算資訊熵，并最後計算此特征劃分的資訊熵之和
        for value in equalValueSet:
            #擷取到該value值劃分的資料集，計算劃分到此資料集的機率
            subDataSet = splitDataSet(dataSet,i,value)
            pro = float(len(subDataSet))/len(dataSet)
            #劃分特征的資訊熵等于各個子集的資訊熵之和，calShannonEnt(subDataSet)函數計算的是一個集合的資訊熵
            splitedScore += pro*calShannonEnt(subDataSet)
        getDevScore = noSplitScore - splitedScore
        if(getDevScore > gainScore ):
            gainScore = getDevScore
            bestFeatrueIndex = i
    return bestFeatrueIndex

注：valueList = [sample[i] for sample in dataSet] 一句在大循環中，是以一次大循環中此句中的内層循環會循環完。

三、遞歸建構決策樹：

工作原理：得到原始資料集，然後基于最好的屬性劃分資料集，第一次劃分後，資料将被向下傳遞到樹分支的下個節點，遞歸結束的條件是：程式周遊完所有劃分集的屬性，或者每個分支下所有執行個體都具有相同的分類。

如果資料集已經處理了所有屬性，但是類标簽依然不是唯一的，此時需要根據投票政策決定該葉子節點。

#當特征值清單中值不唯一時采用投票機制傳回數量較多的值，傳入參數為特征值清單
def voteToDecision(classList):
    classCountSet = {}
    for one in classList:
        if one not in classCountSet.keys():
            classCountSet[one] = 
        classCountSet[one] += 
    sortedCountSet = sorted(classCountSet.items(),key=operator.itemgetter[],reverse=True)
    return sortedCountSet[][]

建立樹：

#建構樹
def createTree(dataSet,labels):
    classList = [sample[-] for sample in dataSet]
    #遞歸停止的兩個條件
    #1.最終屬性值清單類相同，直接傳回分類值
    if classList.count(classList[]) == len(classList):
        return classList[]
    #2.屬性都周遊的情況下，不能直接得出分類，則投票傳回分類标簽
    if len(dataSet[]) == :
        return voteToDecision(classList)
    #開始建立樹
    #擷取最佳劃分特征
    bestFIndex = chooseBestFeatureIndex(dataSet)
    bestLabel = labels[bestFIndex]
    # 樹的存儲結構為字典
    myTree = {bestLabel: {}}
    del(labels[bestFIndex])
    #擷取目前特征的唯一set集
    valueList = [sample[bestFIndex] for sample in dataSet]
    equalValueSet = set(valueList)
    for value in equalValueSet:
        newLabels = labels[:]
        #遞歸建立樹
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFIndex,value),newLabels)
    return myTree

注：遞歸建樹的兩個遞歸停止條件：1.所有的類标簽完全相同，直接傳回該類标簽

2.使用完了所有特征，仍然不能将資料集劃分為包含唯一類别的分組（此處使用投票政策），使用字典資料嵌套結構存儲整棵樹

四、使用Matplotlib注解繪制樹形圖

使用文本注解繪制節點：

# -*- coding: utf-8 -*-
import matplotlib.pyplot as plt

#定義文本框格式和箭頭格式
decisionNode = dict(boxstyle="sawtooth",fc="0.8")
leafNode = dict(boxstyle="round4",fc="0.8")
arrow_args = dict(arrowstyle="<-")

#使用文本注解繪制樹節點
def plotNode(nodeTxt,centerPt,parentPt,nodeType):
    #繪制文本注釋
    createPlot.ax1.annotate(nodeTxt,xy=parentPt,xycoords='axes fraction',xytext=centerPt,textcoords='axes fraction',\
                            va="center",ha="center",bbox=nodeType,arrowprops=arrow_args)
def plotMidText(cntrPt,parentPt,txtString):
    xMid = (parentPt[]-cntrPt[])/+cntrPt[]
    yMid = (parentPt[]-cntrPt[])/+cntrPt[]
    createPlot.ax1.text(xMid,yMid,txtString)

def plotTree(myTree,parentPt,nodeTxt):
    numLeafs = getNumLeaf(myTree)
    depth = getDepthTree(myTree)
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstStr = keyList[]
    cntrPt = (plotTree.xOff+(+float(numLeafs))//plotTree.totalW,plotTree.yOff)
    plotMidText(cntrPt,parentPt,nodeTxt)
    plotNode(firstStr,cntrPt,parentPt,decisionNode)
    secondDict = myTree[firstStr]
    plotTree.yOff = plotTree.yOff - /plotTree.totalD
    for key in secondDict.keys():
        if type(secondDict[key]).__name__ == 'dict':
            plotTree(secondDict[key],cntrPt,str(key))
        else:
            plotTree.xOff = plotTree.xOff  + /plotTree.totalW
            plotNode(secondDict[key],(plotTree.xOff,plotTree.yOff),cntrPt,leafNode)
            plotMidText((plotTree.xOff,plotTree.yOff),cntrPt,str(key))
    plotTree.yOff = plotTree.yOff + /plotTree.totalD
def createPlot(inTree):
    fig = plt.figure(,facecolor='white')
    fig.clf()
    axprops = dict(xticks=[],yticks=[])
    createPlot.ax1 = plt.subplot(, frameon=False,**axprops)
    # plotNode("decisionNode",(0.5,0.1),(0.1,0.5),decisionNode)
    # plotNode("leafNode",(0.8,0.1),(0.3,0.8),leafNode)
    plotTree.totalW = float(getNumLeaf(inTree))
    plotTree.totalD = float(getDepthTree(inTree))
    plotTree.xOff = -/plotTree.totalW
    plotTree.yOff = 
    plotTree(inTree,(,),'')
    plt.show()

五、構造注解樹：

擷取葉節點的數目和樹的層數：

#繪制決策樹時需要知道樹葉節點的個數和樹的深度
#擷取樹的葉子個數
def getNumLeaf(myTree):
    numLeaf = 
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstKey = keyList[]
    secDict = myTree[firstKey]
    #如果該節點為字典，此節點為判斷節點，需要向下遞歸調用，如果不是字典，則說明該節點是葉子節點
    for key in secDict.keys():
        if type(secDict[key]).__name__=='dict':
            numLeaf += getNumLeaf(secDict[key])
        else:
            #葉子節點數目累加
            numLeaf += 
    return numLeaf

#擷取樹的深度
def getDepthTree(myTree):
    maxDepth = 
    keyList = []
    for item in myTree.keys():
        keyList.append(item)
    firstKey = keyList[]
    secDict = myTree[firstKey]
    #如果該節點為字典，此節點為判斷節點，需要向下遞歸調用，如果不是字典，則說明該節點是葉子節點
    for key in secDict.keys():
        if type(secDict[key]).__name__=='dict':
            thisDepth = + getDepthTree(secDict[key])
        else:
            thisDepth = 
    if(thisDepth>maxDepth):
        maxDepth = thisDepth
    return maxDepth

繪制一顆完整的樹：

#建構樹
def createTree(dataSet,labels):
    classList = [sample[-] for sample in dataSet]
    #遞歸停止的兩個條件
    #1.最終屬性值清單類相同，直接傳回分類值
    if classList.count(classList[]) == len(classList):
        return classList[]
    #2.屬性都周遊的情況下，不能直接得出分類，則投票傳回分類标簽
    if len(dataSet[]) == :
        return voteToDecision(classList)
    #開始建立樹
    #擷取最佳劃分特征
    bestFIndex = chooseBestFeatureIndex(dataSet)
    bestLabel = labels[bestFIndex]
    # 樹的存儲結構為字典
    myTree = {bestLabel: {}}
    del(labels[bestFIndex])
    #擷取目前特征的唯一set集
    valueList = [sample[bestFIndex] for sample in dataSet]
    equalValueSet = set(valueList)
    for value in equalValueSet:
        newLabels = labels[:]
        #遞歸建立樹
        myTree[bestLabel][value] = createTree(splitDataSet(dataSet,bestFIndex,value),newLabels)
    return myTree

六、測試和存儲分類器

利用決策樹執行資料分類和存儲分類器

1.使用決策樹的分類函數：

#使用決策樹建立分類函數
#輸入決策樹，标簽向量，測試資料
def classify(inputTree,labelsVec,testVec):
    keyList = []
    for item in inputTree.keys():
        keyList.append(item)
    firstKey = keyList[]
    secDict = inputTree[firstKey]
    labelIndex = labelsVec.index(firstKey)
    # 周遊決策樹，将測試資料與決策樹上的節點進行比較
    # 如果是判斷節點，則遞歸調用，直到到葉子節點，得到測試資料的分類
    for key in secDict.keys():
        #比較測試資料與決策樹上的值，如果滿足要求，則遞歸分類
        if testVec[labelIndex] == key:
            if type(secDict[key]).__name__ == 'dict':
                classLabel = classify(secDict[key],labelsVec,testVec)
            else:
                classLabel = secDict[key]
    return classLabel

注：python2.x和python3.x在dict.keys()函數中的傳回值不同，python2.x此函數傳回key值清單，但是python3.x該函數傳回的是key值的疊代器。

2.狗雜決策樹很耗時，是以使用pickle子產品将決策樹對象存儲在檔案中，在需要使用時再次讀取出來即可。

使用pickle子產品存儲決策樹：

#将分類樹存儲在磁盤上
def store_tree(input_tree,filename):
    import pickle
    #以二進制寫方式打開檔案，否則會報錯
    fp = open(filename, 'wb')
    #将分類器以二進制形式存儲在檔案中
    pickle.dump(input_tree, fp)
    fp.close()

#引用以存儲好的樹結構
def grab_tree(filename):
    import pickle
    #以二進制讀方式打開檔案
    fp = open(filename,'rb')
    #加載檔案中存儲的分類器
    return pickle.load(fp)

示例：使用決策樹預測隐形眼鏡類型

注：隐形眼鏡資料集可在網上下載下傳，資料及檔案内容如下所示：

機器學習實戰—決策樹

資料特征标簽為：age,prescript,astigmatic,tearRate

隐形眼鏡類型包括：硬材質，軟材質，不适合佩戴隐形眼鏡

注：函數都儲存在一個.py檔案中，檔案中的函數就是上面所列出的所有函數，通過檔案中的main函數調用，main函數如下：

#決策樹分類算法：ID3
if __name__ == "__main__":
    # dataSet, labelVec = createDataSet()
    # print("dataSet:\n",dataSet)
    # print("labelVec:\n",labelVec)
    # shannonEnt = calShannonEnt(dataSet)
    # print("shannonEnt of label:",shannonEnt)
    # index = 
    # value = 
    # retDataSet = splitDataSet(dataSet,index,value)
    # print("splitedDataSet(base featrue_%d):\n"%(index),retDataSet)
    # bestFeatrueIndex = chooseBestFeatureIndex(dataSet)
    # print("bestFeatrueIndex:",bestFeatrueIndex)
    # myTree = createTree(dataSet,labelVec)
    # print("樹結構：",myTree)
    # myTree = retrive_tree()
    # print(myTree)
    # classLabel1= classify(myTree,labelVec,[,])
    # classLabel2 = classify(myTree, labelVec, [,])
    # print("classLabel_0:%s\nclassLabel_1:%s"%(classLabel1,classLabel2))
    # store_tree(myTree,'my_tree.txt')
    # myTree = grab_tree('my_tree.txt')
    # print("my_tree:",myTree)
    #打開檔案
    fp = open("lenses.txt")
    #逐行周遊檔案内容，每行資料去除空格後按tab鍵分割，獲得資料集
    splitDataList = [sample.strip().split('\t')  for sample in fp.readlines()]
    #建立标簽向量
    labelsVec = ['age','prescript','astigmatic','tearRate']
    #訓練算法（即根據訓練資料建立決策樹）
    my_tree = createTree(splitDataList,labelsVec)
    createPlot(my_tree)

注：注釋掉的代碼都是用來測試之前寫的函數的，此次的決策樹算法使用的時ID3算法，即特征數目在每次劃分資料集後減少。ID3算法無法直接處理數值型資料，是以有數值型資料時需要将連續數值離散化為若幹區間。

機器學習實戰—決策樹

繼續閱讀

簡單文檔分類——樸素貝葉斯算法樸素貝葉斯算法簡單文檔分類執行個體步驟總結樸素貝葉斯分類調用(sklearn)

【分類算法】什麼是分類算法定義分類與聚類分類過程方法

分類算法的評價名額

K-近鄰算法以及圖像分類應用

weka之NB算法

使用weka的select attribute

weka中分類器算法

在weka中內建自己的算法

【多變量線性回歸】學習記錄序思路實作終

申請評分模型拒絕推斷（RI）方法申請評分模型拒絕推斷（RI）方法

【人工智能行業大師訪談1】吳恩達采訪 Geoffery Hinton

【趨高機器視覺】機器視覺技術原了解析及解決方案

吳恩達 coursera ML 第七課總結+作業答案前言目錄正文模型表示作業答案

XGBoost Plotting API以及GBDT組合特征實踐 XGBoost Plotting API以及GBDT組合特征實踐

解碼器用于語義分割：資料依賴的解碼可以實作靈活的特征聚合

2021-2025年中國運動療法（KT）帶行業市場供需與戰略研究報告