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

課程內容自 這裡 
Introduction: 
A 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". 有興趣可以下載來自己研究, 至於使用的方法可以參考下面範例代碼: 

view plaincopy to clipboardprint?

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

[OO 設計模式] Gossip@DesignPattern : Behavioral - Memento 模式

轉載自 這裡 
前言 : 
您的使用者可以對應用程式屬性進行設定，假設應用程式相關屬性是放在Application物件中，您想要設計一個屬性備份還原功能，如果您直接在Application物件中建立備份復原機制，這會使得物件本身的職責加重，與其在物件內建立備份復原機制，不如將備份復原機制從物件中脫離出來，如此一來還有可能在別的地方重用備份復原機制. 

Memento 模式 : 
您可使用一個 Backup物件 來封裝想要備份的資訊，Application 會負責建立Backup物件，建立的 Backup物件 則交由一個 Recovery物件 來管理，一個可能的設計方式如下所示 : 

- Backup.java :

view plaincopy to clipboardprint?

1. package john.dp.memento;  
2.   
3. import java.util.Date;  
4.   
5. public class Backup {  
6.     final String state;  
7.     final Date date;  
8.     Backup(String state) {  
9.         this.state = state;  
10.         this.date = new Date();  
11.     }  
12. }  

- Application.java :

view plaincopy to clipboardprint?

1. package john.dp.memento;  
2.   
3. public class Application {  
4.     private String state = "default setting";  
5.       
6.     Backup backup() {  
7.         return new Backup(state);  
8.     }  
9.     void recover(Backup backup) {  
10.         this.state = backup.state;  
11.     }  
12.       
13.     void setState(String state) {  
14.         this.state = state;  
15.     }  
16.     String getState() {  
17.         return state;  
18.     }  
19. }  

- Recovery.java :

view plaincopy to clipboardprint?

1. package john.dp.memento;  
2.   
3. import java.util.ArrayList;  
4. import java.util.Date;  
5. import java.util.List;  
6.   
7. public class Recovery {  
8.     private List backups = new ArrayList();  
9.     void add(Backup backup) {  
10.         backups.add(backup);  
11.     }  
12.     Backup retrieve(Date date) {  
13.         for(Backup backup : backups) {  
14.             if(backup.date.equals(date)) {  
15.                 backups.remove(backup);  
16.                 return backup;  
17.             }  
18.         }  
19.         return null;  
20.     }  
21. }  

在改變 Application 狀態設定之前，您可以使用 backup() 方法對狀態進行備份，Recovery 則管理儲存 Backup 物件，之後若想要還原 Application 狀態，則可以從 Recovery 取得備份資訊進行還原。例如 : 

view plaincopy to clipboardprint?

1. package john.dp.memento;  
2.   
3. import java.util.Date;  
4.   
5. public class Main {  
6.     public static void main(String[] args) {  
7.         Application application = new Application();  
8.         Recovery recovery = new Recovery();  
9.           
10.         System.out.println(application.getState());  
11.           
12.         Backup backup = application.backup();  // 建立備忘  
13.         recovery.add(backup); // 加入備忘錄  
14.           
15.         application.setState("customer setting");  
16.         System.out.println(application.getState());  
17.           
18.         Date date = backup.date; // 假設 date 是使用者自行設定所要取得的還原時間！  
19.         application.recover(recovery.retrieve(date)); // 取得備忘來還原  
20.         System.out.println(application.getState());  
21.     }  
22. }  

這是 Memento 模式 的一個例子。Memento 模式 在 Originator 中保留一個 Memento 成員，這個Memento 可以包括 Originator 的成員資訊，在外部的話， Memento 可以由一個 Caretaker 維護，每對 Originator 作一個動作，Caretaker 就保留 Originator 動作前的成員狀 態，如果以後要復原物件狀態，只要從 Caretaker 取回 Memento 物件，對 Originator 進行狀態復原. Memento 模式的 UML 類別結構圖如下所示 : 
 
圖中的 Caretaker 是用來保留原發者所創造的備忘錄物件，以供日後復原時取回，state 表示一個內部狀態，內部狀態多時，也可以將之組織為一個類別，Caretaker 維護的 Memento 可以是多個，可用來實現 Redo 與 Undo 多次的功能. 範例中 Application 即 Originator 的角色， Backup 即 Memento 的角色，Recovery 即 Caretaker 的角色.