1第十一講

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

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

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

。S中的最優劃分應使不純凈性下降最多，即

的值最大。14不純凈性度量（一）——基尼系數令p(l│t)表示節點t中類別l的比例。基尼系數:若p(l│t)=……=p(K│t)=1/K(即節點t是最不“純凈”的)，基尼系數達到最大值。若某個p(l│t)等于1而其它類別的比例等于0(即節點t是最“純凈”的)，基尼系數達到最小值。基尼系數可解釋為誤分類的概率：如果在節點t中隨機抽取一個觀測，那么該觀測以p(l1│t)的概率屬于類別l1(1≤l1≤K)；若再將該觀測按節點t內各類別的概率分布隨機歸類，它被歸于類別l2的比例為p(l2│t)(1≤l2≤K)；誤分類的情形對應于l1≠l2，其概率等于

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

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

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

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