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

1第十二講

決策樹（2）2對缺失數(shù)據(jù)的處理決策樹的建模過程會忽略因變量缺失的觀測，但是決策樹可以有效地處理自變量的缺失值。在劃分節(jié)點t時，如果訓(xùn)練數(shù)據(jù)集中自變量xr存在缺失值，那么，根據(jù)xr缺失的觀測被歸入哪一個子節(jié)點，S中原有的使用xr的每一個候選劃分都變成H個候選劃分;最簡單的做法是在劃分節(jié)點時將劃分變量缺失的所有觀測歸入同一個子節(jié)點。還增加一些這樣的候選劃分:將xr缺失的觀測歸入一個子節(jié)點，而將其它所有觀測歸入另外H-1個子節(jié)點。新的候選劃分集生成后，可再從中選擇最優(yōu)劃分。3對缺失數(shù)據(jù)的處理這樣處理缺失數(shù)據(jù)，相當(dāng)于：對名義變量而言將缺失值看作一個單獨的類別，而對定序或連續(xù)變量而言，將缺失值看作同一個未知的數(shù)值。但是，對xr缺失的那些觀測，這種做法完全忽視了其它自變量可能含有的關(guān)于xr的信息，因而不太妥當(dāng)。4對缺失數(shù)據(jù)的處理另一種更為妥當(dāng)?shù)奶幚碜宰兞咳笔е档姆椒ㄊ鞘褂锰娲鷦澐忠?guī)則(surrogatesplittingrule)。假設(shè)節(jié)點t的最優(yōu)劃分規(guī)則使用了自變量xr，我們稱該劃分規(guī)則為主劃分規(guī)則(mainsplittingrule)，稱xr為主劃分變量。xr值缺失的觀測觀測不是立即被歸入接受缺失值的子節(jié)點，而是先使用第一替代規(guī)則進(jìn)行劃分，如果第一替代規(guī)則使用的變量也缺失，則使用第二替代規(guī)則進(jìn)行劃分，如此等等;如果所有替代規(guī)則使用的變量都缺失，這些觀測才被主劃分規(guī)則歸入接受缺失值的子節(jié)點。例如，在對購買金額進(jìn)行預(yù)測時，某個節(jié)點可能先嘗試使用收入進(jìn)行劃分，如果觀測的收入值缺失，可能嘗試使用性別進(jìn)行劃分，如果性別也缺失，可能再嘗試使用教育程度進(jìn)行劃分，等等。5對缺失數(shù)據(jù)的處理可以按照候選劃分規(guī)則與主規(guī)則的相似度從高到低的順序來選擇替代規(guī)則。相似度被定義為主規(guī)則和替代規(guī)則劃分入同一個子節(jié)點的訓(xùn)練觀測的比例。如果某訓(xùn)練觀測的主劃分變量不缺失而替代劃分變量缺失，那么該觀測被當(dāng)作由這兩個規(guī)則劃分入不同的子節(jié)點。在計算過程中，主劃分變量缺失的訓(xùn)練觀測不納入相似度的計算中;6變量選擇決策樹可用來做變量選擇。首先定義樹中每個節(jié)點t對于訓(xùn)練數(shù)據(jù)集的誤差平方和SSE(t):若因變量是連續(xù)變量，那么：若因變量是分類變量，那么：其中δiltrain是關(guān)于訓(xùn)練觀測i的指示變量，如果訓(xùn)練觀測i屬于類別l，則δiltrain

=1，否則δiltrain

=0。7變量選擇若將非葉節(jié)點t劃分為H個子節(jié)點：t1,…,tH，該劃分所帶來的誤差平方和減少量為：

