決策樹筆記：使用ID3算法

機器學習

---

先說一個偶然的想法：同樣的一堆節點構成的二叉樹，平衡樹和非平衡樹的區別，可以認為是“是否按照重要度逐漸降低”的順序來分叉的。

其實這個也不一定局限于平衡樹的解釋。huffman編碼就是這么干的：出現頻率最高的編碼一定是與root直接相連的，是層數最淺的。

什么是決策樹

簡單講就是一棵多叉樹，每個節點表示一個決策，它的不同分支表示依據決策結果劃分的子類；子樹要么仍然是決策數，要么是葉節點。葉節點表示原有label或某一個維度屬性。

決策樹算法，就是用訓練數據構造一棵決策樹，作為分類器，為測試數據使用。因此，決策樹是一個學習的結果，是一個模型。

ID3算法是基于信息熵的決策樹構造算法。假設你處于這樣一個環境：你需要判斷一個事物的類別，你只能通過問一系列問題來判斷。顯然，每次問的問題越有質量，就越容易得到答案。什么樣的問題算有質量？能最大限度獲取信息、使得你能縮小猜測范圍，這樣的問題是有質量的問題。這個過程持續進行，直到猜到該事物的分類。

在猜測過程中，所謂“盡可能縮小分類范圍”，也就是每次得到盡可能多的信息。信息論中，使用信息熵表示不確定程度，信息熵越大，越不確定；信息熵越小，信息越多，事物越確定。因此，每一次決策都試圖去獲得最大的信息熵負增量，就是獲得越多的信息。so，每一次決策時，我怎么知道信息熵是多少？

比如用于訓練的向量形如$(a,b,c,label)$，那么我我依次用a、b、c屬性節點做決策，看看使用這個屬性后，我能得到信息熵負增量是多少。比較每一個決策點，選一個最大值作為本次決策節點。

設$p_i$表示事件i出現的概率，依據信息論可知，信息熵等于

$$-∑p_i log\ p_i$$

信息熵公式的證明

這個公式的證明似乎沒有什么用處，看看就好。通過閱讀Shannon那篇A Mathematical Theory of Communication的附錄2不難推出。

考慮如下情形：你需要確定下一件發生的事件，然而你只知道每一個事件發生的概率：$p_1$,$p_2$,...,$p_n$。用$H$表示本次決策的熵。我們的決策基于如下3個假設：
1. $H$在$p_i$處連續
2. 若所有$p_i$相等，即$p_i$=$1\over n$，則$H$為n的嚴格增函數
3. 若某一個選擇被打散，變為兩次連續的選擇，則原有$H$應等于各獨立的$H$的權和。

個人認為假設3最重要，也很難翻譯準確，原文如下：

If a choice be broken down into two successive choices, the original $H$ should be the weighted sum of the individual values of $H$.

例如

從左邊的樹狀圖轉換到右邊一個樹狀圖，是后兩個分支先合并在分離，原來的一次決策變為兩次決策，才能確定后面兩個節點：

$$H(\frac{1}{2},\frac{1}{3},\frac{1}{6})=H(\frac{1}{2},\frac{1}{2})+\frac{1}{2}H(\frac{2}{3},\frac{1}{3})$$
其中\frac{1}{2}表示這個分支的概率。這個假設能用來把平面式的數據塑造為樹狀、有層次的數據，在后面起到重要作用。

公式$A(s^m)=mA(s)$的證明

假設$A(n)=H(\frac{1}{n},\frac{1}{n},...,\frac{1}{n})$，怎樣證明$A(s^m)=mA(s)$？

$A(s)$可以看作：root節點只有一層子節點，子節點一共有$s$個，每個子節點被選中的概率為$\frac{1}{s}$。

$A(s^m)$則可以看作：root節點只有一層子節點，子節點一共有$s^m$個，每個子節點被選中的概率都是$\frac{1}{s^m}$。

如果把對于任意一個$\frac{1}{s^m}$概率事件的確定，從原有的一步分解為兩步：先做$\frac{1}{s}$再做$\frac{1}{s^{m-1}}$，那么熵值$H$的計算依據假設（3）即可計算：通過把$A(s^m)$的每$s^{m-1}$個連續的分支搓成一股，下一股則為$A(s^{m-1})$，得到：

$$A(s^m)=A(s)+\frac{1}{s}*A(s^{m-1})*s\\=>A(s^m)=mA(s)$$

公式$A(t)=K\ log\ t$的證明

$$\forall n, \exists m, s.t.s^m \le t^n \lt s^{m+1}$$
取對數并除以$n\ log\ s$，有：
$$\frac{m}{n} \le \frac{log\ t}{log\ s} \lt \frac{m}{n} + \frac{1}{n}，\\即：|\frac{log\ t}{log\ s} - \frac{m}{n}| \lt \frac{1}{n} \to 0$$
由假設2$A(n)$對n嚴格增有：
$$A(s^m) \lt A(t^n) \lt A(s^{m+1}) \\=> mA(s) \le nA(t) \lt (m+1)A(s)$$
同除$nA(s)$:
$$\frac{m}{n} \lt \frac{A(t)}{A(s)} \lt \frac{m}{n} + \frac{1}{n} \\=> |\frac{m}{n} - \frac{A(t)}{A(s)}| \lt \frac{1}{n} \to 0$$
由上面兩個趨向于0的絕對值不等式有：
$$|\frac{A(t)}{A(s)}-\frac{log\ t}{log\ s}| \to 0 \\=> A(t)=K\ log\ t, K>0$$

