1第十二講

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

=1，否則δiltrain

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

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