1、 1機器學習第3章 決策樹學習 2概論決策樹學習是應用最廣的歸納推理算法之一是一種逼近離散值函數的方法很好的健壯性能夠學習析取表達式ID3, Assistant, C4.5搜索一個完整表示的假設空間歸納偏置是優先選擇較小的樹決策樹表示了多個if-then規則 3提綱決策樹定義適用問題特征基本ID3算法決策樹學習的歸納偏置訓練數據的過度擬合更深入的話題 4決策樹表示法決策樹通過把實例從根節點排列到某個葉子節點來分類實例。葉子節點即為實例所屬的分類樹上每個節點說明了對實例的某個屬性的測試節點的每個后繼分支對應于該屬性的一個可能值圖3-1決策樹代表實例屬性值約束的合取的析取式。從樹根到樹葉的每一條路

2、徑對應一組屬性測試的合取，樹本身對應這些合取的析取。 5決策樹學習的適用問題適用問題的特征實例由“屬性-值”對表示目標函數具有離散的輸出值可能需要析取的描述訓練數據可以包含錯誤訓練數據可以包含缺少屬性值的實例問題舉例根據疾病分類患者根據起因分類設備故障根據拖欠支付的可能性分類貸款申請分類問題核心任務是把樣例分類到各可能的離散值對應的類別 6基本的決策樹學習算法大多數決策樹學習算法是一種核心算法的變體采用自頂向下的貪婪搜索遍歷可能的決策樹空間ID3是這種算法的代表 7基本的決策樹學習算法（2）ID3的思想自頂向下構造決策樹從“哪一個屬性將在樹的根節點被測試”開始使用統計測試來確定每一個實例屬性單

3、獨分類訓練樣例的能力ID3的過程分類能力最好的屬性被選作樹的根節點根節點的每個可能值產生一個分支訓練樣例排列到適當的分支重復上面的過程 8表3-1 用于學習布爾函數的ID3算法概要ID3(Examples, Target_attribute, Attributes)創建樹的root節點如果Examples都為正,返回label=+的單節點樹root如果Examples都為反,返回label=-的單節點樹root如果Attributes為空，那么返回單節點root，label=Examples中最普遍的Target_attribute值否則開始AAttributes中分類examples能力最好

4、的屬性root的決策屬性A對于A的每個可能值vi在root下加一個新的分支對應測試A=vi令Examplesvi為Examples中滿足A屬性值為vi的子集如果Examplesvi為空在這個新分支下加一個葉子節點，節點的label=Examples中最普遍的Target_attribute值否則在新分支下加一個子樹ID3（ Examplesvi,Target_attribute,Attributes-A）結束返回root 9最佳分類屬性信息增益用來衡量給定的屬性區分訓練樣例的能力ID3算法在增長樹的每一步使用信息增益從候選屬性中選擇屬性用熵度量樣例的均一性熵刻畫了任意樣例集的純度給定包含關于某

5、個目標概念的正反樣例的樣例集S，那么S相對這個布爾型分類的熵為Entropy(S)=-p+log2p+ - p-log2p-信息論中對熵的一種解釋，熵確定了要編碼集合S中任意成員的分類所需要的最少二進制位數更一般地，如果目標屬性具有c個不同的值，那么S相對于c個狀態的分類的熵定義為 Entropy(S)= 10最佳分類屬性（2）用信息增益度量期望的熵降低屬性的信息增益，由于使用這個屬性分割樣例而導致的期望熵降低Gain(S,A)是在知道屬性A的值后可以節省的二進制位數例子 11ID3算法舉例表3-2繼續這個過程，直到滿足以下兩個條件中的一個所有的屬性已經被這條路經包括與這個節點關聯的所有訓練樣

6、例都具有相同的目標屬性值 12決策樹學習中的假設空間搜索觀察ID3的搜索空間和搜索策略，認識到這個算法的優勢和不足假設空間包含所有的決策樹，它是關于現有屬性的有限離散值函數的一個完整空間維護單一的當前假設（不同于第二章的變型空間候選消除算法）不進行回溯，可能收斂到局部最優每一步使用所有的訓練樣例，不同于基于單獨的訓練樣例遞增作出決定，容錯性增強 13決策樹學習的歸納偏置ID3的搜索策略優先選擇較短的樹選擇那些信息增益高的屬性離根節點較近的樹很難準確刻畫ID3的歸納偏置近似的ID3的歸納偏置較短的樹比較長的樹優先近似在于ID3得到局部最優，而不一定是全局最優一個精確具有這個歸納偏置的算法，BFS

