Python · 決策樹（一）· 準則

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

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

這一章主要打算用大白話說一下決策樹是什麼，然後介紹一個演算法中的核心輔助結構——Cluster 的實現（我也不知道中文叫什麼我也不知道為什麼當初腦子裡第一個蹦出來的就是這個名字）（逃）

決策樹，顧名思義，就是用來決策的樹（廢話）。可以這樣去想一個決策樹的決策過程：

1. 輸入一個數據
2. 根據數據的某個特徵來把數據分成好幾份
3. 如果分完數據後發現
1. 某堆數據裡面某一個類別的數據占相當大多數，就不再分隔這堆數據、直接輸出類別
2. 某堆數據還很「混亂無序」，那麼就這堆數據就要繼續分下去（轉第 2. 步）

我們同時還可以發現，這個過程是個遞歸過程。通俗點來說，就是整個過程都是對同一類物體做的同一系列操作

以上兩個發現對應著兩個核心。這一章我們就先講第一個核心——準則

常見的準則有兩種，分別是熵和 Gini 係數。它們的定義可以參見這篇文章，這裡就主講實現（Again，我會先講一個相對樸素的實現，而把支持樣本權重的版本放在後面）：

1. 預處理數據，準備好接下來可能要用到的變數

   

   其中：
1. 輸入的 data 是維的；n 代表有 n 個數據，d 代表有 d 個維度
2. 輸入的 labels 是標籤向量
3. Counter 是內置庫的功能，用於數 labels 中各個類別的出現次數
4. base 是計算熵的時候對數的底，基本可以不管
2. 熵與條件熵
1. 利用 labels 和 counters 計算熵

   

   這裡支持用戶自己輸入各類別的出現次數；如果沒有輸入，就用內置的類別次數代替

   eps 則是為了數值穩定
2. 利用上述 ent 函數計算相對熵（建議先知道定義是什麼再看……）

   

   看上去很複雜，其實就四點：
1. 獲取指定維度數據的所有特徵
2. 根據這些特徵將原數據切分成若干份
3. 將這幾份數據分別餵給一個 Cluster 並利用上面第 1. 步定義的 ent 函數算出熵
4. 把這些熵按定義弄出一個條件熵
3. Gini 係數，這個實現起來比較方便、因為形式比較簡單

   

   同樣支持用戶自己輸入各類別的出現次數

4. 信息增益。這是決策樹生長的重點，但有了上面兩個函數之後，根據定義的話、直接條件熵減去熵就行（或者更寬泛地說、是混亂程度減去條件混亂程度），最多再做一些小的改動。相信聰明的觀眾老爺們可以輕鬆地完成最樸素的實現，所以在這裡我就不細講怎麼定義 info_gain 了，等到講比較複雜的模型時再補吧~
   順便也可以當做作業和練習呢~
   其實主要是因為懶呢~（被 pia 飛）

   ========== 更新 ==========

   這裡提供一個根據 ID3 演算法的信息增益實現，C4.5 和 CART 的話會在後面講~

   

   相當直觀吧 ( σω)σ

那麼以上就把準則的實現大概說明了一下，接下來就要處理第二個核心問題——遞歸生成、裁剪我們的決策樹了

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

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