第5章決策樹及應用5.1問題概述各個領域的人工智能實現，常常要涉及這樣的問題：從實際問題中提取數據，并從數據中提煉一組數據規則，以支持知識推理實現智能的功能。知識規則一般以“原因一結果”形式表示。一般地，獲取知識規則可以通過樣本集｛（老）,考），…，X,）,|/c=1,2,建模實現。由于推理結果是有限個，艮IJy的取值是有限的，所以這樣的建模屬于分類問題。利用神經網絡可以實現分類問題建模，但當影響因素變量&的個數較大時，建模后的知識規則不易表示，特別地，當默寫變量勤的取值缺失時，即使神經網絡具有容錯性，也會在一定程度上影響分類結果的不確定性。實際應用中，決定分類結果可能只是幾個主要影響因素取值，不依賴全部因素變量，因此，知識規則的提取，可以轉換為這樣的問題：某一分類卜哪些變量是主要的影響因素，這些主要影響因素與分類結果的因素規則表示如何獲取？決策樹就是解決這些問題的方法之一。5.2決策樹概述決策樹學習算法是一組樣本數據集（一個樣本數據也可以稱為實例）為基礎的一種歸納學習算法，它著眼于從一組無次序、無規則的樣本數據（概念）中推理出決策樹表示形式的分類規則。假設這里的樣本數據應該能夠用“屬性一結論”。決策時是一個可以自動對數據進行分類的樹形結構，是樹形結構的知識表示，可以直接轉換為分類規則。它能被看做基于屬性的預測模型，樹的根節點是整個數據集空間，每個分結點對應一個分裂問題，它是對某個單一變量的測試，該測試將數據集合空間分割成兩個或更多數據塊，每個葉結點是帶有分類結果的數據分割。決策樹算法主要針對“以離散型變量作為屬性類型進行分類”的學習方法。對于連續性變量，必須被離散化才能被學習和分類。基于決策樹的決策算法的最大的有點就在于它在學習過程中不需要了解很多的背景知識，只從樣本數據及提供的信息就能夠產生一顆決策樹，通過樹結點的分叉判別可以使某一分類問題僅與主要的樹結點對應的變量屬性取值相關，即不需要全部變量取值來判別對應的范類。5.2.1決策樹基本算法一顆決策樹的內部結點是屬性或屬性的集合，兒葉結點就是學習劃分的類別或結論，內部結點的屬性稱為測試屬性或分裂屬性。當通過一組樣本數據集的學習產生了一顆決策樹之后，就可以對一組新的未知數據進行分類。使用決策樹對數據進行分類的時候，采用自頂向卜?的遞歸方法，對決策樹內部結點進行屬性值的判斷比較并根據不同的屬性值決定走向哪一條分支，在葉節點處就得到了新數據的類別或結論。從上面的描述可以看出從根結點到葉結點的一條路徑對應著一條合取規則，而整棵決策樹對應著一組合取規則。圖5.1簡單決策樹根據決策樹內部結點的各種不同的屬性，可以將決策樹分為以卜幾種：（1） 當決策樹的每一個內部結點都只包含一個屬性時，稱為單變量決策樹：當決策樹存在包含多個變量的內部結點時，稱為多變量決策樹。（2） 根據測試屬性的不同屬性值的個數，可?能使得每一個內部結點有兩個或者是多個分支，如果每一個內部結點只有兩個分支則稱之為二叉樹決策。（3） 分類結果可能是兩類也可能是多類，二叉樹決策的分類結果只能有兩類，股也稱之為布爾決策樹。5.2.2CLS算法CLS學習算法是1966年有Hunt等人提出的。它是最早的決策樹學習算法。后來的許多決策樹算法都可以看作是CLS學習算法的改進與更新。CLS的算法的思想就是從一個空的決策出發，根據樣本數據不斷增加新的分支結點，直到產生的決策樹能夠正確地將樣本數據分類為止。CLS算法的步驟如下：（1）令決策樹T的初始狀態只含有一個樹根（X,Q）,其中X是全體樣本數據的集合,Q是全體測試屬性的集合。（2） 如果T中所有葉結點（X，，Q'）都有如下狀態：或者X，中的樣本數據都是屬于同一個類，或者Q'為空，則停止執行學習算法，學習的結果為T。（3） 否則，選擇一個不具有（2）所描述狀態的葉節點3,Q'）.（4） 對于Q',按照一定規則選取屬性beQ',設X，被b的不同取值分為m個不同的子集X',1<i<m,從（XLQ）伸出m個分支，每個分支代表屬性b的一個不同取值，從而形成m個新的葉結點（X',Q-|b|）,1<i<mo（5） 轉（2）o在算法步驟（4）中，并沒有明確地說明按照怎樣的規則來選取測試屬性，所以CLS有很大的改進空間，而后來很多的決策樹學習算法都是采取了各種各樣的規則和標準來選取測試屬性，所以說后來的各種決策樹學習算法都是CLS學習算法的改進。5.2.3信息炳Shannon在1948年提出并發展了信息論的觀點，主張用數學方法度量和研究信息，提出了以下的一些概念。決策樹學習算法是以信息炳為基礎的，這些概念將有助于理解后續的算法。（1） 自信息量：在收到％之前，接收者對信源發出％的不確定性定義為信息符號位的自信息量［（缶）=一10g2P（a‘），其中P（缶）是取值為叫的概率。自信息量反映了接收㈤的不確定性，自信息量越大，不確定性越大。（2） 信息炳：自信息量只能反映符號的不確定性，而信息上可以用來度量整個信源X整體的不確定性。H（X）=［-p（ai）log2p（ai）］+…+［-「（如）log2p（an）］=-器iP（q）1哈P（?i） （5.1）式中：n是信源X所有可能的符號數：缶是可能取到的值；p（缶）是取值為叫的概率：信息炳是各個自信息量的期望。（3） 條件炳：如果信源X與隨機變量Y不是相互獨立的，接收者收到信息Y,那么用條件炳H（X|Y）來度量接信者收到隨機變量Y之后，對隨機變量X仍然存在的不確定性。X對應信源符號a^i=1,2,…，n）,Y對應信源符號饑（i=l,2,…，s）,?（叫|如）為當Y為與時X為％的概率，則有H（X|Y）=A（bj）H（X|bj）J=1S 71=2p（》J）一￡p（a曲）log2P（&|bj）j=l i=lS71=一￡2p（S）P（a也）log2P（a#j）j=li=lS71=一￡2P（%，?）log2P（a也）j=li=l即條件炳是各種不同條件卜的信息炳期望。（4）平均互信息量：用來表示信號Y所能提供的關于X的信息量的大小，用下式表示,即I（X|Y）=H（X）—H（X|Y）ID3算法上一節己經提到的CLS算法并沒有明確地說明按照怎樣的規則和標準來確定不同層次的樹結點（即測試屬性），Quinlan于1979年提出的以信息炳的下降速度作為選取測試屬性的標準。ID3算法是各種決策樹學習算法中最有影響力、使用最廣泛的一種決策樹學習算法。5.3.1基本思想設樣本數據集為X,目的是要把樣本數據集分為n類。設屬于第i類的樣本數據個數是G,X中總的樣本數據個數是|X|,則一個樣本數據屬于第i類的概率P（G）=協。此時決策樹對劃分C的不確定程度（即信息炳）為H（x,C）=H（X）=-囂1P（G）10g2p（G）若選擇屬性a（設屬性a有m個不同的取值）進行測試，其不確定程度（即條件炳）為H(X|a)=—￡￡p(G，a=%)log2P(G|a=印)1=1j=lnm=—=a；)p(G|a=a；)log2p(Cj|a=a；)i=lj=l=〉p(a=a；)￡p(q|a=a;)log2p(Cf|a=a；)j=l i=l則屬性a對于分類提供的信息量為I（X,a）=H（X）_H（X|a）式中：I（X,a）表示選擇了屬性a作為分類屬性之后信息炳的下降程度，亦即不確定性下降的程度，所以應該選擇時的I（X，a）最大的屬性作為分類的屬性，這樣得到的決策樹的確定性最大。可見ID3算法繼承了CLS算法，并旦根據信息論選擇時的I（X,a）最大的屬性作為分類屬性的測試屬性選擇標準。另外，ID3算法除了引入信息論作為選擇測試屬性的標準之外，并且引入窗II的方法進行增量學習。ID3算法的步驟如下：（1） 選出整個樣本數據集X的規模為W的隨機子集X]（W稱為窗I1規模，子集稱為窗口）。（2） 以I（X,a）=H（X）-H（X|a）的值最大，即H（X|a）的值最小為標準，選取每次的測試屬性，形成當前窗II的決策樹。（3） 順序掃描所有樣本數據，找出當前的決策樹的例外，如果沒有例外則結束。（4） 組合當前窗II的一些樣本數據與某些（3）中找到的李哇哦形成新的窗II,轉（2）。5.3.2ID3算法應用實例表5.1是有關天*的數據樣本集合。每一樣本有4個屬性變量:Outlook,Temperature,Humidity和Windyo樣本被分為兩類，P和N,分別表示正例和反例。表5.1天氣樣本數據

