1、第9章決策樹算法1第第9章章 決策樹算法決策樹算法第9章決策樹算法2本章大綱：本章大綱： 決策樹算法原理常用決策樹算法決策樹剪枝由決策樹提取分類規則應用實例分析 第9章決策樹算法39.1 決策樹算法原理優點：l 使用者不需要了解很多背景知識，只要訓練事例能用屬性結論的方式表達出來，就能用該算法學習；l 決策樹模型效率高，對訓練集數據量較大的情況較為適合；l 分類模型是樹狀結構，簡單直觀，可將到達每個葉結點的路徑轉換為IFTHEN形式的規則，易于理解；l 決策樹方法具有較高的分類精確度。 第9章決策樹算法49.1 決策樹算法原理傳統的數據分類操作通常有以下兩個步驟:l模型訓練階段：根據給定的訓練

2、集，找到合適的映射函數H:C的表示模型。l使用上一步訓練完成的函數模型預測數據的類別，或利用該函數模型，對數據集中的每一類數據進行描述，形成分類規則。第9章決策樹算法59.1 決策樹算法原理l工作過程： 決策樹分類模型的工作過程圖 第9章決策樹算法69.1 決策樹算法原理l定義定義 9.1 給定一個訓練數據集D，其中每個實例，稱為例子，訓練數據集中包含以下屬性A=。同時給定類別集合C。對于訓練數據集D，決策樹決策樹是指具有以下性質的樹：l每個內部節點都被標記一個屬性Ai。l每個弧都被標記一個值，這個值對應于相應父結點的屬性。l每個葉節點都被標記一個類Cj。第9章決策樹算法79.1 決策樹算法原

3、理l定義定義9.2 分裂準則分裂準則 定義為在決策樹算法中將訓練數據集D中的元組劃分為個體類的最好的方法與策略，它告訴我們在節點N上測試哪個屬性合適，如何選擇測試與測試的方法，從節點N上應該生長出哪些分支。l定義定義9.3 分裂屬性分裂屬性Xi定義為決策樹中每個內部節點都對應的一個用于分裂數據集的屬性。Xi A=,21hAAA第9章決策樹算法89.1 決策樹算法原理l定義定義9.4 如果Xi是連續屬性，那么分裂準則的形式為Xi，其中，就稱為節點n的分裂點分裂點。l定義定義9.5 如果Xi是離散屬性，那么的形式為，其中，就稱為節點n的分裂子集分裂子集。注意：注意：分裂準則與分裂屬性、分裂點、分裂

