這小節的內容很多，那我來慢慢看吧！
4-3 Decision Tree Induction 決策樹簡介
哇！這小節好多子小節，有的看了。
4-3-1 How a Decision Tree Works 決策樹如何運作
先來簡單的介紹「樹」，他有三種類型的節點。
- Root node : 他沒有incoming edges 而且可能沒有或是很多outgoing edges.
- Internal node:確實有一個incoming edge 而且擁有兩個或是更多的outgoing edges.
- Leaf or Terminal node: 確實有一個incoming edge並且沒有outgoing edges.
在決策樹中，每一個leaf node都是一個class label。非終端節點(non-terminal node)包含root node以及internal nodes，node中包含了屬性測試條件，是用來分離不同特性的record。
4-3-2 How to Build a Decision Tree 如何建立決策樹
從所給予的屬性集合看來，可以建立的決策樹數目有exponential，然而我們要去計算最佳化的決策樹也是無法做到的，因為會非常耗費記憶體空間。
這些演算法通常會利用greedy strategy去建立一棵決策樹，例如：Hunt’s algorithm就是利用greedy strategy(貪婪法則)，他同時也是很多決策樹歸納演算法的基本演算法，包含ID3, C4.5, 以及CART。
這小節主要就是探討Hunt’s algorithm以及討論演算法設計的問題。
先來介紹一下「Hunt’s algorithm」
在這個演算法中，他是利用把training record分成連續的子集合然後以recursive fashion去建立一個決策樹。
Dt：是一個traning records的集合，連結了node t 以及y={y1,y2,…,yc}，而y是class label (類別標籤)。
Def. of Hunt’s algorithm
Step1: 如果在Dt中的全部record都是屬於同一個類別yt，那t就是會被標成yt類別的leaf node.
Step2: 如果Dt中包含的record屬於兩個以上的類別，那就會選擇一個attribute test condition(屬性測試條件) 去把records分成多個子集合。每一次屬性測試都會產生一個child node(子節點)，而Dt裡的record會依照結果去分散在child node底下。
此演算法是以遞迴方式應用在每一個child node底下。
用下圖例子來說明這個演算法的過程：
右圖就是Training Record，欄位屬性由左到右分別是ID、償還、婚姻狀態、收入，然後分類方法是會不會欺騙(cheat)。
左圖是決策樹建立過程，用比較簡單的考量方式，從第一個屬性開始分，會不會償還有兩條路可以走，Yes的那條最後結果一定是不會欺騙，而No這條可能會也有可能不會欺騙，所以要繼續分下去。接著考慮第二個屬性「婚姻狀態」，如果是已婚的話，結果就是不會欺騙，若是單身或是離婚者就有可能會欺騙，所以這條路還需繼續往下分，最後一個屬性「收入」，如果收入小於80K者，一定不會欺騙，而大於80K者，則會欺騙。
以上就是Hunt’s algorithm建立過程，不過屬性使用的順序有許多種，而這只是其中之一。
如果在training data裡的每一個屬性值組合都可以表示而且每一個組合都有唯一一個class label，那這個演算法就可以正常運作。對於那些實際上的情況而言，這些假設都太嚴謹了，所以我們必須考量額外兩個案例：
- 對於在Step2所建立的Child node，有一些可能會是空的。
=>the node is declared a leaf node with the same class label as the majority class of training records associated with its parent node. (這個node會被宣告成leaf node，而class label會標成與父節點底下的training records的主要class。） - 在Step2中，若Dt中的全部records皆擁有相同的屬性值，則無法在進一步做分離這些records。
=>the node is declared a leaf node with the same class label as the majority class of training records associated with this node. (這個node會被宣告成leaf node，而class label會標成與這個node相連結的training records的主要class一樣。）
Design Issue of Decision Tree Induction 決策樹的設計問題介紹
歸納決策樹的演算法必須注意兩個問題：
- How should the training records be split?
建立樹的process的每一個recursive step必須挑選一個attribute test condition 去把records分成小的集合。為了實作此步驟，演算法必須提供一個方法，對於不同屬性形態可以去詳細指明測試條件。 - How should the splitting procedure stop?
終止一個建立樹的process是需要一個停止條件的。可能的方法就是一直展開節點直到所有record都屬於同一個類別或者是所有records都有相同的屬性值。雖然這兩種條件都可以有效率的讓建立樹的process暫停，但也有可能有其他的標準可以讓這個prcoess更早暫停。在後面4-4-5將會談到。
呼！好累！看原文書還要瞭解，然後在寫成我自己的筆記，挺累的！
4-3-3 Methods for Expressing Attribute Test Conditions 表達屬性測試條件的方法
這小節比較單純了，主要在介紹表達屬性測試的方法，以及對於不同屬性類型他的相對應結果。
Binary Attributes：對於binary attribute來說，測試條件只會產生兩個可能的結果。例如：體溫：恆溫或是變溫。
Nominal Attributes：nominal attribute可以有多個數值，所以測試條件可以用兩種方式來表示。如下圖，一種是Multiway split，另一種則是Binary split。
Ordinal Attributes：ordinal attribute也可以分成binary split 或是 multiway split，ordinal attribute value可以被分成一群一群，只要不違背attribute value的順序性質就行。如下圖。
Continuous Attributes：對於continous attributes，測試條件可以表示成比較測試(A<v) or (A>=v)，或是範圍詢問，例如vi<=A<vi+1，i=1,..,k，如下圖。
這小小節比較簡單，用圖片表示，就可以很容易理解。
4-3-4 Measures for Selecting the Best Split 選擇最好分割的標準
這小小節是在介紹說如何選擇一個最好的分割方法，我們先定義一些變數，p(i|t)指的是在node t 時，那部分的records屬於class i。
在2-class的問題中，在每一個node，class distribution可以寫成(p0,p1)，而p1=1-p0。
選擇最好分割的標準通常建立在 impurity 子節點上的degree。impurity measures包括了
c是類別個數，在entropy計算中，0log0=0。
下圖可以看到三個數值的比較，觀察之後，你可以看到三個標準的最大值都在uniform（p=0.5)時，而最小值會是在所有records都屬於同一個class時（p=0 or1)。
為了計算測試條件執行的如何，我們需要比較父節點的impurity的degree。差異越大的話，測試條件越佳。
Gain，△，是一個被用來計算分割是否佳的標準。
I(‧)是node的impurity measure，N是位於父節點所有的record數目，N(vj)是與child node vj連結的records數目。決策樹演算法通常會選擇一個測試條件來使gain達到最大值。因為I(parent)對於所有的測試條件都是相等的，所以只要minimize 後面那個
∑ 就可以了。
Splitting of Binary Attributes，
如下圖，如果有兩個方法可以把資料分成較小的集合，若屬性A先選的話，Gini(N1)=0.4898，G(N2)=0.480，對於descendent nodes來說，weighted average of the Gini index＝(7/12)x0.4898+(5/12)x0.480=0.486。相同的，若先選B的話，weighted average of the Gini index=0.375，因為B有比較小的Gini index，所以會先選擇屬性B。
Splitting of Nominal Attributes
binary split的算法跟binary attribute一樣，所以左邊的Gini index=0.468，而右邊Gini index=0.167，所以會選擇右邊的分割方法。另一個Multiway split的算法也是差不多，Gini index=4/20 x 0.375+8/20 x 0 + 8/20 x 0.219=0.163，比起binary split的方法，multiway split的gini index更小。
Splitting of Continuous Attributes
Gain Ratio
在一些少數極端的狀況下，測試條件可能會造成結果不是所想要的，因為每一個區塊的records數目太小以致於不能做有用的預測。有兩個方法可以來解決這樣的問題。第一個就是強制測試條件只能binary splite，另一個就是考慮到屬性測試條件所產生的結果數目，然後去修改分割標準。例如：在C4.5決策樹演算法中，gain ratio被使用來計算分割是否優良。
Gain ratio=△info/Split Info，
k:分割的個數。舉例：如果每一個屬性值都有相同的紀錄數目，那P(vi)=1/k而且splite info會等於log2k，這例子建議如果有一個屬性產生大量的分割數，它的分割資訊也會很大，同時他就會降低gain ratio。
終於結束了！4-3太長了，好累喔！快累死了！不過對於很多東西也清楚了許多。