P摩性OutlookemperaturHunidityWindy類別1OvercastHotHighNot1-12OvercastHotHighVeryN3OvercastHotHighMediumN4SunnyHotHighNotP5SunnyHotHighMediumP6RainKildHighNot1-17RainMildHighMedii-unN8RainHotNormalNotp9RainCoolNormalMedimriN10RainHotNormalVeryN11SunnyCoolNormalVeryF12SunnyCoolNormalMediumF13OvercastKildHighNotN14OvercastMildHighMediumN15OvercastCoolNormalNotP16OvercastCoolNormalMedimnF17RainTiTildNormalNotN18RainMildNormalMedimriN19OvercastMildNormalMediumP20OvercastKildNormalVeryP21SunnyMildHighVeryF22SunnyMildHighMediumF23SunnyHotNormalNotP24RainMildHighVeryN首先計算信息炳H(X),由表5.1nJ知，一共有24條記錄，其中P類的記錄和N類的記錄都是12條，則根據上面介紹的信息炳和條件炳的算法，可以得到信息炳值為,、 12 1212 12H(X)=-弱10g2西-護Og2冗=1如果選取Outlook屬性作為測試屬性，則計算條件炳值H(X|O頑00幻。有表5.1可■知，Outlook屬性共有3個屬性值，分別是Overcast、Sunny和Rain。Outlook屬性取Overcast屬性值的記錄共有9條，其中P類的記錄和N類的記錄分別是4條和5條，因此有Overcast引起的炳值為一土⑨哈：+：1哈而Outlook屬性取Sunny屬性值的記錄共有7條，其中P類的記錄和N類的記錄分別是7條和0條，因此有Sunny引起的炳值為一￡(；1。&2；)。同理，Outlook屬性取Rain屬性值的記錄共有8條，其中P類的記錄和N類的記錄分別是1條和7條，因此有Rain引起的燔值為—￡弓1哈§+：log2齊因此條件炳值H(X|O卻。。k)應為上述三個式子之和，得到

9/4 45 5\H(X\Outlook)=-—log2-+-log2-j-￡(國)一土Glog2i+il°g2i)=05528仿照上面條件炳值H(X|OuHook)的計算方法，可以得到，如果選取Temperature屬性為測試屬性，則條件炳值為8/4 44 4、H{X\Temperature)=-—-log2-+-log2-