4、子集并不等同，它們是四個不同的概念，并且分裂子集分裂點分裂屬性分裂準則 第9章決策樹算法99.1 決策樹算法原理l將上面的定義結合實際的決策樹例子可得決策樹圖如下圖9-1，圖9-2，圖9-3所示，圖中設X為分裂屬性，是屬性X的已知值。 圖9-2 按照分裂點劃分而成的決策樹圖與相關的具體例子圖第9章決策樹算法109.1 決策樹算法原理l 圖9-3 按照分裂子集劃分而成的決策樹圖與相關的兩個具體例子圖第9章決策樹算法119.1 決策樹算法原理圖9-4 按照分裂子集劃分而成的決策樹（只能是二叉樹）圖與相關的具體例子圖 第9章決策樹算法129.1 決策樹算法原理l目前主要使用如下幾個量化評估標準 l(

5、1)預測準確性 l(2)模型強健性 l(3)描述的簡潔性 l(4)計算復雜性 l(5)處理規模性 第9章決策樹算法139.2 常用決策樹算法常用決策樹算法ID3算法 ID3是Quinlan于1986年提出的，是機器學習中一種廣為人知的一個算法，它的提出開創了決策樹算法的先河，而且是國際上最早最有影響的決策樹方法，在該算法中，引入了信息論中熵的概念，利用分割前后的熵來計算信息增益，作為判別能力的度量。 第9章決策樹算法149.2.1 ID3算法 定義定義9.6 信息熵信息熵l 自信息量只能反映符號的不確定性，而信息熵可以用來度量整個信源X整體的不確定性。設某事物具有n種相互獨立的可能結果(或稱狀

6、態)： ，每一種結果出現的概率分別為 且有： l （9.1）l 那么，該事物所具有的不確定量為： l （9.2）l nxxx,21),(),(),(21nxPxPxP1)(1niixp)(log)()()()()()()()(212211iniinnxPxpxIxpxIxpxIxpXH第9章決策樹算法159.2.1 ID3算法l上式即為著名的香農信息量公式。注意到式中的對數以2為底，當n=2時且時，熵=1比特。由此可見，一個等概率的二選一事件具有1比特的不確定性。所以，可以把一個等概率的二選一事件所具有信息量定為信息量的單位。任何一個事件能夠分解成n個可能的二選一事件，它的信息量就是n比特。

7、第9章決策樹算法169.2.1 ID3算法lQuinlan的首創性工作主要是在決策樹的學習算法中第一次引入了信息論中的互信息（稱之為信息增益），以之作為屬性選擇的標準，并且將建樹的方法嵌入在其中，其核心是在決策樹的各級節點上選擇屬性，用信息增益作為屬性選擇標準 第9章決策樹算法179.2.1 ID3算法l下面給出的是ID3算法中將香農的信息熵定義應用到決策樹構造中，進而給出的信息增益的定義。nDDD21jDntttd,21njDtjj, 2 , 1, 設訓練數據集D=, 是n維有窮向量空間，其中是有窮離散符號集，D中的每個元素，叫做例子，其中設PD和ND是D的兩個子集，分別叫做正例集和反例集。

8、第9章決策樹算法189.2.1 ID3算法 假設訓練數據集D中的正例集PD和反例集ND的大小分別為p和n，則ID3基于下面兩個假設給出該決策樹算法中信息增益的定義，因為信息是用二進制編碼的，所以在下面的公式定義中都用以2為底的對數。（1）在訓練數據集D上的一棵正確決策樹對任意例子的分類概率同D中正反例的概率一致；（2）一棵決策樹能對一個例子做出正確類別判斷所需的信息量如下公式所示：第9章決策樹算法199.2.1 ID3算法l 如果以屬性A作為決策樹的根，A具有v個值 ，它將A分為v個子集 ，假設中含有p個正例和n個反例，那么子集所需的信息期望是，那么，以屬性A為根所需的信息期望如下公式所示：n

9、pnnpnnppnppnpI22loglog),(,21vvvv,21veee),()(1iiviiinpInpnpAE因此，以A為根的信息增益如下公式所示： )(),()(AEnpIAgain第9章決策樹算法209.2.1 ID3算法l 上面給出的ID3中的信息論的相關定義主要是在兩類分類問題的前提下，下面給出將其擴展到多類后的相關定義描述。l 設訓練數據集D一共有m類樣例，每類樣例數為： 。同樣以屬性A作為決策樹的根，具有v個值 ，它將D分為v個子集 ，假設子集中任意元組屬于類C的概率 用表示，并用 估計。那么，該子集的信息量定義如下所示：l mipi, 2 , 1,vvvv,21,21v

10、eeeipDCDi/,)(log)(21imiirppeI那么以A為根分類后所需的信息期望如下面公式所示：)()(1rvjreIDeAE第9章決策樹算法219.2.2 C4.5算法l（1）分裂 l（2）連續數據 l（3）缺失數據 l（4）規則 第9章決策樹算法229.2.2.1 C4.5的分裂屬性選擇度量lID系列的算法為什么會產生歸納偏置呢？l歸納偏置是一系列前提，這些前提與訓練數據一起演繹論證未來實例分類。如果給定一個訓練數據集，那么通常有很多決策樹與這些樣例一致。所以，要描述ID系列算法的歸納偏置，應找到它從所有一致假設中選擇一個的根據。 第9章決策樹算法239.2.2.1 C4.5的分

11、裂屬性選擇度量lID系列的搜索策略為：（1）優先選擇較短的樹而不是較長的；（2）選擇那些信息增益高的屬性離根節點較近的樹。 l結論：ID系列算法的歸納偏置是因為它在選的時候較短的樹比較長的樹優先所產生的，也就是那些信息增益高的屬性更靠近的根節點將會有優先生成樹的特權。第9章決策樹算法249.2.2.1 C4.5的分裂屬性選擇度量l 為了避免這個偏置，彌補ID系列算法的不足就要舍棄信息增益這個度量而選擇別的決策屬性作為度量標準。Quinlan在他1986年中的論文中提出了一種可以使用的度量標準：增益比率。l 增益比率通過加入一個被稱為分裂信息（split information）的項來懲罰類似D

12、ate這樣的屬性，分裂信息用來衡量屬性分裂數據的廣度和均勻性，它由如下公式所示：l )(log)(21DeDeDSplitIrvjrA第9章決策樹算法259.2.2.1 C4.5的分裂屬性選擇度量l增益比率的公式如下所示： )()()(ASplitIAGainAGainRatio第9章決策樹算法269.2.2.2 C4.5對連續數據的處理lID3算法最初的定義是假設屬性值是離散值，但在實際環境中，有很多屬性是連續的，不能夠用一個確定的標準來對其進行劃分。C4.5使用下面的一系列處理過程來對連續的屬性劃分成離散的屬性，進而達到能夠建立決策樹的目的。第9章決策樹算法279.2.2.2 C4.5對連

13、續數據的處理l Step1 根據訓練數據集D中各個屬性的值對該訓練數據集進行排序；l Step2 利用其中各屬性的值對該訓練數據集動態地進行劃分；l Step3 在劃分后的得到的不同的結果集中確定一個閾值，該閾值將訓練數據集數據劃分為兩個部分；l Step4 針對這兩邊各部分的值分別計算它們的增益或增益比率，以保證選擇的劃分使得增益最大。第9章決策樹算法289.2.2.3 C4.5對缺失數據的處理l 為了評估屬性A是否是決策節點n的最佳測試屬性，要計算決策樹在該節點的信息增益Gain(D,A)。假定是S中的一個訓練樣例，并且其屬性A的通過值分得的信息值表示為 .ididie第9章決策樹算法29

14、9.2.2.4 C4.5對生成規則的利用 l只要生成了決策樹后，就可以把樹轉換成一個IF-THEN規則的集合。當然，每種算法生成的決策樹都可以轉換成相應的if-then規則，C4.5算法處理規則與其他算法不同在于它把規則存儲在一個二維數組中，每一行都代表著樹中的一個規則，即從樹根到葉子之間的一個路徑 .第9章決策樹算法309.2.3 CART算法l CART（Classification and Regression Trees）算法是由幾位統計學家L.Breiman，J.Friedman，R.Olshen和C.Stone在發表的刊物分類與回歸樹中提出的一種產生二叉決策樹分類模型的技術。它與前

15、面Quinlan提出的ID系列算法和C4.5不同的是，使用的屬性度量標準是Gini指標，它和后面將要介紹的算法的共同點也是在于都是利用了相同的屬性度量標準Gini指標。第9章決策樹算法319.2.3 CART算法l Gini指標主要是度量數據劃分或訓練數據集D的不純度為主，系數值的屬性作為測試屬性，Gini值越小，表明樣本的“純凈度”越高。Gini指標定義為如下公式：miipDGini121)(第9章決策樹算法329.2.3 CART算法l 由于二叉樹不易產生數據碎片，精確度往往也會高于多叉樹，所以在CART算法中，統計學家們采用了二元劃分，在分支節點上進行Gini值的測試，如果滿足一定純度則

16、劃分到左子樹，否則劃分到右子樹，最終生成一棵二叉決策樹。l 在只有二元分裂的時候，對于訓練數據集D中的屬性A將D分成的D1和D2，則給定劃分D的Gini指標如下公式所示：)()()(2211DGiniDDDGiniDDDGiniA第9章決策樹算法339.2.3 CART算法l對于離散值屬性，在算法中遞歸的選擇該屬性產生最小Gini指標的子集作為它的分裂子集。l對于連續值屬性，必須考慮所有可能的分裂點。其策略類似于上面ID3中介紹的信息增益處理方法，可以用如下公式所示：)()(1iviiADGiniDDDGini第9章決策樹算法349.2.3 CART算法l CART算法在滿足下列條件之一，即視

17、為葉節點不再進行分支操作。l （1）所有葉節點的樣本數為1、樣本數小于某個給定的最小值或者樣本都屬于同一類的時候；l （2）決策樹的高度達到用戶設置的閾值，或者分支后的葉節點中的樣本屬性都屬于同一個類的時候；l （3）當訓練數據集中不再有屬性向量作為分支選擇的時候。第9章決策樹算法359.2.4 PUBLIC算法l 前面幾個小節的決策樹算法都是先建樹再剪枝。PUBLIC( Pruning and Building Integrated in Classification)算法8,17將建樹、剪枝結合到一步完成，即是預剪枝，在建樹階段不生成會被剪枝的子樹，從而大大提高了效率 。l PUBLIC算

18、法的建樹是基于SPRINT方法、對其決策樹的剪枝使用的是基于最小編碼代價的MDL算法，但MDL原則不能直接應用 。第9章決策樹算法369.2.5 SLIQ算法l SLIQ (Supervised Learning In Quest)算法利用3種數據結構來構造樹，分別是屬性表、類表和類直方圖。l SLIQ算法在建樹階段，對連續屬性采取預排序技術與廣度優先相結合的策略生成樹，對離散屬性采取快速的求子集算法確定劃分條件。具體步驟如下：l Step1 建立類表和各個屬性表，并且進行預排序，即對每個連續屬性的屬性表進行獨立排序，以避免在每個節點上都要給連續屬性值重利用新排序；l Step 2 如果每個葉

19、節點中的樣本都能歸為一類，則算法停止；否則轉(3) ；l Step 3利用屬性表尋找擁有最小Gini值的劃分作為最佳劃分方案。 第9章決策樹算法379.2.5 SLIQ算法lStep4 根據第3步得到的最佳方案劃分節點，判斷為真的樣本劃歸為左孩子節點，否則劃歸為右孩子節點。這樣，(3) (4)步就構成了廣度優先的生成樹策略。lStep 5 更新類表中的第二項，使之指向樣本劃分后所在的葉節點。lStep 6 轉到步驟(2)。第9章決策樹算法389.2.6 SPRINT算法l SPRINT算法是對SLIQ算法的改進，其目的有兩個：l 一是為了能夠更好的并行建立決策樹，二是為了使得決策樹T適合更大的

20、數據集。l SPRINT (Scalable Parallelizable Induction of Classification Tree)算法是一種可擴展的、可并行的歸納決策樹，它完全不受內存限制，運行速度快，且允許多個處理器協同創建一個決策樹模型。 第9章決策樹算法399.2.6 SPRINT算法l SPRINT算法定義了兩種數據結構，分別是屬性表和直方圖。屬性表由一組三元組組成，它隨節點的擴張而劃分，并附屬于相應的子節點 。l 與SLIQ算法不同，SPRINT算法采取傳統的深度優先生成樹策略，具體步驟如下：l Step1 生成根節點，并為所有屬性建立屬性表，同時預排序連續屬性的屬性表。

21、l Step2 如果節點中的樣本可歸為一類，則算法停止；否則轉(3) 。l Step3 利用屬性表尋找擁有最小Gini值的劃分作為最佳劃分方案。算法依次掃描該節點上的每張屬性表。 l Step4 根據劃分方案，生成該節點的兩個子節點,。l Step5 劃分該節點上的各屬性表，使之關聯到或上。 第9章決策樹算法409.2.6 SPRINT算法l Step6 分別轉到步驟(2)考察,節點。l SPRINT算法在剪枝階段進行基于MDL的剪枝，至此構成了SPRINT算法的串行化算法。將串行化算法稍加改進，就成為并行化算法：將訓練數據集平均分布到n個處理器上，而后每個處理器生成自己的數據分片。由于連續屬

22、性值要求全局排序，因此要將n個處理器上的連續屬性的屬性表綜合重新排序，再平均分布到n個處理器上。在建立Hash表之前，需要從n個處理器上收集所有的樣本號信息。第9章決策樹算法419.3決策樹剪枝決策樹剪枝l在現實世界中，獲得的數據并不可能保證其完美性與完整性，所以，在當被用來創建決策樹的訓練數據集中存在有噪聲，或者數量太少以至于不能產生目標函數的有代表性的采樣的時候，我們使用決策樹算法生成的決策樹很多分支反映的是訓練數據集中的異常。在上面任意一種情況發生的時候，利用簡單算法產生的樹會出現過擬合訓練樣例的現象。 第9章決策樹算法429.3決策樹剪枝決策樹剪枝l在利用決策樹算法進行分類的過程中，有

23、兩個過程，在9.1節中有介紹，第一個過程我們必須要利用訓練數據來進行決策樹分類模型的建立，另一個過程則是將建立好的決策樹分類模型對給定的測試數據進行分類。 第9章決策樹算法439.3.1預剪枝l預剪枝也稱為先剪枝，在該方法中主要是通過提前停止樹的構造（例如，通過確定在給定的節點不再分裂或劃分訓練元組的子集）來對決策樹進行剪枝。一旦停止以后，剩下的那個節點就成為了樹葉。該樹葉可能持有子集元組中最頻繁的類或這些元組的概率分布。第9章決策樹算法449.3.1預剪枝l 預剪枝判斷停止決策樹的生長的方法大體上可以歸納為以下幾種：l （1）一種最為簡單的方法就是在決策樹到達一定高度的情況下就停止樹的生長；

24、l （2）到達此結點的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生長。這種情況可以處理數據中的數據沖突問題；l （3）到達此結點的實例個數小于某一個閾值也可停止樹的生長；l （4）更為普遍的做法是計算每次擴張對系統性能的增益，如果這個增益值小于某個閾值則不進行擴展。如果在最好情況下的擴展增益都小于閾值，即使有些葉子結點的實例不屬于同一類，也停止樹的增長。第9章決策樹算法459.3.2后剪枝l 后剪枝算法已經得到了廣泛的應用，這個算法最初是由Breiman等提出，它首先構造完整的決策樹，允許決策樹過度擬合訓練數據，然后對那些置信度不夠的結點的子樹用葉子結點來替代，這個葉子結點所應標記

25、的類別為子樹中大多數實例所屬的類別。 第9章決策樹算法46悲觀錯誤剪枝PEP(Pessimistic Error Pruning)l REP方法進行剪枝具有以下優點：l （1）運用REP方法得到的決策樹是關于測試數據集的具有最高精度的子樹，并且是規模最小的樹。l （2）它的計算復雜性是線性的，這是因為決策樹中的每個非葉子結點只需要訪問一次就可以評估其子樹被修剪的概率。l （3）由于使用獨立的測試數據集，和原始決策樹相比，修剪后的決策樹對未來新事例的預測偏差較小。第9章決策樹算法47悲觀錯誤剪枝PEP(Pessimistic Error Pruning)l正是由于REP方法出現的一系列問題，隨后

26、Quinlan提出了可以在一定程度彌補上面缺陷的PEP方法，也就是悲觀剪枝方法。該方法引入了統計學上連續修正的概念來彌補這一個缺陷，在評價子樹的訓練錯誤的公式中添加了一個常數，假定每個葉節點都自動對實例的某部分進行錯誤的分類 。第9章決策樹算法48悲觀錯誤剪枝PEP(Pessimistic Error Pruning)l 所用來剪枝的度量的基本思想可以概述為以下幾點：l （1）假設訓練數據集生成原始樹為T，某一葉子結點的實例個數為，其中錯誤分類的個數為；l （2）我們定義訓練數據集的誤差率如下公式9.13所示： l （9.13）l 由于訓練數據集既用來生成決策樹又用來修剪樹，所以是有偏倚的，利

27、用它來修剪的決策樹樹并不是最精確，最好的；l （3）為此，Quinlan在誤差估計度量中增加了連續性校正，將誤差率的公式修改為如下公式9.14所示:l （9.14） tttnep/tttneP/ 21第9章決策樹算法49悲觀錯誤剪枝PEP(Pessimistic Error Pruning)l 那么，同樣的，我們假設s為樹T的子樹的其中一個子節點，則該子樹的葉子結點的個數為 ， 的分類誤差率如下公式所示:sssssssTnlenePt221在定量的分析中，為簡單起見，我們用誤差總數取代上面誤差率的表示，即有公式: 21tteE那么，對于子樹tT，它的分類誤差總數如下公式所示：tT2ssTleE

28、tsltT第9章決策樹算法50最小錯誤剪枝MEP(Minimum Error Pruning)l MEP方法是由Niblett和Bratko首先提出來的，它在一個相對獨立的數據集上從樹的葉子結點開始，向上搜索一個單一的樹來使分類誤差的期望概率達到最小，但它并不需要一個額外的修剪數據集。使用的信息來自于訓練數據集，其目的是在未知的數據集上產生最小預測分類錯誤率。 第9章決策樹算法51代價復雜度剪枝CCP(Cost-Complexity Pruning)lCCP方法就是著名的CART （ Classification and Regression Trees )剪枝算法，它包含兩個步驟：l(1)自

