程式扎記: [ML in DH] Decision Tree (決策樹)

標籤

2014年5月29日 星期四

[ML in DH] Decision Tree (決策樹)

課程內容自 這裡 
Introduction: 
decision tree is a flow-chart-like tree structure: 
– each internal node denotes a test on an attribute
– each branch represents an outcome of the test, and
– leaf nodes represent classes or class distribution

問題: 建構決策樹時,該優先選擇那個屬性來進行「分支」的動作? 
 

Entropy 熵:亂度、隨機程度 
考慮以下三個機率分佈函數: 
– P(X=0)=0, P(X=1)=1
– P(X=0)=0.2, P(X=1)=0.8
– P(X=0)=0.5, P(X=1)=0.5

那一個「比較隨機」? 第一個並沒有隨機性,「亂度」應最小 ; 第三個隨機性應最高,「亂度」應最大! 那怎樣估算一個機率函數的「混亂程度」? 

Entropy: Definition 
 

Entropy 可被用來估算隨機變數在機率分佈上「有多隨機」。熵值越高,表示該隨機變數的「混亂程度」越大。 另外一種解釋,是將 Entropy 視為該隨機變數在隨機試驗前的不確定程度。因試驗後結果確知(亂度或不確定性減少),我們說該試驗提供了試驗前 Entropy 值(單位為 bit)那麼多的資訊量! 

Entropy: Illustration 
對先前提到的三個機率函數而言, 其 entropy 為: 
 

