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

1第十二講

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

=1，否則δiltrain

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

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