Z4*\oooo/一芬償1昭2普+￡】昭2￡)-^04+>g2i)=0.9172如果選取Humidity屬性為測試屬性，則條件炳值為H(X|Humidity)=H(X|Humidity)=-芬③。位￡+瀏哈苔)-^(^log2^+]llog2]l)=°.922如果選取Windy屬性為測試屬性，則條件炳值為, 8z444 4H(X|WZindy)=_^7(plog2+plog2p

Z4-\O OOO.一鱷(會1哈號+&1哈會)=1可見H(X|。國。決)的值最小，所以應該選擇Outlook屬性作為測試屬性，得到根據結點為Outlook屬性，根據不同記錄的Outlook屬性取值的不同，向下引出三條分支，如圖5.2所示,其中的數字代表第幾條記錄。(123,13,14,15,16,19,20)(4,5,11,12,21,2423)(6,7,8,9,10,17,18,24)(123,13,14,15,16,19,20)(4,5,11,12,21,2423)(6,7,8,9,10,17,18,24)圖5.2ID3算法第一次分類的決策樹綜合表5.1和圖5.2可以看出,由Sunny引出的分支包括(4,5,11,12,21,22,23)共7條記錄,這7條記錄都是屬于P類的，因此由Sunny音粗的分支得到的是P類。由Overcast引出的分支包括（1,2,343,14,15,16,19,20）共9條記錄，類似上面的做法，可以求得3/3 3\H(X|Temperatiire)=—-(^-log2-j-|Qlog2^)=04444. 5/5 5\ 4/4 4\Humidity)=--^-log2-J 6(丁°&1)=0H(X|Windy)= log2|+|log21-|(|log2|+|log2|)一言（：1哈：+：1哈9=0.9728可見HQX\Humidity）的值最小,因此,對于由Overcast引出的分支包括的9條記錄(1,2,3,13,14,15,16,19,20)應該選擇Humidity作為測試屬性。重復上面的做法，直到每一個分支的記錄的都是屬于同一類，算法結束。最后得到的決策樹如圖5.3所示。圖5.3ID3算法下的決策樹C4.5算法C4.5算法（信息比算法）是由Quinlan自己擴充ID3算法提出來的，是ID3算法的改進，它在ID3的基礎上增加了對連續屬性、屬性空缺情況的處理，對樹剪枝也有了較成熟的方法。5.4.1基本思想與ID3算法不同，C4.5算法挑選具有最高信息增益率的屬性最為測試屬性。對樣本集T,假設變量a有n個屬性，屬性取值四，氣，…，勤，對應a取值為叫出席那的樣本個數分別為叩若n是樣本的總數，則應有*+n2+…+nk=noQuinlan利用屬性a的炳值H（X,a）來定義為了獲取樣本關于屬性a的信息所需要付出的代價，即k kH（X’a）=-，P（q）log?一（缶）&->,l°g2:

