決策樹建立
在Q23中，我們提及決策樹的分類、基本建構步驟、三種典型的決策樹演算法。
決策樹模型不只可以做分類也可以做回歸，分類就是樹模型的每個葉子節點代表一個類別；回歸則是根據特徵向量來決定對應的輸出值。回歸樹就是將特徵空間劃分成數個單元，每個劃分單元有個特定的輸出。對於測試數據，只要按照特徵將其歸到某個單元，就能得到對應的輸出值。
在本文中，將針對特徵選擇、剪枝，介紹該如何依目前已有的樣本資料，來建立決策樹。
決策樹分類過程
1、特徵選擇
從訓練數據中眾多特徵中選擇一個「特徵」作為節點的分裂標準。而如何選擇特徵有不同的量化評估標準，會產生不同的決策算法。
2、決策樹生長
依據選擇的特徵評估標準，從上至下的生成子節點，直到數據集不可分類，則決策樹停止生長。在決策樹中，所有的特徵均為離散值，如果某個特徵是連續的，需要先將它離散化。
3、剪枝
由於決策樹容易過擬合，一般需要剪枝，縮小樹結構的規模，來緩解過擬合。剪枝技術有兩種：預剪枝、後剪枝。
以下將針對三個分類過程，進行介紹。
特徵選擇
我們要選一個合適的特徵，作為判斷節點。才能快速分類，減少決策樹的深度。由於決策樹的目標，是把資料集按照相對應的類型標籤，進行分類。
通常最理想的狀況是，透過「特徵選擇」把不同類別的資料集，貼上對應的類型標籤。特徵選擇的目標，會讓分類後的資料集較單純。
而該如何衡量一個資料集的純度呢？
需要引入「資料純度函式」，以下介紹兩種函示。
1、資訊增益 Information Gain
是特徵選擇中的一個重要指標，它的定義是，一個特徵能為分類系統帶來多少資訊，資訊越多，該特徵就越重要。
而資訊熵 (Information entropy) ，表示的是不確定度。熵是指接收的每則消息中，包含的資訊平均量，為不確定性的量度。在均勻分佈時，不確定度最大，此時，熵就最大。
當選擇某個特徵對資料集進行分類時，分類後的資訊熵會比分類前的小，其差值表示為資訊增益。資訊增益可以衡量某個特徵對分類結果的影響大小。
構建決策樹時，根據給多少樣本資料集，選擇某個「特徵值」作為樹的節點。在資料集中，可以計算出該資料中的資訊熵。
在資料集中，可以計算出該資料中的資訊熵，計算如下：
作用後的資訊熵計算公式
- D：訓練資料集，表示目前的數據集合。
- c：資料類別數，表示當前數據集合中的第c類，也就是我們目標變量的類型。
- Pi：表示類別 i 樣本數量佔所有樣本的比例。
對應資料集D，若選擇特徵 A 作為決策樹判斷節點時，在特徵 A 作用後的資訊熵就是 Info(D)，計算如下：
作用後的資訊熵計算公式
其中 k 表示樣本 D被分為 k 個部分。資訊增益表示資料集 D 在特徵 A 的作用後，其資訊熵減少的值。公式如下：
資訊熵差值計算公式
對於決策樹節點最合適的特徵選擇，就是 Gain(A) 值最大的特徵。
2、吉尼係數 Gini coefficient
是經濟學中用來衡量一個「國家收入差距」的常用指標。是另一種資料的不純度的度量方法，它的公式是：
吉尼係數計算公式
- c：資料集中類別的數量
- Pi：類別 i 樣本數量佔所有樣本的比例
從此公式可以得知，當資料集中資料混合的程度越高，吉尼係數也就越高。當資料集 D 只有一種資料型別，那吉尼係數的值為最低 0。
如果選取的屬性為 A，那麼分裂後的資料集 D 的吉尼係數的計算公式為：
分裂後的吉尼係數計算公式
其中 k 表示樣本 D 被分為 k 個部分，資料集 D 分裂成為 k 個 Dj 資料集。
對於特徵選取，需要選擇最小的分裂後的吉尼係數。也可以用吉尼係數的「增益值」作為決策樹選擇特徵的依據。公式如下：
吉尼係數差值計算公式
在決策樹選擇特徵時，應選擇吉尼係數增益值最大的特徵，作為該節點分裂條件。
接下來談談「剪枝」。
剪枝
在分類模型建立的過程中，很容易出現過擬合的現象。
過擬合是指擬合了每個數據，反而丟失要的規律，使用擬合結果去預測另一個訓練集時誤差會更為明顯。這個意思就是說，在模型學習訓練中，訓練樣本達到非常高、逼近精度，但對檢驗的樣本逼近誤差，卻隨著訓練次數，而呈現「先下降，後上升」現象。過擬合時，訓練誤差很小，但是檢驗誤差很大，非常不利於實用。
但我們可以透過剪枝，來處理決策樹的過擬合現象。剪枝分為：預先剪枝、後剪枝，這兩種方式。
1、預先剪枝
在決策樹生長過程中，會使用一定條件加以限制，讓決策樹在完全擬合之前，就停止生長。預先剪枝的判斷方法有很多種，如：資訊增益小於一定閥值時，透過剪枝使決策樹停止生長。
但如何確定一個合適的閥值也需要一定的依據，閥值太高會讓模型擬合不足，閥值太低又讓模型過擬合。
- 限制樹的深度
- 最小節點樣本數
- 最大葉子節點數
- 限制信息增益的大小
2、後剪枝
後剪枝是在決策樹生長完成後，自根部向上的方式來修剪決策樹。透過使用交叉
後剪枝有兩種方式，一種用新的葉子節點替換子樹，此節點的預測類由子樹資料集中的多數類決定。另一種用子樹中最常使用的分支代替子樹。
這兩種剪枝方式的差異在於，後剪枝比預剪枝保留了更多分支。預先剪枝可能過早的終止決策樹的生長，後剪枝反而能夠產生比較好的效果。但後剪枝在子樹被剪掉後，決策樹生長的一部分計算也會消失。
建模過程的補充
1、決策樹為什麼容易過擬合？
決策樹的生長過程中，透過不斷分支，將樣本實例劃分到合適的單元，當樣本中存在噪聲，即可能是特徵值觀測誤差或者標籤值觀測誤差，讓分支歸節點的時候產生矛盾，這時決策樹選擇繼續生成新的分支，來產生更「完美」的葉子節點，這就是由於噪音數據帶來的誤生長的分支，讓訓練變得更加優越，而泛化能力下降。
* 泛化 Generalization
意思是設計模組可以應對未來的數據，
也就是可以被廣泛使用卻仍在模型範圍內，
也就是他的適應性很好，這就是泛化。
2、決策樹出現過擬合的原因
- 決策樹在構建過程中，對決策樹生長沒有進行合理的限制
- 在建模過程中使用較多的輸出變量
- 樣本中有一些噪聲數據，噪聲數據對決策樹的構建影響很多
緯育TibaMe已經有10萬人次來學習AI/資料科學知識或技術，若你想進一步了解或學習 AI / 資料科學的相關知識或技能，歡迎來TibaMe 👉 https://bit.ly/3o4N39e
每日5分鐘， 提拔我園丁陪你快速添補AI/資料科學知識與技能。
若您想了解更多AI/資料科學的小知識、及各產業的相關應用，歡迎訂閱TibaMe FB及部落格，或你有其他想了解的主題歡迎在下方留言讓我們知道唷！
參考資料