Branching: Idea 
回到之前決策樹選擇屬性進行測試的想法:確定某個屬性之後,亂度 (entropy應減少測試每個屬性確立後所能獲得的資訊量。將「分支前的總亂度」減去「分支後的總亂度」,就是該屬性所能獲得的 information gain
 

Building a Decision Tree: 
我們利用 information gain 來選擇用來進行分支的屬性: 
– 令 S 為 training set 的資料樣本,其個數 |S| = s
– 假設我們有 m 種不同的分類結果 {C1, ..., Cm}。令 Si 代表 S 中被分類於 Ci 的集合,|Si| = si .

尚未進行 branching 前,樣本空間的亂度是: 
 
其中 pi 是該樣本空間中,類別 Ci 所佔的比例(或者說,任取一個樣本,它會屬於 Ci 的機率) 

若 training set 為一個良好的取樣,則可利用 training set 的統計值,作為「分支前樣本空間」統計量的估計值。 也就是說,我們可用 si/S 來估算 pi,或者用 S 來分析 X 的特性. 若屬性 A 有 v 種可能結果 {a1, a2, ..., av},則我們可用該屬性來將 S 分割為 v 個子集 {S1, S2, ..., Sv},其中 Sj 是 S 中屬性 A 的值為 aj 的集合。 

令 sij 代表在 Sj 中,屬於 class Ci 的樣本數量。 則利用屬性 A 將 S 分支後的總熵值(分支後的系統亂度)為: 
 

因此,利用屬性 A 進行 branching,其 information gain 為: 
 

對每個屬性計算「利用該屬性進行分支」所能產生的 IG。選擇能夠得到最大 IG 的屬性來進行 branching! 持續進行 branching 的動作,直到不能再分支為止. 

Decision-Tree Algorithm: 
 

Example: Test Attribute Selection 
 

14 個 training data 中,有 9 個 YES,5 個 NO。因此其 Entropy 為: 
 

接著假設挑選 「年齡」作為測試屬性, 計算 entropy for attribute「年齡」: 
 

同樣地,計算「收入」、「學生」、「信用狀況」得到: IG(收入) = 0.029,IG(學生) = 0.151,IG(信用狀況) = 0.048 .因此,選擇「年齡」這個屬性來進行第一層分類! 
 

Toolkit 使用: 
根據上面的說明, 我實作了該演算法為 "DTBuilder.groovy". 有興趣可以下載來自己研究, 至於使用的方法可以參考下面範例代碼: 
  1. def labels = ["Age""Income""Student?""CC""Class"]  
  2. def datas =  [["<=30""高""N""O""N"],  
  3.               ["<=30""高""N""G""N"],  
  4.               ["31-40""高""N""O""Y"],  
  5.               [">40""中""N""O""Y"],  
  6.               [">40""低""Y""O""Y"],  
  7.               [">40""低""Y""G""N"],  
  8.               ["31-40""低""Y""G""Y"],  
  9.               ["<=30""中""N""O""N"],  
  10.               ["<=30""低""Y""O""Y"],  
  11.               [">40""中""Y""O""Y"],  
  12.               ["<=30""中""Y""G""Y"],  
  13.               ["31-40""中""N""G""Y"],  
  14.               ["31-40""高""Y""O""Y"],  
  15.               [">40""中""N""G""N"]]  
  16. // Part1  
  17. DTBuilder dtb = new DTBuilder(dataSet:datas, labels:labels)  
  18. def ageSet = [] as Set  
  19. def incSet = [] as Set  
  20. def issSet = [] as Set  
  21. def iccSet = [] as Set        
  22. ageSet.addAll(datas.collect {it[0]})  
  23. incSet.addAll(datas.collect {it[1]})  
  24. issSet.addAll(datas.collect {it[2]})  
  25. iccSet.addAll(datas.collect {it[3]})  
  26. def origE = dtb.calcShannonEnt(datas)  
  27. printf "\t[Info] Original E=%.03f\n", origE  
  28. printf "\t[Info] Calculage Age E:\n"  
  29. double aftrE=0  
  30. for(age in ageSet)  
  31. {  
  32.     def sd = dtb.splitDataSet(datas, 0, age)  
  33.     def se = dtb.calcShannonEnt(sd)  
  34.     printf "\t\tAge='%s' with E=%.03f\n", age, se  
  35.     aftrE+=(((double)sd.size())/datas.size())*se  
  36. }  
  37. printf "\t[Info] IG(age)=%.04f!\n\n", origE - aftrE  
  38.   
  39.   
  40. printf "\t[Info] Calculage Income E:\n"  
  41. aftrE=0  
  42. for(inc in incSet)  
  43. {  
  44.     def sd = dtb.splitDataSet(datas, 1, inc)  
  45.     def se = dtb.calcShannonEnt(sd)  
  46.     printf "\t\tIncome='%s' with E=%.03f\n", inc, se  
  47.     aftrE+=(((double)sd.size())/datas.size())*se  
  48. }  
  49. printf "\t[Info] IG(Income)=%.04f!\n\n", origE - aftrE  
  50.   
  51.   
  52. printf "\t[Info] Calculage Student? E:\n"  
  53. aftrE=0  
  54. for(i in issSet)  
  55. {  
  56.     def sd = dtb.splitDataSet(datas, 2, i)  
  57.     def se = dtb.calcShannonEnt(sd)  
  58.     printf "\t\tissSet='%s' with E=%.03f\n", i, se  
  59.     aftrE+=(((double)sd.size())/datas.size())*se  
  60. }  
  61. printf "\t[Info] IG(Student?)=%.04f!\n\n", origE - aftrE  
  62.   
  63. printf "\t[Info] Calculage CC E:\n"  
  64. aftrE=0  
  65. for(i in iccSet)  
  66. {  
  67.     def sd = dtb.splitDataSet(datas, 3, i)  
  68.     def se = dtb.calcShannonEnt(sd)  
  69.     printf "\t\tissSet='%s' with E=%.03f\n", i, se  
  70.     aftrE+=(((double)sd.size())/datas.size())*se  
  71. }  
  72. printf "\t[Info] IG(CC)=%.04f!\n\n", origE - aftrE  
  73.   
  74. // Part2  
  75. def decisionTree = dtb.createTree()  
  76. printf "\t[Info] Decision Tree: %s\n\n", decisionTree  
執行結果: 
 

Supplement: 
[ ML In Action ] Decision Tree Construction

沒有留言:

張貼留言

網誌存檔