吃瓜第四章決策樹 2023-12-19

決策樹

1 概述

決策樹的學(xué)習(xí)目的是產(chǎn)生一棵泛化能力強(qiáng)的決策樹白筹，基本流程遵循“分而治之”的策略芒澜。

決策樹

最頂層是根節(jié)點(diǎn)随闺，包含所有樣本
每個(gè)葉節(jié)點(diǎn)代表類或類分布（幾類的概率分布）（預(yù)測(cè)時(shí)直接選概率最大的類）虾标，對(duì)應(yīng)決策結(jié)果
每個(gè)樣本均被劃分到一個(gè)葉節(jié)點(diǎn)

樹的生成

選擇特征
選擇閾值

2 四種建樹算法

基本算法框架：

基本算法

有三種特殊情況導(dǎo)致遞歸返回：

當(dāng)前結(jié)點(diǎn)包含的所有樣本都是同一類別了
當(dāng)前屬性集為空现拒，或是所有樣本所有屬性都一樣
當(dāng)前結(jié)點(diǎn)不包含任何樣本

圖中最關(guān)鍵的是第8行辣垒，也就是如何選擇最佳屬性。在這個(gè)問題上印蔬，有四種衍生出的算法：

CLS
ID3
C4.5
CART

接下來一一介紹勋桶。

2.1 CLS

CLS是第一個(gè)決策樹算法。
CLS算法的基本思想是通過遞歸地將數(shù)據(jù)集分割成多個(gè)子集侥猬，直到滿足某個(gè)停止條件為止例驹。在每個(gè)節(jié)點(diǎn)上，CLS算法選擇最優(yōu)的特征進(jìn)行分割陵究，并根據(jù)特征的取值將數(shù)據(jù)集劃分成不同的子集眠饮。
一旦數(shù)據(jù)集被劃分成子集，CLS算法會(huì)遞歸地在每個(gè)子集上重復(fù)上述過程铜邮，直到滿足停止條件為止仪召。
采用不同的測(cè)試屬性及其先后順序會(huì)生成不同的決策樹。
不展開松蒜。

2.2 ID3

信息增益

先給出信息熵與條件熵的定義扔茅。
假設(shè) $X$ 是取有限個(gè)值的離散隨機(jī)變量，每個(gè)的概率為 $p_i$ 秸苗，則X的(信息)熵定義為
$H(X) = -\sum_{i=1}^n p_i \log p_i$ 信息熵的值越小召娜，代表樣本集合純度越高。

條件熵 $H(Y|X)$ 指在已知隨機(jī)變量 $X$ 的條件下隨機(jī)變量Y的不確定性惊楼，定義為 $X$ 在給定條件下 $Y$ 的條件概率分布的熵對(duì) $X$ 的數(shù)學(xué)期望玖瘸。
$H(Y|X)=\sum^n_{i=1}p_iH(Y|X=x_i)$

信息增益表示得知特征的值而使得類的信息的不確定性減少的程度秸讹。
特征A對(duì)訓(xùn)練數(shù)據(jù)集D的信息增益，即 $Gain(D,A)=H(D)-H(D|A)$
一般的雅倒，熵與條件熵之差被稱作互信息璃诀，決策樹學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中類與特征的互信息。

在決策樹學(xué)習(xí)中蔑匣，信息增益就表示由于特征A而使得對(duì)數(shù)據(jù)集D進(jìn)行分類的不確定性減少的程度劣欢。減少程度越大，意味著信息增益越大裁良。所以我們選擇信息增益最大的特征凿将。

ID3算法

設(shè)樣本集合為D，第k類樣本占比為 $p_k$ 价脾，則
$Ent(D)=-\sum_{k=1}^Kp_k \log_2p_k$ 特征a對(duì)D條件熵為 $\sum_{v=1}^V\frac{D^v}{D}Ent(D^v)$ 其中 $v$ 是特征a的可能取值牧抵， $D^v$ 是這種取值對(duì)應(yīng)的樣本數(shù)， $\frac{D^v}{D}$ 即a取這種值得概率彼棍。
那么灭忠，信息增益就是
$Gain(D, a) = Ent(D) - \sum_{v=1}^V\frac{D^v}{D}Ent(D^v)$
過程：
輸入：數(shù)據(jù)集D，特征集A座硕，閾值 $\epsilon$
輸出：決策樹T

