本周學(xué)了一種非要重要也非常基礎(chǔ)的核心分類(lèi)算法——決策樹(shù)嗅榕。下面對(duì)決策樹(shù)算法做一個(gè)總結(jié)：）

決策樹(shù)（decision tree）是一種基本的分類(lèi)與回歸方法。這里主要總結(jié)用于分類(lèi)的決策樹(shù)吵聪。決策樹(shù)模型呈樹(shù)形結(jié)構(gòu)凌那，在分類(lèi)問(wèn)題中，表示基于特征對(duì)實(shí)例進(jìn)行分類(lèi)的過(guò)程吟逝。它可以認(rèn)為是if-then規(guī)則的集合帽蝶，也可以認(rèn)為是定義在特征空間與類(lèi)空間上的條件概率分布。主要優(yōu)點(diǎn)是模型具有可讀性块攒，分類(lèi)速度快励稳。學(xué)習(xí)時(shí)，利用訓(xùn)練數(shù)據(jù)囱井，根據(jù)損失函數(shù)最小化的原則建立決策樹(shù)驹尼。預(yù)測(cè)時(shí)，對(duì)新的數(shù)據(jù)庞呕，利用決策樹(shù)模型進(jìn)行分類(lèi)新翎。決策樹(shù)學(xué)習(xí)通常包括3個(gè)步驟：特征選擇、決策樹(shù)的生成和決策的修建住练。生成決策樹(shù)后就可以根據(jù)它來(lái)進(jìn)行分類(lèi)了地啰。這些決策樹(shù)的思想主要來(lái)源于由Quinlan在1986年提出的ID3算法和1993年提出的C4.5算法，以及由Breiman等人在1984年提出的CART算法讲逛。（其實(shí)這幾種算法的主要區(qū)別就在于采用什么方式選擇最合適的屬性作為分裂準(zhǔn)則亏吝，也叫屬性選擇度量），這里介紹的是基礎(chǔ)的ID3算法盏混，采用的是信息增益最大的屬性進(jìn)行分裂蔚鸥。

選擇根屬性惜论，就好比下面一堆數(shù)據(jù)，構(gòu)成的決策樹(shù)

決策樹(shù)

信息熵

項(xiàng)目案例和實(shí)際代碼編寫(xiě)

根據(jù)以下 2 個(gè)特征，將動(dòng)物分成兩類(lèi)：魚(yú)類(lèi)和非魚(yú)類(lèi)命迈。
特征：
不浮出水面是否可以生存
是否有腳蹼

1.選擇根屬性（也就是分裂的屬性）

首先贩绕，我們需要把數(shù)據(jù)讀入到一個(gè)數(shù)據(jù)集中去：

from math import log

original_labels = []

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

其實(shí)，根據(jù)我們上面的算法思路計(jì)算數(shù)據(jù)集的整體信息熵壶愤，這里可以進(jìn)行測(cè)試一下

def calcShannonEnt(dataSet):
    # 求list的長(zhǎng)度淑倾，表示計(jì)算參與訓(xùn)練的數(shù)據(jù)量
    numEntries = len(dataSet)
    # 計(jì)算分類(lèi)標(biāo)簽label出現(xiàn)的次數(shù)
    labelCounts = {}

    for featVec in dataSet:
        # 每行的最后一列元素就是分類(lèi)標(biāo)簽
        currentLabel = featVec[-1]
        # 更新標(biāo)簽的計(jì)數(shù)
        labelCounts[currentLabel] = labelCounts.get(currentLabel,0)+1

    # 根據(jù)標(biāo)簽的占比求出香農(nóng)熵
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        # 計(jì)算香農(nóng)熵，以2為底征椒，求對(duì)數(shù)
        shannonEnt -= prob*log(prob,2)
    return shannonEnt

dataSet,labels = createDataSet()
shannonEnt = calcShannonEnt(dataSet)
print("shannonEnt = %s"%shannonEnt)

