第五章 決策樹演算法金融學院

1、第五章 決策樹演算法游政憲決策樹簡介n決策樹是採用樹狀分岔的架構(gòu)來產(chǎn)生規(guī)則，適用於所有分類的問題。nEx: 信用卡授信、直效行銷回應(yīng)、顧客流失預測等決策樹生長流程n資料母體作為根節(jié)點。n根據(jù)最佳變數(shù)產(chǎn)生分岔，產(chǎn)生子節(jié)點。n根據(jù)每個子節(jié)點案例分佈狀況指派分類結(jié)果。n決策樹持續(xù)生長，最後採用修剪技術(shù)減去不必要的規(guī)則。產(chǎn)生決策樹時的問題n純淨度是一個抽象的概念，須以數(shù)學公式量化。n每個變數(shù)產(chǎn)生的分岔數(shù)目不同，須將純淨度加總以評估可讓純淨度最高的變數(shù)。n子節(jié)點的純淨度總合必須能和母節(jié)點的純淨度互相比較，以決定分岔是否要保留。n輸入變數(shù)若為連續(xù)變數(shù)，如何快速找出最好的切割點使得純淨度最高。決策樹的分岔準

2、則n將全體資料隨機切割成訓練組及鑑效組。n根據(jù)分岔準則利用訓練組資料產(chǎn)生第一個分岔點。n利用鑑效組資料驗證第一個分岔點是否為最佳分岔，若規(guī)則可再現(xiàn)，則繼續(xù)進行後續(xù)分岔，若規(guī)則不能再現(xiàn)(過度學習)則捨棄，從剩餘變數(shù)中篩選最佳分岔變數(shù)。n反覆進行以上步驟直到?jīng)]有更純淨的子結(jié)點產(chǎn)生為止。n利用修剪技術(shù)將無效的分岔節(jié)點修剪掉。決策樹的成長觀念歸納n建立決策樹是二種力量互相拉扯所產(chǎn)生之結(jié)果。利用變數(shù)產(chǎn)生分岔的成長力量透過驗證以及修剪來抑制決策樹成長n抑制成長的二種力量同步抑制：透過鑑效組資料來驗證修剪事後抑制：將最後多餘的節(jié)點修剪掉n鑑效組修剪法最早應(yīng)用於80年代的AID 決策樹演算法。決策樹的計算n常

3、用的決策樹演算法 ID3, C4, C4.5, C5, CART, CHAID, QUESTnC4.5決策樹演算法修正ID3以資訊報酬作為分岔準則的做法，改以增益比值的計算公式來取代，增益比值的觀念為當使用某變數(shù)作為分岔變數(shù)時，檢視母節(jié)點與子節(jié)點總合的純淨度變化量，使純淨度提升較多的變數(shù)就是有效變數(shù)。增益比值公式gain ratio=(entropy before entropy after) / split gains增益比例=母節(jié)點與子節(jié)點的亂度差 / 分岔程度的修正量 entropy (熵) 表示亂度 (來自於化學熱力學)，用來表示物體分佈的分散狀況，亂度越高則越無規(guī)則。決策樹的計算範例

4、-1n假設(shè)建置模型的訓練資料有100個案例，其中20%的人合約到期後三個月內(nèi)會流失，則母節(jié)點亂度的計算式為：entropy母節(jié)點 = -X log2 X X是指預測變數(shù)選項i的分率 ni / n = -(20/100) log2 (20/100) (80/100) log2 (80/100) = 0.721928決策樹的計算範例-2n假設(shè)再使用性別作為切割變數(shù)，則可以將母節(jié)點切成二塊(男性60人，流失率25%；女性40人，流失率12.5%)，二個子節(jié)點的亂度計算式為：entropy 分支 = (n 子節(jié)點 / n 母節(jié)點) * entropy 子節(jié)點 = (60/100) * (-(15/60

5、) log2 (15/60) (45/60) log2 (45/60) + (40/100) * (-(5/40) log2 (5/40) (35/40) log2 (35/40) = 0.704913決策樹的計算範例-3n此例中將資料由100切割為60,40二塊，其亂度變化為：Split gains = - (60/100) log2 (60/100) (40/100) log2 (40/100) = 0.970951gains ratio = (entropy母節(jié)點 entropy子節(jié)點) / split gains = (0.721928 0.704913) / 0.970951 = 0.017524決策樹的計算範例-4n再假設(shè)有一個變數(shù)是費率，若根據(jù)費率來作為分岔變數(shù)，則可知：A費率：30人，拆機人數(shù)3人B費率：45人，拆機人數(shù)15人C費率：25人，拆機人數(shù)2人請計算其增益比例值：gains ratio = (entropy母節(jié)點 entropy子節(jié)點) / split gains = (0.721928 0.654477) / 1.539491 = 0.043814gains ratio 費率 gains ratio 性別 = 費率較適合作為分岔變數(shù)n經(jīng)過鑑效組資料驗證之後若在容忍誤差範圍內(nèi)則可成為分岔變數(shù)決策樹