7、-ID3更貼切近似的歸納偏置較短的樹比較長的樹優先，信息增益高的屬性更靠近根節點的樹優先 14限定偏置和優選偏置ID3和候選消除算法的比較ID3的搜索范圍是一個完整的假設空間，但不徹底地搜索這個空間候選消除算法的搜索范圍是不完整的假設空間，但徹底地搜索這個空間ID3的歸納偏置完全是搜索策略排序假設的結果，來自搜索策略候選消除算法完全是假設表示的表達能力的結果，來自對搜索空間的定義 15限定偏置和優選偏置優選偏置ID3的歸納偏置是對某種假設勝過其他假設的一種優選，對最終可列舉的假設沒有硬性限制限定偏置候選消除算法的偏置是對待考慮假設的一種限定通常優選偏置比限定偏置更符合歸納學習的需要優選偏置和限

8、定偏置的結合考慮第1章的例子 16為什么短的假設優先ID3的歸納偏置的哲學基礎奧坎姆剃刀優先選擇擬合數據的最簡單的假設科學上的例子物理學家優先選擇行星運動的簡單假設簡單假設的數量遠比復雜假設的數量少簡單假設對訓練樣例的針對性更小，更像是泛化的規律，而不是訓練樣例的另一種描述 17為什么短的假設優先奧坎姆剃刀的困難我們反問，使用上頁的推理，應該優先選擇包含恰好17個葉子節點和11個非葉子節點的決策樹？假設的規模由學習器內部使用的特定表示決定從生物進化的觀點看內部表示和奧坎姆剃刀原則 18決策樹學習的常見問題決策樹學習的實際問題確定決策樹增長的深度處理連續值的屬性選擇一個適當的屬性篩選度量標準處理

9、屬性值不完整的訓練數據處理不同代價的屬性提高計算效率針對這些問題，ID3被擴展成C4.5 19避免過度擬合數據過度擬合對于一個假設，當存在其他的假設對訓練樣例的擬合比它差，但事實上在實例的整個分布上表現得卻更好時，我們說這個假設過度擬合訓練樣例定義：給定一個假設空間H，一個假設hH，如果存在其他的假設hH，使得在訓練樣例上h的錯誤率比h小，但在整個實例分布上h的錯誤率比h小，那么就說假設h過度擬合訓練數據。圖3-6的例子 20避免過度擬合數據（2）導致過度擬合的原因一種可能原因是訓練樣例含有隨機錯誤或噪聲當訓練數據沒有噪聲時，過度擬合也有可能發生，特別是當少量的樣例被關聯到葉子節點時，很可能出

10、現巧合的規律性，使得一些屬性恰巧可以很好地分割樣例，但卻與實際的目標函數并無關系。 21避免過度擬合數據（3）避免過度擬合的方法及早停止樹增長后修剪法兩種方法的特點第一種方法更直觀第一種方法中，精確地估計何時停止樹增長很困難第二種方法被證明在實踐中更成功 22避免過度擬合數據（4）避免過度擬合的關鍵使用什么樣的準則來確定最終正確樹的規模解決方法使用與訓練樣例截然不同的一套分離的樣例，來評估通過后修剪方法從樹上修建節點的效用。使用所有可用數據進行訓練，但進行統計測試來估計擴展（或修剪）一個特定的節點是否有可能改善在訓練集合外的實例上的性能。使用一個明確的標準來衡量訓練樣例和決策樹的復雜度，當這個

11、編碼的長度最小時停止樹增長。 23避免過度擬合數據（5）方法評述第一種方法是最普通的，常被稱為訓練和驗證集法。可用數據分成兩個樣例集合：訓練集合，形成學習到的假設驗證集合，評估這個假設在后續數據上的精度方法的動機：即使學習器可能會被訓練集合誤導，但驗證集合不大可能表現出同樣的隨機波動驗證集合應該足夠大，以便它本身可提供具有統計意義的實例樣本。常見的做法是，樣例的三分之二作訓練集合，三分之一作驗證集合。 24錯誤率降低修剪將樹上的每一個節點作為修剪得候選對象修剪步驟刪除以此節點為根的子樹，使它成為葉結點把和該節點關聯的訓練樣例的最常見分類賦給它反復修剪節點，每次總是選取那些刪除后可以最大提高決策

