決策樹算法演示文稿

決策樹算法演示文稿目前一頁\總數(shù)六十五頁\編于十二點決策樹算法ppt課件目前二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法3本章大綱：

決策樹算法原理常用決策樹算法決策樹剪枝由決策樹提取分類規(guī)則應(yīng)用實例分析目前三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法49.1決策樹算法原理優(yōu)點：使用者不需要了解很多背景知識，只要訓(xùn)練事例能用屬性→結(jié)論的方式表達(dá)出來，就能用該算法學(xué)習(xí)；決策樹模型效率高，對訓(xùn)練集數(shù)據(jù)量較大的情況較為適合；分類模型是樹狀結(jié)構(gòu)，簡單直觀，可將到達(dá)每個葉結(jié)點的路徑轉(zhuǎn)換為IF→THEN形式的規(guī)則，易于理解；決策樹方法具有較高的分類精確度。目前四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法59.1決策樹算法原理傳統(tǒng)的數(shù)據(jù)分類操作通常有以下兩個步驟:模型訓(xùn)練階段：根據(jù)給定的訓(xùn)練集，找到合適的映射函數(shù)H:→C的表示模型。使用上一步訓(xùn)練完成的函數(shù)模型預(yù)測數(shù)據(jù)的類別，或利用該函數(shù)模型，對數(shù)據(jù)集中的每一類數(shù)據(jù)進行描述，形成分類規(guī)則。目前五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法69.1決策樹算法原理工作過程：決策樹分類模型的工作過程圖目前六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法79.1決策樹算法原理定義9.1給定一個訓(xùn)練數(shù)據(jù)集D＝，其中每個實例，稱為例子，訓(xùn)練數(shù)據(jù)集中包含以下屬性A=。同時給定類別集合C。對于訓(xùn)練數(shù)據(jù)集D，決策樹是指具有以下性質(zhì)的樹：每個內(nèi)部節(jié)點都被標(biāo)記一個屬性Ai。每個弧都被標(biāo)記一個值，這個值對應(yīng)于相應(yīng)父結(jié)點的屬性。每個葉節(jié)點都被標(biāo)記一個類Cj。目前七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法89.1決策樹算法原理定義9.2分裂準(zhǔn)則定義為在決策樹算法中將訓(xùn)練數(shù)據(jù)集D中的元組劃分為個體類的最好的方法與策略，它告訴我們在節(jié)點N上測試哪個屬性合適，如何選擇測試與測試的方法，從節(jié)點N上應(yīng)該生長出哪些分支。定義9.3分裂屬性Xi定義為決策樹中每個內(nèi)部節(jié)點都對應(yīng)的一個用于分裂數(shù)據(jù)集的屬性。XiA=目前八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法99.1決策樹算法原理定義9.4

如果Xi是連續(xù)屬性，那么分裂準(zhǔn)則的形式為Xi，其中，就稱為節(jié)點n的分裂點。定義9.5如果Xi是離散屬性，那么的形式為，其中，就稱為節(jié)點n的分裂子集。注意：分裂準(zhǔn)則與分裂屬性、分裂點、分裂子集并不等同，它們是四個不同的概念，并且分裂子集分裂點分裂屬性分裂準(zhǔn)則目前九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法109.1決策樹算法原理將上面的定義結(jié)合實際的決策樹例子可得決策樹圖如下圖9-1，圖9-2，圖9-3所示，圖中設(shè)X為分裂屬性，是屬性X的已知值。

圖9-2按照分裂點劃分而成的決策樹圖與相關(guān)的具體例子圖目前十頁\總數(shù)六十五頁\編于十二點第9章決策樹算法119.1決策樹算法原理

圖9-3按照分裂子集劃分而成的決策樹圖與相關(guān)的兩個具體例子圖目前十一頁\總數(shù)六十五頁\編于十二點第9章決策樹算法129.1決策樹算法原理圖9-4按照分裂子集劃分而成的決策樹（只能是二叉樹）圖與相關(guān)的具體例子圖

目前十二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法139.1決策樹算法原理目前主要使用如下幾個量化評估標(biāo)準(zhǔn)(1)預(yù)測準(zhǔn)確性(2)模型強健性(3)描述的簡潔性(4)計算復(fù)雜性(5)處理規(guī)模性目前十三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法149.2常用決策樹算法ID3算法

