【正文】 也可為 regression模型變量的篩選和決策提供指導(dǎo) 。 ? 決策樹 所建立的算法把最勝任的拆分字段變量放在樹的根節(jié)點(diǎn) （ 并且同一個字段在樹的其他層也可以出現(xiàn) ） 。 然而這些能力有時有些夸大， 確實(shí)對于某一個已經(jīng)分過類的記錄來說 ， 為了產(chǎn)生這種分類 ， 很簡單只要沿著從根到葉的路徑走就可以了 ， 然而一個較復(fù)雜的決策樹可能包含成千上萬的葉 ， 這么一棵樹從整體上很難提供有關(guān)問題可以理解的信息 。 ? 當(dāng)每一類的訓(xùn)練樣本數(shù)較小時 ， 決策樹是容易出錯的 ， 有好多分支的樹或者每個節(jié)點(diǎn)有太多枝的樹最有可能這樣 ， 決策樹對輸出結(jié)果的密度很敏感； ? 有的研究表明 ， regression模型樣本量選擇中， 最好各組樣本含量大于解釋變量數(shù)的 20倍 。他們統(tǒng)計計算的有效性嚴(yán)重的被許多不相關(guān)和冗余的輸入變量影響。標(biāo)準(zhǔn)的回歸模型具有線性和可加性。 一些樹模型作為最后模型并不合適。 決策樹有很多的優(yōu)點(diǎn)，可解釋性、計算快捷、缺失值的處理、對于多值名義變量不需要建立啞變量、對輸入變量異常值穩(wěn)健。 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是采用 遞歸分割的貪婪算法 。 ? 通用的決策樹分裂目標(biāo)是整棵樹的熵總量最小 ， 每一步分裂時 ， 選擇使熵減小最大的準(zhǔn)則 ， 這種方案使最具有分類潛力的準(zhǔn)則最先被提取出來 ? 它首先對數(shù)據(jù)進(jìn)行處理 ， 利用歸納法生成可讀的規(guī)則和決策樹 ， 然后使用決策對新數(shù)據(jù)進(jìn)行分析 。 ? 分類原則的選擇 ， 即在眾多分類準(zhǔn)則中 ， 每一步選擇哪一準(zhǔn)則使最終的樹更令人滿意 。如圖 613的決策樹可以轉(zhuǎn)換成下規(guī)則： IF “個子大 ” THEN IF “脖子短 ” THEN IF “鼻子長 ” THEN 可能是大象 形式化表示成 可能是大象鼻子長脖子短個子大 ??? 根結(jié)點(diǎn) 個子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會吱吱叫 鼻子長 脖子長 個子小 不會吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 構(gòu)造一棵決策樹要解決四個問題： ? 收集待分類的數(shù)據(jù) ， 這些數(shù)據(jù)的所有屬性應(yīng)該是完全標(biāo)注的 。 ? 判定結(jié)構(gòu)可以機(jī)械的轉(zhuǎn)變成產(chǎn)生式規(guī)則 。 根結(jié)點(diǎn) 個子大 可能是松鼠 可能是老鼠 可能是大象 在水里 會吱吱叫 鼻子長 脖子長 個子小 不會吱吱叫 鼻子短 脖子短 可能是長頸鹿 在陸地上 可能是犀牛 可能是河馬 ? 可以看到 ， 一個決策樹的內(nèi)部結(jié)點(diǎn)包含學(xué)習(xí)的實(shí)例 ， 每層分枝代表了實(shí)例的一個屬性的可能取值 ， 葉節(jié)點(diǎn)是最終劃分成的類 。 樹是圖的一個特例 ， 圖是更一般的數(shù)學(xué)結(jié)構(gòu) ，如貝葉斯網(wǎng)絡(luò) 。 決策樹的基本原理 ? 樹是由節(jié)點(diǎn)和分枝組成的層次數(shù)據(jù)結(jié)構(gòu) 。 在學(xué)習(xí)的過程中 ， 不需要使用者了解過多背景知識 ， 只需要對訓(xùn)練例子進(jìn)行較好的標(biāo)注 ， 就能夠進(jìn)行學(xué)習(xí) 。 整個決策樹就對應(yīng)著一組析取的規(guī)則 。 ? 決策樹的每一層節(jié)點(diǎn)依照某一屬性值向下分為子節(jié)點(diǎn) ， 待分類的實(shí)例在每一節(jié)點(diǎn)處與該節(jié)點(diǎn)相關(guān)的屬性值進(jìn)行比較 ，根據(jù)不同的比較結(jié)果向相應(yīng)的子節(jié)點(diǎn)擴(kuò)展 ， 這一過程在到達(dá)決策樹的葉節(jié)點(diǎn)時結(jié)束 ， 此時得到結(jié)論 。 ? 其基本思想是以信息熵為度量構(gòu)造一棵熵值下降最快的樹 ， 到葉子節(jié)點(diǎn)處的熵值為零 ， 此時每個葉節(jié)點(diǎn)中的實(shí)例都屬于同一類 。 1993年 ， Quinlan 進(jìn)一步發(fā)展了 ID3算法 ， 改進(jìn)成 。 Schlimmer 和 Fisher 于 1986年對 ID3進(jìn)行改造 ， 在每個可能的決策樹節(jié)點(diǎn)創(chuàng)建緩沖區(qū) ， 使決策樹可以遞增式生成 ， 得到 ID4算法 。 ? 概念分類學(xué)習(xí)算法：來源于 Hunt,Marin和 Stone 于 1966年研制的 CLS學(xué)習(xí)系統(tǒng) ， 用于學(xué)習(xí)單個概念 。 })1,0{:( ?xhh決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 4） ? 決策樹學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí) 。 定義 歸納學(xué)習(xí)假設(shè)：任一假設(shè)如果在足夠大的訓(xùn)練樣例中很 好地逼近目標(biāo)函數(shù)，則它也能在未見實(shí)例中很好地逼近目標(biāo)函數(shù)。由于對 c僅有的信息只是它在訓(xùn)練樣例上 的值，因此歸納學(xué)習(xí)最多只能保證輸出的假設(shè)能與訓(xùn)練樣例相擬 合。一般 H表示所有可能假設(shè)。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 3） 分類模型的性能根據(jù)模型正確和錯誤預(yù)測也可以根據(jù)的檢驗(yàn)記錄計數(shù) 進(jìn)行評估。它在預(yù)定義的假設(shè)空間中搜索假設(shè)，使其與 訓(xùn)練樣例有最佳的擬合度。 ??????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è)空間上的一個搜索。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 2） 從這些不同的變形中選擇最佳的假設(shè)（或者說權(quán)值集合）。通過 調(diào)整假設(shè)的表示，學(xué)習(xí)過程將產(chǎn)生出假設(shè)的不同變形。假設(shè)需要以某種形式表示。 學(xué)習(xí)過程將產(chǎn)生對目標(biāo)函數(shù) f的不同逼近。 決策樹基本概念 從機(jī)器學(xué)習(xí)看分類及歸納推理等問題（ 1） 從特殊的訓(xùn)練樣例中歸納出一般函數(shù)是機(jī)器學(xué)習(xí)的中心問題； 從訓(xùn)練樣例中進(jìn)行學(xué)習(xí)通常被視為歸納推理。直 到最終的一般化描述。 自底向上法一次處理一個輸入對象。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (3) 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (4) 歸納過程就是在描述空間中進(jìn)行搜索的過程。歸納學(xué)習(xí)存在一個基本的假設(shè)： 任一假設(shè)如果能夠在足夠大的訓(xùn)練樣本集中很好的逼近目標(biāo)函數(shù)，則它也能在未見樣本中很好地逼近目標(biāo)函數(shù)。這種一般性 描述能夠解釋給定的輸入數(shù)據(jù)，并可以用來預(yù)測新的數(shù)據(jù)。人類知識的增長 主要來源于歸納學(xué)習(xí)。即從特殊事實(shí)到普遍性規(guī)律的結(jié)論。歸納推理從若干個事實(shí)中表 征出的特征、特性和屬性中，通過比較、總結(jié)、概括而得出一 個規(guī)律性的結(jié)論。 決策樹基本概念 關(guān)于歸納學(xué)習(xí) (1) 決策樹技術(shù)發(fā)現(xiàn)數(shù)據(jù)模式和規(guī)則的核心是歸納算法。 恰當(dāng)?shù)臉? 先生成一個大的樹 考慮一個子樹 子樹就是由大樹進(jìn)行刪減內(nèi)部節(jié)點(diǎn)而得到 . 用 |T|表示樹 T 的葉節(jié)點(diǎn) （ 最終節(jié)點(diǎn) ） 的個數(shù) . 定義 cost plexity criterion: 對于每個 ， 尋找子樹 使得 達(dá)到最小 . 而 則起到了平衡樹的大小和數(shù)據(jù)擬合好壞的作用 . 較大會得到較小的樹 ， 較小則會得到較大的樹 . 0 ,T 0 .TT?|| 21:?( ) ( ) | |.imTi Rmm ix RC T y y T? ???? ? ???? 0TT? ? ()CT??? ?對于每個 ， 可以證明存在唯一的最小的子樹 使得 達(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ù)測的屬性是數(shù)值屬性 ， 非離散值屬性 ? 不純度度量：計算所有數(shù)據(jù)的均值 ， 再計算每條數(shù)據(jù)的值到均值的差值的平方和 ? 葉子結(jié)點(diǎn)用均值表示 kMeans SVM Apriori EM PageRank AdaBoost kNN Na239。 最大樹 決策樹能長到每個葉子都是純的。 一個好的樹模型有低的偏倚和低的方差 ， 模型的復(fù)雜性往往在偏倚和方差之間做一個折中 ， 因此要對樹進(jìn)行剪枝 。 因此建立的樹模型不能很好的推廣到總體中的其他樣本數(shù)據(jù) 。 ipD iC,iDCDGini電腦銷售數(shù)據(jù)集中， 9個樣本屬于“購買電腦”， 5個樣本屬于“未購買電腦” 2295( ) 1 14Gini D ? ? ? ?? ? ? ?? ? ? ?? ? ? ?Gini指標(biāo) 如果按照 的二元分裂，將 劃分成 和 ，則給定該劃分的 1DA D 2D 指標(biāo)為 ： Gini1212( ) ( ) ( )ADDGini D GiniD GiniDDD??Gini指標(biāo)最小，劃分越純。 Boston Housing Data Leaves = Boolean Rules（布爾規(guī)則） Leaf 1 2 3 4 5 6 7 8 RM [, ) [, ) ? ? NOX .51 [.51, .63) [.63, .67) .67 ?.67 .66 .66 ?.66 Predicted MEDV 22 19 27 27 14 33 46 16 If RM ? {values} NOX ? {values}, then MEDV=value CART算法 ? CART: Classification And Regression Trees ? 可用于分類和回歸 (數(shù)值預(yù)測 ) ? 使用 GINI指標(biāo)來選擇分裂屬性 ? 使用二元切分 (將生成二叉樹 ) ? 基于代價 復(fù)雜度剪枝 Gini指標(biāo) 指標(biāo)用來度量數(shù)據(jù)劃分或者數(shù)據(jù)集的不純度 。 從決策樹導(dǎo)出產(chǎn)生式規(guī)則 ? 大型決策樹可讀性較低 ， 可通過從決策樹導(dǎo)出產(chǎn)生式規(guī)則以提高可讀性 ? 把從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑中遇到的所有測試條件聯(lián)合起來 ， 便可建立相對應(yīng)的規(guī)則集 從決策樹導(dǎo)出產(chǎn)生式規(guī)則 ? 但這樣的規(guī)則會導(dǎo)致某些不必要的復(fù)雜性 ? 可用類似的方法對規(guī)則集進(jìn)行剪枝 ? 對于某一規(guī)則 ， 將它的單個條件暫時去除 ， 在測試集上 估計誤差率 ， 并與原規(guī)則的誤差率進(jìn)行比較 ， 若新規(guī)則的結(jié)果較好 ， 則刪除這個條件 IF 天氣 =晴 A