如何選擇𝛼αalpha在成本複雜性修剪中？
在接下來的講座樹方法中，他們在第 21 頁描述了一種用於成本複雜度修剪的樹算法。它說我們將成本複雜度修剪應用於大樹，以獲得最佳子樹序列，作為以下函數. 我最初的想法是我們有一套（IE. 然後我們計算每個集合的 K 折交叉驗證並選擇對應於最低的 K 折交叉驗證。
作為參考，我所指的 K 折交叉驗證在以下Cross-Validation的幻燈片 15 中進行了描述。
然而，經過一番思考和閱讀；我發現有一個定理，即通過最弱鏈接修剪經過的子樹序列將包含子樹. 在哪裡是最小化成本複雜性標準的子樹
在樹方法幻燈片 中的幻燈片 19 中進行了描述。 由於這個定理存在，我認為您可以推斷出每個定理的簡潔映射可能是合理的到最優子樹. 或者至少我們可以看到在一定的時間間隔內s 它將對應於特定的子樹。我在第 4 版的Elements of Statistical Learning book的第 308 頁上找到了這個定理。如果有人能闡明算法並且知道這樣的映射是否存在會有所幫助。
是的，確實存在這樣的映射，但它的用處不如預期。
總體目標是最小化成本複雜度函數 Cα(T)=R(T)+α|T|
在哪裡 |T| 是樹的葉子數 T 和 R(T) 在這些葉子上計算的損失函數。
第一步是計算子樹序列 T0⊇T1…⊇Tn−1⊇Tn 在哪裡 Tn 是僅由根節點組成的樹，並且 T0 整棵樹。
這是通過連續替換子樹來完成的 Tt 有根節點 t 帶有葉子（即折疊此子樹）。在每個步驟中，子樹 Tt 被選中，它使成本複雜度函數的降低最小化，因此是樹的最薄弱環節。
如公式：最小化 Cα(T−Tt)−Cα(T) =R(T−Tt)+α|T−Tt|−(R(T)+α|T|) =R(T−Tt)−R(T)+α(|T−Tt|−|T|) =1R(T)−R(Tt)+R(t)−R(T)+α(|T|−|Tt|+1−|T|) =R(t)−R(Tt)+α(1−|Tt|)
這正好是 0
α=R(t)−R(Tt)|Tt|−1
所以最小化 Cα(T−Tt)−Cα(T) 意味著最小化 α=R(t)−R(Tt)|Tt|−1
所以從整棵樹開始 T0 （和 α0=0 ) 在每一步 s 算法
- 選擇最小化的節點 t R(t)−R(Ts−1t)|Ts−1t|−1
- 放 Ts=Ts−1−Tt , αs=R(t)−R(Ts−1t)|Ts−1t|−1
直到樹只包含根節點。
因此，作為輸出，我們得到一系列子樹
T0⊇T1…⊇Tn−1⊇Tn
與相應的 α -價值觀
0=α0≤α1≤…αn−1≤αn
使用這些值可以定義一個映射 α 到子樹列表。
但
成本複雜度函數和損失/誤差函數是在訓練數據上計算出來的，因此存在自我驗證和過擬合的危險。正因為如此決賽 α 由交叉驗證確定。 2
計算在所有訓練數據上訓練的樹的子樹序列（在通過內部交叉驗證優化之前）至少給了我們一個可能的區間 α - 可供選擇的值。
資料來源：
- Alexey Grigorev解釋的成本複雜性修剪
- Kiran Bangalore Ravi、Jean Serra對隨機森林進行成本複雜性修剪
- 弗里德曼等人的統計學習要素。人
以上所有來源均指的是*Breiman, L.、Friedman, J.、Olshen, R. 和 Stone, C. (1984)。分類和回歸樹，紐約沃茲沃思。*不幸的是，我無法得到它。
附錄
(1)為什麼這是真的？
=R(T−Tt)−R(T)+α(|T−Tt|−|T|) =R(T)−R(Tt)+R(t)−R(T)+α(|T|−|Tt|+1−|T|)
用圖片更容易理解
讓我們看看 R(T−Tt)=R(T)−R(Tt)+R(t)
誤差/損失函數 R 在輸入樹的所有葉子上計算。轉型 T−Tt 折疊子樹 Tt 成一片葉子 t . 所以 R(T−Tt) 是
- R(T) （在所有葉子上）
- - R(Tt) （穿過“已移除”子樹的葉子 Tt )
- + R(t) （穿過新加入的葉子 t 子樹 Tt 已折疊到）
同樣的邏輯適用於計算葉子數量的部分。
(2)如何確定 α 通過交叉驗證？
我不確定這是否是佳能，但我會這樣做。
輸入：外圍交叉驗證提供的訓練數據
在整個訓練數據上訓練樹
計算子樹序列 S 和 α s A 去測試。
應用內部交叉驗證。對於每次運行：在內部交叉驗證提供的訓練數據上訓練樹
計算子樹序列
對於每個 α 在 A ，保留最小化的子樹 Cα(T)
在測試集上評估這些測試樹
選擇 α 基於內部交叉驗證的最佳性能
在序列中查找子樹 S 基於整個訓練數據構建 α
返回那個子樹
在斯坦福大學的一次講座中描述了類似的方法（從幻燈片 10 開始）。