在劃分非葉節(jié)點t所帶來的誤差平方和減少量中，自變量xr的貢獻(xiàn)定義為a(r,t)ΔSSE(t)。自變量xr對t的重要性定義為：若節(jié)點t的主劃分規(guī)則使用xr若節(jié)點t的某替代劃分規(guī)則使用xr其它8變量選擇自變量xr對整個決策樹T的重要性定義為這些貢獻(xiàn)總和的平方根，即：按照l(r,T)從高到低的順序?qū)ψ宰兞颗判?，可選擇排列在前面的一些自變量。9決策樹的優(yōu)缺點相對于其它模型而言，決策樹有如下優(yōu)點:在樹的生長過程中，對定序或連續(xù)自變量而言只需使用變量取值的大小順序而不使用具體取值。決策樹所產(chǎn)生的預(yù)測規(guī)則的形式為：如果xr1A1且,…,且xrmAm，那么Y=y，很容易解釋。因為對這些自變量進(jìn)行任何單調(diào)增變換（例如，取對數(shù)）都不改變變量取值的大小順序，而對自變量進(jìn)行任何單調(diào)減變換（例如，取倒數(shù)）把原來取值的大小順序完全顛倒；所以這些變換都不會改變劃分的結(jié)果。故此，在建立決策樹時，無需考慮自變量的轉(zhuǎn)換（但注意，有時需要考慮因變量的轉(zhuǎn)換）。10決策樹的優(yōu)缺點因為決策樹只使用了定序或連續(xù)自變量取值的大小順序，它對自變量的測量誤差或異常值是穩(wěn)健的。決策樹能夠直接處理自變量的缺失值。在數(shù)據(jù)準(zhǔn)備過程中，如果數(shù)據(jù)中有多個自變量存在缺失，決策樹可用來插補(bǔ)這些自變量的缺失值。決策樹可以用作變量選擇的工具。11決策樹的優(yōu)缺點決策樹也有如下缺點:每個非葉節(jié)點的劃分都只考慮單個變量，因此很難發(fā)現(xiàn)基于多個變量的組合的規(guī)則。為每個非葉節(jié)點選擇最優(yōu)劃分時，都僅考慮對當(dāng)前節(jié)點劃分的結(jié)果，這樣只能夠達(dá)到局部最優(yōu)，而無法達(dá)到全局最優(yōu)。12決策樹的優(yōu)缺點正因為決策樹是局部貪婪的，樹的結(jié)構(gòu)很不穩(wěn)定。例如，若將學(xué)習(xí)數(shù)據(jù)集隨機(jī)分割為不同的訓(xùn)練數(shù)據(jù)集和修正數(shù)據(jù)集，可能對于某次分割，xr1被選作根節(jié)點的劃分變量，而對于另一次分割，xr2(r2≠r1)被選作根節(jié)點的劃分變量，之后繼續(xù)劃分下去，這兩棵樹的結(jié)構(gòu)差異會非常大因為不同結(jié)構(gòu)的樹隱含的預(yù)測規(guī)則存在不同的解釋，所以這種結(jié)構(gòu)不穩(wěn)定性也降低了決策樹的可解釋性。這種差異也可能使得兩棵樹的預(yù)測性能存在很大差異。13Benelearn競賽數(shù)據(jù)我們通過一個例子來察看決策樹的第三個缺點及克服這種缺點的一個簡單辦法。Benelearn是比利時與荷蘭聯(lián)合召開的關(guān)于機(jī)器學(xué)習(xí)的年度會議。1999年的Benelearn會議舉辦了一個機(jī)器學(xué)習(xí)竟賽，由荷蘭的一家數(shù)據(jù)挖掘公司SentientMachineResearch提供一個基于實際商務(wù)的數(shù)據(jù)集(見http://hcs.science.uva.nl/benelearn99/comppage.html)。14Benelearn競賽數(shù)據(jù)該數(shù)據(jù)集含有一個保險公司的客戶的下列信息:變量1-43描述客戶郵編所在地的社會人口特征;變量44-86描述客戶對各保險產(chǎn)品的使用情況;變量86是一個0-1變量，指示客戶是否擁有房車保險，它也是需要預(yù)測的因變量。15Benelearn競賽數(shù)據(jù)每位參賽者都會得到一份含有5823位客戶全部信息的學(xué)習(xí)數(shù)據(jù)集，參賽者需要根據(jù)該數(shù)據(jù)集建立預(yù)測模型。參賽者需要使用自己建立的預(yù)測模型從測試數(shù)據(jù)集中挑選出最有可能擁有房車保險的800位客戶，賽事組織者將計算其中實際擁有房車保險的客戶數(shù)，以此對參賽者進(jìn)行評價。參賽者也會得到一份包含4000位客戶的變量1-85信息的測試數(shù)據(jù)集，只有賽事組織者才知道這些客戶的因變量的真實值。測試數(shù)據(jù)集中實際擁有房車保險的客戶數(shù)為238位，而當(dāng)年勝出的模