機器學習方法總結（五）：決策樹

決策樹

1.決策樹的模型和學習政策

    定義：分類決策樹模型是一種描述對執行個體進行分類的樹形結構，由節點和有向邊組成，建立時由由不同的特征決定每層的分類依據，分類時，從根節點對每個執行個體進行測試并配置設定到子節點，直到分類到葉節點。

    學習政策：決策樹的學習本質上是從訓練資料集中歸納出一組分類規則，最後得到一個與訓練資料集沖突較小同時泛化能力較強的決策樹；從另一角度，決策樹是由訓練資料集估計條件機率模型，基于特征空間劃分的類的條件機率模型有無窮多，而選擇出來的條件機率模型不僅要對訓練資料有很好的拟合同時要對未知資料有很好的預測。

    下文會介紹幾種常見決策樹：ID3、C4.5、CART。

2.特征選擇方法

•  資訊增益準則：

    熵：表示随機變量不确定性的度量，熵越大，随機變量的不确定性就越大，随機變量X的熵定義為：

    條件熵：H(Y|X)表示在已知随機變量X的條件下随機變量Y的不确定性，定義為：

    當熵和條件熵由資料估計得到時，它們分别稱為經驗熵和經驗條件熵。

    資訊增益:特征A對訓練資料集D的資訊增益g(D,A)，定義為集合D的經驗熵H(D)與特征A給定條件D的經驗條件熵H(D|A)之差。

  根據資訊增益準則的特征選擇方法是:對于訓練資料集D,計算每個特征的資訊增益，并比較它們的大小，最後選擇資訊增益最大的特征。

• 資訊增益比準則

    特征A對訓練資料集D的資訊增益比

,由資訊增益除以特征的熵組成。這是為了矯正一個問題，因為基于資訊增益趨向于選擇取值更多的特征。

• GINI系數準則

    在分類問題中，假設有K個類，樣本點屬于第k個類的機率為pk，則機率分布的基尼指數定義為：

    如果樣本集合D根據特征A是否取某一可能值a被分割成D1和D2兩部分，則特征A條件下，集合D的Gini系數為：

    這樣，Gini系數越大，集合的不确定性就和越大，與熵類似。

3.決策樹的生成方法 

• ID3算法：核心是在決策樹各個節點上應用資訊增益準則選擇特征，遞歸建構決策樹。

    輸入：訓練資料集D，特征集A，門檻值e；

    輸出：決策樹T

1. 若D中所有執行個體屬于同一類，則T為單節點樹。
2. 計算A中所有特征對D的資訊增益，選擇資訊增益最大的特征Ag。
3. 如果特征Ag的資訊增益小于e，則置T為單節點樹，并将D中執行個體數最多的類别最為節點類别。
4. 否則，對Ag的每一個可能取值進行分割，建構子節點。
5. 對每個子節點遞歸調用上述方法。

• C4.5的生成算法

    C4.5算法與ID3算法相似，隻是劃分标準變為了資訊增益率。

• CART算法

    分類回歸樹（classification and regression tree）既可作分類也可做回歸，主要由兩部分組成：(1).決策樹生成：基于訓練資料集産生決策樹，生成的決策樹要盡可能大；(2).決策樹剪枝：用驗證資料集對已生成的樹進行剪枝并選擇最優子樹，這時用損失函數最小作為剪枝的标準。這裡提到了剪枝，是以我們需要先講一下樹的剪枝。

    樹的剪枝是為了防止前兩種算法造成了枝葉過多發生過拟合的問題，決策樹的剪枝通常通過極小化整體的損失函數來實作，設樹的節點為|T|,t是樹T的葉節點，該葉節點有Nt個樣本點，其中k類的樣本點有Ntk個，Ht(T)為葉節點t上面的經驗熵，a為參數，則損失函數可定義為：

  右式第一項表示了模型對訓練資料的預測誤差，|T|表示模型複雜度，參數a大于等于零控制着雙方的影響度，而剪枝的過程就是：遞歸向上回縮，每次計算損失函數，直到損失函數不再減小為止。

    CART樹的生成對回歸樹采取平方誤差最小的準則，對分類樹采取基尼系數最小化準則，尤其是在回歸樹的建立上不好了解，我會詳細講解：