信息熵公式$H(p_1,...,p_n)=-K\sum(p_i\ log\ p_i)$的證明

假設有$n$組事件，第$i$組有$n_i$個事件，選中第$n_i$的概率為$p_i$。注意此時事件總數是$\sum n_i$而不是$n$。
此時確定下一個事件，有假設3，可以先從$n$組事件中選出$n_i$這一組，然后再從這$n_i$個事件中選擇一個。這第二次選擇是等概率的。因此有：

$$H_{總體}=K\ log\ \sum n_i = H(p_1,...,p_n)+K\sum p_i\ log\ n_i \\=>H(p_1,...,p_n)=K(log\sum n_i - \sum p_i \ log\ n_i)$$
由$\sum p_i=1$有：
$$log\ \sum n_i=\sum p_i\ log \sum n_i \\=> H(p1,...,pn)=K(\sum p_i\log \sum n_i - \sum p_i \ log\ n_i) \\= -K\sum p_i\ log \frac{n_i}{\sum n_i} \\=-K\sum p_i\ log\ p_i$$

決策樹的構造

如果label只有一個，表示數據都是同一個類別的，那么不必構造。

如果使用完了所有特征，仍然不能將數據劃分成僅包含唯一類別的分組，那么也要停止遞歸，轉調用表決函數。

除此以外，首先將各維度進行比較，看選擇哪一個維度進行分類能得到更多的信息熵。這樣一來，會按照這一列重復元素作為同一個小組，這個小組遞歸地創建決策樹。

為得到最大的信息熵負增量，要逐列計算信息熵。對每一列將重復元素作為一個小組，能算出這個小組的發生概率；累加這些概率與概率對數值的乘積，能算出該列的信息熵負增量。比較每一列的信息熵負增量，用類似打擂臺的方式選出最大的那個，并記錄對應的列序號。最后返回這個序號。

創建決策樹：

def createTree(dataSet, labels):
    """
    創建決策樹
    myTree變量存儲這個結果
    myTree中某一層的一個節點，key是特征向量對應的label，val為屬于key類和不屬于key類的兩個子樹
    """
    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:
        subLabels = labels[:] #列表會按照引用方式傳遞，因此，為了保證不改變labels這個原始列表，使用新變量subLabels來作為參數
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

選出最好的特征列序號：

def chooseBestFeatureToSplit(dataSet):
    """
    選擇最好的數據集劃分方式
    即：對除label外的每一列都進行計算，每一列能算出一個總的信息增量（信息熵增量的負值）。
    信息增量最多的那一列，就是最好的劃分列。
    """
    numFeatures = len(dataSet[0])-1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bastFeature = -1
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        #取出dataSet的第i列
        uniqueVals = set(featList) #set是用來去除重復元素的
        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

切分數據：將指定列中與指定value相等的向量篩選出，并將其去除了指定列得到的子矩陣返回：

def splitDataSet(dataSet, axis, value):
    """
    掃描數據集（矩陣）的指定列（axis列），如果某個向量第axis列的值等于value
    那么將去除這個value后的向量存儲起來
    每一行都這么處理，最后返回的是“axis列與value相等并且去除了axis列的矩陣”
    也就是：按照value劃分了一個類，返回這個類
    """
    retDataSet=[]
    for featVec in dataSet:
        if featVec[axis] == value:
            reducedFeatVec = featVec[:axis]
            reducedFeatVec.extend(featVec[axis+1:])
            #reducedFeatVec:去除axis列后的向量
            retDataSet.append(reducedFeatVec)
    return retDataSet

反倒是計算信息熵的最核心代碼最容易：

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  #書上此行少了一個indent。
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key])/numEntries
        shannonEnt -= prob*log(prob,2)
    return shannonEnt

當決策樹終于構建完畢，就需要用它來預測一個測試向量的分類了：

def classify(inputTree, featLabels, testVec):
    """
    使用決策樹的分類函數
    """
    firstStr = inputTree.keys()[0]
    secondDict = inputTree[firstStr]
    featIndex = featLabels.index[firstStr]
    for key in secondDict.keys():
        if testVec[featIndex]==key:
            if type(secondDict[key]).__name__=='dict':
                classLabel = classify(secondDict[key], featLabels, testVec)
            else:
                classLabel=secondDict[key]
    return classLabel

算法中可替換部件

度量系統無序程度

除了信息熵，也可以用Gini不純度來做。

數據劃分

這里采用ID3算法。也可以用二分法。
還有C4.5和CART算法可用。挖坑待填