決策樹詳解，從熵說起

　　熵，一個神奇的工具，用來衡量資料集資訊量的不確定性，

　　首先，我們先來了解一個指標，資訊量，對于任意一個隨機變數X，樣本空間為{X1,X2，...,Xn},對于任意的樣本Xi，樣本X_i的資訊量也就是l(X_i) = -log(p(Xi))，由于p(Xi)是為樣本Xi的概率，也可以說是類X_i的概率，那么l(X_i)的取值范圍為(+∞，0]，也就是X的的概率越小，其含有的資訊量越大，反之亦然，這也不難理解，X_i的發生的概率越大，我們對他的了解越深，那么他所含有的資訊量就越小，如果隨機變數X是常量，那么我們從任意一個Xi都可以獲取樣本空間的值，那么我們可以認為X沒有任何資訊量，他的資訊量為0，如果說，我們要把隨機變數X樣本空間都了解完，才能獲得X的資訊，那么我們可以認為X的資訊量“無窮大”，其取值為log（2，n)，

　　緊接著，我們就提出了隨機變數X的資訊熵，也就是資訊量的期望，H(X) = -∑ⁿ_i=1p(Xi)log₂(p(Xi))，從離散的角度得出的公式，他有三個特性：

• 單調性，即發生概率越高的事件，其所攜帶的資訊熵越低，極端案例就是“太陽從東方升起”，因為為確定事件，所以不攜帶任何資訊量，從資訊論的角度，認為這句話沒有消除任何不確定性，也就是樣本空間的p(Xi)均為1，
• 非負性，即資訊熵不能為負，這個很好理解，因為負的資訊，即你得知了某個資訊后，卻增加了不確定性是不合邏輯的，
• 累加性，即多隨機事件同時發生存在的總不確定性的量度是可以表示為各事件不確定性的量度的和，

　　有了熵這個基礎，那么我們就要考慮決策樹是怎么生成的了，對于隨機變數X的樣本個數為n的空間，每個樣本都有若干個相同的特征，假設有k個，對于任意一個特征，我們可以對其進行劃分，假設含有性別變數，那么切分后，性別特征消失，變為確定的值，那么隨機變數X資訊的不確定性減少，以此類推，直到達到我們想要的結果結束，這樣就生成了若干棵樹，每棵樹的不確定性降低，如果我們在此程序中進行限制，每次減少的不確定性最大，那么這樣一步一步下來，我們得到的樹，會最快的把不確定性降低到最小，每顆樹的分支，都可以確定一個類別，包含的資訊量極少，確定性極大，這種類別，是可以進行預測的，不確定性小，穩定，可以用于預測，

        有了以上的知識儲備，那么我們要想生成一顆決策樹，只需要每次把特征的資訊量最大的那個找出來進行劃分即可，也就是不確定性最大的那個分支，我們要優先劃分，這就會得出另外一個定義，條件資訊熵H(Y|X)，

根據以上的推導，我們得出資訊增益，H(Y)-H(Y|X)，可以看做是特征X的資訊量，根據這個的最大值，依次得到每個特征，就是我們需要的決策樹，利用Python完成代如下：

from math import log
from collections import defaultdict
import operator

# 計算香農熵
def calcShannonEnt(dataSet):
    num = len(dataSet)
    labelCounts = defaultdict()
    for fVec in dataSet:
        currentLabel = dataSet[-1]
        labelCounts[currentLabel] = labelCounts.get(labelCounts[currentLabel], 0) +1
    shannonEnt = 0.0
    for key in labelCounts:
        prob = float(labelCounts[key]) / num
        shannonEnt -= prob * log(2, prob)
    return shannonEnt

#按照特征劃分資料集，特征的位置為index
def splitDataSet(dataSet, index, value):
    retDataSet = []
    for featVec in dataSet:
        if featVec[index] == value:
            reducedFeatVec = featVec[:index]
            reducedFeatVec.extend(featVec[index+1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet

#尋找資訊增益最大的特征
def chooseBestFeatureToSplit(dataSet):
    numFeatures = len(dataSet[0]) - 1
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain, bestFeature = 0.0, -1.0
    for i in range(numFeatures):
        featList = [example[i] for example in dataSet]
        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 > baseInfoGain):
            bestInfoGain = infoGain
            bestFeature = i
    return bestFeature

# 如果分類不唯一，采用多數表決方法，決定葉子的分類
def majorityCnt(classList):
    classList = defaultdict()
    for vote in classList:
        classList[vote] = classList.get(classList[vote], 0) +1
    SortedClassCount = sorted(classList.items(), operator.itemgetter(1), reverse = True)
    return SortedClassCount[0][0]

# 創建決策樹代碼
def createTree(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[i] for example in dataSet]
    uniqueVals = set(featValues)
    for value in uniqueVals:#利用遞回構建決策樹
        subLabels = labels[:]
        myTree[bestFeatLabel][value] = createTree(splitDataSet(dataSet, bestFeat, value), subLabels)
    return myTree

標籤：其他

上一篇：Jekins修改埠的方法，主要是解決其它地方無法訪問jekins 8080埠問題

下一篇：決策樹詳解，從熵說起