第五章 決策樹(shù)演算法金融學(xué)院

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

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

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

4、-1n假設(shè)建置模型的訓(xùn)練資料有100個(gè)案例，其中20%的人合約到期後三個(gè)月內(nèi)會(huì)流失，則母節(jié)點(diǎn)亂度的計(jì)算式為：entropy母節(jié)點(diǎn) = -X log2 X X是指預(yù)測(cè)變數(shù)選項(xiàng)i的分率 ni / n = -(20/100) log2 (20/100) (80/100) log2 (80/100) = 0.721928決策樹(shù)的計(jì)算範(fàn)例-2n假設(shè)再使用性別作為切割變數(shù)，則可以將母節(jié)點(diǎn)切成二塊(男性60人，流失率25%；女性40人，流失率12.5%)，二個(gè)子節(jié)點(diǎn)的亂度計(jì)算式為：entropy 分支 = (n 子節(jié)點(diǎn) / n 母節(jié)點(diǎn)) * entropy 子節(jié)點(diǎn) = (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決策樹(shù)的計(jì)算範(fàn)例-3n此例中將資料由100切割為60,40二塊，其亂度變化為：Split gains = - (60/100) log2 (60/100) (40/100) log2 (40/100) = 0.970951gains ratio = (entropy母節(jié)點(diǎn) entropy子節(jié)點(diǎn)) / split gains = (0.721928 0.704913) / 0.970951 = 0.017524決策樹(shù)的計(jì)算範(fàn)例-4n再假設(shè)有一個(gè)變數(shù)是費(fèi)率，若根據(jù)費(fèi)率來(lái)作為分岔變數(shù)，則可知：A費(fèi)率：30人，拆機(jī)人數(shù)3人B費(fèi)率：45人，拆機(jī)人數(shù)15人C費(fèi)率：25人，拆機(jī)人數(shù)2人請(qǐng)計(jì)算其增益比例值：gains ratio = (entropy母節(jié)點(diǎn) entropy子節(jié)點(diǎn)) / split gains = (0.721928 0.654477) / 1.539491 = 0.043814gains ratio 費(fèi)率 gains ratio 性別 = 費(fèi)率較適合作為分岔變數(shù)n經(jīng)過(guò)鑑效組資料驗(yàn)證之後若在容忍誤差範(fàn)圍內(nèi)則可成為分岔變數(shù)決策樹(shù)