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