數(shù)據(jù)挖掘與應(yīng)用(十一)_第1頁
數(shù)據(jù)挖掘與應(yīng)用(十一)_第2頁
數(shù)據(jù)挖掘與應(yīng)用(十一)_第3頁
數(shù)據(jù)挖掘與應(yīng)用(十一)_第4頁
數(shù)據(jù)挖掘與應(yīng)用(十一)_第5頁
已閱讀5頁,還剩28頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1第十一講

決策樹(1)2決策樹簡介

決策樹是一種根據(jù)自變量的值進(jìn)行遞歸劃分以預(yù)測(cè)因變量的方法。若因變量為連續(xù)變量,則稱相應(yīng)的決策樹為回歸樹。若因變量為分類變量,則稱相應(yīng)的決策樹為分類樹;3決策樹簡介假設(shè)數(shù)據(jù)集risk中含有下表所示信息:4決策樹簡介根據(jù)數(shù)據(jù)集中其它變量來預(yù)測(cè)風(fēng)險(xiǎn)類別的決策樹模型如下圖所示。5決策樹簡介根節(jié)點(diǎn)包含所有觀測(cè)。根據(jù)收入是否小于25488.5,將觀測(cè)分別歸于節(jié)點(diǎn)1和節(jié)點(diǎn)2。對(duì)于屬于節(jié)點(diǎn)1的觀測(cè),再根據(jù)擁有汽車的數(shù)量是否小于等于3將觀測(cè)分別歸于節(jié)點(diǎn)3和節(jié)點(diǎn)4。節(jié)點(diǎn)3和節(jié)點(diǎn)5不再進(jìn)行進(jìn)一步劃分,則稱其為葉節(jié)點(diǎn)。對(duì)于屬于節(jié)點(diǎn)2的觀測(cè),再根據(jù)孩子數(shù)量是否小于等于1將觀測(cè)分別歸于節(jié)點(diǎn)5和節(jié)點(diǎn)6。對(duì)于樹中各節(jié)點(diǎn),都可計(jì)算其中各風(fēng)險(xiǎn)類別的比例。6決策樹簡介對(duì)每個(gè)葉節(jié)點(diǎn)中的所有觀測(cè),決策樹模型對(duì)其進(jìn)行同樣的分類。從根節(jié)點(diǎn)到每個(gè)葉節(jié)點(diǎn)的路徑都會(huì)給出風(fēng)險(xiǎn)類別的一個(gè)預(yù)測(cè)規(guī)則。舉例來說,如果葉節(jié)點(diǎn)中的所有觀測(cè)都被歸類為該節(jié)點(diǎn)中比例最大的風(fēng)險(xiǎn)類別,圖中節(jié)點(diǎn)3對(duì)應(yīng)的預(yù)測(cè)規(guī)則為“如果收入小于25488.5并且擁有汽車數(shù)量小于等于3,那么風(fēng)險(xiǎn)類別為badprofit”。7決策樹的生長與修剪構(gòu)建決策樹時(shí):先根據(jù)訓(xùn)練數(shù)據(jù)集生成一棵足夠大的決策樹(“足夠大”是指樹足夠深且葉節(jié)點(diǎn)足夠多);再使用修正數(shù)據(jù)集對(duì)樹進(jìn)行修剪,選取對(duì)修正數(shù)據(jù)集預(yù)測(cè)性能最好的子樹。8決策樹的生長與修剪上述過程中有幾個(gè)主要任務(wù)需要完成:2.在決策樹生長過程中,如何決定某個(gè)節(jié)點(diǎn)是葉節(jié)點(diǎn)還是需要進(jìn)一步劃分;1.在決策樹生長過程中,如果需要對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行進(jìn)一步劃分,為其選擇劃分規(guī)則;3.決定每個(gè)葉節(jié)點(diǎn)的預(yù)測(cè)值;4.修剪決策樹。9決策樹的生長與修剪先考察因變量為可取值1,2,…,K的分類變量的情形,此時(shí)建立的決策樹是分類樹。首先來看如何為需要進(jìn)一步劃分的節(jié)點(diǎn)選擇合適的劃分(任務(wù)1)。需要根據(jù)某個(gè)自變量的值,將節(jié)點(diǎn)t的觀測(cè)劃分入H個(gè)子節(jié)t1,…,tH,pth表示劃分入子節(jié)點(diǎn)th的觀測(cè)比例(h=1,…,H)。10候選劃分集的生成首先尋找所有可能的劃分規(guī)則構(gòu)成候選劃分集S,再從中選擇最優(yōu)的劃分。對(duì)每個(gè)自變量xr,可能的劃分規(guī)則如下:若xr是定序或連續(xù)自變量,可將訓(xùn)練數(shù)據(jù)集中該變量的取值按照從小到大的順序排列,假設(shè)不重疊的取值為xr(1)<xr(2)<…<xr(Mr),定義xr(Mr+1)=∞。對(duì)于任何1=i0<i1<…<iH-1<iH=Mr+1,都可構(gòu)造一個(gè)候選劃分:對(duì)h=1,…,H,將滿足

