網路上的決策樹教學大多都是教決策樹的大概念與何呼叫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!)