i=l i=l信息增益率定義為平均互信息與獲取a信息所付出代價的比值，即（ 、I（X,a）E（X,a）=—JH（X,a）即信息增益率是單位代價所獲得的信息量，是一種相對的信息量不確定性度量。一信息增益率作為測試屬性的選擇標準，是選擇E（X,a）最大的屬性a作為測試屬性。算法C4.5在如下幾個方面改進ID3算法：（1） 一些樣本的某些屬性取值可能為空，字啊構建決策樹時，可以簡單地忽略確實的屬性，即再計算增益率時，即考慮具有屬性值的記錄。為了對一個具有缺失屬性值的記錄進行分類,可以基于己知屬性值的其他記錄來預測缺失的屬性值。（2） C4.5算法不僅可以處理離散屬性，而且可以處理連續屬性。基本思想是基于訓練樣本中元祖的屬性值將數據劃分為一些區域。（3） 增加了剪枝算法。在C4.5中，有兩種基本的剪枝策略：子樹替代法剪枝是指用就葉結點替代子樹。僅當替代后的誤差率與原始樹的誤差率接近時才替代。子樹替代是從樹枝向樹根方向進行的。子樹上升法剪枝是指用一顆子樹中最常用的子樹來代替這顆子樹。子樹從當前位置上升到樹中較高的結點處。對于這種替代也需要確定誤差率的增加量。（4） 分裂時ID3算法偏袒具有較多值得屬性，因而可能導致過擬合，而信息增益率函數可以彌補這個缺陷。但是這個算法同樣存在缺點，它偏向于選擇對統一屬性取值比較集中的屬性（即炳值最小的屬性），而并不一定是對分類貢獻最大、最重要的屬性。5.4.2基于信息增益率建模的決策樹數據仍按表5.1所列，為了計算Outlook屬性作為測試屬性的增益比率，首先要計算在忽略類別情況下該測試屬性的炳，即9 9 7 7 8 8Outlook)=--l0g2---log2---log2-=1.5774又根據上一節有又根據上一節有12 1212 12H(X)= logo logo—=1'7 245224245224因此，對于Outlook屬性增益比率值為1-0.5528105774=0.2835/ 、 1(X91-0.5528105774=0.2835E(X,Outlook)= =H(X,Outlook)仍照上面炳值H(X,Outlook)的計算方法，可以得到，如果選取Temperature屬性為測試屬性，則有8 8 11 11 5 5^^Temperature)=一萬】°g2元一無】°g2萬一疝】°g2^=1-5156E(X,Temperature)E(X,Temperature)=1-0.9183 =0.0817112 1212 12如果選取Humidity屬性為測試屬性，則有12 1212 12H(X|Wumidity)=-—log2—log2—=*E(X,Humidity)=E(X,Humidity)=1-0.91721.5156=0.0546如果選取Windy屬性為測試屬性，則有8 8 6 6 10 10H(X|Windy)=-—log2—-—log2—log2—=1.5546/、1—1E(X'風知=辰=。可見E(X,Outlook)的值最大，所以應該選擇Outlook屬性作為測試屬性。在該例中，ID3算法與信息增益率法建模得到的決策樹沒有區別，即以獲取信息量確定性的絕對定義與相對定義在該例建數中沒有區別。這里去下的信息增益率的遞歸算法略去。CART算法5.5.1基本思想在ID3與C4.5算法中，當確定作為某層樹結點的變量屬性取值較多時，按每一屬性值引出一分支進行遞歸算法，就會出現引出的分支較多，對應算法次數也多，使決策樹算法速度緩慢，是否可以是每一樹結點引出分支盡可能少，以提高算法速度？分類與回歸算法(ClassificationandRegressionTrees,CART)是一種產生二叉決策樹的技術，即每個樹結點(即測試屬性)與ID3算法一樣，以平均互信息作為分裂屬性的度量，對于取定的測試屬性變量t,若t有n個屬性值Si，S2，…，s’，應選取哪個屬性值為作為分裂點引出兩個分支