的觀測(cè)劃分入第h個(gè)子節(jié)點(diǎn)。11候選劃分集的生成若xr是名義變量,設(shè)其不同的取值為Vr={xr(1),…,xr(Mr)}??梢詷?gòu)造Vr的分割:ψ1,…,ψH,使得每個(gè)ψh都是Vr的真子集且互相之間交集為空集,再將xr取值屬于ψh的觀測(cè)劃分入第h個(gè)子節(jié)點(diǎn)。注意,ψ1,…,ψH的不同排列得到的劃分是一樣的,因此需要避免冗余。12候選劃分集的約簡減少候選劃分集的大小可以降低決策樹建模的復(fù)雜度。有多種方法可以減少候選劃分集的大小,例如:使用降維方法減少變量個(gè)數(shù);通過數(shù)據(jù)分箱等方法減少定序或連續(xù)變量的不重復(fù)取值的個(gè)數(shù);將名義變量歸于更少的類別。13選擇最優(yōu)劃分的準(zhǔn)則一——不純凈性度量要從S中選擇最優(yōu)劃分,可使用節(jié)點(diǎn)的不純凈性度量Q(·)。劃分前t節(jié)點(diǎn)的不純凈性為Q(t);劃分后的平均不純凈性為:

。S中的最優(yōu)劃分應(yīng)使不純凈性下降最多,即

的值最大。14不純凈性度量(一)——基尼系數(shù)令p(l│t)表示節(jié)點(diǎn)t中類別l的比例?;嵯禂?shù):若p(l│t)=……=p(K│t)=1/K(即節(jié)點(diǎn)t是最不“純凈”的),基尼系數(shù)達(dá)到最大值。若某個(gè)p(l│t)等于1而其它類別的比例等于0(即節(jié)點(diǎn)t是最“純凈”的),基尼系數(shù)達(dá)到最小值?;嵯禂?shù)可解釋為誤分類的概率:如果在節(jié)點(diǎn)t中隨機(jī)抽取一個(gè)觀測(cè),那么該觀測(cè)以p(l1│t)的概率屬于類別l1(1≤l1≤K);若再將該觀測(cè)按節(jié)點(diǎn)t內(nèi)各類別的概率分布隨機(jī)歸類,它被歸于類別l2的比例為p(l2│t)(1≤l2≤K);誤分類的情形對(duì)應(yīng)于l1≠l2,其概率等于

