決策樹4：構建演算法之ID3、C4.5

  • 2019 年 12 月 23 日
  • 筆記

0x01 ID3演算法介紹

1.1 簡介

ID3演算法是一種分類預測演算法，演算法以資訊理論中的「資訊增益」為基礎。核心是通過計算每個特徵的資訊增益，每次劃分選取資訊增益最高的屬性為劃分標準，遞歸地構建決策樹。

ID3相當於用極大似然法進行概率模型的選擇。

具體方法是：

  1. 從根結點(root node)開始，對結點計算所有可能的特徵的資訊增益，選擇資訊增益最大的特徵作為結點的特徵。
  2. 由該特徵的不同取值建立子節點，再對子結點遞歸地調用以上方法，構建決策樹；直到所有特徵的資訊增益均很小或沒有特徵可以選擇為止；
  3. 最後得到一個決策樹。

從ID3的構建樹過程而言，它可以看成使用貪心演算法得到近似最優的一顆決策樹，它無法保證是最優的。

1.2 構建流程

以遞歸的方式構建一棵決策樹，其演算法流程如下：

演算法：createTree(dataSet,featList,bestFeatLists)。由給定的訓練數據產生一棵判定樹。輸入：    dataSet：訓練數據集    featList：分類屬性標籤    bestFeatLists：存儲選擇的最優特徵標籤輸出：    myTree：一棵判定樹。方法：createTree(dataSet,featList,bestFeatLists)1）從傳入的數據集dataSet中切割出分類標籤，yList2）如果yList中只有同一種標籤，說明已經遞歸到分類邊界了，則返回該標籤3）如果已經處理了dataSet中所有屬性（列），但是類標籤依然不是唯一的，採用多數判決的方法決定該子節點的分類4）找出dataSet最優劃分（資訊增益最大）的特徵所在位置bestFeatVec5）在分類屬性標籤featList找出該位置所對應的特徵值bestFeatLabel，並將該特徵值存儲到bestFeatLists中6）將最優劃分特徵值作為當前（子）樹的根節點，生成初始決策樹myTree（用字典表示一個樹結構）7）在featList中刪除當前已經使用過的特徵標籤（因為每次選擇特徵作為條件，dataSet會刪掉這一列，形成新的子類，因此對應的featList中的值也要刪掉）8）確定子樹分支：獲取已選擇的最優劃分特徵所對應的值分類categories（如「年齡」是最優特徵，則「老」「中」「青」三個子類）9）遍歷每一個當前特徵下的子類，在每個子類中，遞歸地調用創建決策樹的方法，將遞歸調用的結果作為當前樹節點的一個分支（構建樹的方法是：特徵作為字典的key，所得到的分類結果作為value；子樹進行嵌套）

0x02 程式碼實例

現在我們以銀行貸款申請業務為例，模擬四個特徵，分別是：年齡、有工作、有房子、信貸情況。

"""函數說明：數據集已經處理了所有屬性，但是類標籤依然不是唯一的,採用多數判決的方法決定該子節點的分類        即統計yList中出現次數最多的元素（類標籤）Parameters：    yList：類標籤列表Returns：    sortedClassCount[0][0]：出現次數最多的元素（類標籤）"""def majorityCnt(yList):    yCount={}    #統計yList中每個元素出現的次數    for vote in yList:        if vote not in yCount.keys():            yCount[vote]=0        yCount[vote]+=1        #根據字典的值降序排列        sortedYCount=sorted(yCount.items(),key=operator.itemgetter(1),reverse=True)    return sortedYCount[0][0]  """函數說明：創建決策樹  Parameters:    dataSet：訓練數據集    featList：分類屬性標籤    bestFeatLists：存儲選擇的最優特徵標籤Returns：    myTree：決策樹"""def createTree(dataSet,featList,bestFeatLists):    # 取訓練數據集最後一列，即分類標籤    yList=[example[-1] for example in dataSet]        # 如果類別完全相同，則停止繼續劃分，    # 即yList中所有類別都是同一數據值（該類別數值個數等於列表長度）    if yList.count(yList[0])==len(yList):        # 返回該類別數值        return yList[0]            # 數據集已經處理了所有屬性，但是類標籤依然不是唯一的，    # 則採用多數判決的方法決定該子節點的分類    # 為什麼要如此判斷？dataSet的列是不斷減少的，dataSet某一行的長度，就是列    if len(dataSet[0])==1:        return majorityCnt(yList)        # 選擇最優劃分的特徵index    bestFeatVec = optimalPartition(dataSet)    # 最優特徵index所對應的分類標籤，作為樹的根節點    bestFeatLabel=featList[bestFeatVec]    # 存儲選擇的最優特徵標籤    bestFeatLists.append(bestFeatLabel)        # 將最優劃分特徵值作為當前（子）樹的根節點，生成初始決策樹（用字典表示一個樹結構）    myTree={bestFeatLabel:{}}        # 刪除已經使用的特徵標籤（del刪除變數，解除引用）    # 因為每次選擇特徵作為條件，dataSet會刪掉這一列，形成新的子類，因此對應的featList中的值也要刪掉    del(featList[bestFeatVec])    print('featList: ',featList)            # 得到訓練集中所有最優特徵那一列所對應的值    featValues=[example[bestFeatVec] for example in dataSet]    # 去掉重複的屬性值，得到最優特徵下的子類    categories=set(featValues)        # 遍歷最優特徵列所對應的值，創建決策樹    # 如「年齡」是最優特徵，則遍歷「老」「中」「青」三個子類    for category in categories:        # 根據當前數據集、最優劃分的特徵index以及每個分類（條件）得到（條件下的子集）        subDataSet = np.array(currentConditionSet(dataSet,bestFeatVec,category))        # 遞歸地調用創建決策樹的方法，將遞歸調用的結果作為當前樹節點的一個分支        myTree[bestFeatLabel][category]=createTree(subDataSet,featList,bestFeatLists)    return myTree  if __name__=='__main__':    #print('featLabels',featLabels)    bestFeatLists = []    myTree=createTree(dataSet,featList,bestFeatLists)    print(myTree)

