決策樹依次詢問關於特徵的是非問題來作預測,每條問題把一個特徵與一個門檻比較。它是既非線性、又易於閱讀、求值成本又低的模型的標準例子,也是集成方法的基本單元。這裏的樹屬 CART 類型:二叉、軸向、貪心生長。本節與隨機梯度及線性分類器兩節互補,那兩節中擬合出的函數來自連續優化;樹則由組合式搜索構造,主要風險並非優化器不佳,而是過度擬合,並以剪枝加以控制。
樹、不純度與分割準則
定義 31.1.1
(軸向二叉樹及其預測)
樹把特徵空間劃分為若干區域,每片葉子對應一個。內部節點檢驗規則 (特徵下標 、門檻 ):滿足的觀測值去左子節點,其餘去右子節點。若葉子含訓練觀測值下標集 ,則分類時預測 中的多數類(並訂明固定的同分規則),回歸時預測均值 。
定義 31.1.2
(節點不純度與分割增益)
對含 個訓練點、各類比例為 的節點,基尼(Gini)不純度為 ,熵為 ()。一次分割把 個點送往左邊、 個送往右邊,兩邊都非空,其增益為
對兩類且第一類比例為 ,。樹的生長程序在每個節點選取增益最大的特徵與門檻,只考慮排序後相鄰且不同的特徵值之間的門檻,並遞歸下去,直至停止規則生效,例如節點純淨或節點大小達到下限。
概念視角組合
把基尼不純度看成分歧的概率
獨立地從節點中有放回地抽兩點,它們屬同一類的概率是 ,所以 就是兩點類別不同的概率。若 個點的類別計數為 ,則 個有序對中有 對類別相同、 對不同,故 。
定理 31.1.3
(分割永不增加不純度)
不純度函數 在概率單純形上是凹函數。因此對每次分割都有 ,且等號成立當且僅當左右兩邊的類比例都等於父節點的類比例。
證明
(基尼不純度的凹性)
函數 是線性函數平方之和,故為凸函數,所以 是凹函數。父節點的比例向量是兩個子節點向量的凸組合 。由 Jensen 不等式,,即 。平方函數嚴格凸,所以等號恰在 時成立,這時兩者都等於 。
等號的情形很重要:一次分割的增益可以為零,而更深的分割卻有用。
反例模式
增益為零就停止,會錯過異或模式
設想一個斷言:若根節點上沒有任何分割有正增益,繼續分割就不會有用。取四個點 ,標籤依次為 。根節點的類比例為 ,所以 。分割 把標籤 送往左邊、 送往右邊,兩個子節點的 都是 ,所以 ;分割 得到相同的值。因此「沒有正增益就停止」的規則只會輸出單一葉子,訓練誤差為 。但先按 分割,再在兩個子節點各按 分割,得到四片純淨葉子,訓練誤差為 。某一層的增益為零,只說明沒有任何單一問題能立刻帶來好處。修正的方法是改用其他停止準則,例如節點純淨或節點大小下限,再以剪枝控制樹的大小。
回歸樹
對數值響應,節點的不純度取為其關於節點均值的平方誤差和 。
定理 31.1.4
(均值最優,且分割增益有閉式)
對任意實數 ,,所以使平方誤差最小的葉值是均值。若一次分割把 分為非空的 與 ,大小為 ,,則
證明
(分割的方差分解)
把 寫成 ,並注意 ,即得第一個恆等式。把它分別應用於 (取 )與 (取 )並相加:。因為 ,有 與 。最後兩項之和為 。
證明透視
為何兩部分都以父節點均值重新對齊
證明中唯一不顯然的一步,是把單集恆等式用於 與 時,兩次都取同一個中心 ,而不是直接比較 與 。恆等式對每個 都成立,它的交叉項 會消失,因為一組數對自身均值的離差之和為零。共同的中心把 拆成 加兩項組間平方和,所以增益恰是組間平方和。關係 是父節點均值唯一被當作加權平均來用的地方;它使兩個偏差都是同一個差 的倍數,因子 即由此而來。定義 、 的均值需要它們非空;若其中一部分為空,增益為 ,與 一致。證明沒有用到分割是軸向的,也沒有用到它如何選出,所以對 的每一種二分都成立。
因子 表明,在均值差相同時,平衡的分割比只剝離一個點的分割獲得更大的增益。
代價複雜度剪枝
完全生長的樹可以精確擬合訓練數據,卻推廣不佳。代價複雜度剪枝對葉子數目施加懲罰。設樹 的葉集為 ,訓練誤差為 (誤分類比例或均方誤差),每片葉子的懲罰為 ,定義
對內部節點 ,以 表示把其下子樹 合併為單一葉子後的誤差,以 表示其葉子數目。
定理 31.1.5
(合併開始有利的門檻)
對 的子樹 ,把它合併為一片葉子會嚴格降低 ,當且僅當 ,其中
證明只需一行:合併使 改變 ,它為負恰當 。最弱連結剪枝反覆合併 最小的節點,每次合併後重新計算 ,得到一列嵌套的樹。 的取值,亦即這列樹中選哪一棵,應該用留出數據或交叉驗證來決定,而不是用訓練誤差。
例題
例題 31.1.6
(一維樣本上的基尼分割)
取 ,標籤為 。父節點有三個 ,所以 。候選門檻為 。門檻 給出由四個 組成的純淨左子節點,以及右子節點 ,其 ,。增益為 。門檻 給出六個點中有一個 的左子節點,,以及純淨的右子節點,所以 。其餘門檻更低: 分別為 。所以根節點在 處分割。
誤分類個數不能區分最好的兩個候選:兩者都恰留下一個錯誤。基尼增益偏好 的分割,因為它的純淨子節點較大(四個點而非兩個),使加權不純度更少。右子節點 在 上,,最佳分割在 ,分為 與 ,增益為 ;門檻 與 各自只得 。
例題 31.1.7
(一次回歸分割與一個剪枝序列)
取 ,。總均值為 ,。在 與 之間分割,得 與 ,均值分別為 與 ,各自 。增益為 ,而恆等式給出 。其他切分點的增益為 。
剪枝方面,設一棵含 個訓練點的樹,根下有兩棵子樹: 有 片葉子、 個錯誤,合併成一片葉子則有 個錯誤; 有 片葉子、 個錯誤,合併則有 個錯誤。若僅合併根得 個錯誤,則 ,,。最小的是 ,所以先合併 。此時樹有 片葉子,誤差為 ,故 ,根成為下一個最弱連結。合併根後只剩一片葉子,所以序列為:完整的樹、合併了 的樹,以及單一葉子。
例題 31.1.8
(同分、零增益門檻與純淨節點)
取 ,標籤為 。根節點 ,。門檻 給出純淨的左子節點 ,以及右子節點 ,其 ,所以 。由對稱,門檻 也得 。門檻 給出 與 ,各自 ,所以 :兩邊的類比例都等於父節點,正是定理的等號情形。最好的兩個門檻同分,需要固定的同分規則;取較小的門檻,根節點便在 處分割。
右子節點 的標籤為 ,。門檻 給出 與 ,增益 ;門檻 給出 與 ,兩邊都純淨,增益為 。所以在 處分割,三片葉子的預測為: 時 , 時 , 時 ,訓練誤差為 。每片葉子都純淨,;純淨節點的任何分割都有 ,又 ,所以該節點保持為葉子。
常見錯誤與細節
常見錯誤
(貪心增益、訓練誤差與樹序列很容易被誤解)
訓練誤差為零的樹不一定好。增益是貪心的:增益為零的分割仍可能需要,而最佳的第一次分割也未必屬於最佳的樹。以最小化訓練誤差來選 ,永遠得到完整的樹,因為最大的樹 最小;選擇必須使用獨立數據。分割門檻必須落在不同特徵值之間,否則分割可能把相等的輸入分開。最後,樹是不穩定的:數據的小改動可以改變根節點的分割,從而改變整棵樹。
常見錯誤
(子節點不純度必須按大小加權)
把兩個子節點的不純度不加權地取平均,會高估只剝離少數點的分割。設父節點兩類各有五個點,把一個第一類的點送往左邊,其餘 送往右邊。左邊 ,右邊 。未加權平均為 ,會讓人以為增益約為 。正確的加權增益是 。
練習
快速檢查
(某節點的類別計數為 。求其基尼不純度。)
把各類比例平方,再用一減去總和。
解答 · 答案
各類比例為 ,所以 。
快速檢查
(某節點兩類各有 個點。一次分割把 送往左邊、 送往右邊。計算增益。再計算異或樣本的根節點在單一特徵上分割的增益。)
每個子節點的不純度要乘以它佔全部點的比例。
解答 · 答案
父節點 。每個子節點 或 ,所以 ,加權子節點不純度為 。增益為 。對含四個點、兩類各兩個的異或樣本,父節點 ;按任一特徵分割,得兩個子節點,各含每類一個點,,所以增益為 。
快速檢查
(設按 排序後 。求父節點的 SSE、三種分割各自的增益,以及最佳分割。並以閉式核對其中一個增益。)
各部分的 SSE 要對它自己的均值計算。
解答 · 答案
均值為 ,父節點 SSE 為 。在第一個點之後分割,得 與 ,SSE 為 與 ,增益為 。在第二個點之後, 與 的 SSE 各為 ,增益為 。在第三個點之後, 的 SSE 為 , 為 ,增益為 。最佳分割在第二個點之後,增益為 。閉式核對:。
快速檢查
(節點 有 ,其子樹有 片葉子,。求 ,並說明在 與 時該節點是否被合併。)
比較 與 。
解答 · 答案
。 時保留子樹; 時合併。