12、樹在驗證集合上的精度的節點繼續修剪，直到進一步的修剪是有害的為止數據分成3個子集訓練樣例，形成決策樹驗證樣例，修剪決策樹測試樣例，精度的無偏估計如果有大量的數據可供使用，那么使用分離的數據集合來引導修剪 25規則后修剪從訓練集合推導出決策樹，增長決策樹直到盡可能好地擬合訓練數據，允許過度擬合發生將決策樹轉化為等價的規則集合，方法是為從根節點到葉節點的每一條路徑創建一條規則通過刪除任何能導致估計精度提高的前件來修剪每一條規則按照修剪過的規則的估計精度對它們進行排序，并按這樣的順序應用這些規則來分類后來的實例 26規則后修剪（2）例子圖3-1的最左一條路徑if (outlook=sunny)(Hu

13、midity=High) then PlayTennis=No考慮刪除先行詞(outlook=sunny)和(Humidity=High)選擇使估計精度有最大提升的步驟考慮修剪第二個前件 27規則后修剪（3）規則精度估計方法使用與訓練集不相交的驗證集基于訓練集合本身被C4.5使用，使用一種保守估計來彌補訓練數據有利于當前規則的估計偏置過程先計算規則在它應用的訓練樣例上的精度然后假定此估計精度為二項式分布，并計算它的標準差對于一個給定的置信區間，采用下界估計作為規則性能的度量評論對于大的數據集，保守預測非常接近觀察精度，隨著數據集合的減小，離觀察精度越來越遠不是統計有效（此概念第5章介紹），但是

14、實踐中發現有效 28規則后修剪（4）把決策樹轉化成規則集的好處可以區分決策節點使用的不同上下文消除了根節點附近的屬性測試和葉節點附近的屬性測試的區別提高了可讀性 29合并連續值屬性ID3被限制為取離散值的屬性學習到的決策樹要預測的目標屬性必須是離散的樹的決策節點的屬性也必須是離散的簡單刪除上面第2個限制的方法通過動態地定義新的離散值屬性來實現，即先把連續值屬性的值域分割為離散的區間集合 30合并連續值屬性（2）例子，Temperature應該定義什么樣的基于閾值的布爾屬性選擇產生最大信息增益的閾值按照連續屬性排列樣例，確定目標分類不同的相鄰實例產生一組候選閾值，它們的值是相應的A值之間的中間值

15、可以證明產生最大信息增益的c值位于這樣的邊界中（Fayyad1991）通過計算與每個候選閾值關聯的信息增益評估這些候選值方法的擴展連續的屬性分割成多個區間，而不是單一閾值的兩個空間 31屬性選擇的其他度量標準信息增益度量存在一個內在偏置，偏向具有較多值的屬性避免方法，其他度量，比如增益比率增益比率通過加入一個被稱作分裂信息的項來懲罰多值屬性，分裂信息用來衡量屬性分裂數據的廣度和均勻性SplitInformation(S,A)=GainRatio(S,A)=分裂信息項阻礙選擇值為均勻分布的屬性問題，當某個SiS。解決方法：采用一些啟發式規則， 比如僅對增益高過平均值的屬性應用增益比率測試 32屬

16、性選擇的其他度量標準（2）基于距離的度量定義了數據劃分間的一種距離尺度計算每個屬性產生的劃分與理想劃分間的距離選擇最接近完美劃分的屬性Lopez de Mantaras定義了這個距離度量，證明了它不偏向有大量值的屬性此外Mingers實驗，不同的屬性選擇度量對最終精度的影響小于后修剪得程度和方法的影響 33缺少屬性值的訓練樣例例子，醫學領域經常需要根據此屬性值已知的實例來估計這個缺少的屬性值為了評估屬性A是否是決策節點n的最佳測試屬性，要計算決策樹在該節點的信息增益Gain(S,A)。假定是S中的一個訓練樣例，并且其屬性A的值A(x)未知 34缺少屬性值的訓練樣例（2）處理缺少屬性值的一種策略

17、是賦給它節點n的訓練樣例中該屬性的最常見值另一種策略是賦給它節點n的被分類為c(x)的訓練樣例中該屬性的最常見值更復雜的策略，為A的每個可能值賦予一個概率，而不是簡單地將最常見的值賦給A(x) 35處理不同代價的屬性實例的屬性可能與代價相關優先選擇盡可能使用低代價屬性的決策樹，僅當需要產生可靠的分類時才依賴高代價屬性通過引入一個代價項到屬性選擇度量中，可以使ID3算法考慮屬性代價Tan和Schlimmer的例子 36小結和補充讀物決策樹學習為概念學習和學習其他離散值的函數提供了一個實用的方法ID3算法貪婪算法從根向下推斷決策樹搜索完整的假設空間歸納偏置，較小的樹過度擬合問題ID3算法的擴展 37小結和補充讀物（2）HuntQuinlanMingers 38附錄C4.5 is a software extension of the basic ID3 algorithm designed by Quinlan to address the following issues not dealt with by ID3: Avoiding overfitting the data Determining how deeply to grow a decision tr