輸出：第0個特徵的增益為0.083第1個特徵的增益為0.324第2個特徵的增益為0.420第3個特徵的增益為0.363最佳的劃分為第2個特徵，是」有自己的房子「，資訊增益為0.420第0個特徵的增益為0.252第1個特徵的增益為0.918第2個特徵的增益為0.474最佳的劃分為第1個特徵，是」有工作「，資訊增益為0.918{'有自己的房子': {0: {'有工作': {0: 0, 1: 1}}, 1: 1}}

解讀結果：

0x03 ID3演算法總結

3.1 優缺點：

相對於其他數據挖掘演算法，決策樹在以下幾個方面擁有優勢：

  1. 決策樹易於理解和實現. 人們在通過解釋後都有能力去理解決策樹所表達的意義。
  2. 對於決策樹，數據的準備往往是簡單或者是不必要的 . 其他的技術往往要求先把數據一般化，比如去掉多餘的或者空白的屬性。
  3. 能夠同時處理數據型和常規型屬性。其他的技術往往要求數據屬性的單一。
  4. 是一個白盒模型如果給定一個觀察的模型，那麼根據所產生的決策樹很容易推出相應的邏輯表達式。
  5. 易於通過靜態測試來對模型進行評測。表示有可能測量該模型的可信度。
  6. 在相對短的時間內能夠對大型數據源做出可行且效果良好的結果

ID3演算法可用於劃分標準稱型數據，但存在一些問題：

  1. 沒有剪枝過程，為了去除過渡數據匹配的問題，可通過裁剪合併相鄰的無法產生大量資訊增益的葉子節點;
  2. 資訊增益的方法偏向選擇具有大量值的屬性，也就是說某個屬性特徵索取的不同值越多，那麼越有可能作為分裂屬性，這樣是不合理的；
  3. 只可以處理離散分布的數據特徵
  4. ID3演算法只考慮了樹的生成，即儘可能的是模型擬合當前訓練數據集，所以該演算法生成的樹容易過擬合。

3.2 總結

總結基本思想：

  1. 初始化屬性集合和數據集合
  2. 計算數據集合資訊熵S和所有屬性的資訊熵，選擇資訊增益最大的屬性作為當前決策節點
  3. 更新數據集合和屬性集合（刪除掉上一步中使用的屬性，並按照屬性值來劃分不同分支的數據集合）
  4. 依次對每種取值情況下的子集重複第二步
  5. 若子集只包含單一屬性，則為分支為葉子節點，根據其屬性值標記。
  6. 完成所有屬性集合的劃分

注意：該演算法使用了貪婪搜索，從不回溯重新考慮之前的選擇情況。

0x04 C4.5演算法

C4.5演算法是數據挖掘十大演算法之一，它是對ID3演算法的改進，相對於ID3演算法主要有以下幾個改進

  1. 用資訊增益比來選擇屬性
  2. 在決策樹的構造過程中對樹進行剪枝
  3. 對非離散數據也能處理
  4. 能夠對不完整數據進行處理

C4.5演算法與ID3演算法過程相似，僅在特徵選擇時，使用資訊增益比作為特徵選擇準則。

其偽程式碼如下：

0xFF 總結

一、ID3：

熵表示的是數據中包含的資訊量大小。熵越小，數據的純度越高，也就是說數據越趨於一致，這是我們希望的劃分之後每個子節點的樣子。

資訊增益 = 劃分前熵 – 劃分後熵。資訊增益越大，則意味著使用屬性 a 來進行劃分所獲得的 「純度提升」 越大 **。也就是說，用屬性 a 來劃分訓練集，得到的結果中純度比較高。

ID3 僅僅適用於二分類問題。ID3 僅僅能夠處理離散屬性。

二、C4.5：

C4.5 克服了 ID3 僅僅能夠處理離散屬性的問題，以及資訊增益偏向選擇取值較多特徵的問題，使用資訊增益比來選擇特徵。資訊增益比 = 資訊增益 / 劃分前熵 選擇資訊增益比最大的作為最優特徵。

C4.5 處理連續特徵是先將特徵取值排序，以連續兩個值中間值作為劃分標準。嘗試每一種劃分，並計算修正後的資訊增益，選擇資訊增益最大的分裂點作為該屬性的分裂點。

三、資訊增益 vs 資訊增益比：

之所以引入了資訊增益比，是由於資訊增益的一個缺點。那就是：資訊增益總是偏向於選擇取值較多的屬性。資訊增益比在此基礎上增加了一個罰項，解決了這個問題。

VirMach 便宜 VPS

QNews

QNews