决策树演算法

決策樹簡介決策樹是採用樹狀分岔的架構來產生規則，適用於所有分類的問題。Ex:信用卡授信、直效行銷回應、顧客流失預測等1決策樹生長流程資料母體作為根節點。根據最佳變數產生分岔，產生子節點。根據每個子節點案例分佈狀況指派分類結果。決策樹持續生長，最後採用修剪技術減去不必要的規則。2產生決策樹時的問題純淨度是一個抽象的概念，須以數學公式量化。每個變數產生的分岔數目不同，須將純淨度加總以評估可讓純淨度最高的變數。子節點的純淨度總合必須能和母節點的純淨度互相比較，以決定分岔是否要保留。輸入變數若為連續變數，如何快速找出最好的切割點使得純淨度最高。3決策樹的分岔準則將全體資料隨機切割成訓練組及鑑效組。根據分岔準則利用訓練組資料產生第一個分岔點。利用鑑效組資料驗證第一個分岔點是否為最佳分岔，若規則可再現，則繼續進行後續分岔，若規則不能再現(過度學習)則捨棄，從剩餘變數中篩選最佳分岔變數。反覆進行以上步驟直到沒有更純淨的子結點產生為止。利用修剪技術將無效的分岔節點修剪掉。4決策樹的成長觀念歸納建立決策樹是二種力量互相拉扯所產生之結果。利用變數產生分岔的成長力量透過驗證以及修剪來抑制決策樹成長抑制成長的二種力量同步抑制：透過鑑效組資料來驗證修剪事後抑制：將最後多餘的節點修剪掉鑑效組修剪法最早應用於80年代的AID決策樹演算法。5決策樹的計算常用的決策樹演算法

ID3,C4,C4.5,C5,CART,CHAID,QUESTC4.5決策樹演算法修正ID3以資訊報酬作為分岔準則的做法，改以增益比值的計算公式來取代，增益比值的觀念為當使用某變數作為分岔變數時，檢視母節點與子節點總合的純淨度變化量，使純淨度提升較多的變數就是有效變數。增益比值公式gainratio=(entropybefore–entropyafter)/splitgains增益比例=母節點與子節點的亂度差/分岔程度的修正量

entropy(熵)表示亂度(來自於化學熱力學)，用來表示物體分佈的分散狀況，亂度越高則越無規則。6決策樹的計算範例-1假設建置模型的訓練資料有100個案例，其中20%的人合約到期後三個月內會流失，則母節點亂度的計算式為：entropy母節點

=-

Xlog2XX是指預測變數選項i的分率ni/n=-(20/100)log2(20/100)–(80/100)log2(80/100)=0.7219287決策樹的計算範例-2假設再使用性別作為切割變數，則可以將母節點切成二塊(男性60人，流失率25%；女性40人，流失率12.5%)，二個子節點的亂度計算式為：entropy分支

=(n子節點

/n母節點)*entropy子節點

=(60/100)*(-(15/60)log2(15/60)–(45/60)log2(45/60))+(40/100)*(-(5/40)log2(5/40)–(35/40)log2(35/40))=0.7049138大家有疑问的，可以询问和交流可以互相讨论下，但要小声点9決策樹的計算範例-3此例中將資料由100切割為60,40二塊，其亂度變化為：Splitgains

=-(60/100)log2(60/100)–(40/100)log2(40/100)=0.970951gainsratio=(entropy母節點

–entropy子節點)/splitgains=(0.721928–0.704913)/0.970951=0.01752410決策樹的計算範例-4再假設有一個變數是費率，若根據費率來作為分岔變數，則可知：A費率：30人，拆機人數3人B費率：45人，拆機人數15人C費率：25人，拆機人數2人請計算其增益比例值：gainsratio=(entropy母節點

–entropy子節點)/splitgains=(0.721928–0.654477)/1.539491=0.04381