ID3是Quinlan于1986年提出的，是機器學(xué)習(xí)中一種廣為人知的一個算法，它的提出開創(chuàng)了決策樹算法的先河，而且是國際上最早最有影響的決策樹方法，在該算法中，引入了信息論中熵的概念，利用分割前后的熵來計算信息增益，作為判別能力的度量。

目前十四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法159.2.1ID3算法

定義9.6信息熵自信息量只能反映符號的不確定性，而信息熵可以用來度量整個信源X整體的不確定性。設(shè)某事物具有n種相互獨立的可能結(jié)果(或稱狀態(tài))：，每一種結(jié)果出現(xiàn)的概率分別為且有：（9.1）那么，該事物所具有的不確定量為：（9.2）

目前十五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法169.2.1ID3算法上式即為著名的香農(nóng)信息量公式。注意到式中的對數(shù)以2為底，當(dāng)n=2時且時，熵=1比特。由此可見，一個等概率的二選一事件具有1比特的不確定性。所以，可以把一個等概率的二選一事件所具有信息量定為信息量的單位。任何一個事件能夠分解成n個可能的二選一事件，它的信息量就是n比特。目前十六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法179.2.1ID3算法Quinlan的首創(chuàng)性工作主要是在決策樹的學(xué)習(xí)算法中第一次引入了信息論中的互信息（稱之為信息增益），以之作為屬性選擇的標(biāo)準(zhǔn)，并且將建樹的方法嵌入在其中，其核心是在決策樹的各級節(jié)點上選擇屬性，用信息增益作為屬性選擇標(biāo)準(zhǔn)目前十七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法189.2.1ID3算法下面給出的是ID3算法中將香農(nóng)的信息熵定義應(yīng)用到?jīng)Q策樹構(gòu)造中，進而給出的信息增益的定義。

設(shè)訓(xùn)練數(shù)據(jù)集D=,是n維有窮向量空間，其中是有窮離散符號集，D中的每個元素，叫做例子，其中設(shè)PD和ND是D的兩個子集，分別叫做正例集和反例集。目前十八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法199.2.1ID3算法

假設(shè)訓(xùn)練數(shù)據(jù)集D中的正例集PD和反例集ND的大小分別為p和n，則ID3基于下面兩個假設(shè)給出該決策樹算法中信息增益的定義，因為信息是用二進制編碼的，所以在下面的公式定義中都用以2為底的對數(shù)。（1）在訓(xùn)練數(shù)據(jù)集D上的一棵正確決策樹對任意例子的分類概率同D中正反例的概率一致；（2）一棵決策樹能對一個例子做出正確類別判斷所需的信息量如下公式所示：目前十九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法209.2.1ID3算法

如果以屬性A作為決策樹的根，A具有v個值，它將A分為v個子集，假設(shè)中含有p個正例和n個反例，那么子集所需的信息期望是，那么，以屬性A為根所需的信息期望如下公式所示：因此，以A為根的信息增益如下公式所示：

目前二十頁\總數(shù)六十五頁\編于十二點第9章決策樹算法219.2.1ID3算法上面給出的ID3中的信息論的相關(guān)定義主要是在兩類分類問題的前提下，下面給出將其擴展到多類后的相關(guān)定義描述。設(shè)訓(xùn)練數(shù)據(jù)集D一共有m類樣例，每類樣例數(shù)為：。同樣以屬性A作為決策樹的根，具有v個值，它將D分為v個子集，假設(shè)子集中任意元組屬于類C的概率用表示，并用估計。那么，該子集的信息量定義如下所示：

那么以A為根分類后所需的信息期望如下面公式所示：目前二十一頁\總數(shù)六十五頁\編于十二點第9章決策樹算法229.2.2C4.5算法