得到：shannonEnt = 0.9709505944546686娇哆，也就是這個(gè)數(shù)據(jù)集的整體信息熵為0.97*****
獲取數(shù)據(jù)子集，也就是某一屬性等于某一個(gè)具體值時(shí)的數(shù)據(jù)子集勃救，計(jì)算某一屬性的信息熵時(shí)需要用到：

'''將dataSet數(shù)據(jù)集分開(kāi)碍讨，遍歷dataSet的行，當(dāng)index列的值等于value時(shí)蒙秒，把這行數(shù)據(jù)劃分進(jìn)我們新的數(shù)據(jù)集中勃黍，同時(shí)要把index列的元素去掉'''
def splitDataSet(dataSet,index,value):
    retDataSet = []
    for featVect in dataSet:
        if(featVect[index]==value):
            reducedFeatVect = featVect[:index]
            reducedFeatVect.extend(featVect[index+1:]) # 其實(shí)這里就是去掉了index列的數(shù)據(jù)，并把這一行單獨(dú)留下來(lái)放到新的數(shù)據(jù)集中去了
            retDataSet.append(reducedFeatVect)
            #retDataSet.append(featVect) # 其實(shí)這里這樣就可以了税肪，沒(méi)必要非要把比較的index列去掉
    return retDataSet

temp = splitDataSet(dataSet,2,'yes')
print(temp)

接下來(lái)溉躲，分別計(jì)算各個(gè)屬性的信息熵榜田，選擇分裂屬性

'''選擇最好的數(shù)據(jù)劃分方式劃分?jǐn)?shù)據(jù)'''
def chooseBestFeatureToSplit(dataSet):
    # 一共有多少列屬性益兄，最后一列是標(biāo)簽列所以要減掉
    numberOfFeatures = len(dataSet[0])-1
    # 數(shù)據(jù)集的原始信息熵
    baseEntropy = calcShannonEnt(dataSet)
    # 初始化信息增益和最佳的屬性列
    bestInfoGain,bestFeature = 0.0,-1
    # 遍歷所有的屬性
    for i in range(numberOfFeatures):
        # 獲取該屬性的所有數(shù)據(jù)
        featureList = [example[i] for example in dataSet] # 這個(gè)寫(xiě)法是遍歷數(shù)據(jù)集中的每一行，把其中的第i個(gè)數(shù)據(jù)取出來(lái)組合成一個(gè)列表
        featureList = set(featureList) # 屬性值去重
        newEntropy = 0.0 # 新的臨時(shí)的信息熵
        # 根據(jù)屬性值進(jìn)行分割數(shù)據(jù)集
        for value in featureList:
            subData = splitDataSet(dataSet,i,value)
            prob = len(subData)/float(len(dataSet)) # 計(jì)算該屬性值等于value的數(shù)據(jù)在總數(shù)據(jù)集中的比例
            newEntropy += prob*calcShannonEnt(subData) # 計(jì)算新的信息熵
        infoGain = baseEntropy - newEntropy # 計(jì)算出該屬性的信息增益
        if(infoGain>bestInfoGain): # 如果信息增益變大了箭券，就把當(dāng)前屬性作為最好的劃分?jǐn)?shù)據(jù)净捅，繼續(xù)遍歷
            bestInfoGain = infoGain
            bestFeature = i
    # 返回最好的劃分屬性
    return bestFeature

bestF = chooseBestFeatureToSplit(dataSet)
print("The best feature is %s"%bestF)

2.構(gòu)造決策樹(shù)

有了最好的分裂屬性后，我們就可以構(gòu)建決策樹(shù)了：

