決策樹-ID3算法

啥是決策樹：

決策樹是一種分類器，通過訓練資料建構決策樹可以對未知的類别的擁有相同屬性的資料進行分類。

決策樹的優點：

• 容易了解，友善可讀
• 效率高
• 訓練資料可以包含錯誤，因為決策樹學習是通過統計進行分類的，對錯誤有很好的健壯性

适用情況：

1. 執行個體是由“屬性-值”對表示的：執行個體是用一系列固定的屬性(例如，溫度)和它們的值(例如，熱)來描述的。在最簡單的決策樹學習中，每一個屬性取少數的離散的值(例如，熱、中、冷)。這裡要求屬性值是離散的。如果是連續的屬性值，可通過将其劃分到離散的箱中對其進行離散化處理，每個箱都指定有對應的上限和下限。
2. 目标函數具有離散的輸出值：決策樹給每個執行個體賦予一個布爾型的分類，例如在銷售某件無片當中有售完或沒有售完兩種情況。如果訓練執行個體可表示為屬性值對，同時目标分類具有離散的輸出值(如，售完和沒有售完)，那麼這樣的問題就特别适合用決策樹來進行學習。
3. 可能需要析取的描述，決策樹可以表示析取表達式。

例子：建立酒吧的評估問題

（手動模拟決策樹建樹過程）

這個例子是關于某個啤酒廠的，它需要對在某些位置是否适合建新酒吧進行評估，也就是說，對于某個指定位置，是應該建新酒吧，還是應該将其劃為不适合?

為了對新位置進行評估，需要對有關該位置坐落區域的諸多屬性進行調查，這些屬性描述包括：該位置是一個城市呢還是一個較大的城鎮，該區域内是否有大學，居住區屬于什麼類型。如果需要，還包括附近是否有工業區(公園)，以及該區域内公共交通的品質和學校的數量。每個屬性都有多個取值，例如，城市屬性取值為{Y－是，N－否}，居住區類型屬性取值為{M－中等，S－小型，N－無，L－大型}, 交通條件取值為{A－一般，P－差，G－好}。

這個啤酒廠擁有一個資料庫，其中包括現有酒吧及其相應屬性值。下表列出了該資料庫的一個子集。每個現有酒吧／飯館都有一個類别, 其中，+(正)表示該位置被認為是成功的，－(負)表示該位置尚可，但他們已不希望将來再進行類似的投資了。該啤酒廠希望利用這個資料庫找到一組規則，以便能夠幫助他們決定某個新位置的潛在可用性。