（1）分裂（2）連續(xù)數(shù)據(jù)（3）缺失數(shù)據(jù)（4）規(guī)則目前二十二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法239.2.2.1C4.5的分裂屬性選擇度量ID系列的算法為什么會產(chǎn)生歸納偏置呢？歸納偏置是一系列前提，這些前提與訓(xùn)練數(shù)據(jù)一起演繹論證未來實例分類。如果給定一個訓(xùn)練數(shù)據(jù)集，那么通常有很多決策樹與這些樣例一致。所以，要描述ID系列算法的歸納偏置，應(yīng)找到它從所有一致假設(shè)中選擇一個的根據(jù)。目前二十三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法249.2.2.1C4.5的分裂屬性選擇度量ID系列的搜索策略為：（1）優(yōu)先選擇較短的樹而不是較長的；（2）選擇那些信息增益高的屬性離根節(jié)點較近的樹。結(jié)論：ID系列算法的歸納偏置是因為它在選的時候較短的樹比較長的樹優(yōu)先所產(chǎn)生的，也就是那些信息增益高的屬性更靠近的根節(jié)點將會有優(yōu)先生成樹的特權(quán)。目前二十四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法259.2.2.1C4.5的分裂屬性選擇度量為了避免這個偏置，彌補ID系列算法的不足就要舍棄信息增益這個度量而選擇別的決策屬性作為度量標(biāo)準(zhǔn)。Quinlan在他1986年中的論文中提出了一種可以使用的度量標(biāo)準(zhǔn)：增益比率。增益比率通過加入一個被稱為分裂信息（splitinformation）的項來懲罰類似Date這樣的屬性，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻性，它由如下公式所示：

目前二十五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法269.2.2.1C4.5的分裂屬性選擇度量增益比率的公式如下所示：

目前二十六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法279.2.2.2C4.5對連續(xù)數(shù)據(jù)的處理ID3算法最初的定義是假設(shè)屬性值是離散值，但在實際環(huán)境中，有很多屬性是連續(xù)的，不能夠用一個確定的標(biāo)準(zhǔn)來對其進行劃分。C4.5使用下面的一系列處理過程來對連續(xù)的屬性劃分成離散的屬性，進而達(dá)到能夠建立決策樹的目的。目前二十七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法289.2.2.2C4.5對連續(xù)數(shù)據(jù)的處理Step1根據(jù)訓(xùn)練數(shù)據(jù)集D中各個屬性的值對該訓(xùn)練數(shù)據(jù)集進行排序；Step2利用其中各屬性的值對該訓(xùn)練數(shù)據(jù)集動態(tài)地進行劃分；Step3在劃分后的得到的不同的結(jié)果集中確定一個閾值，該閾值將訓(xùn)練數(shù)據(jù)集數(shù)據(jù)劃分為兩個部分；Step4針對這兩邊各部分的值分別計算它們的增益或增益比率，以保證選擇的劃分使得增益最大。目前二十八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法299.2.2.3C4.5對缺失數(shù)據(jù)的處理為了評估屬性A是否是決策節(jié)點n的最佳測試屬性，要計算決策樹在該節(jié)點的信息增益Gain(D,A)。假定<,c()>是S中的一個訓(xùn)練樣例，并且其屬性A的通過值分得的信息值表示為

.目前二十九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法309.2.2.4C4.5對生成規(guī)則的利用只要生成了決策樹后，就可以把樹轉(zhuǎn)換成一個IF-THEN規(guī)則的集合。當(dāng)然，每種算法生成的決策樹都可以轉(zhuǎn)換成相應(yīng)的if-then規(guī)則，C4.5算法處理規(guī)則與其他算法不同在于它把規(guī)則存儲在一個二維數(shù)組中，每一行都代表著樹中的一個規(guī)則，即從樹根到葉子之間的一個路徑.目前三十頁\總數(shù)六十五頁\編于十二點第9章決策樹算法319.2.3CART算法