,也就是基尼系數(shù)。15不純凈性度量(二)——熵熵:若某p(l│t)等于1而其它類別的比例等于0(即節(jié)點(diǎn)t是最“純凈”的),那么熵達(dá)到最小值。若p(l│t)=…=p(K│t)=1/K(即節(jié)點(diǎn)t是最不“純凈”的),那么熵達(dá)到最大值;16選擇最優(yōu)劃分的準(zhǔn)則二——卡方檢驗(yàn)值因變量為名義變量時(shí),也可使用卡方檢驗(yàn)選擇最優(yōu)劃分。將觀測(cè)比例按照子節(jié)點(diǎn)和因變量的類別作列聯(lián)表(表中概率為pthp(1│th),l=1,…,K,h=1,…,H)??ǚ綑z驗(yàn)可檢驗(yàn)兩者之間是否獨(dú)立,如果獨(dú)立則說明各個(gè)子節(jié)點(diǎn)內(nèi)因變量的概率分布一樣,都等于被劃分節(jié)點(diǎn)內(nèi)因變量的概率分布,也就是說劃分沒有增強(qiáng)模型對(duì)因變量的辨別能力。鑒此,最優(yōu)的劃分應(yīng)具有最小的p值,即子節(jié)點(diǎn)和因變量的類別最顯著地不獨(dú)立。17參數(shù)的估計(jì)概率p(l│t)和pth都需要使用訓(xùn)練數(shù)據(jù)集來估計(jì)。p(l│t)可使用落入節(jié)點(diǎn)t的訓(xùn)練觀測(cè)中屬于類別l的比例來估計(jì)。pth(h=1,…,H)可使用落入節(jié)點(diǎn)t的訓(xùn)練觀測(cè)中被劃分入子節(jié)點(diǎn)th的比例來估計(jì)。18參數(shù)的估計(jì)如果訓(xùn)練數(shù)據(jù)集的類別比例和將來應(yīng)用模型的數(shù)據(jù)集的類別比例不一致,而又希望在建模過程中使用后者的類別比例,那么就需要把后者的類別比例當(dāng)作先驗(yàn)概率π(l)=Pr(Y=l),在計(jì)算p(l│t)和Pth需要進(jìn)行調(diào)整,調(diào)整方法如下:令Nl(t)表示訓(xùn)練數(shù)據(jù)集中屬于類別l且落入節(jié)點(diǎn)t的觀測(cè)數(shù),Nl表示訓(xùn)練數(shù)據(jù)集中屬于類別l的觀測(cè)數(shù);節(jié)點(diǎn)t給定類別l的條件概率可估計(jì)為:類別l與節(jié)點(diǎn)t的聯(lián)合概率可估計(jì)為:節(jié)點(diǎn)t的邊緣概率可估計(jì)為:類別l給定節(jié)點(diǎn)t的后驗(yàn)概率可估計(jì)為:pth可估計(jì)為:19葉節(jié)點(diǎn)的確定伴隨著劃分過程的持續(xù)進(jìn)行,樹持續(xù)生長,直至下列情況之一發(fā)生才使相應(yīng)的節(jié)點(diǎn)成為葉節(jié)點(diǎn)而不再進(jìn)行劃分:節(jié)點(diǎn)內(nèi)訓(xùn)練數(shù)據(jù)的觀測(cè)數(shù)達(dá)到某個(gè)最小值;樹的深度達(dá)到一定限制;因變量為名義變量且使用卡方檢驗(yàn)選擇劃分時(shí),沒有哪個(gè)劃分的p值小于臨界值。20評(píng)估分類樹的預(yù)測(cè)性能先來看如何評(píng)估分類樹的預(yù)測(cè)性能。令?表示評(píng)估數(shù)據(jù)集,N?為其中的觀測(cè)數(shù),令Yi和?i分別表示?中觀測(cè)i的因變量的真實(shí)值和預(yù)測(cè)值??梢圆捎萌缦乱恍┲笜?biāo)來評(píng)估預(yù)測(cè)性能:誤分類率、平均利潤或平均損失、總的基尼不純凈性度量、提升值。21評(píng)估分類樹的預(yù)測(cè)性能1.誤分類率:對(duì)?的誤分類率為:若因變量為定序變量,可使用按序數(shù)距離加權(quán)的誤分類率:誤分類率越低,分類樹性能越好。22評(píng)估分類樹的預(yù)測(cè)性能2.平均利潤或平均損失:定義利潤矩陣,矩陣中的元素P(l2│l1)表示將一個(gè)實(shí)際屬于類別l1的觀測(cè)歸入類別l2時(shí)產(chǎn)生的利潤(1≤l1,l2≤K)。對(duì)于名義因變量,缺省地對(duì)于定序因變量,缺省地可以定義損失矩陣,矩陣中的元素C(l2│l1)為將一個(gè)實(shí)際屬于類別l1的觀測(cè)歸入類別l2時(shí)產(chǎn)生的損失。對(duì)于名義因變量,缺省地對(duì)于定序因變量,缺省地對(duì)?的平均利潤為

,平均損失為平均利潤越高或平均損失越低,分類樹性能越好。23評(píng)估分類樹的預(yù)測(cè)性能在很多情形下,利潤或損失矩陣的值不同于缺省值。例如:將實(shí)際會(huì)違約的企業(yè)判斷為不違約者,會(huì)帶來信用損失(貸款的本金、利息等);而將實(shí)際不會(huì)違約的企業(yè)判斷為違約者,會(huì)導(dǎo)致銀行失去潛在的業(yè)務(wù)和盈利機(jī)會(huì)。這兩種損失的大小可能不一樣。當(dāng)利潤矩陣或損失矩陣取缺省值時(shí),依據(jù)平均利潤或平均損失來選擇分類樹等價(jià)于依據(jù)誤分類率來選擇分類樹。24評(píng)估分類樹的預(yù)測(cè)性能3.總的基尼不純凈性度量:設(shè)p?(t)為根據(jù)?計(jì)算的葉節(jié)點(diǎn)t的概率,

