【正文】 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預測新的數(shù)據(jù)。 銳角三角形內(nèi)角和等于 180度； 鈍角三角形內(nèi)角和等于 180度； 三角形內(nèi)角和 直角三角形內(nèi)角和等于 180度； 等于 180度 已知三角形 ABC， A角等于 76度， B角等于 89度，則其 C角等于 15度 歸納學習由于依賴于檢驗數(shù)據(jù)，因此又稱為檢驗學習。歸納學習存在一個基本的假設： 任一假設如果能夠在足夠大的訓練樣本集中很好的逼近目標函數(shù)，則它也能在未見樣本中很好地逼近目標函數(shù)。該假定是歸納學習的有效性的前提條件。 決策樹基本概念 關于歸納學習 (3) 決策樹基本概念 關于歸納學習 (4) 歸納過程就是在描述空間中進行搜索的過程。歸納可分為自 頂向下，自底向上和雙向搜索三種方式。 自底向上法一次處理一個輸入對象。將描述逐步一般化。直 到最終的一般化描述。 自頂向下法對可能的一般性描述集進行搜索，試圖找到一些 滿足一定要求的最優(yōu)的描述。 決策樹基本概念 從機器學習看分類及歸納推理等問題（ 1） 從特殊的訓練樣例中歸納出一般函數(shù)是機器學習的中心問題； 從訓練樣例中進行學習通常被視為歸納推理。每個例子都是一個 對偶（序偶）（ x, f(x)），對每個輸入的 x，都有確定的輸出 f(x)。 學習過程將產(chǎn)生對目標函數(shù) f的不同逼近。 F的每一個逼近都 叫做一個假設。假設需要以某種形式表示。例如， y=ax+b。通過 調(diào)整假設的表示，學習過程將產(chǎn)生出假設的不同變形。在表示中 通常需要修改參數(shù)（如 a, b）。 決策樹基本概念 從機器學習看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設（或者說權值集合）。 一般方法如定義為使訓練值與假設值 預測出的值之間的誤差平方 和 E最小為最佳。 ??????a m p l e st r a i n i n g e xbV t r a i nbbVbV tr a inE)(,2^ ))()(( 學習是在假設空間上的一個搜索。概念學習也可以看作是一 個搜索問題的過程。它在預定義的假設空間中搜索假設，使其與 訓練樣例有最佳的擬合度。多數(shù)情況下，為了高效地搜索，可以 利用假設空間中一種自然形成的結構，即一般到特殊的偏序關系。 決策樹基本概念 從機器學習看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯誤預測也可以根據(jù)的檢驗記錄計數(shù) 進行評估。這些計數(shù)存儲在混同矩陣（ Confusion Matrix）的表格中，二元 分類問題混淆矩陣如下： 實際 的類 類 1 f11 類 0 f01 f10 f00 類 1 類 0 預測的類 準確率 =正確的預測數(shù) /預測總數(shù) =（ f11+f00） /(f11+f01+f10+f00) 差錯率 =錯誤的預測數(shù) /預測總數(shù) =（ f10+f01） /(f11+f01+f10+f00) 歸納學習假設 機器學習的任務是在整個實例集合 X上確定與目標概念 c相同 的假設 。一般 H表示所有可能假設。 H中每個假設 h表 示 X上定義的布爾函數(shù)。由于對 c僅有的信息只是它在訓練樣例上 的值，因此歸納學習最多只能保證輸出的假設能與訓練樣例相擬 合。若沒有更多的信息，只能假定對于未見實例最好的假設就是 訓練數(shù)據(jù)最佳擬合的假設。 定義 歸納學習假設：任一假設如果在足夠大的訓練樣例中很 好地逼近目標函數(shù)，則它也能在未見實例中很好地逼近目標函數(shù)。 （ Function Approximation）。 })1,0{:( ?xhh決策樹基本概念 從機器學習看分類及歸納推理等問題（ 4） ? 決策樹學習是以實例為基礎的歸納學習 。 ? 從一類無序 、 無規(guī)則的事物 （ 概念 ） 中推理出決策樹表示的分類規(guī)則 。 ? 概念分類學習算法：來源于 Hunt,Marin和 Stone 于 1966年研制的 CLS學習系統(tǒng) ， 用于學習單個概念 。 1979年 , . Quinlan 給出 ID3算法 ， 并在 1983年和 1986年對 ID3 進行了總結和簡化 ， 使其成為決策樹學習算法的典型 。 Schlimmer 和 Fisher 于 1986年對 ID3進行改造 ， 在每個可能的決策樹節(jié)點創(chuàng)建緩沖區(qū) ， 使決策樹可以遞增式生成 ， 得到 ID4算法 。 1988年 ， Utgoff 在 ID4基礎上提出了 ID5學習算法 ， 進一步提高了效率 。 1993年 ， Quinlan 進一步發(fā)展了 ID3算法 ， 改進成 。 另一類決策樹算法為 CART， 與 ， CART的決策樹由二元邏輯問題生成 ， 每個樹節(jié)點只有兩個分枝 ， 分別包括學習實例的正例與反例 。 ? 其基本思想是以信息熵為度量構造一棵熵值下降最快的樹 ， 到葉子節(jié)點處的熵值為零 ， 此時每個葉節(jié)點中的實例都屬于同一類 。 決策樹的基本原理 ? 決策樹學習采用的是自頂向下的遞歸方法 。 ? 決策樹的每一層節(jié)點依照某一屬性值向下分為子節(jié)點 ， 待分類的實例在每一節(jié)點處與該節(jié)點相關的屬性值進行比較 ，根據(jù)不同的比較結果向相應的子節(jié)點擴展 ， 這一過程在到達決策樹的葉節(jié)點時結束 ， 此時得到結論 。 ? 從根節(jié)點到葉節(jié)點的每一條路經(jīng)都對應著一條合理的規(guī)則 ，規(guī)則間各個部分 （ 各個層的條件 ） 的關系是合取關系 。 整個決策樹就對應著一組析取的規(guī)則 。 ? 決策樹學習算法的最大優(yōu)點是 ， 它可以自學習 。 在學習的過程中 ， 不需要使用者了解過多背景知識 ， 只需要對訓練例子進行較好的標注 ， 就能夠進行學習 。 如果在應用中發(fā)現(xiàn)不符合規(guī)則的實例 ， 程序會詢問用戶該實例的正確分類 ，從而生成新的分枝和葉子 ， 并添加到樹中 。 決策樹的基本原理 ? 樹是由節(jié)點和分枝組成的層次數(shù)據(jù)結構 。 節(jié)點用于存貯信息或知識 ， 分枝用于連接各個節(jié)點 。 樹是圖的一個特例 ， 圖是更一般的數(shù)學結構 ，如貝葉斯網(wǎng)絡 。 ? 決策樹是描述分類過程的一種數(shù)據(jù)結構 ， 從上端的根節(jié)點開始 ， 各種分類原則被引用進來 ， 并依這些分類原則將根節(jié)點的數(shù)據(jù)集劃分為子集 ， 這一劃分過程直到某種約束條件滿足而結束 。 根結點 個子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會吱吱叫 鼻子長 脖子長 個子小 不會吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 可以看到 ， 一個決策樹的內(nèi)部結點包含學習的實例 ， 每層分枝代表了實例的一個屬性的可能取值 ， 葉節(jié)點是最終劃分成的類 。如果判定是二元的 ， 那么構造的將是一棵二叉樹 ， 在樹中每回答一個問題就降到樹的下一層 ， 這類樹一般稱為 CART（ Classification And Regression Tree） 。 ? 判定結構可以機械的轉(zhuǎn)變成產(chǎn)生式規(guī)則 。 可以通過對結構進行廣度優(yōu)先搜索 ， 并在每個節(jié)點生成 “ IF… THEN”規(guī)則來實現(xiàn) 。如圖 613的決策樹可以轉(zhuǎn)換成下規(guī)則： IF “個子大 ” THEN IF “脖子短 ” THEN IF “鼻子長 ” THEN 可能是大象 形式化表示成 可能是大象鼻子長脖子短個子大 ??? 根結點 個子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會吱吱叫 鼻子長 脖子長 個子小 不會吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 構造一棵決策樹要解決四個問題： ? 收集待分類的數(shù)據(jù) ， 這些數(shù)據(jù)的所有屬性應該是完全標注的 。 ? 設計分類原則 ， 即數(shù)據(jù)的哪些屬性可以被用來分類 ， 以及如何將該屬性量化 。 ? 分類原則的選擇 ， 即在眾多分類準則中 ， 每一步選擇哪一準則使最終的樹更令人滿意 。 ? 設計分類停止條件 ， 實際應用中數(shù)據(jù)的屬性很多 ， 真正有分類意義的屬性往往是有限幾個 ， 因此在必要的時候應該停止數(shù)據(jù)集分裂： ? 該節(jié)點包含的數(shù)據(jù)太少不足以分裂， ? 繼續(xù)分裂數(shù)據(jù)集對樹生成的目標 (例如 ID3中的熵下降準則 )沒有貢獻， ? 樹的深度過大不宜再分。 ? 通用的決策樹分裂目標是整棵樹的熵總量最小 ， 每一步分裂時 ， 選擇使熵減小最大的準則 ， 這種方案使最具有分類潛力的準則最先被提取出來 ? 它首先對數(shù)據(jù)進行處理 ， 利用歸納法生成可讀的規(guī)則和決策樹 ， 然后使用決策對新數(shù)據(jù)進行分析 。 本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程 。 決策樹技術發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用 遞歸分割的貪婪算法 。 決策樹的基本原理 決策樹應用 決策樹有很多的優(yōu)點，可解釋性、計算快捷、缺失值的處理、對于多值名義變量不需要建立啞變量、對輸入變量異常值穩(wěn)健。 一些樹模型作為最后模型并不合適。它經(jīng)常作為很多熟悉模型（如回歸模型）的輔助工具。標準的回歸模型具有線性和可加性。他們需要更多的數(shù)據(jù)準備階段：如缺失值的處理、啞變量編碼。他們統(tǒng)計計算的有效性嚴重的被許多不相關和冗余的輸入變量影響。 對數(shù)據(jù)的要求 ? 進行分析時 ， 決策樹對變量的量綱的差異 、 離群值的存在以及有偏分布不太敏感 ， 也就是說對數(shù)據(jù)準備要求不高 。 ? 當每一類的訓練樣本數(shù)較小時 ， 決策樹是容易出錯的 ， 有好多分支的樹或者每個節(jié)點有太多枝的樹最有可能這樣 ， 決策樹對輸出結果的密度很敏感； ? 有的研究表明 ， regression模型樣本量選擇中， 最好各組樣本含量大于解釋變量數(shù)的 20倍 。 ? 決策樹方法之所以經(jīng)常被選用是因為它能理順一些可以理解的規(guī)則 。 然而這些能力有時有些夸大， 確實對于某一個已經(jīng)分過類的記錄來說 ， 為了產(chǎn)生這種分類 ， 很簡單只要沿著從根到葉的路徑走就可以了 ， 然而一個較復雜的決策樹可能包含成千上萬的葉 ， 這么一棵樹從整體上很難提供有關問題可以理解的信息 。 ? 而回歸模型的回歸系數(shù)具有可解釋性 ， 在流行病學研究中 ， 對致病因素的效應 ， 常用一些危險度指標來衡量因素與發(fā)病 （ 或死亡 ） 的聯(lián)系程度或?qū)θ巳喊l(fā)病的致病作用的大小均可通過擬合該模型得出 。 ? 決策樹 所建立的算法把最勝任的拆分字段變量放在樹的根節(jié)點 （ 并且同一個字段在樹的其他層也可以出現(xiàn) ） 。 在用于預測時 ， 重要的變量會漂浮到樹的頂端 ， 這種方式產(chǎn)生的一個有用的結果是使得我們很容易就能發(fā)現(xiàn)哪些解釋變量最勝任預測工作 。 也可為 regression模型變量的篩選和決策提供指導 。 謝謝！ 演講完畢，謝謝觀看！