CART（ClassificationandRegressionTrees）算法是由幾位統(tǒng)計學(xué)家L.Breiman，J.Friedman，R.Olshen和C.Stone在發(fā)表的刊物《分類與回歸樹》中提出的一種產(chǎn)生二叉決策樹分類模型的技術(shù)。它與前面Quinlan提出的ID系列算法和C4.5不同的是，使用的屬性度量標(biāo)準(zhǔn)是Gini指標(biāo)，它和后面將要介紹的算法的共同點也是在于都是利用了相同的屬性度量標(biāo)準(zhǔn)Gini指標(biāo)。目前三十一頁\總數(shù)六十五頁\編于十二點第9章決策樹算法329.2.3CART算法Gini指標(biāo)主要是度量數(shù)據(jù)劃分或訓(xùn)練數(shù)據(jù)集D的不純度為主，系數(shù)值的屬性作為測試屬性，Gini值越小，表明樣本的“純凈度”越高。Gini指標(biāo)定義為如下公式：目前三十二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法339.2.3CART算法由于二叉樹不易產(chǎn)生數(shù)據(jù)碎片，精確度往往也會高于多叉樹，所以在CART算法中，統(tǒng)計學(xué)家們采用了二元劃分，在分支節(jié)點上進行Gini值的測試，如果滿足一定純度則劃分到左子樹，否則劃分到右子樹，最終生成一棵二叉決策樹。在只有二元分裂的時候，對于訓(xùn)練數(shù)據(jù)集D中的屬性A將D分成的D1和D2，則給定劃分D的Gini指標(biāo)如下公式所示：目前三十三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法349.2.3CART算法對于離散值屬性，在算法中遞歸的選擇該屬性產(chǎn)生最小Gini指標(biāo)的子集作為它的分裂子集。對于連續(xù)值屬性，必須考慮所有可能的分裂點。其策略類似于上面ID3中介紹的信息增益處理方法，可以用如下公式所示：目前三十四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法359.2.3CART算法CART算法在滿足下列條件之一，即視為葉節(jié)點不再進行分支操作。（1）所有葉節(jié)點的樣本數(shù)為1、樣本數(shù)小于某個給定的最小值或者樣本都屬于同一類的時候；（2）決策樹的高度達(dá)到用戶設(shè)置的閾值，或者分支后的葉節(jié)點中的樣本屬性都屬于同一個類的時候；（3）當(dāng)訓(xùn)練數(shù)據(jù)集中不再有屬性向量作為分支選擇的時候。目前三十五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法369.2.4PUBLIC算法

前面幾個小節(jié)的決策樹算法都是先建樹再剪枝。PUBLIC(PruningandBuildingIntegratedinClassification)算法[8,17]將建樹、剪枝結(jié)合到一步完成，即是預(yù)剪枝，在建樹階段不生成會被剪枝的子樹，從而大大提高了效率。

PUBLIC算法的建樹是基于SPRINT方法、對其決策樹的剪枝使用的是基于最小編碼代價的MDL算法，但MDL原則不能直接應(yīng)用。目前三十六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法379.2.5SLIQ算法SLIQ(SupervisedLearningInQuest)算法利用3種數(shù)據(jù)結(jié)構(gòu)來構(gòu)造樹，分別是屬性表、類表和類直方圖。SLIQ算法在建樹階段，對連續(xù)屬性采取預(yù)排序技術(shù)與廣度優(yōu)先相結(jié)合的策略生成樹，對離散屬性采取快速的求子集算法確定劃分條件。具體步驟如下：Step1建立類表和各個屬性表，并且進行預(yù)排序，即對每個連續(xù)屬性的屬性表進行獨立排序，以避免在每個節(jié)點上都要給連續(xù)屬性值重利用新排序；Step2如果每個葉節(jié)點中的樣本都能歸為一類，則算法停止；否則轉(zhuǎn)(3)；Step3利用屬性表尋找擁有最小Gini值的劃分作為最佳劃分方案。目前三十七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法389.2.5SLIQ算法Step4根據(jù)第3步得到的最佳方案劃分節(jié)點，判斷為真的樣本劃歸為左孩子節(jié)點，否則劃歸為右孩子節(jié)點。這樣，(3)(4)步就構(gòu)成了廣度優(yōu)先的生成樹策略。Step5更新類表中的第二項，使之指向樣本劃分后所在的葉節(jié)點。Step6轉(zhuǎn)到步驟(2)。目前三十八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法399.2.6SPRINT算法SPRINT算法是對SLIQ算法的改進，其目的有兩個：一是為了能夠更好的并行建立決策樹，二是為了使得決策樹T適合更大的數(shù)據(jù)集。SPRINT(ScalableParallelizableInductionofClassificationTree)算法是一種可擴展的、可并行的歸納決策樹，它完全不受內(nèi)存限制，運行速度快，且允許多個處理器協(xié)同創(chuàng)建一個決策樹模型。