特殊情況：D中樣本同屬一個(gè)類弛作，T為葉子。A為空集华匾，T為葉子映琳，按少數(shù)服從多數(shù)原則確定類別。
計(jì)算A中各個(gè)特征對(duì)D的信息增益蜘拉，選擇信息增益最大的 $A_g$ 作為測(cè)試屬性萨西。
如果 $A_g$ 小于增益閾值 $\epsilon$ ，則置T為單結(jié)點(diǎn)樹旭旭。選D中實(shí)例數(shù)最大的類作為標(biāo)記谎脯，返回T
否則，對(duì) $A_g$ 的每一個(gè)可能值持寄，按 $A_g$ 劃分D為若干非空子集 $D_i$ 源梭，將 $D_i$ 中實(shí)例數(shù)最大的類作為標(biāo)記，構(gòu)建子節(jié)點(diǎn)稍味，由節(jié)點(diǎn)和子節(jié)點(diǎn)構(gòu)成樹T废麻，返回T
對(duì)結(jié)點(diǎn)i，以 $D_i$ 為數(shù)據(jù)集模庐， $A- \left \{ A_g \right \}$ 為特征集烛愧，遞歸計(jì)算。

數(shù)據(jù)清理：
要做數(shù)據(jù)的清理，轉(zhuǎn)換怜姿，相關(guān)性分析...

2.2 C4.5

ID3的缺陷：如果我們用一種特別特殊的特征慎冤，比如編號(hào)，學(xué)號(hào)...每個(gè)特征里只對(duì)應(yīng)一個(gè)樣本沧卢，那這種情況下粪薛， $Ent(D^v)$ 肯定為0，信息增益只剩第一項(xiàng) $Ent(D)$ 搏恤，肯定是所有特征里最大的。但是這樣生成的模型毫無泛化能力湃交，無法對(duì)新樣本進(jìn)行有效預(yù)測(cè)熟空。

信息增益比

用信息增益比來選擇特征
$g_R$ 代指Gain_ratio
$g_R(D,a)=\frac{g(D,a)}{H_a(D)}$
分母是懲罰。劃分類別越多搞莺，熵越大息罗，比值越小。其中
$H_a(D)=-\sum_{v=1}^V \frac{|D^v|}{|D|} \log_2 \frac{|D^v|}{|D|}$ 稱為屬性a的固有值才沧。

遞歸過程和ID3相同迈喉。

2.3 CART

CART(Classification and Regression Tree)分類回歸樹

分類樹：基尼指數(shù)Gini Index
回歸樹：平方誤差最小化

由兩部分組成

決策樹生成
決策樹剪枝
CART決策樹是二叉樹

基尼指數(shù)

CART決策樹采用基尼指數(shù)Gini Index來選擇屬性
基尼值：
$Gini(D) = 1-\sum_{k=1}^K p_k^2$ 直觀上，基尼值反映了從數(shù)據(jù)集中任選兩個(gè)樣本温圆，其類別不一致的概率挨摸。基尼值越小岁歉，純度越高得运。
基尼指數(shù)Gini Index：
對(duì)于屬性a，基尼系數(shù)
$Gini_index(D,a)=\sum^V_{v=1}\frac{|D^v|}{|D|}Gini(D^v)$ 在通過a分成的每一塊中锅移，算Gini并乘上比例熔掺。

3 剪枝

剪枝可以減少?zèng)Q策樹的規(guī)模（復(fù)雜度），處理過擬合的問題非剃。
分為預(yù)剪枝和后剪枝

預(yù)剪枝

在生成時(shí)對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行估計(jì)置逻，如果當(dāng)前結(jié)點(diǎn)的劃分不能提升泛化性能，就不劃分备绽∪耄可以使用性能評(píng)估的方法（如留出法等）來判斷。但是有欠擬合的風(fēng)險(xiǎn)疯坤。

后剪枝

在樹建成之后报慕，自底向上地進(jìn)行剪枝。
極小化Cost Complexity函數(shù)：
$CC(T)=Err(T)+\lambda R(T)$
第一項(xiàng)是樹T的錯(cuò)誤压怠，第二項(xiàng)是正則項(xiàng)眠冈，代表樹的復(fù)雜度， $\lambda \ge0$ 為正則化參數(shù)。

CC(T)

過程：
輸入：樹

T

蜗顽，正則參數(shù)
輸出：修建后的樹

T_0

計(jì)算每個(gè)葉子節(jié)點(diǎn)的代價(jià)
計(jì)算如果這個(gè)節(jié)點(diǎn)回縮到父節(jié)點(diǎn)之后的代價(jià)布卡，如果回縮之后代價(jià)減少了，就剪枝
遞歸地向上回溯

根據(jù)驗(yàn)證集上的代價(jià)決定是否剪枝

CART決策樹的剪枝

詳情可見：https://www.cnblogs.com/yang-ding/archive/2022/10/19/16805491.html

CART 剪枝

Step2：利用獨(dú)立的驗(yàn)證集在子樹序列中選擇誤差最小的雇盖。

4 連續(xù)屬性與缺失屬性的處理

連續(xù)值處理

