Python · 決策樹（三）· 節點

（這裡是本章用到的 GitHub 地址）

（這裡是本章用到的 Python 相關知識）

上一章我們把 node 的結構搭好了，這一章要做的就是塞東西進去。為此，我們不妨先看看我們需要實現什麼：

• 一個 fit 函數，它能夠根據輸入的數據遞歸生成一顆決策樹
• 一個 handle_terminate 函數，它在 node 成為 leaf 時調用，用於更新它爸爸和它爸爸的爸爸和……等等的信息
• 一個 prune 函數，用於剪枝
• 一個 view 函數，用於可視化

大提上來說就是這兩點，剩下的就是一些細節。我們分開來說說怎麼去實現它們

• fit 函數
• 先說一下大概的流程：
• 接受數據和相應的標籤

• 判斷該 node 是否應該被當做 leaf；若是，則 return，否則繼續往下走算出各維度的條件熵，記錄下最好的條件熵、信息增益和此時關注的數據維度
  比如說，如果輸入的數據和標籤為：
  那麼通過計算各個維度的條件熵和信息增益可知，此時該 node 關注的數據維度應該是第一維、也就是 A 對應的那一維。直觀來說，這意味著 A 提供的信息量最大（事實上在這個栗子中，A 和 Label 是一樣的）

• 根據信息增益判斷是否終止（比如在 ID3 中，如果信息增益小於閾值的話就直接終止。這種判斷方法會有比較嚴重的缺陷，觀眾老爺們可以想一想為什麼 ( σω)σ 【提示：異或數據集】）

• 根據所選的數據維度的各個特徵把數據集切分成幾份，分別餵給新的 node、遞歸，同時把這些 node 記錄在自己的 children 裡面

• 由於利用了遞歸，感覺還是一個比較乾淨利落的實現。下面就貼一些核心的代碼，完整的實現可以參見這裡
• 計算各個維度的條件熵和信息增益，這裡就要用到準則章節的東西了

  

• 遞歸

  

• handle_terminate 函數
• 如果童鞋們還記得我們 node 的結構的話，大概就會知道當一個 node 成為 leaf 後、需要做的事情有兩個：
  • 計算該 leaf 屬於哪一類
  • 更新它列祖列宗的 leafs 變數

  只要分別實現它們就好了：

  

  其中

  

• prune 函數
• 需要指出的是，node 的 prune 函數不是決策樹的剪枝演算法、而是會在決策樹的剪枝演算法中被調用。它僅僅是為了該 node 的所有子孫都切了而已（喂
• 先說說流程，核心思想其實就是把該 node 變成一個 leaf：

• 判斷該 node 應該屬於哪一類
• 把該 node 的 leafs 中的 leaf 從該 node 的列祖列宗中的 leafs 中刪除
• 把該 node 存進列祖列宗的 leafs 中
• 把該 node 自身及其所有子孫打上「已被剪枝」的標籤

• 接下來是實現：
  其中打標籤用的 self.mark_pruned 函數的定義如下：

• view 函數
• 基本思路很簡單：如果自己是 leaf、就直接輸出相關信息，否則在輸出自己相關信息的同時、還要調用自己所有 children 的 view 函數。以下是實現：

這一章有點長，稍微總結一下：

1. 決策樹的生長關鍵是靠遞歸。當 node 接收一個數據和標籤時，它會選出數據的某個維度、記錄下來，然後會根據該維度的各個特徵將數據、標籤進行劃分，分別餵給新的 node、從而能夠遞歸下去
2. 在 node 被判定應該是 leaf 時，要判斷它屬於哪一類並更新它列祖列宗的 leafs 變數
3. node 的 prune 函數是用來把 node 變成 leaf 並更新結構的，它本身不是決策樹的剪枝演算法、但它會在決策樹的剪枝演算法中被調用

下一章我們就要說說怎麼建立一個框架以利用這些 node 來搭建一顆真正的決策樹了。可能有童鞋已經敏銳地發現：不就只剩一個剪枝演算法沒有實現了嗎？

事實上正是如此。下一章的框架確實只額外地實現了剪枝演算法，剩下的都是封裝的活兒

希望觀眾老爺們能夠喜歡~

（猛戳我進入下一章！( σω)σ）