開(kāi)學(xué)那會(huì)兒翻開(kāi)這本書(shū)的目錄第四章“決策樹(shù)”三個(gè)字平平無(wú)奇我甚至一度覺(jué)得它是最沒(méi)技術(shù)含量的一章——不就是if-else嵌套嗎直到用Python里的庫(kù)跑完幾個(gè)模型的對(duì)比又回頭啃了兩遍這章內(nèi)容才發(fā)現(xiàn)自己錯(cuò)得離譜。純啃公式的讀書(shū)筆記太多了這一篇我盡量換個(gè)講法不按原書(shū)章節(jié)順序走而是先把“一棵樹(shù)到底是怎么長(zhǎng)出來(lái)的”講明白再回到那些容易被跳過(guò)的難點(diǎn)上比如剪枝、連續(xù)值、缺失值、多變量樹(shù)。如果你也是正在啃這本書(shū)的初學(xué)者或者用了一段時(shí)間樹(shù)模型想看下底層邏輯這篇筆記應(yīng)該能幫你省不少力氣。1. 決策樹(shù)的核心邏輯一套“先問(wèn)哪個(gè)問(wèn)題”的分層篩選機(jī)制這一節(jié)在原書(shū)里屬于基礎(chǔ)鋪墊但很多人恰恰是在這里就開(kāi)始吃?shī)A生飯。決策樹(shù)的推理邏輯說(shuō)白了就是一句大白話遇到一個(gè)新樣本我不知道它屬于哪一類(lèi)就反復(fù)問(wèn)它“你的某個(gè)特征是什么”每問(wèn)一次縮小一圈候選范圍最后剩下來(lái)的類(lèi)別就是預(yù)測(cè)結(jié)果。這個(gè)過(guò)程放到數(shù)據(jù)結(jié)構(gòu)里就是一棵樹(shù)。頂部叫根節(jié)點(diǎn)中間每個(gè)判斷點(diǎn)叫內(nèi)部節(jié)點(diǎn)最底部不再繼續(xù)分叉的叫葉節(jié)點(diǎn)每個(gè)葉節(jié)點(diǎn)對(duì)應(yīng)一個(gè)決策結(jié)果。整棵樹(shù)的生成過(guò)程是從根節(jié)點(diǎn)開(kāi)始遞歸地“選屬性、分?jǐn)?shù)據(jù)、建子樹(shù)”直到數(shù)據(jù)被分隔得足夠純或者可用特征用完為止。書(shū)中給的基本流程里有兩個(gè)細(xì)節(jié)值得圈出來(lái)每一個(gè)非葉節(jié)點(diǎn)只挑一個(gè)最優(yōu)屬性劃分這個(gè)“最優(yōu)”是局部意義上的最優(yōu)決策樹(shù)整體并不保證全局最優(yōu)。遞歸終止有三個(gè)條件當(dāng)前節(jié)點(diǎn)樣本全屬于同一類(lèi)別當(dāng)前屬性集為空或所有樣本在剩余屬性上取值相同樣本集合為空。第三個(gè)條件容易被漏掉它對(duì)應(yīng)一種特殊處理——把父節(jié)點(diǎn)中樣本最多的類(lèi)別作為葉節(jié)點(diǎn)的標(biāo)記。這種“分而治之”的策略之所以幾十年不過(guò)時(shí)在于它和人類(lèi)的分類(lèi)認(rèn)知高度吻合。我拿生活中最常見(jiàn)的場(chǎng)景舉例你媽給你介紹對(duì)象對(duì)方資料擺在桌上你第一眼看的既不是學(xué)歷也不是收入而是“在不在一個(gè)城市”。見(jiàn)了面看“聊不聊得來(lái)”再往下看“有沒(méi)有存款”。每問(wèn)一個(gè)問(wèn)題都砍掉一批選項(xiàng)這就是一棵活脫脫的決策樹(shù)。樹(shù)模型的強(qiáng)項(xiàng)不是像線性回歸那樣給出一個(gè)光滑的連續(xù)打分而是把規(guī)則攤開(kāi)每一步都講得出理由——所以它在風(fēng)控、醫(yī)療診斷這類(lèi)需要解釋性的場(chǎng)景里依然是主力。這里的原書(shū)內(nèi)容我建議反復(fù)讀三遍核心不是背流程而是理解“遞歸”“劃分”“純度”這幾個(gè)詞背后到底對(duì)應(yīng)了什么操作。2. 屬性選擇到底在優(yōu)化什么信息熵、信息增益、增益率、基尼系數(shù)的來(lái)龍去脈如果決策樹(shù)生成過(guò)程是一臺(tái)機(jī)器那“選哪個(gè)屬性作為當(dāng)前節(jié)點(diǎn)”就是這臺(tái)機(jī)器的發(fā)動(dòng)機(jī)。書(shū)里真正難啃的第一塊硬骨頭就在這里——明明叫決策樹(shù)為什么非要扯上信息論里的“熵”。信息熵這個(gè)概念當(dāng)初也繞了我一陣。你把它理解成不確定性程度就對(duì)了。一箱球如果全是紅的閉著眼睛猜都能猜對(duì)熵為0如果五種顏色各占五分之一猜錯(cuò)概率高熵就大。公式是Ent(D) -Σ p(k) × log2(p(k))其中k是類(lèi)別下標(biāo)p(k)是第k類(lèi)樣本占比。這個(gè)公式不要求你會(huì)推導(dǎo)但要求你能說(shuō)出一個(gè)直覺(jué)含義熵越小數(shù)據(jù)越純。信息增益說(shuō)白了就是“劃分之前的不確定性”減去“劃分之后的不確定性”。Gain(D, a) Ent(D) - Σ(|Dv| / |D| × Ent(Dv))其中v是屬性a的各個(gè)取值。這個(gè)差值越大說(shuō)明用了這個(gè)屬性之后類(lèi)別變得更確定了那它就應(yīng)該被優(yōu)先拿來(lái)劃分。ID3決策樹(shù)就是按信息增益選屬性的。信息增益有個(gè)明顯毛病——它天然偏好取值數(shù)目多的屬性。比如你拿樣本編號(hào)當(dāng)屬性每個(gè)編號(hào)一個(gè)值信息增益直接拉滿但這顯然毫無(wú)泛化能力。為了掰回這種傾向C4.5改成用增益率公式是Gain_ratio(D, a) Gain(D, a) / IV(a)其中IV(a)是屬性a的固有值等于 -Σ(|Dv| / |D| × log2(|Dv| / |D|))。取值多的屬性IV值通常更大等于給信息增益做了個(gè)除法懲罰。但懲罰也不能太狠否則又會(huì)偏向取值少的屬性所以C4.5的做法是先挑信息增益高于平均水平的屬性再?gòu)睦锩孢x增益率最高的?；嵯禂?shù)又是另一套思路它不用熵的log運(yùn)算公式是Gini(D) 1 - Σ p(k)2。直觀含義是從數(shù)據(jù)集里隨便抽兩個(gè)樣本它們類(lèi)別不一致的概率。概率越小數(shù)據(jù)集越純。CART決策樹(shù)就是基于基尼指數(shù)來(lái)選劃分屬性的。我曾經(jīng)在項(xiàng)目里只盯著準(zhǔn)確率看對(duì)Node上的impurity不純度指標(biāo)毫不在意。后來(lái)遇到一棵深度夸張的樹(shù)打印出的結(jié)構(gòu)完全不符合業(yè)務(wù)直覺(jué)回頭排查才發(fā)現(xiàn)是不同節(jié)點(diǎn)用了不同的分裂標(biāo)準(zhǔn)模型庫(kù)默認(rèn)的配置和書(shū)上寫(xiě)的算法根本對(duì)不上。所以我建議你把這些數(shù)學(xué)指標(biāo)動(dòng)手算一遍——取一個(gè)20條樣本的小表分別用三種指標(biāo)算同一個(gè)屬性的得分你就知道它們的結(jié)果差在哪了。不親手算只看公式你永遠(yuǎn)記不牢。為了更直觀這里放一個(gè)我當(dāng)年手工推演的對(duì)照小表虛構(gòu)數(shù)據(jù)集“天氣、溫度、是否出門(mén)”劃分屬性信息增益增益率基尼指數(shù)按劃分后加權(quán)均值天氣0.2470.2860.350溫度0.1070.1390.408選擇結(jié)論選“天氣”若增益率比較仍可能偏向“天氣”選“天氣”不同指標(biāo)在大部分簡(jiǎn)單數(shù)據(jù)上結(jié)論一致但在特征取值數(shù)差異很大的數(shù)據(jù)集上ID3和C4.5會(huì)有明顯分歧。這也是為什么工程上更常用CART因?yàn)樗?jì)算快而且后面能直接對(duì)接梯度提升框架。3. 剪枝處理為什么樹(shù)不能任它長(zhǎng)到完美在我第一次用默認(rèn)參數(shù)訓(xùn)練決策樹(shù)時(shí)訓(xùn)練集的準(zhǔn)確率直逼100%一到測(cè)試集立刻掉到剛及格的水平。當(dāng)時(shí)的我把鍋甩給數(shù)據(jù)集太小后來(lái)讀了剪枝一節(jié)才恍然大悟——樹(shù)長(zhǎng)過(guò)頭了把訓(xùn)練集里的細(xì)枝末節(jié)全記下來(lái)了這種狀態(tài)叫過(guò)擬合。剪枝是決策樹(shù)對(duì)抗噪聲和過(guò)擬合的主要手段。書(shū)里講了兩種思路預(yù)剪枝和后剪枝。預(yù)剪枝的策略是邊構(gòu)建邊剪每次嘗試劃分一個(gè)節(jié)點(diǎn)時(shí)先用驗(yàn)證集估算一下如果這個(gè)劃分不做的精度再估算一下做了的精度只有后者更高才允許生成。它可以防止樹(shù)長(zhǎng)得太大減少訓(xùn)練時(shí)間但風(fēng)險(xiǎn)在于“只看一步”——當(dāng)前收益不高不代表后續(xù)幾步不會(huì)帶來(lái)更大收益。這種貪心式的近視眼可能會(huì)導(dǎo)致某些有潛力的分支還沒(méi)展開(kāi)就夭折了精度提升有限。后剪枝的策略是先讓你把那棵樹(shù)完整長(zhǎng)出來(lái)然后自底向上對(duì)每個(gè)非葉節(jié)點(diǎn)做手腳如果把以它為首的分支整個(gè)換成一個(gè)葉節(jié)點(diǎn)驗(yàn)證集精度不降反升那就果斷砍掉。這個(gè)方案保留了更多分支空間通常比預(yù)剪枝更能降低過(guò)擬合風(fēng)險(xiǎn)但代價(jià)是訓(xùn)練時(shí)間明顯增加。我曾拿一個(gè)中等規(guī)模的數(shù)據(jù)集做過(guò)對(duì)比用預(yù)剪枝生成的樹(shù)小了一半訓(xùn)練時(shí)間少了一大截但測(cè)試集精度比后剪枝低了三個(gè)多點(diǎn)?？梢?jiàn)“懶得多花時(shí)間”這種心態(tài)在機(jī)器學(xué)習(xí)里經(jīng)常要付出精度代價(jià)。書(shū)里還暗示了一個(gè)在實(shí)際建模時(shí)很重要、但寫(xiě)得比較含蓄的點(diǎn)剪枝用的驗(yàn)證集數(shù)據(jù)會(huì)參與“訓(xùn)練”嗎嚴(yán)格說(shuō)驗(yàn)證集參與了模型超參數(shù)的選擇也就是結(jié)構(gòu)的選擇這部分信息依然可能造成一定程度的間接過(guò)擬合。很多人在做交叉驗(yàn)證時(shí)會(huì)忽略這層耦合關(guān)系。我的習(xí)慣是如果數(shù)據(jù)量充足預(yù)留30%作為最終測(cè)試集剪枝只在內(nèi)部做交叉驗(yàn)證數(shù)據(jù)量緊張時(shí)寧可少剪幾刀也要保證測(cè)試集是“干凈”的。4. 連續(xù)值與缺失值處理容易被漏掉的工程細(xì)節(jié)如果說(shuō)剪枝是這章最容易丟分的主觀題那連續(xù)值和缺失值就是最容易被跳過(guò)的客觀題。很多人學(xué)完ID3、C4.5就覺(jué)得自己會(huì)決策樹(shù)了一上手遇到“年齡27.5歲”這種連續(xù)特征就愣住因?yàn)樾畔⒃鲆婺翘桌碚撃J(rèn)屬性是離散的。書(shū)里給的標(biāo)準(zhǔn)解法叫二分法思路極簡(jiǎn)屬性有N個(gè)不同取值就排序把相鄰取值的中間點(diǎn)作為候選劃分點(diǎn)把連續(xù)值變成“大于等于這個(gè)點(diǎn)”和“小于這個(gè)點(diǎn)”兩個(gè)離散塊然后按離散屬性去算信息增益。注意連續(xù)值特征可以被多次使用不同層次的節(jié)點(diǎn)可以在不同切分點(diǎn)上重復(fù)利用它這一點(diǎn)和離散屬性“用一次就不能再用”完全不同。這一節(jié)還有一處對(duì)小白尤其不友好就是缺失值的處理。訓(xùn)練集里如果某條樣本缺少了當(dāng)前劃分屬性上的取值既不能直接扔掉樣本太少會(huì)浪費(fèi)信息也不能隨便填個(gè)均值會(huì)引入噪聲。書(shū)里給出的方案是找劃分屬性時(shí)用無(wú)缺失值樣本作為子集計(jì)算信息增益再按缺失樣本比例折算。某個(gè)樣本在劃分屬性上缺失時(shí)把它按不同權(quán)重劃分到所有子節(jié)點(diǎn)權(quán)重和樣本落入子節(jié)點(diǎn)的比例相關(guān)。權(quán)重機(jī)制貫穿始終每個(gè)樣本初始權(quán)重為1缺失值樣本每次劃分都按比例更新權(quán)重最后被用于葉節(jié)點(diǎn)的類(lèi)別統(tǒng)計(jì)。這個(gè)機(jī)制讀起來(lái)很容易被繞暈我建議你在紙上畫(huà)一個(gè)只有10條數(shù)據(jù)的小例子手動(dòng)走一遍“1號(hào)樣本缺失顏色特征”時(shí)的權(quán)重流動(dòng)過(guò)程比看十遍公式都管用。真要在具體庫(kù)中處理時(shí)實(shí)現(xiàn)略有差異但思路相同處理好缺失值后模型對(duì)比才有意義。5. 從單棵樹(shù)到一片森林這本書(shū)埋下的進(jìn)階線索CART樹(shù)在實(shí)踐中的使用是深度學(xué)習(xí)中也會(huì)用到的構(gòu)件。因?yàn)槿魏位跊Q策樹(shù)的集成方法除了極少數(shù)情況外都需要在每一輪迭代中擬合一棵樹(shù)這棵樹(shù)的分裂質(zhì)量直接決定了集成的上限。所以看第四章的時(shí)候多留一個(gè)心眼底層邏輯扎實(shí)了后面學(xué)梯度提升時(shí)會(huì)順利得多。在此之前你手頭的工具配置就可以先跑通了。裝好環(huán)境后隨便找一個(gè)公開(kāi)的表格數(shù)據(jù)比如鳶尾花、泰坦尼克用默認(rèn)參數(shù)擬合一棵CART樹(shù)再打印出樹(shù)結(jié)構(gòu)圖你會(huì)對(duì)“劃分”“純度”“葉節(jié)點(diǎn)樣本數(shù)”這些詞有非常直觀的認(rèn)知。不用急著調(diào)參主要為了建立體感讓博士式的符號(hào)變成看得見(jiàn)的圖形。剪枝在庫(kù)中通常由成本復(fù)雜度參數(shù)控制數(shù)值越大、樹(shù)被砍得越狠可以簡(jiǎn)單地把這個(gè)參數(shù)理解成后剪枝力度的一種實(shí)現(xiàn)。這部分再往后就是調(diào)參藝術(shù)了。6. 多變量決策樹(shù)線性的根邏輯的葉這一節(jié)在初讀時(shí)很容易被當(dāng)成“選讀內(nèi)容”掠過(guò)但它其實(shí)回答了一個(gè)關(guān)鍵問(wèn)題——決策樹(shù)的分類(lèi)邊界為什么總是橫平豎直的普通決策樹(shù)在每個(gè)節(jié)點(diǎn)只做單屬性判斷學(xué)到的分類(lèi)邊界是軸平行的也就是和坐標(biāo)軸垂直的線。如果真實(shí)數(shù)據(jù)的最優(yōu)邊界是斜的普通決策樹(shù)就尷尬了——它必須用一堆階梯狀的折線去反復(fù)逼近那條斜線樹(shù)深直接翻倍泛化能力自然受影響。多變量決策樹(shù)的想法是一個(gè)節(jié)點(diǎn)的劃分不用單個(gè)屬性而用多個(gè)屬性的線性組合。每個(gè)非葉節(jié)點(diǎn)維護(hù)一組系數(shù)相當(dāng)于在以這些屬性為坐標(biāo)的空間中畫(huà)一條任意方向的斜線作為邊界。這樣針對(duì)斜向分布的類(lèi)別樹(shù)不用長(zhǎng)很高就能分開(kāi)。書(shū)的第四章在這里點(diǎn)到為止但對(duì)讀后續(xù)章節(jié)很重要因?yàn)楹芏嗉赡Ｐ椭械碾S機(jī)特征子空間、線性樹(shù)等概念都能從這里找到思想源頭。我在工作中用到的調(diào)參和模型融合方案也是基于這種思路做一些組合特征。比如給決策樹(shù)喂一些手工構(gòu)造的“組合后特征”而非原始單特征往往能顯著壓縮樹(shù)深度。這也算是多變量樹(shù)思想在工程里的“窮人手寫(xiě)版”吧。7. 動(dòng)手實(shí)現(xiàn)一版迷你決策樹(shù)從零開(kāi)始不長(zhǎng)篇大論這章的筆記如果看完就散那確實(shí)太可惜了。建議用最精簡(jiǎn)的方式在十幾分鐘內(nèi)把核心跑通我寫(xiě)過(guò)一版簡(jiǎn)化實(shí)現(xiàn)核心偽代碼如下函數(shù) 生成節(jié)點(diǎn)(樣本集D, 屬性集A): 如果 D 全部屬于同一類(lèi): 返回葉節(jié)點(diǎn) 如果 A 為空 或 D 在A上取值相同: 返回葉節(jié)點(diǎn)標(biāo)記為 D 中最多的類(lèi) 對(duì)每個(gè)屬性 a in A: 計(jì)算按 a 劃分后的純度指標(biāo) 選出最優(yōu)屬性 best_a 創(chuàng)建節(jié)點(diǎn) node標(biāo)記為 best_a 對(duì) best_a 的每個(gè)取值 v: 子集 Dv D 中 best_a v 的樣本 如果 Dv 為空: 創(chuàng)建葉節(jié)點(diǎn)標(biāo)記為 D 中最多的類(lèi) 否則: 遞歸調(diào)用 生成節(jié)點(diǎn)(Dv, A \ {best_a})這里最有價(jià)值的是條件“D在A上取值相同”。很多人實(shí)現(xiàn)時(shí)會(huì)漏掉它導(dǎo)致遞歸無(wú)限循環(huán)——所有樣本在剩余屬性上完全一樣了再往下分已經(jīng)不可能但代碼意識(shí)不到還在硬選屬性。等你寫(xiě)代碼親自踩一次這個(gè)坑就知道書(shū)中為什么特意加這個(gè)終止條件了。寫(xiě)完這個(gè)骨架后再跑一下剪枝對(duì)比課堂味和工程味就都有了。8. 筆記之外結(jié)合實(shí)戰(zhàn)的三個(gè)提醒很多人在讀書(shū)筆記階段非常認(rèn)真但一到自己的數(shù)據(jù)集上就陷入“默認(rèn)參數(shù)流”。決策樹(shù)模型的有效性并不取決于那個(gè)“魔力參數(shù)”被調(diào)得有多準(zhǔn)而取決于數(shù)據(jù)和模型的匹配度。針對(duì)樹(shù)的調(diào)優(yōu)我個(gè)人的經(jīng)驗(yàn)有以下幾點(diǎn)樹(shù)的深度和葉子節(jié)點(diǎn)最小樣本數(shù)比分裂標(biāo)準(zhǔn)對(duì)結(jié)果影響大得多。設(shè)置葉子節(jié)點(diǎn)最小樣本數(shù)可以連續(xù)抑制過(guò)擬合比每次調(diào)裁剪復(fù)雜度參數(shù)更易解釋。特征數(shù)值范圍敏感度低但特征重要性會(huì)被取值多的特征帶偏。決策樹(shù)的信息增益偏好會(huì)在真實(shí)數(shù)據(jù)中導(dǎo)致偏差用C4.5思路先算增益均值再選增益率最大往往比直接調(diào)默認(rèn)參數(shù)更穩(wěn)。樹(shù)模型天然適合處理混合類(lèi)型特征但前提是把缺失值編碼成顯式狀態(tài)而不是全部填成-1或者0。缺失本身可能是重要的信號(hào)。書(shū)里不會(huì)告訴你的是同樣的超參數(shù)在數(shù)據(jù)量變化超過(guò)一個(gè)數(shù)量級(jí)之后需要完全重調(diào)。樹(shù)的復(fù)雜度本質(zhì)上由樣本密度決定樣本越多樹(shù)越有空間長(zhǎng)深。我在多個(gè)項(xiàng)目中的保守做法是先固定一個(gè)合理的葉子最小樣本數(shù)再通過(guò)交叉驗(yàn)證選擇深度和特征數(shù)量并把這種配置寫(xiě)入項(xiàng)目記錄中。沒(méi)有記錄不清的調(diào)參經(jīng)驗(yàn)跟過(guò)擬合有什么區(qū)別9. 回頭看這一章到底教會(huì)了什么第四章看上去信息量巨大把原始樹(shù)的誕生過(guò)程拆開(kāi)來(lái)看不過(guò)幾年時(shí)間沉淀下來(lái)的幾個(gè)經(jīng)驗(yàn)找最有區(qū)分度的特征、控制生成規(guī)模、容忍真實(shí)數(shù)據(jù)的臟亂、必要時(shí)允許邊界傾斜。如果把這本書(shū)當(dāng)作一本“手藝集”第四章就是最核心的入門(mén)工具章。讀完筆記之后別忘了回原書(shū)看每個(gè)小節(jié)最后的小結(jié)和習(xí)題。習(xí)題雖少但每道題都值得認(rèn)真推理尤其是那些要求你“用公式計(jì)算”的題——不親手算一遍你真的會(huì)以為自己懂了。這一章讀完之后再往后看神經(jīng)網(wǎng)絡(luò)、支持向量機(jī)這些黑箱模型時(shí)你會(huì)多一個(gè)對(duì)比參照黑箱模型犧牲了可解釋性換來(lái)了表達(dá)復(fù)雜邊界的能力而決策樹(shù)一直堅(jiān)持把決策攤在臺(tái)面上代價(jià)是邊界表達(dá)受限。沒(méi)有十全十美的模型只有適不適合你當(dāng)前場(chǎng)景的選擇。就我個(gè)人而言很多模型上線后最煎熬的環(huán)節(jié)就是向業(yè)務(wù)方解釋預(yù)測(cè)邏輯每到這種時(shí)候我都會(huì)懷念決策樹(shù)的直白。