以使分類結果是盡可能合理正確？“最佳〃分裂屬性值So被定義為滿足條件0（s（）/t）=max（st/t）i其中m0（s/t）=2Pz,Pr￡|P（C也）—P（q|tR）|j=i0（5/t）主要度量在結點t的S屬性值引出的兩個分支時，兩只分支的出現的可能性以及兩分支每個分類結果出現的可■能性差異大小。當0（5/t）較大時，表示兩分支分類結果出現的可能性差異大，即分類不均勻，特別地，當一分支完全含有同一類別結果的樣本而另一分支不含有時，差異最大，這種情況越早出現，表示利用越少結點，可以越快獲得分類結果O0（S/t）中的L和R是指樹中當前結點的左子樹和右子樹。Pl和&分別指在訓練集（樣本集）中的樣本在樹的左邊和右邊的概率，具體定義為左子樹中的樣本數

P,= 樣本總數右分支的定義為_右子樹中的樣本數

PR=~樣本總數-p（g電）和p（g電）分別指在左子樹和右子樹中的樣本屬于類別a的概率，定義為…、左子樹屬于Cl類的樣本數

P（G= h結點樣本數P(G|t&)=右子樹屬于P(G|t&)=右子樹屬于C\類的樣本數

以結點樣本數5.5.2基于CART算法建模的決策樹表5.2給出了一個光宇身高的數據集合。它有兩個屬性：性別和身高，被分為三類，分別是矮、中和高。表5.2身高樣本數據也 名輪沮1Kristino女"6搖Jim2Masue：i&女1.9中Mamha女1-SS中Stzorjbianio女"7Bob1.銳Kaxhy女1.6Dave男1.722St—x/cc2.1Debbi女L8中Todd男1.95中Kim女"9中Z￥ny女L8中Wyneizte女1L75中設應用平均互信獲得當前樹結點是身高屬性t,t的取值s被劃分為6個自區間：(0,1.6),[1.6,1.7),[1.7,1.8),[1.8,1.9),[1.9,2.0),[2.0,8)。利用這些區間，可得到潛在的分裂值1.6,1.7,1.8,1.9,2.0。因此，一句上述分裂點定義，需要從6個可能的屬性值中選擇一個分裂點，CART算法如下：當S=l.6時，由于Pl(身高vL6)=%=0,所以0(1.6|身蜀=0。XD當S=1.7時，設％代表矮類，C2代表中類，