決策樹(shù)這個(gè)家族乍一看像是機(jī)器學(xué)習(xí)教材里最樸素的一章真到動(dòng)手寫(xiě)代碼、調(diào)參、處理真實(shí)臟數(shù)據(jù)的時(shí)候你會(huì)發(fā)現(xiàn)它比很多花哨的模型更考驗(yàn)基本功。CART、ID3、C4.5這三個(gè)名字幾乎每一本講機(jī)器學(xué)習(xí)的書(shū)都會(huì)提到但真正把三者放在一起對(duì)比、把分裂準(zhǔn)則的數(shù)學(xué)推導(dǎo)講透、再手寫(xiě)一遍Python實(shí)現(xiàn)的資料并不多。我當(dāng)初學(xué)這塊的時(shí)候最大的困惑不是信息增益是什么而是為什么ID3偏愛(ài)取值多的特征C4.5的增益率到底怎么修正CART的基尼指數(shù)和熵到底差在哪連續(xù)值和缺失值分別怎么處理。這些問(wèn)題教材往往一筆帶過(guò)但實(shí)際寫(xiě)代碼時(shí)全是坑。這篇內(nèi)容就是把我自己從零實(shí)現(xiàn)這三個(gè)算法的完整過(guò)程整理出來(lái)包括分裂準(zhǔn)則的數(shù)學(xué)原理、連續(xù)特征離散化的細(xì)節(jié)、剪枝策略的取舍、以及一份可以直接跑起來(lái)的Python代碼。適合已經(jīng)了解決策樹(shù)基本概念、想深入理解三種算法差異、并且希望自己動(dòng)手實(shí)現(xiàn)一遍的讀者。哪怕你只是想在面試前把這三個(gè)算法的區(qū)別理清楚這篇也能幫你把底層邏輯串起來(lái)。全文會(huì)圍繞為什么這么設(shè)計(jì)展開(kāi)而不是只丟結(jié)論因?yàn)闆Q策樹(shù)這塊理解了動(dòng)機(jī)代碼自然就寫(xiě)出來(lái)了。1. 三種算法的整體設(shè)計(jì)思路與選型邏輯1.1 決策樹(shù)的本質(zhì)用一系列if-else把空間切開(kāi)決策樹(shù)的核心思想其實(shí)特別樸素給定一堆樣本每個(gè)樣本有若干特征和一個(gè)標(biāo)簽我想通過(guò)一連串如果特征A大于某值就走向左邊否則走向右邊的判斷把樣本逐步分到足夠純的子集里。每一次判斷就是一個(gè)內(nèi)部節(jié)點(diǎn)最終的分類(lèi)結(jié)果就是葉子節(jié)點(diǎn)。整棵樹(shù)本質(zhì)上就是一堆嵌套的if-else規(guī)則這也是它最大的優(yōu)點(diǎn)——可解釋性強(qiáng)白盒模型業(yè)務(wù)方看得懂。但問(wèn)題來(lái)了一個(gè)特征可能有無(wú)數(shù)種切法我到底該選哪個(gè)特征、按哪個(gè)閾值來(lái)切這就是三種算法的核心分歧所在。ID3、C4.5、CART的差別說(shuō)到底就是如何衡量一次分裂的好壞以及樹(shù)長(zhǎng)成什么樣這兩件事上的不同選擇。理解了這一點(diǎn)后面所有的細(xì)節(jié)都是圍繞這個(gè)核心展開(kāi)的。我習(xí)慣把決策樹(shù)的構(gòu)建拆成三個(gè)問(wèn)題第一選哪個(gè)特征分裂分裂準(zhǔn)則第二什么時(shí)候停止分裂停止條件第三怎么防止過(guò)擬合剪枝。三種算法在這三個(gè)問(wèn)題上的答案各有側(cè)重下面逐個(gè)拆解。1.2 ID3用信息增益選特征簡(jiǎn)單但偏心ID3Iterative Dichotomiser 3是最早的一批決策樹(shù)算法它的分裂準(zhǔn)則用的是信息增益。信息增益的直覺(jué)是如果我按某個(gè)特征把數(shù)據(jù)集切開(kāi)之后整體的混亂程度下降得越多說(shuō)明這個(gè)特征越有用。衡量混亂程度用的是信息熵公式是$$H(D) -\sum_{k1}^{K} p_k \log_2 p_k$$其中 $p_k$ 是第 $k$ 類(lèi)樣本在數(shù)據(jù)集 $D$ 中占的比例。熵越大越混亂熵為0表示完全純凈。信息增益就是父節(jié)點(diǎn)的熵減去按某特征分裂后各子節(jié)點(diǎn)熵的加權(quán)平均$$Gain(D, A) H(D) - \sum_{v} \frac{|D^v|}{|D|} H(D^v)$$ID3每次選信息增益最大的特征來(lái)分裂。它的優(yōu)點(diǎn)是概念清晰、計(jì)算簡(jiǎn)單但有個(gè)致命缺陷信息增益偏向取值多的特征。極端情況下如果有個(gè)特征是樣本ID每個(gè)樣本取值都不同那按它分裂后每個(gè)子節(jié)點(diǎn)只有一個(gè)樣本熵全是0信息增益達(dá)到最大但這顯然毫無(wú)泛化意義。這個(gè)缺陷是ID3被詬病最多的地方也是C4.5誕生的直接原因。1.3 C4.5用增益率修正偏好工程化程度更高C4.5是ID3的改進(jìn)版針對(duì)信息增益的偏好問(wèn)題它引入了增益率Gain Ratio。思路是既然取值多的特征信息增益天然偏高那我就除以一個(gè)和特征取值數(shù)量相關(guān)的量來(lái)懲罰它。這個(gè)懲罰項(xiàng)叫固有值Intrinsic Value$$IV(A) -\sum_{v} \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$$增益率就是$$GainRatio(D, A) \frac{Gain(D, A)}{IV(A)}$$特征取值越多$IV(A)$ 越大增益率就被壓得越低。但這里有個(gè)新問(wèn)題如果某個(gè)特征每個(gè)樣本取值都不同$IV(A)$ 會(huì)趨近于0甚至為0導(dǎo)致增益率爆炸。所以C4.5實(shí)際用了一個(gè)啟發(fā)式策略——先從候選特征里挑出信息增益高于平均值的那些再?gòu)闹羞x增益率最高的。這個(gè)先篩選再選優(yōu)的兩步走是C4.5工程實(shí)現(xiàn)里很容易被忽略的細(xì)節(jié)。除了增益率C4.5還解決了ID3的兩個(gè)大短板連續(xù)特征處理和缺失值處理。ID3只能處理離散特征C4.5通過(guò)二分法把連續(xù)特征離散化ID3遇到缺失值直接沒(méi)法算C4.5用加權(quán)的方式讓缺失樣本以一定概率進(jìn)入各個(gè)分支。這兩塊后面會(huì)詳細(xì)講。1.4 CART用基尼指數(shù)只做二叉樹(shù)CARTClassification and Regression Trees和前兩者最大的不同是它生成的永遠(yuǎn)是二叉樹(shù)。不管特征有多少個(gè)取值CART都只把它切成兩份。這個(gè)設(shè)計(jì)讓CART的實(shí)現(xiàn)更統(tǒng)一也更容易做回歸任務(wù)。分類(lèi)任務(wù)上CART用的分裂準(zhǔn)則是基尼指數(shù)Gini Index$$Gini(D) 1 - \sum_{k1}^{K} p_k^2$$基尼指數(shù)可以理解為從數(shù)據(jù)集里隨機(jī)抽兩個(gè)樣本它們類(lèi)別不一致的概率。和熵一樣它衡量的是不純度越小越純。按特征A的某個(gè)取值a把數(shù)據(jù)切成 $D_1$ 和 $D_2$ 兩部分后$$Gini(D, A) \frac{|D_1|}{|D|} Gini(D_1) \frac{|D_2|}{|D|} Gini(D_2)$$CART選讓加權(quán)基尼指數(shù)最小的那個(gè)切分點(diǎn)。相比熵基尼指數(shù)沒(méi)有對(duì)數(shù)運(yùn)算計(jì)算更快而且實(shí)際效果和熵非常接近這也是CART在工業(yè)界更受歡迎的原因之一?；貧w任務(wù)上CART用均方誤差MSE作為分裂準(zhǔn)則選讓兩邊MSE加權(quán)和最小的切分點(diǎn)葉子節(jié)點(diǎn)的預(yù)測(cè)值取該節(jié)點(diǎn)樣本的均值。這一點(diǎn)是ID3和C4.5不具備的它們只能做分類(lèi)。1.5 三者對(duì)比一張表看清差異維度ID3C4.5CART分裂準(zhǔn)則信息增益增益率基尼指數(shù)分類(lèi)/ MSE回歸樹(shù)的結(jié)構(gòu)多叉樹(shù)多叉樹(shù)二叉樹(shù)連續(xù)特征不支持支持二分法支持二分法缺失值不支持支持加權(quán)支持代理分裂剪枝無(wú)悲觀剪枝代價(jià)復(fù)雜度剪枝任務(wù)類(lèi)型分類(lèi)分類(lèi)分類(lèi)回歸特征偏好偏向多取值已修正無(wú)偏好這張表建議背下來(lái)面試問(wèn)三種算法的區(qū)別基本就是這些點(diǎn)。但光背沒(méi)用下面我會(huì)把每個(gè)點(diǎn)背后的為什么講清楚。2. 核心細(xì)節(jié)解析與實(shí)操要點(diǎn)2.1 信息熵、條件熵與信息增益的完整推導(dǎo)很多人對(duì)信息增益的理解停留在公式層面我建議從不確定性減少這個(gè)角度重新理解一遍。信息熵 $H(D)$ 衡量的是在不知道任何特征的情況下判斷一個(gè)樣本類(lèi)別的不確定性。條件熵 $H(D|A)$ 衡量的是知道了特征A的取值之后判斷類(lèi)別還剩多少不確定性。信息增益就是兩者之差也就是知道特征A之后不確定性減少了多少。舉個(gè)具體例子。假設(shè)數(shù)據(jù)集有10個(gè)樣本正負(fù)各5個(gè)那么 $H(D) -0.5\log_2 0.5 - 0.5\log_2 0.5 1$ bit。現(xiàn)在有個(gè)特征A按它分裂后得到兩個(gè)子集一個(gè)全是正例熵0一個(gè)全是負(fù)例熵0那么條件熵 $H(D|A) 0$信息增益就是1 bit說(shuō)明這個(gè)特征完美區(qū)分了類(lèi)別。反過(guò)來(lái)如果分裂后兩個(gè)子集還是正負(fù)各半條件熵還是1信息增益為0說(shuō)明這個(gè)特征沒(méi)用。這里有個(gè)實(shí)操細(xì)節(jié)熵的計(jì)算要處理 $p_k 0$ 的情況。因?yàn)?$\log_2 0$ 是負(fù)無(wú)窮代碼里必須約定 $0 \log 0 0$。我見(jiàn)過(guò)不少手寫(xiě)實(shí)現(xiàn)因?yàn)闆](méi)處理這個(gè)遇到純凈子集直接報(bào)錯(cuò)或者返回NaN。2.2 增益率為什么能修正偏好以及它的新問(wèn)題增益率修正偏好的邏輯用一個(gè)例子最直觀。假設(shè)有個(gè)特征A有100個(gè)取值每個(gè)取值對(duì)應(yīng)一個(gè)樣本那么 $IV(A) -\sum_{i1}^{100} \frac{1}{100}\log_2\frac{1}{100} \log_2 100 \approx 6.64$。信息增益雖然很大因?yàn)槊總€(gè)子集都純凈但除以6.64之后就被壓下來(lái)了。而另一個(gè)只有2個(gè)取值的特征B$IV(B)$ 最多是1即使信息增益稍小增益率也可能反超。但增益率本身有個(gè)反向偏好它偏向取值少的特征。極端情況下如果某個(gè)特征只有一個(gè)取值相當(dāng)于沒(méi)分裂$IV(A) 0$增益率無(wú)定義。所以C4.5不能直接用增益率選特征而是先用信息增益篩一遍。這個(gè)兩步策略在代碼里體現(xiàn)為先算所有特征的信息增益求平均保留高于平均的再在這些特征里選增益率最高的。這個(gè)細(xì)節(jié)很多教程不講但自己實(shí)現(xiàn)時(shí)如果漏了遇到極端數(shù)據(jù)會(huì)出問(wèn)題。2.3 基尼指數(shù)與熵的對(duì)比為什么CART選基尼基尼指數(shù)和熵都是不純度度量形狀很像都是凸函數(shù)都在 $p0.5$二分類(lèi)時(shí)取最大值。區(qū)別在于熵在 $p0.5$ 附近更陡對(duì)不純更敏感基尼指數(shù)計(jì)算沒(méi)有對(duì)數(shù)快很多。我做過(guò)一個(gè)粗略的benchmark在同樣規(guī)模的數(shù)據(jù)上用基尼指數(shù)比用熵大約快15%到20%因?yàn)槭〉袅藢?duì)數(shù)運(yùn)算。對(duì)于大規(guī)模數(shù)據(jù)或者需要頻繁分裂的場(chǎng)景這個(gè)差距會(huì)累積。而且實(shí)際分類(lèi)效果上兩者差異通常在1%以內(nèi)所以CART選基尼是效果幾乎不損失速度明顯提升的理性選擇。不過(guò)要注意基尼指數(shù)對(duì)多分類(lèi)的處理和熵略有不同。當(dāng)類(lèi)別數(shù)很多時(shí)基尼指數(shù)的最大值會(huì)趨近于1而熵的最大值是 $\log_2 K$。這個(gè)差異在類(lèi)別極多時(shí)會(huì)影響分裂點(diǎn)的選擇但實(shí)際業(yè)務(wù)里類(lèi)別數(shù)通常不會(huì)太夸張影響有限。2.4 連續(xù)特征離散化C4.5和CART的二分法ID3處理不了連續(xù)特征這是硬傷。C4.5和CART都用二分法解決把連續(xù)特征的所有取值排序取相鄰兩個(gè)值的中點(diǎn)作為候選切分點(diǎn)然后遍歷所有候選點(diǎn)選讓分裂準(zhǔn)則最優(yōu)的那個(gè)。具體步驟是假設(shè)特征A在數(shù)據(jù)集上有m個(gè)不同取值排序后得到 $a_1 a_2 ... a_m$那么有 $m-1$ 個(gè)候選切分點(diǎn)分別是 $\frac{a_1a_2}{2}, \frac{a_2a_3}{2}, ...$。對(duì)每個(gè)候選點(diǎn)把數(shù)據(jù)分成小于等于切分點(diǎn)和大于切分點(diǎn)兩部分計(jì)算分裂準(zhǔn)則選最優(yōu)的。這里有個(gè)優(yōu)化技巧不用每次都重新排序和計(jì)算?？梢韵葘?duì)數(shù)據(jù)按特征A排序然后從左到右掃描每移動(dòng)一個(gè)位置就更新左右兩邊的類(lèi)別計(jì)數(shù)增量式計(jì)算熵或基尼指數(shù)。這樣復(fù)雜度從 $O(m \cdot n)$ 降到 $O(m \log m n)$在大數(shù)據(jù)上差別巨大。我第一版實(shí)現(xiàn)就是暴力遍歷跑10萬(wàn)條數(shù)據(jù)慢得想砸鍵盤(pán)改成增量式之后快了一個(gè)數(shù)量級(jí)。2.5 缺失值處理C4.5的加權(quán)和CART的代理分裂缺失值是真實(shí)數(shù)據(jù)的常態(tài)三種算法里只有C4.5和CART有處理機(jī)制思路完全不同。C4.5的思路是加權(quán)分配。假設(shè)特征A在部分樣本上缺失那么計(jì)算信息增益時(shí)只用A不缺失的樣本算但最后乘一個(gè)系數(shù) $\frac{|D_{不缺失}|}{|D|}$ 來(lái)懲罰。分裂時(shí)缺失樣本不是被丟掉而是以不同權(quán)重同時(shí)進(jìn)入所有子節(jié)點(diǎn)權(quán)重等于各子節(jié)點(diǎn)樣本占比。預(yù)測(cè)時(shí)遇到缺失就把樣本同時(shí)送到所有分支最后按權(quán)重匯總結(jié)果。CART的思路是代理分裂Surrogate Split。主分裂點(diǎn)選好后再為它找?guī)讉€(gè)代理特征這些代理特征在能正確復(fù)現(xiàn)主分裂結(jié)果的前提下對(duì)缺失樣本做替補(bǔ)判斷。預(yù)測(cè)時(shí)如果主特征缺失就用第一代理特征還缺失就用第二代理以此類(lèi)推。這個(gè)機(jī)制更復(fù)雜但預(yù)測(cè)時(shí)更穩(wěn)定。實(shí)操中如果缺失比例不高比如低于5%直接刪除缺失樣本往往比復(fù)雜處理更省事效果也不差。缺失比例高的時(shí)候才值得上加權(quán)或代理。這是我踩過(guò)坑之后的經(jīng)驗(yàn)不要為了處理缺失值而處理先看缺失比例和缺失機(jī)制隨機(jī)缺失還是系統(tǒng)性缺失。3. 實(shí)操過(guò)程與核心環(huán)節(jié)實(shí)現(xiàn)3.1 數(shù)據(jù)準(zhǔn)備與工具選型我用的是Python 3.10核心依賴只有numpy畫(huà)圖用matplotlib數(shù)據(jù)集用經(jīng)典的鳶尾花和自己構(gòu)造的一份帶缺失值的模擬數(shù)據(jù)。不依賴sklearn因?yàn)槟康氖鞘謱?xiě)實(shí)現(xiàn)用sklearn就失去意義了。如果你想對(duì)照驗(yàn)證可以最后用sklearn的DecisionTreeClassifier跑一遍對(duì)比準(zhǔn)確率。數(shù)據(jù)結(jié)構(gòu)上我用numpy的二維數(shù)組存特征一維數(shù)組存標(biāo)簽。特征可以是離散的整數(shù)編碼或連續(xù)的浮點(diǎn)標(biāo)簽統(tǒng)一整數(shù)編碼。缺失值用np.nan表示。這個(gè)約定貫穿整個(gè)實(shí)現(xiàn)。3.2 信息熵與基尼指數(shù)的代碼實(shí)現(xiàn)先寫(xiě)最基礎(chǔ)的不純度函數(shù)。注意 $0\log 0 0$ 的處理import numpy as np def entropy(y): 計(jì)算信息熵y是標(biāo)簽數(shù)組 if len(y) 0: return 0.0 _, counts np.unique(y, return_countsTrue) probs counts / len(y) # 過(guò)濾掉概率為0的項(xiàng)避免log(0) probs probs[probs 0] return -np.sum(probs * np.log2(probs)) def gini(y): 計(jì)算基尼指數(shù) if len(y) 0: return 0.0 _, counts np.unique(y, return_countsTrue) probs counts / len(y) return 1.0 - np.sum(probs ** 2)這兩個(gè)函數(shù)是整個(gè)算法的基礎(chǔ)務(wù)必保證正確。我建議寫(xiě)完先用幾個(gè)手算的例子驗(yàn)證比如entropy([0,0,0,0])應(yīng)該返回0entropy([0,1])應(yīng)該返回1gini([0,1])應(yīng)該返回0.5。3.3 ID3的分裂邏輯實(shí)現(xiàn)ID3的核心是遍歷所有離散特征算信息增益選最大的def information_gain(X, y, feature_idx): 計(jì)算按feature_idx分裂的信息增益 parent_entropy entropy(y) values np.unique(X[:, feature_idx]) # 如果特征只有一個(gè)取值無(wú)法分裂 if len(values) 1: return 0.0 weighted_entropy 0.0 for v in values: mask X[:, feature_idx] v weighted_entropy (np.sum(mask) / len(y)) * entropy(y[mask]) return parent_entropy - weighted_entropy def choose_best_feature_id3(X, y, feature_indices): ID3選特征信息增益最大 best_gain -1 best_feature None for idx in feature_indices: gain information_gain(X, y, idx) if gain best_gain: best_gain gain best_feature idx return best_feature, best_gain這里有個(gè)細(xì)節(jié)如果所有特征的信息增益都是0比如所有樣本標(biāo)簽相同或者特征都沒(méi)區(qū)分度應(yīng)該返回None讓上層停止分裂。這個(gè)判斷放在遞歸的停止條件里。3.4 C4.5的增益率與兩步篩選實(shí)現(xiàn)C4.5在ID3基礎(chǔ)上加固有值和兩步篩選def intrinsic_value(X, feature_idx): 計(jì)算特征的固有值 values, counts np.unique(X[:, feature_idx], return_countsTrue) probs counts / len(X) probs probs[probs 0] return -np.sum(probs * np.log2(probs)) def gain_ratio(X, y, feature_idx): 計(jì)算增益率 iv intrinsic_value(X, feature_idx) if iv 0: return 0.0 return information_gain(X, y, feature_idx) / iv def choose_best_feature_c45(X, y, feature_indices): C4.5選特征先按信息增益篩選再選增益率最高 gains {} for idx in feature_indices: gains[idx] information_gain(X, y, idx) if not gains: return None, 0.0 avg_gain np.mean(list(gains.values())) # 只保留信息增益高于平均的特征 candidates [idx for idx, g in gains.items() if g avg_gain] if not candidates: candidates list(gains.keys()) best_ratio -1 best_feature None for idx in candidates: ratio gain_ratio(X, y, idx) if ratio best_ratio: best_ratio ratio best_feature idx return best_feature, best_ratio這個(gè)兩步篩選是C4.5的精髓也是它比ID3穩(wěn)的原因。我實(shí)測(cè)下來(lái)在特征取值數(shù)量差異很大的數(shù)據(jù)集上C4.5選出的特征明顯比ID3更合理。3.5 CART的二叉樹(shù)分裂實(shí)現(xiàn)CART要遍歷每個(gè)特征和每個(gè)切分點(diǎn)找加權(quán)基尼指數(shù)最小的組合。對(duì)離散特征CART也做二分把所有取值分成兩組def cart_split(X, y, feature_indices, taskclassification): CART找最優(yōu)分裂返回(特征索引, 切分點(diǎn), 左右掩碼) best_score float(inf) best_split None n len(y) for idx in feature_indices: values np.unique(X[:, idx]) if len(values) 1: continue # 連續(xù)特征用中點(diǎn)離散特征用取值本身做二分 if np.issubdtype(X[:, idx].dtype, np.floating): thresholds (values[:-1] values[1:]) / 2 else: thresholds values[:-1] for t in thresholds: left_mask X[:, idx] t right_mask ~left_mask if np.sum(left_mask) 0 or np.sum(right_mask) 0: continue if task classification: score (np.sum(left_mask) / n) * gini(y[left_mask]) \ (np.sum(right_mask) / n) * gini(y[right_mask]) else: score (np.sum(left_mask) / n) * np.var(y[left_mask]) \ (np.sum(right_mask) / n) * np.var(y[right_mask]) if score best_score: best_score score best_split (idx, t, left_mask, right_mask) return best_split注意回歸任務(wù)用的是方差MSE的等價(jià)形式葉子節(jié)點(diǎn)預(yù)測(cè)值取均值。這塊和分類(lèi)任務(wù)共用一套框架只是準(zhǔn)則和葉子輸出不同。3.6 遞歸建樹(shù)與停止條件三種算法共用一套遞歸框架區(qū)別只在選特征/切分點(diǎn)的函數(shù)class DecisionTree: def __init__(self, algorithmCART, max_depth10, min_samples_split2, min_samples_leaf1, taskclassification): self.algorithm algorithm self.max_depth max_depth self.min_samples_split min_samples_split self.min_samples_leaf min_samples_leaf self.task task self.tree None def fit(self, X, y): self.n_features X.shape[1] self.tree self._build(X, y, depth0) return self def _build(self, X, y, depth): # 停止條件1達(dá)到最大深度 # 停止條件2樣本數(shù)少于min_samples_split # 停止條件3節(jié)點(diǎn)純凈所有標(biāo)簽相同 # 停止條件4沒(méi)有特征可用 if (depth self.max_depth or len(y) self.min_samples_split or len(np.unique(y)) 1): return self._make_leaf(y) feature_indices list(range(self.n_features)) if self.algorithm ID3: feat, _ choose_best_feature_id3(X, y, feature_indices) if feat is None: return self._make_leaf(y) return self._split_id3(X, y, feat, depth) elif self.algorithm C4.5: feat, _ choose_best_feature_c45(X, y, feature_indices) if feat is None: return self._make_leaf(y) return self._split_id3(X, y, feat, depth) # 分裂方式同ID3 else: # CART split cart_split(X, y, feature_indices, self.task) if split is None: return self._make_leaf(y) idx, t, left_mask, right_mask split left self._build(X[left_mask], y[left_mask], depth 1) right self._build(X[right_mask], y[right_mask], depth 1) return {feature: idx, threshold: t, left: left, right: right} def _make_leaf(self, y): if self.task classification: values, counts np.unique(y, return_countsTrue) return {leaf: True, value: values[np.argmax(counts)]} else: return {leaf: True, value: np.mean(y)}ID3和C4.5的分裂是多叉的每個(gè)取值一個(gè)分支CART是二叉的只有左右兩個(gè)分支。這個(gè)結(jié)構(gòu)差異決定了預(yù)測(cè)函數(shù)的寫(xiě)法也不同。3.7 預(yù)測(cè)函數(shù)與剪枝預(yù)測(cè)就是沿著樹(shù)往下走到葉子返回結(jié)果def predict_one(tree, x): if tree.get(leaf): return tree[value] if threshold in tree: # CART if x[tree[feature]] tree[threshold]: return predict_one(tree[left], x) else: return predict_one(tree[right], x) else: # ID3/C4.5多叉 v x[tree[feature]] if v in tree[children]: return predict_one(tree[children][v], x) else: # 遇到訓(xùn)練時(shí)沒(méi)見(jiàn)過(guò)的取值返回該節(jié)點(diǎn)多數(shù)類(lèi) return tree[default]剪枝這塊C4.5用悲觀剪枝PEPCART用代價(jià)復(fù)雜度剪枝CCP。PEP的思路是用訓(xùn)練集上的錯(cuò)誤率加上一個(gè)基于二項(xiàng)分布的懲罰項(xiàng)來(lái)估計(jì)泛化錯(cuò)誤如果剪掉子樹(shù)后估計(jì)錯(cuò)誤不升反降就剪。CCP則是構(gòu)造一系列子樹(shù)用交叉驗(yàn)證選最優(yōu)的 $\alpha$ 參數(shù)。實(shí)際實(shí)現(xiàn)里PEP簡(jiǎn)單但偏激進(jìn)CCP復(fù)雜但更穩(wěn)。我一般先用預(yù)剪枝限制深度、最小樣本數(shù)控制復(fù)雜度后剪枝作為補(bǔ)充。4. 常見(jiàn)問(wèn)題與排查技巧實(shí)錄4.1 遞歸深度爆炸與棧溢出手寫(xiě)決策樹(shù)最容易踩的坑就是遞歸太深導(dǎo)致棧溢出。如果數(shù)據(jù)里有連續(xù)特征且切分點(diǎn)選得很細(xì)樹(shù)可能長(zhǎng)到幾百層。解決辦法有三個(gè)一是設(shè)max_depth硬限制二是設(shè)min_samples_leaf保證葉子至少有若干樣本三是把遞歸改成迭代用棧模擬。我一般用前兩個(gè)就夠了第三個(gè)除非數(shù)據(jù)量特別大否則沒(méi)必要。還有個(gè)隱蔽的坑如果停止條件寫(xiě)漏了遇到所有特征都無(wú)法分裂但標(biāo)簽還不純的情況會(huì)無(wú)限遞歸。比如所有樣本特征完全相同但標(biāo)簽不同這時(shí)候任何分裂都無(wú)效必須強(qiáng)制返回葉子。這個(gè)判斷一定要加。4.2 信息增益為0但樹(shù)還在長(zhǎng)有時(shí)候所有特征的信息增益都是0但節(jié)點(diǎn)標(biāo)簽還不純比如特征完全相同的樣本標(biāo)簽不同。這時(shí)候ID3會(huì)返回None上層應(yīng)該停止分裂并返回多數(shù)類(lèi)。如果代碼里沒(méi)處理這個(gè)會(huì)陷入死循環(huán)或者報(bào)錯(cuò)。C4.5同理增益率也可能全為0。CART的基尼指數(shù)雖然不會(huì)全為0但如果所有切分點(diǎn)的加權(quán)基尼都等于父節(jié)點(diǎn)基尼說(shuō)明分裂無(wú)意義也該停。4.3 連續(xù)特征切分點(diǎn)過(guò)多導(dǎo)致過(guò)擬合連續(xù)特征每個(gè)不同取值都產(chǎn)生一個(gè)候選切分點(diǎn)如果特征取值很分散候選點(diǎn)會(huì)非常多樹(shù)容易記住訓(xùn)練數(shù)據(jù)的噪聲。緩解辦法一是對(duì)連續(xù)特征先做分箱比如等頻分箱成10到20個(gè)桶減少候選點(diǎn)二是提高min_samples_leaf三是限制樹(shù)的深度。我實(shí)測(cè)下來(lái)分箱對(duì)連續(xù)特征特別多的數(shù)據(jù)集效果明顯能顯著降低過(guò)擬合。4.4 類(lèi)別不平衡導(dǎo)致分裂偏向多數(shù)類(lèi)如果標(biāo)簽嚴(yán)重不平衡比如正例占99%熵和基尼指數(shù)都會(huì)被多數(shù)類(lèi)主導(dǎo)分裂準(zhǔn)則傾向于把少數(shù)類(lèi)單獨(dú)分出來(lái)但整體不純度下降有限。這時(shí)候可以考慮一是對(duì)少數(shù)類(lèi)過(guò)采樣或多數(shù)類(lèi)欠采樣二是用類(lèi)別權(quán)重在計(jì)算熵或基尼時(shí)給少數(shù)類(lèi)更高權(quán)重三是換用對(duì)不平衡更魯棒的準(zhǔn)則比如基于F1的分裂準(zhǔn)則。這塊超出了三種經(jīng)典算法的范圍但實(shí)際業(yè)務(wù)里很常見(jiàn)值得注意。4.5 常見(jiàn)問(wèn)題速查表問(wèn)題現(xiàn)象可能原因排查與解決遞歸棧溢出樹(shù)太深設(shè)max_depth、min_samples_leaf無(wú)限遞歸停止條件漏了加無(wú)特征可分裂判斷信息增益全為0特征無(wú)區(qū)分度返回多數(shù)類(lèi)停止分裂連續(xù)特征過(guò)擬合切分點(diǎn)太多分箱、提高min_samples_leaf分裂偏向多數(shù)類(lèi)類(lèi)別不平衡采樣、類(lèi)別權(quán)重預(yù)測(cè)遇到未知取值訓(xùn)練集沒(méi)覆蓋返回節(jié)點(diǎn)多數(shù)類(lèi)增益率爆炸IV接近0用兩步篩選先按增益過(guò)濾基尼和熵結(jié)果差異大類(lèi)別數(shù)很多檢查是否類(lèi)別極多考慮換準(zhǔn)則4.6 幾個(gè)實(shí)操心得第一先用小數(shù)據(jù)驗(yàn)證正確性。我習(xí)慣構(gòu)造一個(gè)10個(gè)樣本、2個(gè)特征的小數(shù)據(jù)集手算出最優(yōu)分裂然后看代碼輸出是否一致。這一步能抓出80%的實(shí)現(xiàn)bug。第二和sklearn對(duì)照。雖然不用sklearn實(shí)現(xiàn)但可以用它驗(yàn)證。注意sklearn的CART默認(rèn)用基尼且對(duì)連續(xù)特征的處理和手寫(xiě)版可能有細(xì)微差異準(zhǔn)確率差1%到2%是正常的差太多說(shuō)明實(shí)現(xiàn)有問(wèn)題。第三剪枝不要過(guò)度。我見(jiàn)過(guò)為了追求測(cè)試集準(zhǔn)確率把樹(shù)剪得只剩一個(gè)根節(jié)點(diǎn)的情況那還不如直接用多數(shù)類(lèi)分類(lèi)器。剪枝的目標(biāo)是平衡偏差和方差不是單純追求某一項(xiàng)指標(biāo)。第四特征編碼要統(tǒng)一。離散特征用整數(shù)編碼連續(xù)特征用浮點(diǎn)缺失值用np.nan這個(gè)約定要在整個(gè)流程里保持一致否則分裂時(shí)類(lèi)型比較會(huì)出各種詭異問(wèn)題。第五注意數(shù)值穩(wěn)定性。熵和基尼的計(jì)算涉及除法和對(duì)數(shù)當(dāng)樣本數(shù)很少時(shí)容易出現(xiàn)精度問(wèn)題?？梢栽诜帜干霞右粋€(gè)極小值eps或者對(duì)概率做歸一化。這套實(shí)現(xiàn)我前后改了三版第一版暴力遍歷慢得沒(méi)法用第二版加了增量式計(jì)算快了很多但缺失值處理有bug第三版才比較完善。決策樹(shù)這東西看懂了和寫(xiě)出來(lái)是兩回事寫(xiě)出來(lái)和寫(xiě)對(duì)了又是兩回事。建議你一定要自己動(dòng)手敲一遍哪怕照著抄抄的過(guò)程中遇到的問(wèn)題才是真正學(xué)到的東西。后面如果要做集成學(xué)習(xí)這套手寫(xiě)的樹(shù)還能直接拿來(lái)做隨機(jī)森林或梯度提升的基礎(chǔ)組件算是把地基打牢了。