更多文章可以訪問我的博客Aengus | Blog
決策樹的概念比較簡(jiǎn)單,可以將決策樹看做一個(gè)if-then集合:如果“條件1”,那么...。決策樹學(xué)習(xí)的損失函數(shù)通常是正則化后極大似然函數(shù),學(xué)習(xí)的算法通常是一個(gè)遞歸的選擇最優(yōu)特征吓笙,并根據(jù)該特征對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行分割,使得對(duì)各個(gè)子數(shù)據(jù)集有一個(gè)最好的分類的過程巾腕∶婢Γ可以看出,決策樹算法一般包含特征選擇尊搬,決策樹的生成與決策樹的剪枝過程叁鉴。
特征選擇
信息增益
熵和條件熵
在了解信息增益之前需先給出熵和條件熵的定義。
熵代表隨機(jī)變量不確定性的度量佛寿,設(shè)在一個(gè)有限個(gè)值的離散隨機(jī)變量幌墓,其概率分布為
則隨便變量的熵定義為
如果,則定義
;對(duì)數(shù)一般取以2為底或者以
為底克锣,這時(shí)候熵的單位分別稱作比特(bit)和納特(nat)。由定義可知腔长,熵只依賴于
的分布袭祟,而和
的取值無關(guān),因此也可以將
的熵記作
捞附,即:
熵越大巾乳,隨機(jī)變量的不確定性就越大,根據(jù)定義可以得到:
條件熵表示在已知隨機(jī)變量
的條件下鸟召,隨機(jī)變量
的不確定性胆绊。隨機(jī)變量
給定的條件下隨機(jī)變量
的條件熵
,定義為
給定條件下
的條件概率分布的熵對(duì)
的數(shù)學(xué)期望:
其中欧募,压状。
當(dāng)熵和條件熵中的概率由數(shù)據(jù)估計(jì)(尤其是極大似然估計(jì))得到時(shí),所對(duì)應(yīng)的熵和條件熵分別稱為經(jīng)驗(yàn)熵和經(jīng)驗(yàn)條件熵跟继。
定義
信息增益表示得知特征的信息而使得類
的信息的不確定性減少的程度种冬。
特征對(duì)訓(xùn)練集
的信息增益
,定義為集合
的經(jīng)驗(yàn)熵
與特征
給定條件下
的經(jīng)驗(yàn)條件熵
之差舔糖,即
一般來說娱两,熵與條件熵
之差稱作互信息。
根據(jù)信息增益選擇特征的方法是選擇信息增益最大的特征金吗。
信息增益算法
對(duì)于給定的訓(xùn)練集和特征
十兢,計(jì)算特征
對(duì)于訓(xùn)練集
的信息增益
一般有以下步驟:
(1)計(jì)算數(shù)據(jù)集的經(jīng)驗(yàn)熵
:
(2)計(jì)算特征對(duì)數(shù)據(jù)集
的經(jīng)驗(yàn)條件熵
:
(3)計(jì)算信息增益
信息增益比
以信息增益作為劃分訓(xùn)練數(shù)據(jù)集的特征,存在偏向于選擇取值較多的特征的問題摇庙。使用信息增益比可以校正這一問題旱物。
定義
對(duì)于給定的訓(xùn)練集和特征
,特征
對(duì)于訓(xùn)練集
的信息增益比
定義為其信息增益
與訓(xùn)練數(shù)據(jù)集
關(guān)于特征
的值的熵
之比跟匆,即:
其中异袄,,
是特征
取值的個(gè)數(shù)玛臂。
決策樹的生成
ID3算法
ID3算法的核心是在決策樹各個(gè)結(jié)點(diǎn)上應(yīng)用信息增益選擇特征烤蜕,遞歸的構(gòu)建決策樹。ID3相當(dāng)于用極大似然法進(jìn)行概率模型的選擇迹冤。
假設(shè)輸入訓(xùn)練數(shù)據(jù)集讽营,特征集
和閾值
,按照以下步驟求得決策樹
:
(1)如果中所有實(shí)例屬于同一類
泡徙,則
為單結(jié)點(diǎn)樹橱鹏,并將類
作為該結(jié)點(diǎn)的類標(biāo)記,返回
;
(2)若莉兰,則
為單結(jié)點(diǎn)樹挑围,并將
中實(shí)例數(shù)最大的類
作為該結(jié)點(diǎn)的類標(biāo)記松申,返回
注益;
(3)否則,按照信息增益的算法計(jì)算中各特征對(duì)
的信息增益班缰,選擇信息增益最大的特征
捶朵;
(4) 如果的信息增益小于閾值
蜘矢,則置
為單結(jié)點(diǎn)樹,并將
中實(shí)例數(shù)最大的類
作為該結(jié)點(diǎn)的類作為該結(jié)點(diǎn)的類標(biāo)記综看,返回
品腹;
(5)否則,對(duì)的每一個(gè)可能值
红碑,依
將
分割為若干非空子集
舞吭,將
中實(shí)例數(shù)最大的類作為標(biāo)記,構(gòu)建子結(jié)點(diǎn)句喷,由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹
镣典,返回
;
(6)對(duì)第個(gè)子結(jié)點(diǎn)唾琼,以
為訓(xùn)練集兄春,以
為特征集,遞歸地調(diào)用(1)~(5)步锡溯,得到子樹
并返回赶舆;
C4.5算法
C4.5算法和ID3算法類似,不過是用信息增益比替換掉了信息增益祭饭;
假設(shè)輸入訓(xùn)練數(shù)據(jù)集芜茵,特征集
和閾值
,按照以下步驟求得決策樹
:
(1)如果中所有實(shí)例屬于同一類
倡蝙,則
為單結(jié)點(diǎn)樹九串,并將類
作為該結(jié)點(diǎn)的類標(biāo)記,返回
寺鸥;
(2)若猪钮,則
為單結(jié)點(diǎn)樹,并將
中實(shí)例數(shù)最大的類
作為該結(jié)點(diǎn)的類標(biāo)記胆建,返回
烤低;
(3)否則,按照信息增益比的算法計(jì)算中各特征對(duì)
的信息增益比笆载,選擇信息增益比最大的特征
扑馁;
(4) 如果的信息增益比小于閾值
涯呻,則置
為單結(jié)點(diǎn)樹,并將
中實(shí)例數(shù)最大的類
作為該結(jié)點(diǎn)的類作為該結(jié)點(diǎn)的類標(biāo)記腻要,返回
复罐;
(5)否則,對(duì)的每一個(gè)可能值
雄家,依
將
分割為若干非空子集
市栗,將
中實(shí)例數(shù)最大的類作為標(biāo)記,構(gòu)建子結(jié)點(diǎn)咳短,由結(jié)點(diǎn)及其子結(jié)點(diǎn)構(gòu)成樹
,返回
蛛淋;
(6)對(duì)第個(gè)子結(jié)點(diǎn)咙好,以
為訓(xùn)練集,以
為特征集褐荷,遞歸地調(diào)用(1)~(5)步勾效,得到子樹
并返回;
可以看到兩個(gè)算法除了加粗的部分叛甫,其他部分都一樣层宫。
決策樹的剪枝
決策樹生成算法遞歸的產(chǎn)生決策樹直到不能繼續(xù)下去為止,這樣的樹往往對(duì)訓(xùn)練數(shù)據(jù)分類比較準(zhǔn)確其监,但是對(duì)未知的測(cè)試數(shù)據(jù)往往沒那么精準(zhǔn)萌腿,即出現(xiàn)過擬合現(xiàn)象。對(duì)于這種情況可以將決策樹進(jìn)行簡(jiǎn)化抖苦,也被稱為決策樹的剪枝毁菱。
決策樹的剪枝往往通過極小化決策樹整體的損失函數(shù)或代價(jià)函數(shù)來實(shí)現(xiàn)。設(shè)樹的葉結(jié)點(diǎn)個(gè)數(shù)為
锌历,
是樹
的葉結(jié)點(diǎn)贮庞,該葉結(jié)點(diǎn)有
個(gè)樣本點(diǎn),其中
類的樣本點(diǎn)有
個(gè)究西,
窗慎,
為葉結(jié)點(diǎn)
上的經(jīng)驗(yàn)熵,
為參數(shù)卤材,則決策樹學(xué)習(xí)的損失函數(shù)可以定義為:
其中經(jīng)驗(yàn)熵為:
在損失函數(shù)中遮斥,將損失函數(shù)右端的第一項(xiàng)記作
這時(shí)有
剪枝就意味著當(dāng)確定時(shí),選擇損失函數(shù)最小的模型商膊,即損失函數(shù)最小的子樹(
較大時(shí)促使選擇比較簡(jiǎn)單的模型伏伐,較小時(shí)促進(jìn)選擇復(fù)雜的模型)。
剪枝算法
輸入生成的決策樹以及參數(shù)
晕拆,輸出剪枝后的子樹
:
(1)計(jì)算每個(gè)結(jié)點(diǎn)的經(jīng)驗(yàn)熵藐翎;
(2)遞歸地從樹的葉結(jié)點(diǎn)向上回縮材蹬,設(shè)一組葉結(jié)點(diǎn)回縮到其父結(jié)點(diǎn)之前與之后的整體樹分別為與
,其對(duì)應(yīng)的損失函數(shù)值分別是
與
吝镣,如果
則進(jìn)行剪枝堤器,即將父結(jié)點(diǎn)變?yōu)樾碌娜~結(jié)點(diǎn);
(3)重復(fù)步驟(2)末贾,直至不能繼續(xù)為止闸溃,得到損失函數(shù)最小的子樹;
CART算法
分類與回歸樹(classification and regression tree, CART)模型是應(yīng)用廣泛的決策樹學(xué)習(xí)方法拱撵,CART同樣由特征選擇辉川、樹的生成以及剪枝組成,既可以用于分類也可以用于回歸拴测。
CART是在給定輸入隨機(jī)變量的條件下輸出隨機(jī)變量
的條件概率分布的學(xué)習(xí)方法乓旗。CART假設(shè)決策樹是二叉樹,內(nèi)部結(jié)點(diǎn)特征的取值是“是”或“否”集索,左分支是取值為“是”的分支屿愚,右分支是取值為“否”的分支。CART算法由以下兩步組成:
(1)決策樹生成:基于訓(xùn)練數(shù)據(jù)集生成決策樹务荆,生成的決策樹要盡量大妆距;
(2)決策樹剪枝:用驗(yàn)證數(shù)據(jù)集對(duì)已生成的樹進(jìn)行剪枝并選擇最優(yōu)子樹,這時(shí)用損失函數(shù)最小作為剪枝的標(biāo)準(zhǔn)函匕;
CART生成
對(duì)于回歸樹用平方誤差最小化準(zhǔn)則娱据,對(duì)分類樹用基尼指數(shù)最小化準(zhǔn)則進(jìn)行特征選擇,生成二叉樹盅惜。
回歸樹的生成
一顆回歸樹對(duì)應(yīng)著輸入空間的一個(gè)劃分以及在劃分單元上的輸出值吸耿。假設(shè)將輸入空間劃分為個(gè)單元
,并且在每個(gè)單元
上有一個(gè)固定的輸出值
酷窥,于是回歸樹模型可表示為:
當(dāng)輸入空間的劃分確定時(shí)咽安,可以用用平方誤差來表示回歸樹對(duì)于訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差,用平方誤差最小的準(zhǔn)則求解每個(gè)單元上的最優(yōu)輸出值蓬推。易知單元
上的
的最優(yōu)值
是
上所有輸入實(shí)例
對(duì)應(yīng)的輸出
的均值妆棒,即
問題是怎樣對(duì)輸入空間進(jìn)行劃分,也就是如何選擇劃分結(jié)點(diǎn):
假設(shè)輸入訓(xùn)練集沸伏,在訓(xùn)練數(shù)據(jù)集所在的輸入空間中糕珊,遞歸地將每個(gè)區(qū)域劃分為兩個(gè)子區(qū)域并決定每個(gè)子區(qū)域上的輸出值,構(gòu)建二叉決策樹毅糟。具體步驟為:
(1)選擇第個(gè)變量
和它取的值
作為劃分變量和劃分點(diǎn)红选,并定義兩個(gè)區(qū)域:
然后尋找最優(yōu)劃分變量和最優(yōu)劃分點(diǎn)
,具體的姆另,求解:
遍歷變量喇肋,對(duì)固定的劃分變量
掃描切分點(diǎn)
坟乾,選擇式上式達(dá)到最小值的
;
(2)用選定的劃分區(qū)域
并決定相應(yīng)的輸出值:
(3)繼續(xù)對(duì)兩個(gè)子區(qū)域調(diào)用步驟(1)蝶防,(2)甚侣,直到滿足停止條件;
(4)將輸入空間劃分為個(gè)區(qū)域
间学,生成決策樹:
分類樹的生成
基尼指數(shù):在分類問題中殷费,假設(shè)有個(gè)類,樣本點(diǎn)屬于第
類的概率是
低葫,則概率分布的基尼指數(shù)定義為:
對(duì)于二分類問題详羡,若樣本點(diǎn)屬于第一個(gè)分類的概率為,則概率分布的基尼指數(shù)為:
對(duì)于給定的樣本集合嘿悬,其基尼指數(shù)為:
這里殷绍,是
中屬于第
類的樣本子集,
是類的個(gè)數(shù)鹊漠。
如果樣本集合根據(jù)特征
是否取值
被分割成
和
兩部分,即:
那么在特征的條件下茶行,集合
的基尼指數(shù)定義為:
基尼指數(shù)代表集合
的不確定性躯概,基尼指數(shù)
表示經(jīng)
分割后集合
的不確定性∨鲜Γ基尼指數(shù)越大代表不確定性程度越大娶靡。
假設(shè)輸入訓(xùn)練數(shù)據(jù)集以及停止計(jì)算的條件,根據(jù)訓(xùn)練集看锉,從根結(jié)點(diǎn)開始姿锭,遞歸地對(duì)每個(gè)結(jié)點(diǎn)進(jìn)行以下操作,構(gòu)建決策樹:
(1)計(jì)算現(xiàn)有特征對(duì)訓(xùn)練數(shù)據(jù)集的基尼指數(shù)伯铣。此時(shí)呻此,對(duì)每一個(gè)特征,對(duì)其可能取的每個(gè)值
腔寡,根據(jù)樣本點(diǎn)對(duì)
的測(cè)試為“是”或“否”焚鲜,將
分為
和
兩部分,利用上式計(jì)算
的基尼指數(shù)放前;
(2)對(duì)所有可能的特征以及他忿磅,他們所有可能的切分點(diǎn)
中,選擇基尼指數(shù)最小的特征及其對(duì)應(yīng)的切分點(diǎn)作為最優(yōu)特征與最優(yōu)切分點(diǎn)凭语。依最優(yōu)特征與最優(yōu)切分點(diǎn)葱她,從現(xiàn)結(jié)點(diǎn)生成兩個(gè)子結(jié)點(diǎn),將訓(xùn)練集依特征分配到兩個(gè)子結(jié)點(diǎn)去似扔;
(3)對(duì)兩個(gè)子結(jié)點(diǎn)遞歸調(diào)用(1)和(2)步驟吨些,直至滿足停止條件搓谆;
(4)生成CART決策樹;
算法停止的條件是結(jié)點(diǎn)中樣本個(gè)數(shù)小于預(yù)定閾值或者樣本的基尼指數(shù)小于預(yù)定閾值(此時(shí)此結(jié)點(diǎn)上的樣本基本屬于同一類)锤灿,或者沒有更多特征挽拔。
CART剪枝
輸入為CART算法生成的決策樹,輸出為最優(yōu)決策樹
但校,步驟如下:
(1)設(shè)螃诅;
(2)設(shè)
(3)自下而上地對(duì)各內(nèi)部結(jié)點(diǎn)計(jì)算
,
以及
這里状囱,表示以
為根結(jié)點(diǎn)的子樹术裸,
是對(duì)訓(xùn)練數(shù)據(jù)的預(yù)測(cè)誤差,
是
的葉結(jié)點(diǎn)個(gè)數(shù)亭枷;
(4)對(duì)的內(nèi)部結(jié)點(diǎn)
進(jìn)行剪枝袭艺,并對(duì)葉結(jié)點(diǎn)
以多數(shù)表決法決定其類,得到樹
叨粘;
(5)設(shè)猾编;
(6)如果不是由根結(jié)點(diǎn)及兩個(gè)葉結(jié)點(diǎn)構(gòu)成的樹,則回到步驟(2)升敲;否則令
答倡;
(7)采用交叉驗(yàn)證法在子樹序列中選取最優(yōu)子樹
;
參考
李航《統(tǒng)計(jì)學(xué)習(xí)方法(第二版)》第五章