目前三十九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法409.2.6SPRINT算法SPRINT算法定義了兩種數(shù)據(jù)結(jié)構(gòu)，分別是屬性表和直方圖。屬性表由一組三元組<屬性值、類別屬性、樣本號>組成，它隨節(jié)點的擴張而劃分，并附屬于相應(yīng)的子節(jié)點。與SLIQ算法不同，SPRINT算法采取傳統(tǒng)的深度優(yōu)先生成樹策略，具體步驟如下：

Step1生成根節(jié)點，并為所有屬性建立屬性表，同時預(yù)排序連續(xù)屬性的屬性表。Step2如果節(jié)點中的樣本可歸為一類，則算法停止；否則轉(zhuǎn)(3)。Step3利用屬性表尋找擁有最小Gini值的劃分作為最佳劃分方案。算法依次掃描該節(jié)點上的每張屬性表。Step4根據(jù)劃分方案，生成該節(jié)點的兩個子節(jié)點,。Step5劃分該節(jié)點上的各屬性表，使之關(guān)聯(lián)到或上。目前四十頁\總數(shù)六十五頁\編于十二點第9章決策樹算法419.2.6SPRINT算法Step6分別轉(zhuǎn)到步驟(2)考察,節(jié)點。SPRINT算法在剪枝階段進行基于MDL的剪枝，至此構(gòu)成了SPRINT算法的串行化算法。將串行化算法稍加改進，就成為并行化算法：將訓(xùn)練數(shù)據(jù)集平均分布到n個處理器上，而后每個處理器生成自己的數(shù)據(jù)分片。由于連續(xù)屬性值要求全局排序，因此要將n個處理器上的連續(xù)屬性的屬性表綜合重新排序，再平均分布到n個處理器上。在建立Hash表之前，需要從n個處理器上收集所有的樣本號信息。目前四十一頁\總數(shù)六十五頁\編于十二點第9章決策樹算法429.3決策樹剪枝在現(xiàn)實世界中，獲得的數(shù)據(jù)并不可能保證其完美性與完整性，所以，在當(dāng)被用來創(chuàng)建決策樹的訓(xùn)練數(shù)據(jù)集中存在有噪聲，或者數(shù)量太少以至于不能產(chǎn)生目標(biāo)函數(shù)的有代表性的采樣的時候，我們使用決策樹算法生成的決策樹很多分支反映的是訓(xùn)練數(shù)據(jù)集中的異常。在上面任意一種情況發(fā)生的時候，利用簡單算法產(chǎn)生的樹會出現(xiàn)過擬合訓(xùn)練樣例的現(xiàn)象。目前四十二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法439.3決策樹剪枝在利用決策樹算法進行分類的過程中，有兩個過程，在9.1節(jié)中有介紹，第一個過程我們必須要利用訓(xùn)練數(shù)據(jù)來進行決策樹分類模型的建立，另一個過程則是將建立好的決策樹分類模型對給定的測試數(shù)據(jù)進行分類。目前四十三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法44預(yù)剪枝預(yù)剪枝也稱為先剪枝，在該方法中主要是通過提前停止樹的構(gòu)造（例如，通過確定在給定的節(jié)點不再分裂或劃分訓(xùn)練元組的子集）來對決策樹進行剪枝。一旦停止以后，剩下的那個節(jié)點就成為了樹葉。該樹葉可能持有子集元組中最頻繁的類或這些元組的概率分布。目前四十四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法45預(yù)剪枝預(yù)剪枝判斷停止決策樹的生長的方法大體上可以歸納為以下幾種：（1）一種最為簡單的方法就是在決策樹到達(dá)一定高度的情況下就停止樹的生長；（2）到達(dá)此結(jié)點的實例具有相同的特征向量，而不必一定屬于同一類，也可停止生長。這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問題；（3）到達(dá)此結(jié)點的實例個數(shù)小于某一個閾值也可停止樹的生長；（4）更為普遍的做法是計算每次擴張對系統(tǒng)性能的增益，如果這個增益值小于某個閾值則不進行擴展。如果在最好情況下的擴展增益都小于閾值，即使有些葉子結(jié)點的實例不屬于同一類，也停止樹的增長。目前四十五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法46后剪枝

