數(shù)據(jù)挖掘與應(yīng)用(十一)

1第十一講

決策樹（1）2決策樹簡(jiǎn)介

決策樹是一種根據(jù)自變量的值進(jìn)行遞歸劃分以預(yù)測(cè)因變量的方法。若因變量為連續(xù)變量，則稱相應(yīng)的決策樹為回歸樹。若因變量為分類變量，則稱相應(yīng)的決策樹為分類樹;3決策樹簡(jiǎn)介假設(shè)數(shù)據(jù)集risk中含有下表所示信息:4決策樹簡(jiǎn)介根據(jù)數(shù)據(jù)集中其它變量來預(yù)測(cè)風(fēng)險(xiǎn)類別的決策樹模型如下圖所示。5決策樹簡(jiǎn)介根節(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決策樹簡(jiǎn)介對(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決策樹的生長(zhǎng)與修剪構(gòu)建決策樹時(shí):先根據(jù)訓(xùn)練數(shù)據(jù)集生成一棵足夠大的決策樹（“足夠大”是指樹足夠深且葉節(jié)點(diǎn)足夠多）；再使用修正數(shù)據(jù)集對(duì)樹進(jìn)行修剪，選取對(duì)修正數(shù)據(jù)集預(yù)測(cè)性能最好的子樹。8決策樹的生長(zhǎng)與修剪上述過程中有幾個(gè)主要任務(wù)需要完成:2.在決策樹生長(zhǎng)過程中，如何決定某個(gè)節(jié)點(diǎn)是葉節(jié)點(diǎn)還是需要進(jìn)一步劃分；1.在決策樹生長(zhǎng)過程中，如果需要對(duì)某個(gè)節(jié)點(diǎn)進(jìn)行進(jìn)一步劃分，為其選擇劃分規(guī)則；3.決定每個(gè)葉節(jié)點(diǎn)的預(yù)測(cè)值;4.修剪決策樹。9決策樹的生長(zhǎng)與修剪先考察因變量為可取值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，再?gòu)闹羞x擇最優(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候選劃分集的約簡(jiǎn)減少候選劃分集的大小可以降低決策樹建模的復(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ù)生長(zhǎng)，直至下列情況之一發(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è)性能：誤分類率、平均利潤(rùn)或平均損失、總的基尼不純凈性度量、提升值。21評(píng)估分類樹的預(yù)測(cè)性能1.誤分類率:對(duì)?的誤分類率為：若因變量為定序變量，可使用按序數(shù)距離加權(quán)的誤分類率：誤分類率越低，分類樹性能越好。22評(píng)估分類樹的預(yù)測(cè)性能2.平均利潤(rùn)或平均損失:定義利潤(rùn)矩陣，矩陣中的元素P(l2│l1)表示將一個(gè)實(shí)際屬于類別l1的觀測(cè)歸入類別l2時(shí)產(chǎn)生的利潤(rùn)(1≤l1,l2≤K)。對(duì)于名義因變量，缺省地對(duì)于定序因變量，缺省地可以定義損失矩陣，矩陣中的元素C(l2│l1)為將一個(gè)實(shí)際屬于類別l1的觀測(cè)歸入類別l2時(shí)產(chǎn)生的損失。對(duì)于名義因變量，缺省地對(duì)于定序因變量，缺省地對(duì)?的平均利潤(rùn)為

，平均損失為平均利潤(rùn)越高或平均損失越低，分類樹性能越好。23評(píng)估分類樹的預(yù)測(cè)性能在很多情形下，利潤(rùn)或損失矩陣的值不同于缺省值。例如：將實(shí)際會(huì)違約的企業(yè)判斷為不違約者，會(huì)帶來信用損失（貸款的本金、利息等）；而將實(shí)際不會(huì)違約的企業(yè)判斷為違約者，會(huì)導(dǎo)致銀行失去潛在的業(yè)務(wù)和盈利機(jī)會(huì)。這兩種損失的大小可能不一樣。當(dāng)利潤(rùn)矩陣或損失矩陣取缺省值時(shí)，依據(jù)平均利潤(rùn)或平均損失來選擇分類樹等價(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)直郵營(yíng)銷等)，可按照目標(biāo)事件的預(yù)測(cè)概率從大到小的順序排列?中的觀測(cè);前n%的觀測(cè)中，目標(biāo)事件真實(shí)發(fā)生的比例越高，分類樹性能越好。若定義了利潤(rùn)或損失矩陣，可按照預(yù)測(cè)利潤(rùn)從高到低或預(yù)測(cè)損失從低到高的順序排列?中的觀測(cè)；前n%的觀測(cè)中，實(shí)際平均利潤(rùn)越高或?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)整)。如果沒有定義利潤(rùn)和損失矩陣，可將葉節(jié)點(diǎn)t歸入使P(l│t)最大的類別l。若定義了利潤(rùn)矩陣，可將葉節(jié)點(diǎn)t歸入使最大的類別l*。若定義了損失矩陣，可將葉節(jié)點(diǎn)t歸入使最小的類別l*。27分類樹的修剪分類樹的修剪分類樹是根據(jù)訓(xùn)練數(shù)據(jù)集生長(zhǎng)而成的，葉節(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