p?(l│t)為根據(jù)數(shù)據(jù)?計(jì)算的葉節(jié)點(diǎn)t內(nèi)類別l的概率,它們可能經(jīng)過先驗(yàn)概率調(diào)整。葉節(jié)點(diǎn)t內(nèi)的基尼不純凈性度量等于按照各葉節(jié)點(diǎn)概率分布,可計(jì)算總的基尼不純凈性度量:總的基尼不純凈性度量越低,分類樹性能越好。25評(píng)估分類樹的預(yù)測(cè)性能4.提升值:假設(shè)有一目標(biāo)事件(如違約、欺作、響應(yīng)直郵營銷等),可按照目標(biāo)事件的預(yù)測(cè)概率從大到小的順序排列?中的觀測(cè);前n%的觀測(cè)中,目標(biāo)事件真實(shí)發(fā)生的比例越高,分類樹性能越好。若定義了利潤或損失矩陣,可按照預(yù)測(cè)利潤從高到低或預(yù)測(cè)損失從低到高的順序排列?中的觀測(cè);前n%的觀測(cè)中,實(shí)際平均利潤越高或?qū)嶋H平均損失越低,分類樹性能越好。26決定葉節(jié)點(diǎn)的預(yù)測(cè)值分類樹構(gòu)建好之后,需要對(duì)每個(gè)葉節(jié)點(diǎn)t進(jìn)行歸類(任務(wù)3)??疾旄鶕?jù)訓(xùn)練數(shù)據(jù)集計(jì)算的P(l│t)(可能經(jīng)過先驗(yàn)概率調(diào)整)。如果沒有定義利潤和損失矩陣,可將葉節(jié)點(diǎn)t歸入使P(l│t)最大的類別l。若定義了利潤矩陣,可將葉節(jié)點(diǎn)t歸入使最大的類別l*。若定義了損失矩陣,可將葉節(jié)點(diǎn)t歸入使最小的類別l*。27分類樹的修剪分類樹的修剪分類樹是根據(jù)訓(xùn)練數(shù)據(jù)集生長而成的,葉節(jié)點(diǎn)越多,對(duì)訓(xùn)練數(shù)據(jù)集的預(yù)測(cè)性能越好,但葉節(jié)點(diǎn)過多會(huì)把訓(xùn)練數(shù)據(jù)集的噪音也學(xué)習(xí)進(jìn)來,造成過度擬合。鑒此,需要對(duì)分類樹進(jìn)行修剪(任務(wù)4),這時(shí)需要依據(jù)各子樹對(duì)修正數(shù)據(jù)集的預(yù)測(cè)性能來選擇最優(yōu)的子樹。28決策樹的修剪舉例而言,下表列出了某決策樹的各子樹對(duì)訓(xùn)練數(shù)據(jù)集和修正數(shù)據(jù)集的誤分類率。葉節(jié)點(diǎn)越多,對(duì)訓(xùn)練數(shù)據(jù)集的誤分類率越低;修正數(shù)據(jù)集的誤分類率卻先下降后上升;我們應(yīng)該選擇有10個(gè)葉節(jié)點(diǎn)的子樹作為最終的模型。29回歸樹回歸樹和分類樹建立的過程類似。在選擇劃分時(shí),同樣可以用不純凈性下降幅度最大作為標(biāo)準(zhǔn)。節(jié)點(diǎn)t的不純凈性可用方差來度量。具體而言,令Yirain為訓(xùn)練數(shù)據(jù)集中觀測(cè)i的因變量值,

Yirain為落入節(jié)點(diǎn)t的訓(xùn)練觀測(cè)的因變量的平均值,那么節(jié)點(diǎn)t的不純凈性度量為:30回歸樹也可使用F檢驗(yàn)也可以選擇最優(yōu)劃分。F檢驗(yàn)可檢驗(yàn)各子節(jié)點(diǎn)的因變量均值是否相等(類似于單因素方差分析中的F檢驗(yàn))。如果相等,說明劃分沒有增強(qiáng)模型對(duì)因變量的辨別能力。因此,最優(yōu)的劃分具有最小的p值,即各子節(jié)點(diǎn)內(nèi)觀測(cè)的因變量均值最顯著地不相等。31回歸樹如果節(jié)點(diǎn)內(nèi)訓(xùn)練觀測(cè)數(shù)達(dá)到某個(gè)最小值,或樹的深度達(dá)到一定限制,或使用F檢驗(yàn)選擇最優(yōu)劃分時(shí)沒有哪個(gè)劃分的p值小于某個(gè)臨界值,那么當(dāng)前節(jié)點(diǎn)就成為葉節(jié)點(diǎn)。對(duì)葉節(jié)點(diǎn)t內(nèi)的所有觀測(cè),預(yù)測(cè)值都等于Ytrai

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論