機器學習--決策樹（公式結論）

本文記錄周志華《機器學習》決策樹内容：***(文中公式内容均來自周志華《機器學習》)***

決策樹是基于樹結構進行決策問題的算法，一般來說，一棵決策樹包括一個根節點、若幹内部節點和若幹個葉子節點(決策結果)，其餘每個節點則對應于一個屬性測試。每個節點包含的樣本集合根據屬性測試的結果被劃分到子節點中。進而實作以下的類似結構

基礎知識：

1. 資訊熵：度量樣本集合純度常用的名額，值越小，則D的純度越高， p k {p_k} pk​為樣本集合D中第k類樣本所占的比例 ( k = 1 , 2 , . . . , ∣ y ∣ ) \left( {k = 1,2,...,|y|} \right) (k=1,2,...,∣y∣)。

   E n t ( D ) = − ∑ k = 1 ∣ y ∣ p k log ⁡ 2 p k Ent(D) = - \sum\limits_{k = 1}^{|y|} {{p_k}{{\log }_2}{p_k}} Ent(D)=−k=1∑∣y∣​pk​log2​pk​

2. 資訊增益：考慮不同分支節點的樣本數不同，故對其賦予權重 ∣ D v ∣ / ∣ D ∣ |{D^v}|/|D| ∣Dv∣/∣D∣，即樣本數越多的分支節點影響越大，式中a為離散屬性，有V個可能的取值。資訊增益越大越好。

   G a i n ( D , a ) = E n t ( D ) − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ E n t ( D v ) Gain(D,a) = Ent(D) - \sum\limits_{v = 1}^V {{{|{D^v}|} \over {|D|}}Ent({D^v})} Gain(D,a)=Ent(D)−v=1∑V​∣D∣∣Dv∣​Ent(Dv)

3. 增益率：資訊增益準則對可取值數位較多的屬性有所偏好，而增益率準則對可取值數目較少的屬性有所偏好，是以C4.5算法不是直接選擇增益率最大的候選劃分屬性，而是先從候選劃分屬性中宣傳資訊增益高于平均水準的屬性，再在其中選擇增益率最高的。 G a i n _ r a t i o ( D , a ) = G a i n ( D , a ) I V ( a ) Gain\_ratio(D,a) = {{Gain(D,a)} \over {IV(a)}} Gain_ratio(D,a)=IV(a)Gain(D,a)​ I V ( a ) = − ∑ v = 1 V ∣ D v ∣ ∣ D ∣ log ⁡ 2 ∣ D v ∣ ∣ D ∣ IV(a) = - \sum\limits_{v = 1}^V {{{|{D^v}|} \over {|D|}}{{\log }_2}{{|{D^v}|} \over {|D|}}} IV(a)=−v=1∑V​∣D∣∣Dv∣​log2​∣D∣∣Dv∣​
4. 基尼指數(Gini):反映從資料集D中随機抽取兩個樣本，其類别标記不一緻的機率。Gini(D)越小，則資料純度越高。 G i n i ( D ) = 1 − ∑ k = 1 ∣ y ∣ p k 2 Gini(D) = 1 - \sum\limits_{k = 1}^{|y|} {{p_k}^2} Gini(D)=1−k=1∑∣y∣​pk​2屬性a的基尼指數，使得劃分後基尼指數最小的屬性為最優劃分屬性 G i n i _ i n d e x ( D , a ) = ∑ v = 1 V ∣ D v ∣ ∣ D ∣ G i n i ( D v ) Gini\_index(D,a) = \sum\limits_{v = 1}^V {{{|{D^v}|} \over {|D|}}Gini({D^v})} Gini_index(D,a)=v=1∑V​∣D∣∣Dv∣​Gini(Dv)

預防過拟合問題：【可以通過設立驗證集，對比各個節點劃分前後的精度，來缺定該節點是否需要劃分】

