機器學習二 -- 決策樹學習
從今天開始，堅持每天學習一個機器學習的新知識，加油！
決策樹學習是應用最廣的歸納推理算法之一，是一種逼近離散值目標函數的方法，在這種方法中學習到的函數被表示為一顆決策樹。
決策樹表示法
決策樹通過把實例從根結點排列到某個葉子結點來分類實例，葉子結點即為實例所屬的分類。樹上的每一個結點指定了對實例的某個屬性的測試，并且該結 點的每一個后繼分支對應于該屬性的一個可能值。分類實例的方法是從這棵樹的根節點開始，冊數這個結點指定的屬性，然后按照給定實例的該屬性對應的樹枝向下 移動，然后這個過程再以新結點為根的子樹上重復。
上圖畫出了一顆典型的學習到的決策樹，這顆決策樹根據天氣情況分類“星期六上午是否適合打網球”。貌似很多機器學習和數據挖掘的書籍提到這個決策樹的時候都是說的這個例子，汗！不過呢，我們還可以根據這顆決策樹寫出對應的表達式：
決策樹學習的適用問題
- 實例是由“屬性-值”對（pair）表示的
- 目標函數具有離散的輸出值
- 可能需要析取的描述
- 訓練數據可以包含錯誤
- 訓練數據可以包含缺少屬性值的實例
決策樹學習的應用列舉
- 根據疾病分類患者
- 根據起因分類設備故障
- 根據拖欠支付的可能性分類貸款申請
決策樹學習的算法ID3
基本的ID3算法通過自頂向下構造決策樹來進行學習。構造過程是從“哪一個屬性將從樹的根結點被測試？”這個問題開始的。我們使用統計測試來確定 每一個實例屬性單獨分類訓練樣例的能力。分類能力最好的屬性（即信息增益最大的屬性）被選作樹的根結點的測試。然后為根結點屬性的每個可能值產生一個分 支，并把訓練樣例排列到適當的分支之下。然后重復整個過程，用每個分支結點關聯的訓練樣例來選取在該點被測試的最佳屬性。這形成了對合格決策樹的貪婪搜 索，也就是算法從不回溯重新考慮以前的選擇。
熵 ：表示了任意樣例集的純度。
假定S為訓練集，S的目標屬性C有m個可能的類標號值，C={C1,C2,C3…Cm}，每個類標號值相應的概率為p1，p2,p3…pm。那么 訓練集S的信息熵定義為：Entropy(S)=Entropy(p1,p2,,,,pm)=- (p1*log2(p1)+p2*log2(p2)+pm*log2(pm));
信息增益 ：一個屬性的信息增益就是由于使用這個屬性分割樣例而導致的期望熵降低。
假設訓練集為S，并用屬性A來劃分S，那么屬性A的信息增益Gain（S,A）為訓練集S的熵減去按屬性A劃分S后的子集的熵，即Gain（S,A） = Entropy(S) - Entropy_A(S)。
Entropy_A(S)=abs(Si)/abs(S)Entropy(Si)（Si表示描述屬性A的離散值的集合，abs(Si)表示屬性A當前這個值的個數）
ID3 算法的優勢和不足
它是關于現有屬性的有限離散值函數的一個完整空間。但是當遍歷決策樹空間時，ID3 僅維護單一的當前假設，這樣就失去了表示所有一致假設帶來的優勢，而且ID3 算法在搜索中不進行回溯，每當在樹的某一層次選擇了一個屬性進行測試，它不會再回溯重新考慮這個選擇，所以它易受無回溯的爬山搜索中的常見風險影響：收斂 到局部最優的答案，而不是全局最優的。
決策樹學習的歸納偏置
如果給定一個訓練樣例的集合，那么通常有很多決策樹與這些樣例一致。所以，要描述ID3 算法的歸納偏置，應該找到它從所有一致的假設中選擇一個的根據。ID3從這些決策樹中會選擇哪一個呢？它會選擇在使用簡答到復雜的爬山算法遍歷可能的樹空 間時遇到的第一個可接受的樹。總結的說，ID3歸納偏置的搜索策略為：較短的樹比較長的樹優先；那些信息增益高的屬性更靠近根結點的樹優先。
為什么短的假設優先？
假設物理學家優先選擇行星運動簡單的解釋，而不用復雜的解釋，為什么？一種解釋是短假設的數量少于長假設的數量，所以找到一個短的但同時與訓練數 據擬合的假設的可能性較小。相反，常常有很多非常復雜的假設擬合當前的訓練數據，但卻無法正確地泛化到后來的數據。比如考慮決策樹假設，500個結點的決 策樹比5個結點的決策樹多得多，如果給定一個20個訓練樣例的集合，可以預期能夠找到很多500個結點的決策樹與訓練數據一致，而如果一個5個結點的決策 樹也可以完美的擬合這些數據當然是出乎意料的。所以我們會相信5個結點的樹不太可能是統計巧合，因而優先選擇這個5個結點的決策樹的假設，而不選擇500 個結點的。
處理決策樹學習的常見問題
避免過度擬合數據
對于一個假設，當存在其他的假設對訓練數據樣例的擬合比它差，但事實上在實例的整個分布中表現得卻更好時，我們說這個假設 過度擬合 。
避免決策樹學習中的過度擬合的方法被分為兩類：
- 及早停止樹增長，在ID3算法完美分類訓練數據之前就停止樹增長。
- 后修剪法：即允許樹過度擬合數據，然后對這個樹進行后修剪。
在實踐中證實第二種方法后修剪更加成功的實施準則：
1:使用與訓練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修剪結點的效用。
2:使用所有可用數據進行訓練，但是進行統計測試來估計擴展（或修剪）一個特定的結點是否有可能改善在訓練集合外的實例上的性能。
3:使用一個明確的標準來衡量訓練樣例和決策樹的復雜度，當這個編碼的長度最小時停止樹增長。
合并連續值的屬性
我們最初的ID3定義被限制為取離散值的屬性。所以，我們可以先把連續值屬性的值域分割為離散的區間集合。例如，對于連續值的屬性A，算法可以動態的創建一個新的布爾屬性Ac，如果A<c，那么Ac為真，否則為假。這樣，就把連續值的屬性的值離散化了。
屬性選擇的其他度量標準
有一些極端的例子里，采取信息增益來作為選擇樹的結點的優先性，有時這棵樹雖然可以理想的分類訓練數據，但是對于實例的數據的性能非常差，不是一個很好的預測器。所以我們選擇了新的度量標準：增益比率。增益比率的計算方法先略過，這個我在后面的總結里會詳細的講解到。
處理缺少屬性值的訓練樣例
- 賦給屬性A決策結點n的訓練樣例中該屬性的最常見值。
- 為屬性A的每個可能值賦予一個概率。
處理不同代價的屬性
在某些學習任務中，實例的屬性可能與代價相關。例如，在學習分類疾病時，我們可能以這些屬性來描述患者：體溫、活組織切片檢查、脈搏、血液化驗結 果等，這些屬性在代價方面差別非常大。對于這樣的任務，我們將優先選擇盡可能使用低代價屬性的決策樹，通過引入一個代價項到屬性選擇度量中，我們可以用信 息增益除以屬性的代價，這樣我們就可以使低代價的屬性會被優先選擇。僅當需要產生可靠的分類時我們才依賴高代價屬性。