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

1第十一講

決策樹（1）2決策樹簡介

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

的觀測劃分入第h個子節(jié)點(diǎn)。11候選劃分集的生成若xr是名義變量，設(shè)其不同的取值為Vr={xr(1),…,xr(Mr)}。可以構(gòu)造Vr的分割:ψ1,…,ψH，使得每個ψh都是Vr的真子集且互相之間交集為空集，再將xr取值屬于ψh的觀測劃分入第h個子節(jié)點(diǎn)。注意，ψ1,…,ψH的不同排列得到的劃分是一樣的，因此需要避免冗余。12候選劃分集的約簡減少候選劃分集的大小可以降低決策樹建模的復(fù)雜度。有多種方法可以減少候選劃分集的大小，例如:使用降維方法減少變量個數(shù)；通過數(shù)據(jù)分箱等方法減少定序或連續(xù)變量的不重復(fù)取值的個數(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á)到最大值。若某個p(l│t)等于1而其它類別的比例等于0(即節(jié)點(diǎn)t是最“純凈”的)，基尼系數(shù)達(dá)到最小值?；嵯禂?shù)可解釋為誤分類的概率：如果在節(jié)點(diǎn)t中隨機(jī)抽取一個觀測，那么該觀測以p(l1│t)的概率屬于類別l1(1≤l1≤K)；若再將該觀測按節(jié)點(diǎn)t內(nèi)各類別的概率分布隨機(jī)歸類，它被歸于類別l2的比例為p(l2│t)(1≤l2≤K)；誤分類的情形對應(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ōu)劃分。將觀測比例按照子節(jié)點(diǎn)和因變量的類別作列聯(lián)表（表中概率為pthp(1│th)，l=1,…,K，h=1,…,H)?？ǚ綑z驗可檢驗兩者之間是否獨(dú)立，如果獨(dú)立則說明各個子節(jié)點(diǎn)內(nèi)因變量的概率分布一樣，都等于被劃分節(jié)點(diǎn)內(nèi)因變量的概率分布，也就是說劃分沒有增強(qiáng)模型對因變量的辨別能力。鑒此，最優(yōu)的劃分應(yīng)具有最小的p值，即子節(jié)點(diǎn)和因變量的類別最顯著地不獨(dú)立。17參數(shù)的估計概率p(l│t)和pth都需要使用訓(xùn)練數(shù)據(jù)集來估計。p(l│t)可使用落入節(jié)點(diǎn)t的訓(xùn)練觀測中屬于類別l的比例來估計。pth(h=1,…,H)可使用落入節(jié)點(diǎn)t的訓(xùn)練觀測中被劃分入子節(jié)點(diǎn)th的比例來估計。18參數(shù)的估計如果訓(xùn)練數(shù)據(jù)集的類別比例和將來應(yīng)用模型的數(shù)據(jù)集的類別比例不一致，而又希望在建模過程中使用后者的類別比例，那么就需要把后者的類別比例當(dāng)作先驗概率π(l)=Pr(Y=l)，在計算p(l│t)和Pth需要進(jìn)行調(diào)整，調(diào)整方法如下:令Nl(t)表示訓(xùn)練數(shù)據(jù)集中屬于類別l且落入節(jié)點(diǎn)t的觀測數(shù)，Nl表示訓(xùn)練數(shù)據(jù)集中屬于類別l的觀測數(shù);節(jié)點(diǎn)t給定類別l的條件概率可估計為:類別l與節(jié)點(diǎn)t的聯(lián)合概率可估計為:節(jié)點(diǎn)t的邊緣概率可估計為:類別l給定節(jié)點(diǎn)t的后驗概率可估計為:pth可估計為: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ù)的觀測數(shù)達(dá)到某個最小值;樹的深度達(dá)到一定限制;因變量為名義變量且使用卡方檢驗選擇劃分時，沒有哪個劃分的p值小于臨界值。20評估分類樹的預(yù)測性能先來看如何評估分類樹的預(yù)測性能。令?表示評估數(shù)據(jù)集，N?為其中的觀測數(shù)，令Yi和?i分別表示?中觀測i的因變量的真實值和預(yù)測值?？梢圆捎萌缦乱恍┲笜?biāo)來評估預(yù)測性能：誤分類率、平均利潤或平均損失、總的基尼不純凈性度量、提升值。21評估分類樹的預(yù)測性能1.誤分類率:對?的誤分類率為：若因變量為定序變量，可使用按序數(shù)距離加權(quán)的誤分類率：誤分類率越低，分類樹性能越好。22評估分類樹的預(yù)測性能2.平均利潤或平均損失:定義利潤矩陣，矩陣中的元素P(l2│l1)表示將一個實際屬于類別l1的觀測歸入類別l2時產(chǎn)生的利潤(1≤l1,l2≤K)。對于名義因變量，缺省地對于定序因變量，缺省地可以定義損失矩陣，矩陣中的元素C(l2│l1)為將一個實際屬于類別l1的觀測歸入類別l2時產(chǎn)生的損失。對于名義因變量，缺省地對于定序因變量，缺省地對?的平均利潤為

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

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

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