今天的上課重點是
１. Decision Tree 決策樹分類法則 -- Entropy
２. Decision Tree 決策樹，在分割後，評估結果是否改善
３. Decision Tree 的 特色介紹
４. Decision Tree 的 一般化錯誤( Generalization Error )
５. 如何改善 Decision Tree 過度學習( Over-fitting )
６. Decision Tree 的 成本矩陣( Cost Matrix )
1. Decision Tree 決策樹分類法則 -- Entropy
上周講到了Decision Tree 決策樹分類法以 Gini 為分類指標的方法
本周上課則也敘述另外一個常用的分類指標 Entropy 熵
而 Entropy 主要用在 C4.5 與 ID3分類法中
其公式如下：
注:Entropy 越小越好
直接舉個例子，比較好了解公式
P(Class 1) = 0/6 =0 ， P(Class 2) = 6/6 = 1
P(Class 1) = 1/6 ， P(Class 2)=5/6
由上面兩個例子就可以看得出來，Entropy越小，分類的越清楚
而 Entropy 的最大功用是計算 Information Gain，其計算方式是
分類前的資訊量 減 分類後的資訊量
2. Decision Tree 決策樹，在分割後，評估結果是否改善
在學會上述兩個分類方式評估值 Gini 與 Entropy 後
我們接下來要學習分了分割決策樹後，分割出來的子節點到底有沒有比父節點來的優異
一樣，直接以一個例子來說
以下為Gini的切割方法：
我們有父節點 A，分了兩個子節點 N1 與 N2
父節點原本是C1 有7個，C2有3個，其 Gini 值為0.42
而 子節點 N1，共3個，C1有3個，C2有0個，其 Gini 值為 0
而 子節點 N2，共7個，C1有4個，C2有3個，其 Gini 值為 0.489
而 整個子節點的 Gini 值為 0.342所以 Gini(Parent)=0.42 大於 Gini(Children)=0.324
可以這個子節點的分割是有改善分類的
以下為Entropy的切割方法：
同樣的，我們有父節點 A，分了兩個子節點 N1 與 N2
父節點原本是C1 有7個，C2有3個，其 Entropy 值為 0.881
而 子節點 N1，共3個，C1有3個，C2有0個，其 Entropy 值為 0
而 子節點 N2，共7個，C1有4個，C2有3個，其
Entropy 值為 0.985
而 整個子節點的
Entropy 值為 0.6895所以 Entropy(Parent)=0.881 大於 Entropy (Children)=0.6895
可以這個子節點的分割是有改善分類的
3. Decision Tree Induction 決策樹特性介紹
再來，決策樹的分類會有一些特點，比方說「貪婪策略 Greedy Strategy」，每一步面臨選擇時， 都做眼前最有利的選擇,，不考慮對將來是否有不良的影響。
這樣會造成一些問題，比方說：如何分割紀錄？怎麼指定條件？怎麼判斷最佳分割？以及最重要的，甚麼時候要停止分割？
一般停止分割的策略是：１.每一筆資料都歸類到同一個類別。２.所有的紀錄都是相同的值。３.決策者自行中斷。
而分類決策樹(Decision Tree Base Classification)有甚麼好處呢？
便捷的建造成本、快速分類未知的紀錄、小型的決策樹很容易被人解讀、對小樣本的資料正確性能夠比其他分類技術來的高
舉個決策樹分類方法 C4.5 建議參考資料:http://en.wikipedia.org/wiki/C4.5
１.這是以深度為優先的分類方法
２.使用資訊量(Information Gain)為評估指標
３.在每個節點中，排序連續型屬性
４.需要將資料匯入記憶體當中 -- 需要外製記憶體
4. Decision Tree 的 一般化錯誤( Generalization Error )
在真實世界中，資料通常不會這麼美好，分類容易訓練不足( Underfitting )或是過度學習( Overfitting )、容易有遺漏值、分類成本
圖中可以看到，訓練資料的錯誤會因為節點數越多，而開始下降
但測試資料因為節點越來越多，反而開始上升
這意味了訓練時把錯誤的趨勢也給學進去了
過度學習的情況之下，會有下面的幾個現象
１.過度學習的結果容易造成複雜化
２.決策樹不再提供好的預測水準
３.需要一個新方法來估計預測誤差
因此學者又提出了針對決策樹的結果進行所謂「誤差的估計」
而誤差是指「被誤判的個數」大致可以分成
１.訓練誤差( Re-substitution Error )，在「訓練階段」產生的錯誤總數
２.推論誤差又稱一般化誤差( Generalization Error )，在代入「測試資料」的錯誤總數
在作「推論誤差」或是「一般化誤差」估計有下面幾個方法
１.樂觀估計法或天真預測法( Optimistic approach ) ：
．每個節點都必須加入錯誤權重：
有一決策樹共有３０個葉節點，共有１０００筆資料，其中在訓練時產生了１０個錯誤
求此決策樹的訓練誤差與推論誤差(一般化誤差)為多少？
訓練誤差（Training Error ) = 10/1000 = 1%
一般化誤差( Generalization Error ) = (10 + 30 * 0.5 ) / 1000 = 2.5%
３.消除誤差修剪法 Reduced error pruning (REP)
這則是採用「驗證資料( Validation data set )」，在採用上述的悲觀估計法來預測「測試資料的誤差」
既然提到了決策樹的修剪(Pruning)，那就先提一下「奧坎剃刀(The Occam's Razor)」理論
其定義就是：「兩個相同的推論錯誤率下，越簡單的樹越好」
也就是說我們在評估一個決策樹的好壞時，複雜程度也是考量之一
因此，又衍生了一個以Occam's Razor為理論基礎的評估原則
「最小描述原則 ( Minimum Description Length ，MDL )」
定義公式：Cost(Model,Data) = Cost(Data|Model) + Cost(Model)
其中Cost指的是這棵樹進行編碼後有多少Bit大小，最後，找到最小Bit的決策樹，作為我們最好的模型
Cost(Data|Model) 是指錯誤分類的資料占多少Bit
Cost(Model) 是節點的編碼Bit + 分割狀況的Bit
５. 如何改善 Decision Tree 過度學習( Over-fitting )
為了避免過度學習或者超適( Over-fitting )的問題，可以有下列幾種方式
1.預先修剪( Pre-Pruning )
2.事後修剪( Post-pruning )
預先修剪的意思是，在決策樹生長完成前，就對其樹枝進行修剪。
其停止條件就跟第三段決策樹的特性介紹提到的一樣
「每一筆資料都歸類到同一個類別」、「所有的紀錄都是相同的值」
如果要在進一步的提前修剪的話，還可以有下列選擇
「當如果在子節點中的記錄少於使用者設定的門檻」
「當分割的子節點並沒有顯著的改善（Gini or information gain ）」
事後修剪的意思是，在決策樹完全生長完畢後，才對樹枝進行修剪。
而其修剪規則是看「是否有改善 一般化錯誤 generalization error 」
每次節點的修剪計算都可以先標記起來，最後再決定是否要修剪
舉個事後修剪的例子，來了解一下
修剪前的 訓練誤差（Training Error）是10/30，其悲觀誤差（Pessimistic error）是 10.5/30
修剪後的 訓練誤差（Training Error）是 （4+3+1+1）/ 30 （占多數的為真）
悲觀誤差（Pessimistic error ）是 11/30
結論， 10.5/30 < 11.5/30 ，故這個切割並沒有顯著的改善。
６. Decision Tree 的 成本矩陣( Cost Matrix )
在來，我們來討論關於決策樹預測的正確性，這也是一個評估的指標
但是，正確性有一個很容易出現的盲點
在10000筆的資料當中，只有10筆的錯誤資料，預測模型的正確性，表面上高達99.9％
但是你丟了100筆資料下去，他幾乎找不到任何錯誤資料
如果以信用卡交易來說，絕大多數的交易都是正確的
如果出現一筆詐欺資料，而模型卻預測他是正確的，這個損失將會遠遠高過其他正常交易
因此，發展了所謂的成本矩陣（Cost Matrix ），希望加上權重的概念，放大預測錯誤會造成的影響。
舉個例子來說：
我們有400筆資料及兩個預測模型 M1 與 M2 ，還有一個成本矩陣
預測是＋，且實際是＋，可以減少1的成本
預測是－，但實際是＋，會增加100的成本
預測是＋，但實際是－，會增加1的成本
預測是－，且實際是－，則不影響成本
所以說
M1的正確性是 （150+250）/ 400 ＝ 80％，其成本是 3910
M2的正確性是（250+200）/ 400 ＝ 90％，其成本是 4255
結論
雖然說M2的正確性比M1來的好，但他卻會多造成 345的成本產生。
1.預先修剪( Pre-Pruning )
2.事後修剪( Post-pruning )
預先修剪的意思是，在決策樹生長完成前，就對其樹枝進行修剪。
其停止條件就跟第三段決策樹的特性介紹提到的一樣
「每一筆資料都歸類到同一個類別」、「所有的紀錄都是相同的值」
如果要在進一步的提前修剪的話，還可以有下列選擇
「當如果在子節點中的記錄少於使用者設定的門檻」
「當分割的子節點並沒有顯著的改善（Gini or information gain ）」
事後修剪的意思是，在決策樹完全生長完畢後，才對樹枝進行修剪。
而其修剪規則是看「是否有改善 一般化錯誤 generalization error 」
每次節點的修剪計算都可以先標記起來，最後再決定是否要修剪
舉個事後修剪的例子，來了解一下
修剪後的 訓練誤差（Training Error）是 （4+3+1+1）/ 30 （占多數的為真）
悲觀誤差（Pessimistic error ）是 11/30
結論， 10.5/30 < 11.5/30 ，故這個切割並沒有顯著的改善。
６. Decision Tree 的 成本矩陣( Cost Matrix )
在來，我們來討論關於決策樹預測的正確性，這也是一個評估的指標
這是一個正確性的矩陣，也是一個用來分類實際與預測差異的常用矩陣
．TP（True Positive）預測正確，實際也是正確
．FN（False Negative）預測錯誤，但實際是正確
．FP（False Positive）預測正確，但實際是錯誤
．TN（True Negative）預測錯誤，實際也是錯誤
所以正確性的就是，所有結果中，預測跟實際相同的總共占了多少
但是，正確性有一個很容易出現的盲點
在10000筆的資料當中，只有10筆的錯誤資料，預測模型的正確性，表面上高達99.9％
但是你丟了100筆資料下去，他幾乎找不到任何錯誤資料
如果以信用卡交易來說，絕大多數的交易都是正確的
如果出現一筆詐欺資料，而模型卻預測他是正確的，這個損失將會遠遠高過其他正常交易
因此，發展了所謂的成本矩陣（Cost Matrix ），希望加上權重的概念，放大預測錯誤會造成的影響。
舉個例子來說：
我們有400筆資料及兩個預測模型 M1 與 M2 ，還有一個成本矩陣
預測是＋，且實際是＋，可以減少1的成本
預測是－，但實際是＋，會增加100的成本
預測是＋，但實際是－，會增加1的成本
預測是－，且實際是－，則不影響成本
所以說
M1的正確性是 （150+250）/ 400 ＝ 80％，其成本是 3910
M2的正確性是（250+200）/ 400 ＝ 90％，其成本是 4255
結論
雖然說M2的正確性比M1來的好，但他卻會多造成 345的成本產生。
