Python · 決策樹（四）· 樹

========== 2017.1.11 更新 ==========

今天抽時間用 cv2 寫了一個決策樹的可視化

========== 分割線的說 ==========

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

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

這一章就是樸素實現的最後一章了，我們會在這一部分搭建一個比較完整的決策樹框架

上一章我們也提過，我們主要還需要做的只有一個：剪枝

同樣的，為了簡潔（懶），我們採用普通的剪枝演算法：

• 取出待剪枝的節點

  

• 根據定義計算剪枝前（_old）的混亂程度和剪枝後（_new）的混亂程度

  

• 選出剪枝後混亂程度降低的 node、調用 node 的 prune 函數來剪枝、剪枝後把被剪掉的 node 從備選 node 列表中刪去、然後再次調用整個決策樹的剪枝演算法

這些就是剪枝演算法的全部了，不知是否比你想像中的要簡潔一些？當然了、這是通過犧牲效率來換取的簡潔，好的做法應該是：

• 找到決策樹「從下往上」的次序
• 依次判斷每個 Node 是否應該剪枝

這樣做的話演算法複雜度會降低不少、但實現起來也會稍微複雜一點。如果有時間的話（嘖）會在後序章節中進行補充

最後放一下在數據集上運行的結果。在 Python · 決策樹（零）· 簡介 這一章中，我用到了這麼兩張圖：

它們其實都是在另一種剪枝演算法下的最終結果。如果按這一章的演算法（令懲罰因子 alpha = 1）來做，最終結果是這樣的：

以上及之前的各章節加總即是一個比較樸素的決策樹的所有實現，它有如下功能：

• 支持任意形式的離散數據、不必將數據預處理成數值形式

• 支持可視化最終的決策樹模型
• 支持通過準確率來評估模型的好壞

========== 分割線的說 ==========

這不算是一個很完善的決策樹、但基本的雛形已經有了，而且由於抽象做得比較好、它的可拓展性會比較強。接下來（如果有時間的話）我們會繼續做如下事情：

• 利用 np.bincount 來加速我們的演算法
• 讓我們的決策樹支持輸入樣本權重和支持連續型特徵
• 將 C4.5 演算法整合到這個框架中

• （爭取）把 CART 演算法也整合到這個框架中

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