5. 預剪枝：邊建立決策樹邊進行剪枝操作(限制深度，葉子節點個數，葉子節點樣本數，資訊增益量等)

6. 後剪枝：建立完決策樹後進行剪枝操作(通過一定的衡量标準）

後剪枝前：

後剪枝後：

後剪枝決策樹通常比預剪枝決策樹保留了更多分支，故欠拟合風險很小，泛化性能往往由于預剪枝決策樹，但其訓練時間開銷比未剪枝決策樹和預剪枝決策樹都要大很多。

連續屬性處理：

當連續屬性的可取值數目不再有限，是以不能直接根據連續屬性的可取值來對節點進行劃分，是以可利用連續屬性離散化，如最簡單的二分法對其進行處理。即将連續屬性由小到大進行排序{a1,a2,…,an}，基于劃分點t将D分為子集 D t − D_t^ - Dt−​和 D t + D_t^ + Dt+​，前者為再屬性a上不大于t的樣本，後者為大于t的樣本，而劃分點t的取值為 T a = { a i + a i + 1 2 ∣ 1 ≤ i ≤ n − 1 } {T_a} = \{ {{{a^i} + {a^{i + 1}}} \over 2}|1 \le i \le n - 1\} Ta​={2ai+ai+1​∣1≤i≤n−1}

然後依次選取劃分點，進行劃分，進而計算資訊增益，按照max(資訊增益)的原則，選取最優劃分點即可。

注意：與離散屬性不同，若目前節點劃分屬性為連續屬性，該屬性還可作為其後代節點的劃分屬性。

算法流程：（利用遞歸操作）

大緻流程：

1.判斷是否遞歸傳回：目前節點包含樣本全部屬于同一類别；目前屬性集為空，或所有樣本在所有屬性上取值相同無法劃分。符合以上兩種情況，則傳回類别值的衆數。

2.周遊屬性，計算分割後的資訊增益，選取最優分割屬性

3.如果最優分割屬性為離散屬性，則剔除。以後不再使用其進行劃分

4.按照最優分割屬性，分割資料集，然後重新進行第一步，進行遞歸操作。

程式：

import operator
from math import log


def dataset():
    data = [[0, 0, 0.56, 0.8, 'no'],
               [0, 0, 0.34, 1.2, 'no'],
               [0, 1, 0.25, 1.8, 'yes'],
               [0, 1, 1.4, 0.3, 'yes'],
               [0, 0, 0.43, 0.5, 'no'],
               [1, 0, 0.24, 0.9, 'no'],
               [1, 0, 0.22, 1.9, 'no'],
               [1, 1, 1.14, 1.4, 'yes'],
               [1, 0, 1.87, 2.2, 'yes'],
               [1, 0, 1.44, 2.55, 'yes'],
               [2, 0, 1.0, 2.79, 'yes'],
               [2, 0, 1.55, 1.1, 'yes'],
               [2, 1, 0.14, 1.0, 'yes'],
               [2, 1, 0.58, 2.66, 'yes'],
               [2, 0, 0.44, 0.55, 'no']]
    lebels = ['F1', 'F2', 'F3', 'F4']
    return data, lebels


def creattree(data, labels, featlabels):
    classlist = [example[-1] for example in data]  # 目前資料的分類
    # 停止條件1---分類全部一緻
    if classlist.count(classlist[0]) == len(classlist):
        return classlist[0]
    # 停止條件2---無可分屬性
    if len(data[0]) == 1:
        return majorityCnt(classlist)

    bestfeat, threshold = chooseBestFeature(data)  # 選擇最優分割屬性id和連續屬性時的分割門檻值
    bestfeatlabel = labels[bestfeat]  # 最優分割屬性
    information = (bestfeatlabel, threshold)
    featlabels.append(information)

    tree = {information: {}}

    if threshold == None:  # 離散屬性
        del labels[bestfeat]  # 剔除此屬性标簽
        featvalue = [example[bestfeat] for example in data]
        uniqueVals = set(featvalue)  # 屬性下不同值
        # 根據不同值創造多個子節點
        for value in uniqueVals:
            sublabels = labels[:]
            tree[information][value] = creattree(splitDisDataSet(data, bestfeat, value), sublabels, featlabels)  # 子節點
        return tree
    else:  # 連續屬性
        uniquePolar = [0, 1]
        for polar in uniquePolar:
            sublabels = labels[:]
            tree[information][polar] = creattree(splitConDataSet(data, bestfeat, threshold, polar), sublabels, featlabels)  # 子節點
        return tree


# 傳回類别數最多的類别id
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 chooseBestFeature(data):
    numfeatures = len(data[0]) - 1  # 目前資料屬性數量
    baseentropy = calnonent(data)  # 父節點熵值
    bestinfogain = 0
    bestfeature = -1
    threshold = None

    for i in range(numfeatures):
        featlist = [example[i] for example in data]
        uniquevals = set(featlist)  # 同一屬性下不同值
        newentropy = 0  # 子節點熵值

        if type(featlist[0]) == int:
            for val in uniquevals:
                subdata = splitDisDataSet(data, i, val)  # 分割後的資料集(剔除目前屬性)
                prob = len(subdata) / float(len(data))
                newentropy += prob * calnonent(subdata)
            infogain = baseentropy - newentropy  # 資訊增益
            if infogain >= bestinfogain:
                bestinfogain = infogain
                bestfeature = i
                threshold = None

        if type(featlist[0]) == float:
            thresholds = sorted(uniquevals)
            entropy = baseentropy
            # 二分法
            for j in range(len(thresholds) - 1):
                thresholdlter = (thresholds[j] + thresholds[j+1]) / 2
                subdata_l = splitConDataSet(data, i, thresholdlter, 0)  # 負樣本
                prob_l = len(subdata_l) / float(len(data))
                subdata_r = splitConDataSet(data, i, thresholdlter, 1)  # 正樣本
                prob_r = len(subdata_r) / float(len(data))
                newentropy = prob_l * calnonent(subdata_l) + prob_r * calnonent(subdata_r)
                infogain = baseentropy - newentropy
                if infogain >= bestinfogain:
                    bestinfogain = infogain
                    bestfeature = i
                    threshold = thresholdlter
    return bestfeature, threshold


# 分割離散屬性資料
def splitDisDataSet(data, axis, val):
    retdata = []
    for featvec in data:
        if featvec[axis] == val:
            reducedfeatvec = featvec[:axis]
            reducedfeatvec.extend(featvec[axis+1:])
            retdata.append(reducedfeatvec)
    return retdata


# 分割連續屬性資料
def splitConDataSet(data, axis, threshold, polar):
    retdata = []
    for featvec in data:
        if polar == 0:
            if featvec[axis] <= threshold:
                reducedfeatvec = featvec[:axis]
                reducedfeatvec.extend(featvec[axis + 1:])
                retdata.append(reducedfeatvec)
        else:
            if featvec[axis] > threshold:
                reducedfeatvec = featvec[:axis]
                reducedfeatvec.extend(featvec[axis + 1:])
                retdata.append(reducedfeatvec)
    return retdata


def calnonent(dataset):
    numexamples = len(dataset)  # 資料個數
    labelCounts = {}
    # 計算各個标簽值數量
    for featVec in dataset:
        currentlabel = featVec[-1]
        if currentlabel not in labelCounts.keys():
            labelCounts[currentlabel] = 0
        labelCounts[currentlabel] += 1
    shannonEnt = 0  # 目前節點熵值
    for key in labelCounts:
        prop = float(labelCounts[key]) / numexamples
        shannonEnt -= prop * log(prop, 2)
    return shannonEnt


if __name__ == '__main__':
    dataSet, labels = dataset()
    featLabels = []
    myTree = creattree(dataSet, labels, featLabels)
    print(myTree)