在上一個專題中，我們溫習了機率論與數理統計的秋招考點。本文將結合面試題目，詳細解釋機器學習專題中決策樹的考察重點和原理。
面試題 1：請簡述決策樹的原理
決策樹是一種樹結構，從根節點出發，每個分支都將訓練資料劃分成了互不相交的子集。分支的劃分可以以單個特徵為依據，也可以以特徵的線性組合為依據。決策樹可以解決迴歸和分類問題，在預測過程中，一個測試資料會依據已經訓練好的決策樹到達某一葉子節點，該葉子節點即為迴歸或分類問題的預測結果。
從機率論的角度理解，決策樹是定義在特徵空間和類空間上的條件機率分佈。每個父節點可以看作子樹的先驗分佈，子樹則為父節點在當前特徵劃分下的後驗分佈。
面試題 2：請寫出決策樹的虛擬碼
決策樹也是一種樹結構，我們可以以遞迴的方式構建決策樹。首先我們要定義兩個引數：
其中 D 代表訓練集，A 代表特徵集，即訓練集中一共有 n 個數據，每個資料都是一個 d 維向量。
決策樹的構建過程主要分為 3 步，下面將逐一介紹。
第一步
，先要將當前資料生成一個節點，在每次遞迴的時候，首先判斷當前節點是否可以作為葉子節點：即在當前節點是否中止樹的生長。
知識點 1. 決策樹中止條件：
判斷是否中止的條件可以分為兩大類：無需再分和無法再分。無需再分比較好理解，比如在分類問題中，當前節點下所有的資料都屬於同一分類（y 相同），那麼再分下去也沒有意義，自然無需再分；無法再分有多種情況：一種情況是特徵集合 A 中沒有特徵，所有的特徵都用完了。另一種情況是在當前的特徵空間下，所有的訓練資料都相同（x 相同）。還有一種情況：在一次切分之後某個子節點沒剩下任何資料，則無法再分。下面是第一步的偽程式碼表達：
def
TreeGenerate
（
D
，
A
）：
# 生成節點 D
generate
node
=
node
（
D
）
# 如果不能再分則返回
if
D
中樣本全屬於同一類別
：
將
node
標記為該類別
return
node
as
leaf
if
A
為空集
or
在特徵空間
A
上
D
中樣本取值均相同
：
將
node
標記為
D
中樣本數最多的類
return
node
as
leaf
if
D
中不包含任何樣本
：
將
node
標記為
D
的父節點中樣本最多的類
return
node
as
leaf
第二步
，選擇合適的特徵作為劃分子樹的屬性。如何從特徵空間中選擇一個或多個特徵作為劃分子樹的屬性涉及到 Decision Tree 不同的 cost function，這一部分內容將在下一題中詳述，在虛擬碼中，我們只需說明選擇一個最優屬性即可：
def
TreeGenerate
（
D
，
A
）：
# 生成節點 D
generate
node
=
node
（
D
）
# 如果不能再分則返回
if
D
中樣本全屬於同一類別
：
將
node
標記為該類別
return
node
as
leaf
if
A
為空集
or
在特徵空間
A
上
D
中樣本取值均相同
：
將
node
標記為
D
中樣本數最多的類
return
node
as
leaf
if
D
中不包含任何樣本
：
將
node
標記為
D
的父節點中樣本最多的類
return
node
as
leaf
從
A
中選擇最最佳化分屬性
a
*
第三步
，依據第二步劃分子節點，再遞迴求解子樹：
def
TreeGenerate
（
D
，
A
）：
# 生成節點 D
generate
node
=
node
（
D
）
# 如果不能再分則返回
if
D
中樣本全屬於同一類別
：
將
node
標記為該類別
return
node
as
leaf
if
A
為空集
or
在特徵空間
A
上
D
中樣本取值均相同
：
將
node
標記為
D
中樣本數最多的類
return
node
as
leaf
if
D
中不包含任何樣本
：
將
node
標記為
D
的父節點中樣本最多的類
return
node
as
leaf
從
A
中選擇最優劃分屬性
a
*
# 劃分子節點，遞迴求解子樹
for
a
*
中的每一個可能值
a_v
：
切分
D
使得
D_v
中的所有樣本
a
*
特徵下的值均為
a_v
TreeGenerate
（
D_v
，
A
去除
{
a
*
}）
這段虛擬碼中隱去了部分細節，比如如何求解每一步的最優劃分屬性，這些知識點將會在後面的面試題中詳細解釋。
面試題 3: 談談對資訊增益和資訊增益率的理解
資訊增益和資訊增益率，實際上就涉及到決策樹的 cost function，也就是上個題目中，每次尋找最優劃分屬性的方法。
知識點 1. 資訊熵：
資訊熵用來度量樣本集合的純度，公式如下：
資訊熵值越小，D 的純度越高。
知識點 2. 資訊增益：
資訊增益用來描述一次劃分之後純度的提升有多大。用不同的屬性劃分樣本，會得到不同的資訊增益。在 ID3 決策樹演算法中，我們取能使資訊增益最大，即劃分後純度提升最大的屬性作為當前決策樹的劃分屬性。
資訊增益的公式如下：
公式前一項為未劃分時的資訊增益，後一項為每個子樹的資訊增益乘以權重的和，權重的意義是使樣本數多的子節點更重要。
知識點 3. 資訊增益率：
使用資訊增益當作 cost function 會對
可取值數目較多
的屬性有所偏好，使用資訊增益率可以減小這種偏好。
IV 是屬性 a 的固有值，a 的可能取值數目越多（V 越大），IV（a） 的值通常越大，資訊增益率就會減小。
顯然資訊增益率偏好可取值數目少的屬性，不能直接使用它當作 cost function，在 C4。5 決策樹演算法中，先從侯選屬性裡找出資訊增益高於平均值的屬性們，再從中選取資訊增益率最高的。
面試題4：如何對決策樹剪枝？
剪枝是防止決策樹過擬合的方法。一棵完全生長的決策樹很可能失去泛化能力，因此需要剪枝。
知識點 1. 剪枝的策略：
剪枝分為
預剪枝
和
後剪枝
兩種，預剪枝是在構建決策樹時抑制它的生長，後剪枝是決策樹生長完全後再對葉子節點進行修剪。
知識點 2. 預剪枝：
預剪枝的方法有：
設定一個樹的最大高度/深度或者為樹設定一個最大節點數，達到這個值即停止生長
對每個葉子節點的樣本數設定最小值，生長時葉子節點樣本數不能小於這個值
判斷每次生長對系統性能是否有增益
方法 3 裡，對於一個決策樹，每次生長前，可以判斷生長後系統在驗證集上準確度是否提升，如果經過一次生長，系統在驗證集上的準確度降低了，那麼中止這次生長。
知識點 3. 後剪枝：
後剪枝方法是對一棵已經完全生長的決策樹進行剪枝
後剪枝的主要方法有：
錯誤率降低剪枝（Reduced-Error Pruning）
悲觀剪枝（Pessimistic Error Pruning）
代價複雜度剪枝（Cost-Complexity Pruning）
我們重點介紹第一種。錯誤率降低剪枝的方法比較直觀，從下至上遍歷所有非葉子節點的子樹，每次把子樹剪枝（所有資料歸到該節點，將資料中最多的類設為結果），與之前的樹在驗證集上的準確率進行比較，如果有提高，則剪枝，否則不剪，直到所有非葉子節點被遍歷完。
知識點 4. 預剪枝和後剪枝的優缺點比較：
時間成本方面，預剪枝在訓練過程中即進行剪枝，後剪枝要在決策樹完全生長後自底向上逐一考察。顯然，後剪枝訓練時間更長。預剪枝更適合解決大規模問題。
剪枝的效果上，預剪枝的常用方法本質上是基於貪心的思想，但貪心法卻可能導致欠擬合，後剪枝的欠擬合風險很小，泛化效能更高。
另外，預剪枝的有些方法使用了閾值，如何設定一個合理的閾值也是一項挑戰。
本文作者：宮業奇
宣告：本文歸 “力扣” 版權所有，如需轉載請聯絡。
