【正文】 ? 而回歸模型的回歸系數(shù)具有可解釋性 ， 在流行病學(xué)研究中 ， 對(duì)致病因素的效應(yīng) ， 常用一些危險(xiǎn)度指標(biāo)來衡量因素與發(fā)病 （ 或死亡 ） 的聯(lián)系程度或?qū)θ巳喊l(fā)病的致病作用的大小均可通過擬合該模型得出 。它經(jīng)常作為很多熟悉模型（如回歸模型）的輔助工具。 ? 設(shè)計(jì)分類停止條件 ， 實(shí)際應(yīng)用中數(shù)據(jù)的屬性很多 ， 真正有分類意義的屬性往往是有限幾個(gè) ， 因此在必要的時(shí)候應(yīng)該停止數(shù)據(jù)集分裂： ? 該節(jié)點(diǎn)包含的數(shù)據(jù)太少不足以分裂， ? 繼續(xù)分裂數(shù)據(jù)集對(duì)樹生成的目標(biāo) (例如 ID3中的熵下降準(zhǔn)則 )沒有貢獻(xiàn)， ? 樹的深度過大不宜再分。 ? 決策樹是描述分類過程的一種數(shù)據(jù)結(jié)構(gòu) ， 從上端的根節(jié)點(diǎn)開始 ， 各種分類原則被引用進(jìn)來 ， 并依這些分類原則將根節(jié)點(diǎn)的數(shù)據(jù)集劃分為子集 ， 這一劃分過程直到某種約束條件滿足而結(jié)束 。 ? 從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的每一條路經(jīng)都對(duì)應(yīng)著一條合理的規(guī)則 ，規(guī)則間各個(gè)部分 （ 各個(gè)層的條件 ） 的關(guān)系是合取關(guān)系 。 1979年 , . Quinlan 給出 ID3算法 ， 并在 1983年和 1986年對(duì) ID3 進(jìn)行了總結(jié)和簡化 ， 使其成為決策樹學(xué)習(xí)算法的典型 。 H中每個(gè)假設(shè) h表 示 X上定義的布爾函數(shù)。 一般方法如定義為使訓(xùn)練值與假設(shè)值 預(yù)測(cè)出的值之間的誤差平方 和 E最小為最佳。每個(gè)例子都是一個(gè) 對(duì)偶（序偶）（ x, f(x)），對(duì)每個(gè)輸入的 x，都有確定的輸出 f(x)。該假定是歸納學(xué)習(xí)的有效性的前提條件。 歸納推理試圖從對(duì)象的一部分或整體的特定的觀察中獲得 一個(gè)完備且正確的描述。 這里介紹 costplexity pruning。 回歸樹（ Regression Tree） R e g r e s s i o n T r e eR M 6 . 9N O X . 6 6N O X . 6 716R M 6 . 5 14N O X . 5 122 N O X . 6 3272719R M 7 . 44633因變量 continuous ， 葉子為 因變量 的預(yù)測(cè)值。 哺乳動(dòng)物分類的測(cè)試樣例 改進(jìn) 4：決策樹剪枝 How? 預(yù)剪枝(prepruning) 后剪枝(postpruning) 在完全正確分類訓(xùn)練集之前就停止樹的生長。 假設(shè)一連續(xù)值屬性共有 N個(gè)不同的屬性值，則可找到 N1個(gè)可能的 分裂點(diǎn) 。 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用 遞歸分割的貪婪算法 。 當(dāng) D 中 所有數(shù)據(jù)都只屬于一個(gè)類時(shí)，熵得到最小值 。 這樣只要 5次 ， 我就能知道哪支球隊(duì)是冠軍 當(dāng)然 ， 香農(nóng)不是用錢 ， 而是用比特 (bit)來度量信息量 ， 在上例中 ， 這條消息的信息量是 5比特 信息量的比特?cái)?shù)和所有可能 情況的對(duì)數(shù)有關(guān)，例如本例 中，信息量 = log (球隊(duì)數(shù) )， 即 5 = log (32) 信息熵 (Entropy) ? 實(shí)際上可能不需要 5次就能猜出誰是冠軍 ， 因?yàn)橐恍?qiáng)隊(duì)得冠的可能性更高 ， 因此第一次猜測(cè)時(shí)可以把少數(shù)幾支強(qiáng)隊(duì)分成一組 ， 其它球隊(duì)分成另一組 ， 然后猜冠軍球隊(duì)是否在那幾支強(qiáng)隊(duì)中 ? 這樣 ， 也許三次或四次就能猜出結(jié)果 。 ? 下例是為了解決這個(gè)問題而建立的一棵 決策樹 ， 從中可以看到?jīng)Q策樹的基本組成部分： 決策結(jié)點(diǎn) 、 分支 和 葉結(jié)點(diǎn) 決策樹 ? 下圖給出了一個(gè) 商業(yè)上使用的決策樹 的例子 。一般時(shí)候采用二元分裂，因?yàn)槎至言诟F舉搜索中更加靈活。 這個(gè)過程實(shí)際上是一個(gè)從數(shù)據(jù)中獲取知識(shí) ， 進(jìn)行機(jī)器學(xué)習(xí)的過程 ? 第 2步：利用生成完畢的 決策樹 對(duì)輸入數(shù)據(jù)進(jìn)行 分類 。 H(D) = * * = （ 3） D中包含有 100%的正例和 0%的負(fù)例。 按屬性 A對(duì) D劃分后，數(shù)據(jù)集的信息熵 : 1( ) * ( )vjAjjDInfo D Info DD?????????? ???????其中， 充當(dāng)?shù)? j 個(gè)劃分的權(quán)重。對(duì) PID的分裂將產(chǎn)生大量劃分（與樣本個(gè)數(shù)一樣多），每個(gè)分類只包含一個(gè)樣本，且每個(gè)劃分都是純的。人和大象都不是 哺乳動(dòng)物。 2. 計(jì)算剪去節(jié)點(diǎn)前后的損失函數(shù)，如果剪去節(jié)點(diǎn)之后損失函數(shù)變小了，則說明該節(jié)點(diǎn)是可以剪去的，并將其剪去；如果發(fā)現(xiàn)損失函數(shù)并沒有減少，說明該節(jié)點(diǎn)不可剪去，則將樹還原成未剪去之前的狀態(tài)。 因此建立的樹模型不能很好的推廣到總體中的其他樣本數(shù)據(jù) 。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。這種一般性 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測(cè)新的數(shù)據(jù)。直 到最終的一般化描述。通過 調(diào)整假設(shè)的表示，學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯(cuò)誤預(yù)測(cè)也可以根據(jù)的檢驗(yàn)記錄計(jì)數(shù) 進(jìn)行評(píng)估。 })1,0{:( ?xhh決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 4） ? 決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí) 。 ? 其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹 ， 到葉子節(jié)點(diǎn)處的熵值為零 ， 此時(shí)每個(gè)葉節(jié)點(diǎn)中的實(shí)例都屬于同一類 。 決策樹的基本原理 ? 樹是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu) 。如圖 613的決策樹可以轉(zhuǎn)換成下規(guī)則： IF “個(gè)子大 ” THEN IF “脖子短 ” THEN IF “鼻子長 ” THEN 可能是大象 形式化表示成 可能是大象鼻子長脖子短個(gè)子大 ??? 根結(jié)點(diǎn) 個(gè)子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會(huì)吱吱叫 鼻子長 脖子長 個(gè)子小 不會(huì)吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 構(gòu)造一棵決策樹要解決四個(gè)問題： ? 收集待分類的數(shù)據(jù) ， 這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的 。 決策樹有很多的優(yōu)點(diǎn)，可解釋性、計(jì)算快捷、缺失值的處理、對(duì)于多值名義變量不需要建立啞變量、對(duì)輸入變量異常值穩(wěn)健。 ? 當(dāng)每一類的訓(xùn)練樣本數(shù)較小時(shí) ， 決策樹是容易出錯(cuò)的 ， 有好多分支的樹或者每個(gè)節(jié)點(diǎn)有太多枝的樹最有可能這樣 ， 決策樹對(duì)輸出結(jié)果的密度很敏感； ? 有的研究表明 ， regression模型樣本量選擇中， 最好各組樣本含量大于解釋變量數(shù)的 20倍 。 也可為 regression模型變量的篩選和決策提供指導(dǎo) 。他們統(tǒng)計(jì)計(jì)算的有效性嚴(yán)重的被許多不相關(guān)和冗余的輸入變量影響。 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用 遞歸分割的貪婪算法 。 ? 判定結(jié)構(gòu)可以機(jī)械的轉(zhuǎn)變成產(chǎn)生式規(guī)則 。 在學(xué)習(xí)的過程中 ， 不需要使用者了解過多背景知識(shí) ， 只需要對(duì)訓(xùn)練例子進(jìn)行較好的標(biāo)注 ， 就能夠進(jìn)行學(xué)習(xí) 。 1993年 ， Quinlan 進(jìn)一步發(fā)展了 ID3算法 ， 改進(jìn)成 。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很 好地逼近目標(biāo)函數(shù)，則它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。它在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與 訓(xùn)練樣例有最佳的擬合度。假設(shè)需要以某種形式表示。 自底向上法一次處理一個(gè)輸入對(duì)象。人類知識(shí)的增長 主要來源于歸納學(xué)習(xí)。 恰當(dāng)?shù)臉? 先生成一個(gè)大的樹 考慮一個(gè)子樹 子樹就是由大樹進(jìn)行刪減內(nèi)部節(jié)點(diǎn)而得到 . 用 |T|表示樹 T 的葉節(jié)點(diǎn) （ 最終節(jié)點(diǎn) ） 的個(gè)數(shù) . 定義 cost plexity criterion: 對(duì)于每個(gè) ， 尋找子樹 使得 達(dá)到最小 . 而 則起到了平衡樹的大小和數(shù)據(jù)擬合好壞的作用 . 較大會(huì)得到較小的樹 ， 較小則會(huì)得到較大的樹 . 0 ,T 0 .TT?|| 21:?( ) ( ) | |.imTi Rmm ix RC T y y T? ???? ? ???? 0TT? ? ()CT??? ?對(duì)于每個(gè) ， 可以證明存在唯一的最小的子樹 使得 達(dá)到最小 . To find we use weakest link pruning: we successively collapse the internal node that produces the smallest pernode increase in , and continue until we produce the singlenode (root) tree. This gives a sequence of subtrees, and this sequence must contains Estimation of is achieved by crossvalidation: we choose the value to minimize the crossvalidation sum of squares. ? ()CT?T ?T ?2:?()imi Rmi x R yy? ??.T ????用于回歸 ? 要預(yù)測(cè)的屬性是數(shù)值屬性 ， 非離散值屬性 ? 不純度度量：計(jì)算所有數(shù)據(jù)的均值 ， 再計(jì)算每條數(shù)據(jù)的值到均值的差值的平方和 ? 葉子結(jié)點(diǎn)用均值表示 kMeans SVM Apriori EM PageRank AdaBoost kNN Na239。 ipD iC,iDCDGini電腦銷售數(shù)據(jù)集中， 9個(gè)樣本屬于“購買電腦”， 5個(gè)樣本屬于“未購買電腦” 2295( ) 1 14Gini D ? ? ? ?? ? ? ?? ? ? ?? ? ? ?Gini指標(biāo) 如果按照 的二元分裂，將 劃分成 和 ，則給定該劃分的 1DA D 2D 指標(biāo)為 ： Gini1212( ) ( ) ( )ADDGini D GiniD GiniDDD??Gini指標(biāo)最小，劃分越純。 例如通過剪枝使 在測(cè)試集上 誤差率降低。 ? 實(shí)際應(yīng)用中 ， 當(dāng)訓(xùn)練樣本中 有噪聲 或 訓(xùn)練樣例的數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣 時(shí) ， 該策略可能會(huì)遇到困難 ? 在以上情況發(fā)生時(shí) ， 這個(gè)簡單的算法產(chǎn)生的樹會(huì) 過度擬合訓(xùn)練樣例 (過度擬合 : Over fitting) ? 過度擬合產(chǎn)生的原因：訓(xùn)練樣本中 有噪聲 ， 訓(xùn)練樣例太小等 改進(jìn) 4：欠擬合、合適擬合、過擬合 欠擬合 合適擬合 過擬合 改進(jìn) 4：過度擬合 ? 訓(xùn)練樣本中噪聲導(dǎo)致的過度擬合 錯(cuò)誤的類別值 /類標(biāo)簽 ， 屬性值等 ? 訓(xùn)練樣本中缺乏代表性樣本所導(dǎo)致的過度擬合 根據(jù)少量訓(xùn)練記錄作出的分類決策模型容易受過度擬合的影響 。 如果 A 是 離散值