決策樹(shù)在看西瓜書(shū)的時(shí)候已記錄過(guò),此次看《統(tǒng)計(jì)學(xué)習(xí)方法》的決策樹(shù)部分奉芦,除了當(dāng)作復(fù)習(xí)坯汤,也有若干新的思考。因此本篇可視為http://www.reibang.com/p/8b56ea5a1607
的一個(gè)補(bǔ)充蓝晒。
1、決策樹(shù)與條件概率分布
決策樹(shù)除了可以看作一個(gè)規(guī)則的集合以外帖鸦,還可以表示給定特征條件下類(lèi)的條件概率分布芝薇。這一條件概率分布定義在特征空間的一個(gè)劃分上,將特征空間劃分為互不相交的單元或區(qū)域作儿,并在每個(gè)單元或區(qū)域定義一個(gè)類(lèi)的概率分布就構(gòu)成了一個(gè)條件概率分布洛二。
假設(shè)為表示特征的隨機(jī)變量,
為表示類(lèi)的隨機(jī)變量,則這個(gè)條件概率分布可表示為
晾嘶。
取值于給定劃分下單元的集合妓雾,
取值于類(lèi)的集合。各葉結(jié)點(diǎn)上的條件概率往往偏向于某個(gè)類(lèi)变擒,即屬于某個(gè)類(lèi)的概率較大君珠,決策樹(shù)分類(lèi)將該結(jié)點(diǎn)的實(shí)例強(qiáng)行分到條件概率大的那一類(lèi)去。
2娇斑、決策樹(shù)學(xué)習(xí)
決策樹(shù)本質(zhì)上是從訓(xùn)練數(shù)據(jù)集中歸納出一組分類(lèi)規(guī)則策添。與訓(xùn)練數(shù)據(jù)集不矛盾的決策樹(shù)可能有多個(gè)也可能一個(gè)都沒(méi)有。我們需要的是一個(gè)與訓(xùn)練數(shù)據(jù)矛盾較小的決策樹(shù)毫缆,同時(shí)具有很好的泛化能力唯竹。另一個(gè)角度看,決策樹(shù)學(xué)習(xí)是由訓(xùn)練數(shù)據(jù)集估計(jì)條件概率模型苦丁。基于特征空間劃分的類(lèi)的條件概率模型有無(wú)窮多個(gè)浸颓。我們選擇的條件概率模型應(yīng)不僅對(duì)訓(xùn)練數(shù)據(jù)很好的擬合,而且對(duì)未知數(shù)據(jù)有很好的預(yù)測(cè)旺拉。
從所有可能的決策樹(shù)中選擇最優(yōu)的決策樹(shù)是NP-Hard的产上,因此現(xiàn)實(shí)中通常采用啟發(fā)式算法。這樣得到的決策樹(shù)是次最優(yōu)的(sub-optimal)的蛾狗。
決策樹(shù)學(xué)習(xí)算法通常遞歸地選擇最優(yōu)特征晋涣,并根據(jù)該特征對(duì)訓(xùn)練數(shù)據(jù)集進(jìn)行分割,這一過(guò)程對(duì)應(yīng)特征空間的劃分與決策樹(shù)的構(gòu)建沉桌。生成決策樹(shù)后為了解決過(guò)擬合問(wèn)題通常要由下向上進(jìn)行決策樹(shù)剪枝谢鹊。
可以看到,決策樹(shù)學(xué)習(xí)算法包含特征選擇留凭、決策樹(shù)生成與決策樹(shù)剪枝過(guò)程佃扼。決策樹(shù)的生成只考慮局部最優(yōu),決策樹(shù)剪枝則考慮全局最優(yōu)蔼夜。
3兼耀、信息增益
這部分《統(tǒng)計(jì)學(xué)習(xí)方法》比西瓜書(shū)講得要細(xì)致。信息增益是信息論的內(nèi)容求冷,這里也只是較為淺顯的理解翠订。但對(duì)于決策樹(shù)而言這樣的理解已經(jīng)足夠了。
熵是隨機(jī)變量不確定性的度量遵倦。設(shè)是一個(gè)取有限個(gè)值的離散隨機(jī)變量,其概率分布為:
則隨機(jī)變量的熵定義為:
可以看到官撼,熵只依賴(lài)于的概率分布而與其具體取值無(wú)關(guān)梧躺。因此也可以將
的熵記為
:
條件熵表示已知隨機(jī)變量X的條件下隨機(jī)變量Y的不確定性。其定義為X給定的條件下Y的條件概率分布對(duì)X的數(shù)學(xué)期望:
這里。
一般的掠哥,熵與條件熵
之差稱(chēng)為互信息:
互信息是一個(gè)隨機(jī)變量(X)包含另一個(gè)隨機(jī)變量(Y)的信息量的度量巩踏。也可以看作給定X知識(shí)下Y的不確定性的縮減量。
決策樹(shù)學(xué)習(xí)中的信息增益等價(jià)于訓(xùn)練數(shù)據(jù)集中的類(lèi)與特征的互信息:
這里表示特征或?qū)傩裕?img class="math-inline" src="https://math.jianshu.com/math?formula=D" alt="D" mathimg="1">表示訓(xùn)練數(shù)據(jù)集续搀。
表示對(duì)數(shù)據(jù)
分類(lèi)的不確定性塞琼,
表示在特征
給定條件下對(duì)數(shù)據(jù)集
進(jìn)行分類(lèi)的不確定性。所以?xún)烧咧罱希葱畔⒃鲆妫?strong>表示由于特征
使得對(duì)數(shù)據(jù)集
分類(lèi)的不確定性減少的程度彪杉。
因此基于信息增益的決策樹(shù)算法就很自然了,每次選擇信息增益最大的結(jié)點(diǎn)劃分方式直至信息增益小于某個(gè)閾值或結(jié)點(diǎn)中樣本類(lèi)別相同為止牵咙。
采用信息增益作為劃分結(jié)點(diǎn)的指標(biāo)有一個(gè)問(wèn)題——算法會(huì)偏向于選擇取值較多的特征派近。為解決這個(gè)問(wèn)題,我們可以采用信息增益比:
其中是訓(xùn)練數(shù)據(jù)集
關(guān)于特征
的熵洁桌。顯然
的取值越多渴丸,其不確定性?xún)A向于越大,從而熵傾向于越大另凌,這樣就相當(dāng)于在信息增益基礎(chǔ)上增加了一個(gè)關(guān)于特征取值多少的罰項(xiàng)谱轨。
4、決策樹(shù)生成——ID3&C4.5&CART
ID3算法:
輸入:訓(xùn)練數(shù)據(jù)集吠谢,特征集
土童,閾值
(1)若D中所有實(shí)例屬于同一類(lèi),擇
為單節(jié)點(diǎn)樹(shù)囊卜,將類(lèi)
作為該結(jié)點(diǎn)類(lèi)標(biāo)記娜扇,返回
。
(2)若栅组,則
為單結(jié)點(diǎn)樹(shù)雀瓢,并將
中實(shí)例數(shù)最大的類(lèi)
作為該結(jié)點(diǎn)標(biāo)記,返回
玉掸。
(3)否則計(jì)算各特征對(duì)D的信息增益刃麸,選擇信息增益最大的特征。
(4)如果的信息增益小于閾值
司浪,則置
為單結(jié)點(diǎn)樹(shù)泊业,并將
中實(shí)例數(shù)最大的類(lèi)
作為該結(jié)點(diǎn)的類(lèi)標(biāo)記,返回
啊易。
(5)否則吁伺,對(duì)的每一可能值
,依
將
分割為若干非空子集
租谈,將
中實(shí)例數(shù)最大的類(lèi)作為標(biāo)記篮奄,構(gòu)建子結(jié)點(diǎn)捆愁,由結(jié)點(diǎn)及子結(jié)點(diǎn)構(gòu)成樹(shù)
,返回
窟却。
(6)對(duì)第個(gè)子結(jié)點(diǎn)昼丑,以
為訓(xùn)練集,以
為特征集夸赫,遞歸地調(diào)用步驟(1)~(5)得到子樹(shù)
菩帝,返回
。
C4.5算法:
C4.5算法和ID3算法唯一的差異就是把結(jié)點(diǎn)劃分準(zhǔn)則由信息增益改進(jìn)為信息增益比茬腿。
CART(Classification And Regression Tree呼奢,分類(lèi)與回歸樹(shù))算法:
CART假設(shè)決策樹(shù)是二叉樹(shù),內(nèi)部結(jié)點(diǎn)取值特征為“是”和“否”滓彰,左分支是取值為“是”的分支,右分支為取值為“否”的分支揭绑。
在特征選擇方面弓候,對(duì)于回歸樹(shù),采用平方誤差最小準(zhǔn)則他匪,對(duì)分類(lèi)樹(shù)采用基尼系數(shù)最小化準(zhǔn)則菇存。
(a)最小二乘回歸樹(shù):
(1)選擇最優(yōu)切分變量和切分點(diǎn)
,求解:
這里和
表示由切分變量
和切分點(diǎn)
產(chǎn)生的兩個(gè)劃分區(qū)域邦蜜,
和
則表示在
和
區(qū)域上的樣本輸出值的均值依鸥。
也就是說(shuō),遍歷悼沈,對(duì)固定的
贱迟,掃描切分點(diǎn)
,找到使得上式最小的
絮供。
(2)用選定的劃分區(qū)域并決定相應(yīng)的輸出值:
(3)繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步驟(1)(2)直至滿(mǎn)足停止條件衣吠。
(b)分類(lèi)樹(shù)CART算法:
(1)設(shè)結(jié)點(diǎn)的訓(xùn)練數(shù)據(jù)集為,計(jì)算現(xiàn)有特征對(duì)該數(shù)據(jù)集的基尼系數(shù)壤靶,此時(shí)對(duì)每一個(gè)特征及其可能取的每個(gè)取值
缚俏,根據(jù)樣本點(diǎn)對(duì)
的測(cè)試為是或否將
分割成
和
兩個(gè)部分,利用下式計(jì)算
時(shí)的基尼系數(shù):
基尼系數(shù)表示集合
的不確定性贮乳,
表示經(jīng)過(guò)
分割后集合
的不確定性忧换。基尼指數(shù)越大不確定性越大向拆。
(2)在所有可能特征以及它們所有可能的切分點(diǎn)
中選擇基尼指數(shù)最小的特征及對(duì)應(yīng)切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)亚茬,將此結(jié)點(diǎn)分成兩個(gè)子結(jié)點(diǎn)。
(3)對(duì)兩個(gè)子結(jié)點(diǎn)遞歸地調(diào)用(1)(2)直至滿(mǎn)足停止條件(結(jié)點(diǎn)中樣本個(gè)數(shù)小于閾值或基尼系數(shù)小于閾值或沒(méi)有更多特征)浓恳。
5刹缝、決策樹(shù)剪枝
決策樹(shù)剪枝往往通過(guò)極小化決策樹(shù)整體的損失函數(shù)來(lái)實(shí)現(xiàn)葡兑,設(shè)樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)為
,
是樹(shù)
的葉結(jié)點(diǎn)赞草,改葉結(jié)點(diǎn)有
個(gè)樣本點(diǎn),其中第
類(lèi)樣本點(diǎn)有
個(gè)吆鹤,
厨疙,
為葉結(jié)點(diǎn)
上的熵,
為參數(shù)疑务,則決策樹(shù)學(xué)習(xí)的損失函數(shù)可定義為:
其中熵為:
將第一項(xiàng)記作:
則損失函數(shù)為:
其中表示模型對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差沾凄,
表示模型復(fù)雜度,在這里作為正則項(xiàng)來(lái)防止模型過(guò)擬合知允。
樹(shù)的剪枝算法:
(1)計(jì)算每個(gè)結(jié)點(diǎn)的熵撒蟀。
(2)遞歸地從樹(shù)的葉結(jié)點(diǎn)向上回縮。設(shè)一組葉結(jié)點(diǎn)回縮到父節(jié)點(diǎn)前后的整樹(shù)分別為和
温鸽,其對(duì)應(yīng)損失函數(shù)分別為
和
保屯,若:
則進(jìn)行剪枝,將父節(jié)點(diǎn)變成新的葉子結(jié)點(diǎn)涤垫。
(3)重復(fù)(2)直至不能繼續(xù)為止姑尺,得到損失函數(shù)最小的子樹(shù)。
CART剪枝:
CART剪枝算法由兩步組成:
- 從生成的決策樹(shù)
底端開(kāi)始不斷剪枝蝠猬,直到
的根結(jié)點(diǎn)切蟋,形成一個(gè)子樹(shù)序列
。
- 通過(guò)交叉驗(yàn)證法在獨(dú)立的驗(yàn)證集上對(duì)子樹(shù)序列進(jìn)行測(cè)試榆芦,從中選出最優(yōu)子樹(shù)柄粹。
如何形成子樹(shù)序列呢?Breiman等人證明:可以用遞歸的方式對(duì)數(shù)進(jìn)行剪枝匆绣,將從小增大型宝,產(chǎn)生一系列的區(qū)間
;剪枝得到的子樹(shù)序列對(duì)應(yīng)著各區(qū)間的最優(yōu)子樹(shù)序列暖呕。
這個(gè)結(jié)論其實(shí)不難理解挂签,當(dāng)我們緩慢增加的時(shí)候,可能得到的最優(yōu)子樹(shù)并不會(huì)發(fā)生變化凯力,也就是說(shuō)當(dāng)
在某個(gè)區(qū)間內(nèi)取值時(shí)茵瘾,我們得到的最優(yōu)子樹(shù)都是相同的,而當(dāng)
超過(guò)某個(gè)閾值咐鹤,則剪枝后得到的子樹(shù)更優(yōu)拗秘,此時(shí)最優(yōu)子樹(shù)才發(fā)生改變。于是很自然的思路就是找到這些區(qū)間的端點(diǎn)來(lái)進(jìn)行分析祈惶。
具體地雕旨,從整體樹(shù)開(kāi)始剪枝扮匠,對(duì)
的內(nèi)部結(jié)點(diǎn)
,以
為單結(jié)點(diǎn)樹(shù)的損失函數(shù)為:
以為根結(jié)點(diǎn)的子樹(shù)
的損失函數(shù)為:
當(dāng)及
充分小時(shí)凡涩,有不等式:
當(dāng)增大時(shí)棒搜,在某一
有:
此時(shí)解出的為:
為此,對(duì)中每一個(gè)內(nèi)部結(jié)點(diǎn)
活箕,計(jì)算:
它表示剪枝后整體損失函數(shù)減少的程度力麸。在中減去
最小的
,將得到的子樹(shù)作為
育韩,同時(shí)將最小的
作為
克蚂。
為區(qū)間
的最優(yōu)子樹(shù)。
總結(jié)下來(lái)算法流程如下:
(1)設(shè)筋讨,
埃叭。
(2)設(shè)。
(3)自下而上地對(duì)各內(nèi)部結(jié)點(diǎn)計(jì)算
悉罕,
以及:
(4)對(duì)的內(nèi)部結(jié)點(diǎn)
進(jìn)行剪枝赤屋,并對(duì)葉結(jié)點(diǎn)
以多數(shù)表決法確定其類(lèi)別,得到樹(shù)
蛮粮。
(5)設(shè)益缎。
(6)如果樹(shù)不是由根結(jié)點(diǎn)及兩個(gè)葉結(jié)點(diǎn)構(gòu)成的樹(shù)則返回(2)否則令
。
(7)采取交叉驗(yàn)證法在子樹(shù)序列中選取最優(yōu)子樹(shù)
然想。