在上一個專題中,我們溫習了機率論與數理統計的秋招考點。本文將結合面試題目,詳細解釋機器學習專題中決策樹的考察重點和原理。
面試題 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. 預剪枝和後剪枝的優缺點比較:
時間成本方面,預剪枝在訓練過程中即進行剪枝,後剪枝要在決策樹完全生長後自底向上逐一考察。顯然,後剪枝訓練時間更長。預剪枝更適合解決大規模問題。
剪枝的效果上,預剪枝的常用方法本質上是基於貪心的思想,但貪心法卻可能導致欠擬合,後剪枝的欠擬合風險很小,泛化效能更高。
另外,預剪枝的有些方法使用了閾值,如何設定一個合理的閾值也是一項挑戰。
本文作者:宮業奇
宣告:本文歸 “力扣” 版權所有,如需轉載請聯絡。