ML經典算法：決策樹（2）

在前面ML經典算法：決策樹（1）中描述了什麼是決策樹算法，以及介紹了三種不同的屬性劃分方法。不僅要知道理論，還要實踐，下面對這資訊增益劃分方法進行python實作。

先來複習一下資訊增益：

        資訊增益越大，則意味着使用屬性 α 來進行劃分所獲得的"純度提升"越大。

        假定離散屬性 α 有 V 個可能的取值 {α1 ， α2. …， αv}，若使用 α 來對樣本集D 進行劃分，則會産生 V 個分支結點，其中第 u 個分支結點包含了 D 中所有在屬性 α 上取值為 α" 的樣本記為 Du. 先計算出 Du的資訊熵（下面會介紹），再考慮到不同的分支結點所包含的樣本數不同，給分支結點賦予權重 IDuI / IDI ，即樣本數越多的分支結點的影響越大，于是可計算出用屬性 α 對樣本集 D 進行劃分所獲得的"資訊增益"，公式如下：

        其中Ent(D)為"資訊熵" (information entropy)，資訊熵是度量樣本集合純度最常用的一種名額。假定目前樣本集合 D 中第 k 類樣本所占的比例為 Pk (k = 1,2,. . . , IYI) ， D的資訊熵定義為:Ent(D)

1. 計算資訊熵

首先計算資訊熵：

# 計算資訊熵
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 = shannonEnt - prob * log(prob, 2)
    return shannonEnt
           

2. 求資訊增益

首先為求資訊增益中第axis個屬性值為value的樣本子集（即在屬性 α 上取值為 α" 的樣本 Du）：

# 劃分資料集，axis:按第幾個屬性劃分，value:要傳回的子集對應的屬性值
# 獲得資料集中，第axis個屬性值為value的其他屬性和标簽的樣本子集
def splitDataSet(dataSet, axis, value):
    retDataSet = []
    featVec = []
    for featVec in dataSet:
        if featVec[axis] == value:
            # 獲得第axis個屬性之前的幾個屬性
            reducedFeatVec = featVec[:axis]
            # 獲得第axis個屬性之後的幾個屬性
            reducedFeatVec.extend(featVec[axis + 1:])
            retDataSet.append(reducedFeatVec)
    return retDataSet
           

然後求Du的資訊熵和權重 IDuI / IDI ，最後求得資訊增益，獲得增益最大的那個屬性：

# 選擇最好的資料集劃分方式
def chooseBestFeatureToSplit(dataSet):
    # 獲得屬性的個數，-1是去掉标簽
    numFeatures = len(dataSet[0]) - 1
    # 獲得資訊熵Ent（D）
    baseEntropy = calcShannonEnt(dataSet)
    bestInfoGain = 0.0
    bestFeature = -1
    # 對每個屬性技術資訊增益
    for k in range(numFeatures):
        # 獲得所有樣本的第i個屬性值
        featList = [example[k] for example in dataSet]
        # 該屬性的取值集合
        uniqueVals = set(featList)
        newEntropy = 0.0
        # 對每一種取值計算資訊增益
        for value in uniqueVals:
            subDataSet = splitDataSet(dataSet, k, value)
            # 樣本集合中第 k 類樣本所占的比例：權重 IDuI / IDI 
            prob = len(subDataSet) / float(len(dataSet))
            # 獲得獲得第k類屬性值為value的資訊熵：calcShannonEnt(subDataSet)
            newEntropy += prob * calcShannonEnt(subDataSet)
        # 獲得資訊增益
        infoGain = baseEntropy - newEntropy
        # 選擇資訊增益最大的屬性
        if (infoGain > bestInfoGain):
            bestInfoGain = infoGain
            bestFeature = k
    return bestFeature