![[ML]在不使用package的情況下撰寫決策樹程式碼 – Feederboy – Medium](https://miro.medium.com/max/1200/1*Ca2OvU_ItlGVyr0MYLC9aw.png)
網路上的決策樹教學大多都是教決策樹的大概念與何呼叫API，卻沒有詳細說明決策樹的擬合是怎麼進行的。
我認為要徹底了解程式碼的最好方式，就是實際撰寫一遍。因此本文會在不呼叫API的情況下，撰寫出一個能夠進行擬合、預測的決策樹程式碼，並將此程式碼提供給讀者自行把玩。
決策樹的英文為decision tree，因為它就是由一連串的決策（如同if else）組成，並且結構像樹一樣。
決策樹是一種supervised learning（監督式學習），並且可以應用於classification或regression，本文會針對classification進行說明。
決策樹中的nodes可以被區分為以下兩種：
- Internal nodes:
Internal nodes中有決策，用來對輸入進行預測／分類。 - Leaf nodes:
Leaf nodes不做任何決策。若有資料經過決策（internal nodes）後分類到leaf nodes，Leaf nodes會給這筆資料一個預測數值／分類結果。
在講解演算法與程式碼之前，我先說明一些等等會使用到的名詞與意義：
資訊量
通常決策樹會使用Shannon entropy（熵）或者Gini impurity（吉尼不純度）來作為資訊量的計算。在此不細講計算方式，我們只需要知道所有可能發生的結果若機率分布較為平均、分散的話，會有較高的資訊量。反之，若機率分布較為集中的話，會有較低的資訊量。
💡 怎樣算是機率分布平均、分散？
以擲硬幣為例，擲硬幣的兩種可能結果（正面與反面）的機率都是50%，沒有其中一個機率比較高，這就是機率分布平均、分散。
反之，以買樂透為例，若只將結果分為中獎與沒中獎兩種的話（撇除中大獎與小獎的情況），中獎的機率會遠遠小於沒中獎的機率，這就是機率分布集中。
Information Gain
以下文字說明來自維基百科：
In general terms, the expected information gain is the reduction in information entropy Η from a prior state to a state that takes some information as given:
where H(T|a) is the conditional entropy of T given the value of attribute a.
看起來很複雜，接下來我一個一個解釋裡面的每個符號與意義。
- T 代表隨機變數
- H() 代表資訊量
- H(T) 代表在隨機變數T之下的資訊量
- H(T|a) 代表隨機變數T在條件a之下的資訊量
- IG(T,a) 代表在條件a之下，能夠獲得的資訊量
若是以樹的資料結構來看的話，H(T)代表父節點的資訊量，而H(T|a)代表被決策a的分割後的所有子節點的資訊量加總。而information gain IG(T,a)代表進行決策a所帶來的資訊量。
簡單的說，我們希望H(T|a)（也就是經過決策後的資訊量）越少越好，因為這樣代表決策a能夠獲得較多的資訊。而機率分布越不平均、越集中，資訊量越低。因此我們希望經過決策後機率分布會越集中。
藉由information gain，我們可以分析決策a是否能夠有效的區分預測結果。
本文會以不呼叫package的方式實現決策樹程式碼，以利讀者了解實際決策樹的擬合是如何實現的。
決策樹是一種貪婪演算法（greedy algorithm），擬合時會利用遞迴的方式，每次增加一個擁有最大information gain的節點。簡略流程如下：
- 確認是否還要繼續增加節點（為了避免overfitting，當決策樹的深度過深或者樣本數過少可以停止增加節點）。若不繼續增加節點則完成擬合。
- 若要增加節點的話，則選出一個information gain最大（最能夠讓分割後的資料機率分布越集中）的分割分方式。
Kaggle是一個數據分析的競賽平台，同時他也提供了線上撰寫／編輯程式碼的環境，基本的packages如numpy、pandas也都安裝好了。
點擊上方連結並且點選Copy & Edit（見下圖）就可以進入編寫環境了。可以自己研究一下程式碼，並嘗試修改參數把玩一下。
若瞭解了決策樹的程式碼後，可以參考scikit-learn這個package提供的API。會更能夠了解各個參數的意義。連結請點我
[Youtube]Decision Tree Classification in Python (from scratch!)