# 創(chuàng)建決策樹(shù)
def createTree(dataSet,labels):
    classList = [example[-1] for example in dataSet] # 類(lèi)別列表辩块，這是一種快速獲取某列屬性值的方法
    # 第一個(gè)停止條件：如果所有標(biāo)簽分類(lèi)都相同則返回
    if classList.count(classList[0])==len(classList):
        return classList[0]
    # 第二個(gè)停止條件：如果數(shù)據(jù)集只有一列蛔六，那么最初出現(xiàn)label最多的一類(lèi)作為結(jié)果返回
    if(len(dataSet[0])==1):
        return majorityCnt(classList)
    # 選擇最優(yōu)的分裂的類(lèi)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    # 獲取label的名稱(chēng)
    bestFeatLabel = labels[bestFeat]
    # 初始化樹(shù),樹(shù)采用字典存儲(chǔ)
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat]) # 從屬性列表中刪除這個(gè)屬性，因?yàn)橐呀?jīng)分類(lèi)了废亭，接下來(lái)要從剩下的這些屬性中進(jìn)行子樹(shù)的構(gòu)建了
    # 取出最優(yōu)列国章，然后他的分支做分類(lèi)，如“年齡”屬性取出后豆村，剩下的子樹(shù)就是>35歲的和<=35歲的
    featValues = [example[bestFeat] for example in dataSet]
    uniqueValues = set(featValues) # 去重
    for value in uniqueValues:
        # 剩余的標(biāo)簽label
        subLabels = labels[:]
        # 遍歷當(dāng)前選擇特征包含的所有屬性值液兽，在每個(gè)數(shù)據(jù)集劃分上遞歸調(diào)用函數(shù)createTree()
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

注意，決策樹(shù)的物理存儲(chǔ)就是一個(gè)字典掌动，以鍵值對(duì)形式存儲(chǔ)數(shù)據(jù)四啰。

3.使用決策樹(shù)進(jìn)行分類(lèi)

分類(lèi)函數(shù)

# 使用決策樹(shù)進(jìn)行分類(lèi)
def classify(inputTree,featLabels,testVec):
    # 獲取樹(shù)根節(jié)點(diǎn)對(duì)于Key的值
    firstStr = list(inputTree.keys())[0]
    # 獲取對(duì)應(yīng)的值宁玫，其實(shí)也是一個(gè)字典
    secondDict = inputTree[firstStr]
    # 獲取根節(jié)點(diǎn)對(duì)應(yīng)在標(biāo)簽中的序號(hào)
    featIndex = featLabels.index(firstStr)
    # 獲取測(cè)試數(shù)據(jù)集中該標(biāo)簽的值
    key = testVec[featIndex]
    # 獲取值，看看有沒(méi)有子樹(shù)
    valueOfFeat = secondDict[key]
    print("+++"+firstStr+"xxx"+secondDict+"---"+key+">>>"+valueOfFeat)
    # 如果還有子樹(shù)就繼續(xù)往下分類(lèi)
    if(isinstance(valueOfFeat,dict)):
        classLabel = classify(valueOfFeat,featLabels,testVec)
    # 否則就把標(biāo)簽值作為分類(lèi)標(biāo)簽
    else:
        classLabel = valueOfFeat
    return classLabel

4.使用決策樹(shù)進(jìn)行分類(lèi)

dataSet,labels = createDataSet()
for label in labels:
    # 這里用到original_labels就是因?yàn)閘abels調(diào)用label方法后會(huì)被刪除柑晒，無(wú)法在classify方法中使用欧瘪，因此需要另外使用一個(gè)變量保存原始label
    original_labels.append(label) 
inputTree = createTree(dataSet,labels)
print("決策樹(shù)------->%s"%inputTree)
testVec = [0,0]
lb = classify(inputTree,original_labels,testVec)
print("lb=%s"%lb)

我們可以看到最終輸出為：

The best feature is 0
決策樹(shù)------->{'no surfacing': {0: 'no', 1: {'flippers': {0: 'no', 1: 'yes'}}}}
lb=no

可以看到?jīng)Q策樹(shù)，最后就是一個(gè)字典匙赞。最好的分類(lèi)就是屬性'no surfacing'佛掖。[0,0]這個(gè)測(cè)試向量得到的分類(lèi)是no，這個(gè)也符合我們的常識(shí)罚屋，一個(gè)動(dòng)物既不能在水下生存也沒(méi)有腳蹼苦囱，那就肯定不是魚(yú)類(lèi)了。