1. 回歸樹的生成

    (1).在訓練資料集所在的輸入空間中，遞歸地将每個區域劃分成兩個子區域并決定每個區域的輸出值，那這個區域是由某個特征（切分變量j）和特征的一個值（切分點s）決定的，即分為了下列兩個區域：

    (2).那這個切分變量和切分點應該如何求呢？那自然是要讓損失函數最小，我們剛剛說了損失函數是平方誤差，假設R1區域的實際值是c1，R2區域的實際值為c2，我們就能得到：

    (3).c1和c2實際上是R1和R2區域的均值，是以我們隻需要固定j，周遊s，求的c1和c2，上式就可求解，繼續上述步驟産生的回歸樹通常稱為最小二乘樹。

    2. 分類樹的生成類似于上文中前兩個算法，隻是基于基尼系數選擇特征，不再贅述。

• CART剪枝

    思路：首先從生成算法産生的決策樹T的底端開始不斷剪枝，直到T的根節點形成的一個子樹序列{T0,T1......Tn};然後通過交叉驗證法在獨立的驗證資料集上對子樹序列進行測試，選出最優子樹。

    輸入：決策樹T；

    輸出：最優決策樹Ta；

    (1).設k=0，T=T0，a=正無窮

    (2).自下而上計算各内部節點t的C(Tt)、|Tt|以及當C(t)和C(Tt)相等時a的取值，并把它指派給a,第一次算出的樹肯定是根節點。

    (3).根據這個辦法會得到不同的a對應不同的樹序列，再交由交叉驗證得到最好的子樹。

4.實作

#這是脫離庫實作ID3算法
from math import log
import operator
def calcShannonEnt(dataSet):
    '計算香農熵'
    
    # 資料集個數
    numEntries = len(dataSet)
    # 标簽集合
    labelCounts = {}
    for featVec in dataSet:     # 行周遊資料集
        # 目前标簽
        currentLabel = featVec[-1]
        # 加入标簽集合
        if currentLabel not in labelCounts.keys(): labelCounts[currentLabel] = 0
        labelCounts[currentLabel] += 1
    # 計算目前資料集的香農熵并傳回
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob * log(prob,2)
        
    return shannonEnt
# ==============================================
# 輸入：
#        dataSet: 訓練集檔案名(含路徑)
#        axis: 用于劃分的特征的列數
#        value: 劃分值
# 輸出：
#        retDataSet: 劃分後的子清單
# ==============================================
def splitDataSet(dataSet, axis, value):
    '資料集劃分'
    
    # 劃分結果
    retDataSet = []
    for featVec in dataSet:     # 逐行周遊資料集
        if featVec[axis] == value:      # 如果目标特征值等于value
            # 抽取掉資料集中的目标特征值列
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            # 将抽取後的資料加入到劃分結果清單中
            retDataSet.append(reducedFeatVec)
            
    return retDataSet
def chooseBestFeatureToSplit(dataSet):
    '選擇最佳劃分方案'
    
    # 特征個數
    numFeatures = len(dataSet[0]) - 1
    # 原資料集香農熵
    baseEntropy = calcShannonEnt(dataSet)
    # 暫存最大熵增量
    bestInfoGain = 0.0; 
    # 和原資料集熵差最大的劃分對應的特征的列号
    bestFeature = -1
    
    for i in range(numFeatures):    # 逐列周遊資料集
        # 擷取該列所有特征值
        featList = [example[i] for example in dataSet]
        # 将特征值列featList的值唯一化并儲存到集合uniqueVals
        uniqueVals = set(featList)
        
        # 新劃分法香農熵
        newEntropy = 0.0
        # 計算該特征劃分下所有劃分子集的香農熵，并疊加。
        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
            bestFeature = i
            
    return bestFeature
def majorityCnt (classList):
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys(): classCount[vote] = 0
        classCount[vote]+=1
    sortedClassCount = sorted(classCount.items(),key=operator.itemgetter(1),reverse=True)
    return sortedClassCount[0][0]
def createTrees(dataSet,labels):
    classList = [example[-1] for example in dataSet]
    if classList.count(classList[0] == len(classList)):#類别相同停止劃分
        return classList[0]
    if len(dataSet[0]) == 1:#傳回出現次數最多的類别
        return majorityCnt(classList)
    bestFeat = chooseBestFeatureToSplit(dataSet)
    bestFeatLabel = labels[bestFeat]
    myTree = {bestFeatLabel:{}}
    del(labels[bestFeat])
    featValues = [example[bestFeat] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:
        subLables = labels[:]
        myTree[bestFeatLabel][value] = createTrees(splitDataSet(dataSet,bestFeat,value),subLables)
    return myTree
fr = open("lenses.txt")
lenses = [inst.strip().split('\t') for inst in fr.readlines()]
lenses_labels = ['age', 'prescript', 'astigmatic', 'tear_rate']
lenses_tree = createTrees(lenses,labels)
print(lenses_tree)




young    myope    no    reduced    no lenses