29、底向上，通過對原始決策樹中的修剪得到一系列的樹，其中是由中的一個或多個子樹被替換所得到的，為未經任何修剪的原始樹，為只有一個結點的樹。l(2)評價這些樹，根據真實誤差率來選擇一個最優秀的樹作為最后被剪枝的樹。 第9章決策樹算法52基于錯誤剪枝EBP(Error-Based Pruning)l EBP剪枝法是一種應用于C4. 5算法的自下向上的剪枝法，被認為是PEP剪枝法的改進，因為EBP剪枝基于對訓練數據集的更加悲觀的估計。同PEP剪枝，EBP僅利用訓練數據集來構建和剪枝決策樹。假設可將葉結點覆蓋的實例看作統計樣本，葉結點對實例的分類錯誤率遵循二項式分布，并利用置信因子CF控制剪枝的程度。我們

30、將CF定義為如下公式所示:l xNxexppxNCF)1 (0第9章決策樹算法539.4由決策樹提取分類規則由決策樹提取分類規則l決策樹分類方法有它的優點，但是也有一定的局限性，比如，利用算法生成的決策樹的規模會因為訓練數據集的巨大而變得過大使得難以理解，可讀性差。如果直接從決策樹中提取出IFTHEN規則，建立基于規則的分類器，與決策樹分類器相比，IFTHEN規則可能更容易理解，特別是當決策樹分支非常大時也一樣 。第9章決策樹算法549.5 應用實例分析應用實例分析l 下面我們利用上面表9-1根據天氣是否打網球的訓練數據集，利用ID3算法來判斷某天是否適合打網球。 l （1）類別屬性信息熵的計

31、算由于未分區前，訓練數據集中共有14個實例，其中有9個實例屬于p類（適合打網球的），5個實例屬于n類（不適合打網球），因此分區前類別屬性的熵為：bitnpI940. 0145log145149log149),(22第9章決策樹算法559.5 應用實例分析應用實例分析l （2）非類別屬性信息熵的計算若選擇Outlook為測試屬性。l 0.694bit)52log5253log53(155)40log4044log44(144)53log5352log52(145)(222222OutlookE第9章決策樹算法569.5 應用實例分析應用實例分析l 因此，這種劃分的信息增益是： 同理，可以求出 其

32、它三個屬性的信息增益為 ， ， 。由上可知，屬性值Outlook在各個屬性中具有最高的增益，被選作分裂屬性。則第一個根節點T被用標記，并對于每個屬性值生長一個分支：（3）遞歸地創建決策樹的樹枝和葉子l 選擇作為測試屬性后，將訓練實例集分為三個子集，生成三個子節點，對每個子節點遞歸采用上述過程進行分類直至每個節點都成為葉節點而已。 bitOutlookEnpIOutlookGain246.0694.0940.0)(),()(biteTemperaturGain029.0)(bitHumidityGain151. 0)(bitWindGain048. 0)(第9章決策樹算法579.5 應用實例分析

33、應用實例分析l 屬性值Outlook在各個屬性中具有最高的增益，被選作分裂屬性。則第一個根節點T被用標記，并對于每個屬性值生長一個分支：根據信息增益結果生成的以Outlook為根節點的初級決策樹圖 第9章決策樹算法589.5 應用實例分析應用實例分析l A分析圖中的sunny分支，計算其子屬性的信息增益值來決定子分裂屬性形成子分支之一。l 針對sunny中的子訓練數據集分支，有兩個類別，該分支中有3個實例屬于n類，有2個實例屬于p類，因此針對分支的信息熵為：l 若以 ：sunny分支中的屬性Temperature為測試屬性，則測試屬性Temperature的信息量為 ：1T1TbitnpIT9

34、71. 053log5352log52),(2211TbiteTemperaturET400. 0)10log1011log11(51)21log2121log21(52)20log2022log22(52)(2222221第9章決策樹算法599.5 應用實例分析應用實例分析l 其信息增益為：l 若以：sunny分支中的屬性Humidity為測試屬性，則測試屬性Humidity的信息量為 ： l 0.00bit l 其信息增益為：l 若以：sunny分支中的屬性Wind為測試屬性 ，則測試屬性windy的信息量為： l 0.468bitl 其信息增益為： 0.9710.468=0.493bit

35、 biteTemperaturEnpIeTemperaturGainTrT571. 0400. 0971. 0)(),()(111)20log2022log22(52)20log2022log22(53)(22221HumidityET)(),()(111HumidityEnpIHumidityGainTTT0.971-0.00 =0.971bit )21log2132log32(52)21log2132log32(53)(22221windyET)(),()(111windyEnpIwindyGainTTT第9章決策樹算法609.5 應用實例分析應用實例分析l 這時生成的決策樹如圖所示：決策樹構造圖2第9章決策樹算法619.5 應用實例分析應用實例分析l B分析圖9-8中的：rain分支，計算其子屬性的信息增益值來確定子分裂屬性形成子分支之三。 l 針對：rain中的子訓練數據集分支，有兩個類別，該分支中有3個實例屬于n類，有2個實例屬于p類，因此針對分支的信息熵為：l 若以：rain分支中的屬性Temperature為測試屬性，則測試屬性Temperature的信息量為：l 其信息增益值為： l 0.9710.2850.696bit bitnpIT971. 053log5352log52),(223)2