(1)IF交通條件=差 AND有無工業區=無THEN不購買該位置(因為例子{2，4，10，13，18都是負的) 。

(2)IF交通條件=好 THEN購買該位置(因為例子{7，12，16，19，20}都是正的) 。

沿着從根結點到葉結點的每條路徑就會得到相應的規則。路徑上的每個結點都表示了一個屬性，而該屬性對應于路徑上的那個分支就給出了相應的屬性值。

得到的決策樹如下

ID3算法：

基本的ID3算法通過自頂向下構造決策樹來進行學習。那麼構造一顆決策樹要先選擇根節點，怎麼選呢？

這裡要用到資訊增益的熵計算公式，比較啰嗦，後面記錄。

假如現在通過熵增益計算公式得到了一個根節點，然後為根結點屬性的每個可能值産生一個分支，并把訓練例排列到适當的分支(也就是，訓練例的該屬性值對應的分支)之下。然後重複整個過程，用每個分支結點關聯的訓練例來選取在該點被測試的最佳屬性。

例如，在上面的圖中，例子{1，3，6，8，11，15，17}的交通條件屬性都取值為A(一般)。

交通條件屬性有三個取值{一般－A，差－P，好－G}，是以在根結點下就有三個分支，相應地也建立了三個新結點。然後，按照該屬性的相應取值将這些例子分别賦給這三個新結點，如例子{2，4，5，9，10，13，14，18}的交通條件屬性都取值為P。

構造出決策樹後，可以直覺的看出。交通條件好的地方适合當酒吧（交通條件為G）

上面的說的熵增益和根節點的選擇方法如下：

熵(entropy)，用來描述一個系統的混亂程度

1.隻有兩種資訊的熵

假設一個系統S含有兩種資訊, 其中p1表示第一種資訊在S中的比例, p2表示第二種資訊在S中的比例, 那麼系統S相對于這兩種資訊分類的熵為:

Entropy(S)=−p1log2p1−p2log2p2 (1)

在有關熵的所有計算中我們定義0log0為0。

假設S是一個有14個訓練例的集合，它包括9個正例和5個反例 ,我們采用記号[ 9+，5-]來概括這樣的訓練例集。那麼S相對于這個正反例兩種資訊分類的熵為：

Entropy ([9+，5-] )= - (9／14)log2(9／14) - (5／14)log2(5／14) =0．940 (2)

如果S的所有成員屬于同一類，那麼S的熵為0。例如，如果所有的成員都是第一種, p1 =1，那麼p2 就是0，Entropy (S)= -1•log2(1) - 0•log2 (0)= -1•0-0•log2(0)=0。當集合中兩種資訊的數量相等時，熵為l。當集合中兩種資訊的數量不等時，熵介于0和1之間。

2.具有多種資訊的系統的熵

如果目标屬性具有n個不同的資訊，那麼S相對于n種資訊的分類的熵定義為：

Entropy(S)=∑ni=1(−pilog2pi) （3）

其中，pi是S中屬于類别i的比例

3.系統分類後的熵

設原系統S的熵為Entropy(S),又系統S具有屬性A,我們用Values(A)表示屬性A所有可能值的集合，Sv是S中屬性A的值為v的集合

∑v∈Values(A)|Sv||S|Entropy(Sv)

計算熵的例子：

根據天氣判斷“是否适合打網球”。

設S是上表中訓練例的集合,包括14個訓練例,其中9個為正例,5個為反例,表示為[9+，5-], 相對于正反例, S的熵Entropy(S) =0．940(見(2)) 。現考慮S的屬性Wind,它有兩個值Weak和Strong, 14個訓練例中具有Weak 值的有6個正例, 2個反例, ,表示為[6+，2-];同時, 14個訓練例中具有Strong 值的有3個正例, 3個反例, ,表示為[3+，3-],按照屬性Wind分類14個訓練例得到的分類後的熵計算如下。

由此可見, 使用屬性Wind屬性分類後, S的熵大大降低。我們再考慮S的屬性Humidity,按其分類14個訓練例得到的分類後的熵計算如下。

資訊增益最佳分類屬性：

一個屬性A相對訓練例集合S的資訊增益Gain(S，A)被定義為：

等式(4)的第一項就是原集合S的熵，第二項是用A分類S後熵的期望值。這個第二項描述的期望熵就是每個子集的熵的權重和，權值為屬于Sv 的樣例占原始樣例S的比例，是以Gain(S，A)是由于知道屬性A的值而導緻的期望熵減少

相對于目标分類(即是否适合打網球)，Humidity比Wind有更大的資訊增益。這裡，E代表熵，S代表原始樣例集合。已知初始集合S有9個正例和5個反例，即[9+，5－]。用Humidity分類這些樣例産生了子集[ 3+，4－ ] (Humidity=High)和[6+，1－] (Humidity=Normal)。這種分類的資訊增益為0.151，而對于屬性Wind增益僅為0.048

使用ID3算法完整實作”是否适合打網球”

第一步，建立決策樹的最頂端結點

ID3算法計算每一個候選屬性(也就是Outlook、Temperature、Humidity和Wind)的資訊增益，然後選擇資訊增益最高的一個。

所有四個屬性的資訊增益為：

Gain(S，Outlook)=0．246

Gain(S，Humidity)=0．151

Gain(S，Wind)=0．048

Gain(S，Temperature)=0．029

第二步，建立分枝

Outlook被選作根結點的決策屬性，并為它的每一個可能值(也就是Sunny,Overcast和Rain)在根結點下建立分支。

注意到每一個Outlook =Overcast的樣例都是PlayTennis的正例，是以，樹的這個結點成為一個葉子結點，它對目标屬性的分類是PlayTennis=Yes。相反，對應Outlook =Sunny和Outlook=Rain的後繼結點還有非0的熵，是以決策樹會在這些結點下進一步展開。

如圖

Ssunny={D1,D2,D8,D9,D11}

Gain(Ssunny,Humidity)=0.970－(3／5)0.0－(2／5)0.0=0.970

Gain(Ssunny,Temperature=0.970－(2／5)0.0－(2／5)1.0－(1／5)0.0=0.570

Gain(Ssunny,Wind)=0.970－(2／5)1.0－(3／5)0.918=0.019

對于非終端的後繼結點，再重複前面的過程選擇一個新的屬性來分割訓練樣例，這一次僅使用與這個結點關聯的訓練樣例。已經被樹的較高結點測試的屬性被排除在外，以便任何給定的屬性在樹的任意路徑上最多僅出現一次。對于每一個新的葉子結點繼續這個過程，直到滿足以下兩個條件中的任一個：(1)所有的屬性已經被這條路徑包括；(2)與這個結點關聯的所有訓練樣例都具有相同的目标屬性值(也就是它們的熵為0)。

最後的決策樹如下圖

決策樹算法的問題：

上面的例子描述的算法增長樹的每一個分支的深度，直到恰好能對訓練樣例完美地分類，但是當資料中有噪聲或訓練樣例的數量太少以至于不能産生目标函數的有代表性的采樣時，這個政策便會遇到困難。在以上任一種情況發生時，這個簡單的算法産生的樹會過度拟合訓練樣例。

過度拟合的通俗意思就是該算法非常完美的滿足了訓練例，最後使得該算法隻對訓練例中的資料有非常精确的結果，由于訓練例的局限性，對未知資料預測造成了很大的偏差。

例如，在上面打網球的例子當中增加一條訓練正例，但卻被誤标示為反例

< Outlook=Sunny，Temperature=Hot，Humidity=Normal，Wind=Strong，PlayTennis=No>

增加這個不正确的樣例導緻ID3建立一個更複雜的樹，當然，新的決策樹會完美地拟合訓練樣例集，然而，由于新的決策結點隻是拟合訓練樣例中噪聲的結果。

有幾種途徑可被用來避免決策樹學習中的過度拟合

1. 預剪枝，在ID3算法完美分類訓練資料之前就停止樹增長（比如樹達到了一定高度）
2. 後剪枝，即允許樹過度拟合資料，然後對這個樹進行後修剪。

通常後剪枝比預剪枝更加常用

後剪枝的方法有

1. Reduced-Error Pruning(REP,錯誤率降低剪枝）
2. Pesimistic-Error Pruning(PEP,悲觀錯誤剪枝）
3. Cost-Complexity Pruning（CCP，代價複雜度剪枝)
4. EBP(Error-Based Pruning)（基于錯誤的剪枝）

python代碼：

（來自機器學習實戰那本書）

from math import log
import operator

def createDataSet():#建立資料集
    dataSet= [[,,'yes'],#1表示是,0表示否
    [,,'yes'],
    [,,'no'],
    [,,'no'],
    [,,'no']
    ]
    labels = ['no surfaceing','flippers']#資料的标簽
    return dataSet , labels

def calcShannonEnt(dataSet):#計算熵
    numEntries = len(dataSet)
    labelCounts = {}
    for featVec in dataSet:
        currentLabel = featVec[-]#按照最後一列，即yes和no來計算數目
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=
        labelCounts[currentLabel]+=
        shannonEnt = 
        for key in labelCounts:
            prob = float(labelCounts[key])/numEntries
            shannonEnt -= prob * log(prob,)
    return shannonEnt


def splitDataSet(dataSet,axis,value):#資料，資料特征，特征值
    retDataSet = []
    for featVec in dataSet:
        if featVec[axis] == value:
            reduceFeatVec = featVec[:axis]#剔除第axis列屬性
            reduceFeatVec.extend(featVec[axis+:])
            retDataSet.append(reduceFeatVec)
    return retDataSet

def chooseBestFeatureToSplit(dataSet):#計算資料當中熵增益最大的特征
    numFeatures = len(dataSet[])-
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 
    bestFeaturn = -
    for i in range(numFeatures):#select column
        featList = [example[i] for example in dataSet]
        uniqueVals = set(featList)
        newEntropy = 
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet,i,value)
            prob = len(subDataSet)/float(len(dataSet))
            newEntropy += prob*calcShannonEnt(subDataSet)
            infoGain = baseEntropy-newEntropy
            if (infoGain > bestInfoGain):
                bestInfoGain = infoGain
                bestFeaturn = i
    return bestFeaturn

def majorityCnt(classList):#傳回出現次數最多的分類名稱
    classCount={}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote]=
        classCount[vote] += 
        sortedClassCount = sorted(classCount.iteritems(),key=operator.itemgetter(),reverse=True)
    return sortedClassCount[][]

def createTree(dataSet,labels):#建樹
    classList = [example[-] for example in dataSet]#擷取所有資料行當中的yes和no
    if classList.count(classList[]) == len(classList):#如果隻有yes或者隻有no，說明分類完成
        return classList[]
    if len(dataSet[])==:#資料表當中隻剩下一列
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)#選擇熵增益最大的做根節點
    bestFeatLabel = labels[bestFeat]#擷取熵增益最大的标簽
    myTree = {bestFeatLabel:{}}#建樹
    del(labels[bestFeat])#删除找到的熵增益最大的标簽的屬性列
    featValues = [example[bestFeat] for example in dataSet]#擷取最大熵增益标簽的所有屬性（0和1）
    uniqueVals = set(featValues)
    for value in uniqueVals:#按照根節點的标簽的屬性分類建樹（也就是按照0和1屬性分枝出左右子樹）
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet,bestFeat,value),subLabels)
    return myTree

myDat,myLab=createDataSet()
#print (myDat)
print(createTree(myDat,myLab))
           

使用決策樹來執行分類

def classify(inputTree,featLabels,testVec):#傳入的資料為dict類型
    firstSides = list(inputTree.keys())
    firstStr = firstSides[]#找到第一個标簽
    ##這裡表明了python3和python2版本的差别，上述兩行代碼在2.7中為：firstStr = inputTree.key()[0] 
    secondDict = inputTree[firstStr]#建一個以目前找到标簽為根的樹，用來周遊節點使用
    featIndex = featLabels.index(firstStr)#找到在label中firstStr的下标
    for key in secondDict.keys():
        if testVec[featIndex] == key:
            if type(secondDict[key]) == dict:
                classLabel = classify(secondDict[key],featLabels,testVec)
            else:
                classLabel = secondDict[key]
    return classLabel   #比較測試資料中的值和樹上的值，最後得到節點


myDat,myLab=createDataSet()
myLab1=myLab[:]
myTree=createTree(myDat,myLab)
print(classify(myTree,myLab1,[,]))
           

to be continue~