后剪枝算法已經(jīng)得到了廣泛的應(yīng)用，這個算法最初是由Breiman等提出，它首先構(gòu)造完整的決策樹，允許決策樹過度擬合訓(xùn)練數(shù)據(jù)，然后對那些置信度不夠的結(jié)點的子樹用葉子結(jié)點來替代，這個葉子結(jié)點所應(yīng)標(biāo)記的類別為子樹中大多數(shù)實例所屬的類別。目前四十六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法47悲觀錯誤剪枝PEP(PessimisticErrorPruning)REP方法進行剪枝具有以下優(yōu)點：（1）運用REP方法得到的決策樹是關(guān)于測試數(shù)據(jù)集的具有最高精度的子樹，并且是規(guī)模最小的樹。（2）它的計算復(fù)雜性是線性的，這是因為決策樹中的每個非葉子結(jié)點只需要訪問一次就可以評估其子樹被修剪的概率。（3）由于使用獨立的測試數(shù)據(jù)集，和原始決策樹相比，修剪后的決策樹對未來新事例的預(yù)測偏差較小。目前四十七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法48悲觀錯誤剪枝PEP(PessimisticErrorPruning)正是由于REP方法出現(xiàn)的一系列問題，隨后Quinlan提出了可以在一定程度彌補上面缺陷的PEP方法，也就是悲觀剪枝方法。該方法引入了統(tǒng)計學(xué)上連續(xù)修正的概念來彌補這一個缺陷，在評價子樹的訓(xùn)練錯誤的公式中添加了一個常數(shù)，假定每個葉節(jié)點都自動對實例的某部分進行錯誤的分類。目前四十八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法49悲觀錯誤剪枝PEP(PessimisticErrorPruning)所用來剪枝的度量的基本思想可以概述為以下幾點：（1）假設(shè)訓(xùn)練數(shù)據(jù)集生成原始樹為T，某一葉子結(jié)點的實例個數(shù)為，其中錯誤分類的個數(shù)為；（2）我們定義訓(xùn)練數(shù)據(jù)集的誤差率如下公式9.13所示：（9.13）由于訓(xùn)練數(shù)據(jù)集既用來生成決策樹又用來修剪樹，所以是有偏倚的，利用它來修剪的決策樹樹并不是最精確，最好的；（3）為此，Quinlan在誤差估計度量中增加了連續(xù)性校正，將誤差率的公式修改為如下公式9.14所示:

（9.14）目前四十九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法50悲觀錯誤剪枝PEP(PessimisticErrorPruning)

那么，同樣的，我們假設(shè)s為樹T的子樹的其中一個子節(jié)點，則該子樹的葉子結(jié)點的個數(shù)為，的分類誤差率如下公式所示:在定量的分析中，為簡單起見，我們用誤差總數(shù)取代上面誤差率的表示，即有公式:

那么，對于子樹，它的分類誤差總數(shù)如下公式所示：目前五十頁\總數(shù)六十五頁\編于十二點第9章決策樹算法51最小錯誤剪枝MEP(MinimumErrorPruning)MEP方法是由Niblett和Bratko首先提出來的，它在一個相對獨立的數(shù)據(jù)集上從樹的葉子結(jié)點開始，向上搜索一個單一的樹來使分類誤差的期望概率達(dá)到最小，但它并不需要一個額外的修剪數(shù)據(jù)集。使用的信息來自于訓(xùn)練數(shù)據(jù)集，其目的是在未知的數(shù)據(jù)集上產(chǎn)生最小預(yù)測分類錯誤率。目前五十一頁\總數(shù)六十五頁\編于十二點第9章決策樹算法52代價－復(fù)雜度剪枝CCP(Cost-ComplexityPruning)CCP方法就是著名的CART（ClassificationandRegressionTrees)剪枝算法，它包含兩個步驟：(1)自底向上，通過對原始決策樹中的修剪得到一系列的樹，其中是由中的一個或多個子樹被替換所得到的，為未經(jīng)任何修剪的原始樹，為只有一個結(jié)點的樹。(2)評價這些樹，根據(jù)真實誤差率來選擇一個最優(yōu)秀的樹作為最后被剪枝的樹。目前五十二頁\總數(shù)六十五頁\編于十二點第9章決策樹算法53基于錯誤剪枝EBP(Error-BasedPruning)EBP剪枝法是一種應(yīng)用于C4.5算法的自下向上的剪枝法，被認(rèn)為是PEP剪枝法的改進，因為EBP剪枝基于對訓(xùn)練數(shù)據(jù)集的更加悲觀的估計。同PEP剪枝，EBP僅利用訓(xùn)練數(shù)據(jù)集來構(gòu)建和剪枝決策樹。假設(shè)可將葉結(jié)點覆蓋的實例看作統(tǒng)計樣本，葉結(jié)點對實例的分類錯誤率遵循二項式分布，并利用置信因子CF控制剪枝的程度。我們將CF定義為如下公式所示:

目前五十三頁\總數(shù)六十五頁\編于十二點第9章決策樹算法549.4由決策樹提取分類規(guī)則決策樹分類方法有它的優(yōu)點，但是也有一定的局限性，比如，利用算法生成的決策樹的規(guī)模會因為訓(xùn)練數(shù)據(jù)集的巨大而變得過大使得難以理解，可讀性差。如果直接從決策樹中提取出IF－THEN規(guī)則，建立基于規(guī)則的分類器，與決策樹分類器相比，IF－THEN規(guī)則可能更容易理解，特別是當(dāng)決策樹分支非常大時也一樣。目前五十四頁\總數(shù)六十五頁\編于十二點第9章決策樹算法559.5應(yīng)用實例分析下面我們利用上面表9-1根據(jù)天氣是否打網(wǎng)球的訓(xùn)練數(shù)據(jù)集，利用ID3算法來判斷某天是否適合打網(wǎng)球。（1）類別屬性信息熵的計算由于未分區(qū)前，訓(xùn)練數(shù)據(jù)集中共有14個實例，其中有9個實例屬于p類（適合打網(wǎng)球的），5個實例屬于n類（不適合打網(wǎng)球），因此分區(qū)前類別屬性的熵為：目前五十五頁\總數(shù)六十五頁\編于十二點第9章決策樹算法569.5應(yīng)用實例分析（2）非類別屬性信息熵的計算若選擇Outlook為測試屬性。＝0.694bit目前五十六頁\總數(shù)六十五頁\編于十二點第9章決策樹算法579.5應(yīng)用實例分析因此，這種劃分的信息增益是：同理，可以求出其它三個屬性的信息增益為，，。由上可知，屬性值Outlook在各個屬性中具有最高的增益，被選作分裂屬性。則第一個根節(jié)點T被用標(biāo)記，并對于每個屬性值生長一個分支：（3）遞歸地創(chuàng)建決策樹的樹枝和葉子選擇作為測試屬性后，將訓(xùn)練實例集分為三個子集，生成三個子節(jié)點，對每個子節(jié)點遞歸采用上述過程進行分類直至每個節(jié)點都成為葉節(jié)點而已。

目前五十七頁\總數(shù)六十五頁\編于十二點第9章決策樹算法589.5應(yīng)用實例分析屬性值Outlook在各個屬性中具有最高的增益，被選作分裂屬性。則第一個根節(jié)點T被用標(biāo)記，并對于每個屬性值生長一個分支：根據(jù)信息增益結(jié)果生成的以O(shè)utlook為根節(jié)點的初級決策樹圖

目前五十八頁\總數(shù)六十五頁\編于十二點第9章決策樹算法599.5應(yīng)用實例分析A．分析圖中的sunny分支，計算其子屬性的信息增益值來決定子分裂屬性形成子分支之一。針對sunny中的子訓(xùn)練數(shù)據(jù)集分支，有兩個類別，該分支中有3個實例屬于n類，有2個實例屬于p類，因此針對分支的信息熵為：若以：sunny分支中的屬性Temperature為測試屬性，則測試屬性Temperature的信息量為：目前五十九頁\總數(shù)六十五頁\編于十二點第9章決策樹算法609.5應(yīng)用實例分析其信息增益為：若以：sunny分支中的屬性Humidity為測試屬性，則測試屬性Humidity的信息量為：

0.00bit其信息增益為：若以：sunny分支中的屬性Wind為測試屬性

，則測試屬性windy的信息量為：

0.468bit其信息增益為：＝0.971－0.468=0.493bit0.971-0.00=0.971bit目前六十頁\總數(shù)六十五頁\