C4.5和CART都使用了連續(xù)屬性離散化忿等，最簡單的是二分法。
對(duì)數(shù)據(jù)集上此屬性的所有值進(jìn)行由小到大排序（假設(shè)共n個(gè)）崔挖，取每兩個(gè)鄰接的值的中位數(shù)作為劃分點(diǎn)（共n-1個(gè)）贸街。對(duì)每個(gè)點(diǎn)對(duì)應(yīng)的劃分方法，算信息增益狸相，或者增益比薛匪，基尼指數(shù)等來進(jìn)行選擇。

缺失值處理

訓(xùn)練集有缺失脓鹃，如何劃分

$Gain(D,a) = \rho Gain(\tilde{D},a)$
$\rho$ 是數(shù)據(jù)完整的樣本所占（加權(quán)）比例逸尖，
$\tilde{D}$ 是數(shù)據(jù)完整的樣本集合。
同時(shí)劃入所有子節(jié)點(diǎn)瘸右，分別算劃分到各個(gè)子節(jié)點(diǎn)的概率娇跟，且樣本權(quán)值在與屬性值對(duì)應(yīng)的子結(jié)點(diǎn)中調(diào)整為原權(quán)值×這個(gè)屬性值的概率

預(yù)測(cè)時(shí)屬性值缺失

按概率決定類別

5 多變量決策樹

多變量決策樹

參考：

南瓜書https://www.bilibili.com/video/BV1Mh411e7VU/?p=1&vd_source=32ad22ca1aa5a882c8b7fe1b7878657f
《機(jī)器學(xué)習(xí)》周志華
...

最后編輯于：2023.12.20 15:05:44

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市太颤，隨后出現(xiàn)的幾起案子苞俘，更是在濱河造成了極大的恐慌，老刑警劉巖栋齿，帶你破解...
沈念sama閱讀 222,729評(píng)論 6贊 517
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件苗胀，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡瓦堵，警方通過查閱死者的電腦和手機(jī)基协，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 95,226評(píng)論 3贊 399
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來菇用，“玉大人澜驮，你說我怎么就攤上這事⊥锱福” “怎么了杂穷？”我有些...
開封第一講書人閱讀 169,461評(píng)論 0贊 362
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長卦绣。經(jīng)常有香客問我耐量，道長，這世上最難降的妖魔是什么滤港？我笑而不...
開封第一講書人閱讀 60,135評(píng)論 1贊 300
?港島之戀（遺憾婚禮）
正文為了忘掉前任廊蜒，我火速辦了婚禮趴拧，結(jié)果婚禮上，老公的妹妹穿的比我還像新娘山叮。我一直安慰自己著榴，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 69,130評(píng)論 6贊 398
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布屁倔。她就那樣靜靜地躺著脑又，像睡著了一般。火紅的嫁衣襯著肌膚如雪锐借。梳的紋絲不亂的頭發(fā)上问麸，一...
開封第一講書人閱讀 52,736評(píng)論 1贊 312
城市分裂傳說
那天，我揣著相機(jī)與錄音钞翔，去河邊找鬼口叙。笑死，一個(gè)胖子當(dāng)著我的面吹牛嗅战，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播俺亮，決...
沈念sama閱讀 41,179評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼，長吁一口氣：“原來是場(chǎng)噩夢(mèng)啊……” “哼脚曾！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起珊泳，我...
開封第一講書人閱讀 40,124評(píng)論 0贊 277
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎拷沸，沒想到半個(gè)月后色查，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體撞芍，經(jīng)...
沈念sama閱讀 46,657評(píng)論 1贊 320
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 38,723評(píng)論 3贊 342
?白月光啟示錄
正文我和宋清朗相戀三年序无，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了验毡。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 40,872評(píng)論 1贊 353
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡帝嗡，死狀恐怖怕磨，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情沪悲，我是刑警寧澤，帶...
沈念sama閱讀 36,533評(píng)論 5贊 351
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布塘秦，位于F島的核電站，受9級(jí)特大地震影響尊剔，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜须误，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,213評(píng)論 3贊 336
男人毒藥：我在死后第九天來索命
文/蒙蒙一仇轻、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧篷店，春花似錦、人聲如沸疲陕。這莊子的主人今日做“春日...
開封第一講書人閱讀 32,700評(píng)論 0贊 25
一樁弒父案携茂，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽诅岩。三九已至讳苦，卻和暖如春吩谦，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背卿堂。一陣腳步聲響...
開封第一講書人閱讀 33,819評(píng)論 1贊 274
情欲美人皮
我被黑心中介騙來泰國打工懒棉，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人策严。一個(gè)月前我還...
沈念sama閱讀 49,304評(píng)論 3贊 379
代替公主和親
正文我出身青樓，卻偏偏與公主長得像妻导，于是被迫代替她去往敵國和親怀各。傳聞我的和親對(duì)象是個(gè)殘疾皇子术浪，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 45,876評(píng)論 2贊 361

吃瓜第四章 決策樹 2023-12-19

決策樹