第9章_決策樹算法

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

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

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

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

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

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

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

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

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

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

11、裂屬性選擇度量lID系列的搜索策略為：（1）優(yōu)先選擇較短的樹而不是較長(zhǎng)的；（2）選擇那些信息增益高的屬性離根節(jié)點(diǎn)較近的樹。 l結(jié)論：ID系列算法的歸納偏置是因?yàn)樗谶x的時(shí)候較短的樹比較長(zhǎng)的樹優(yōu)先所產(chǎn)生的，也就是那些信息增益高的屬性更靠近的根節(jié)點(diǎn)將會(huì)有優(yōu)先生成樹的特權(quán)。第9章決策樹算法249.2.2.1 C4.5的分裂屬性選擇度量l 為了避免這個(gè)偏置，彌補(bǔ)ID系列算法的不足就要舍棄信息增益這個(gè)度量而選擇別的決策屬性作為度量標(biāo)準(zhǔn)。Quinlan在他1986年中的論文中提出了一種可以使用的度量標(biāo)準(zhǔn)：增益比率。l 增益比率通過(guò)加入一個(gè)被稱為分裂信息（split information）的項(xiàng)來(lái)懲罰類似D

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

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

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

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

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

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

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

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

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

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

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

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

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

25、的類別為子樹中大多數(shù)實(shí)例所屬的類別。 第9章決策樹算法46悲觀錯(cuò)誤剪枝PEP(Pessimistic Error Pruning)l REP方法進(jìn)行剪枝具有以下優(yōu)點(diǎn)：l （1）運(yùn)用REP方法得到的決策樹是關(guān)于測(cè)試數(shù)據(jù)集的具有最高精度的子樹，并且是規(guī)模最小的樹。l （2）它的計(jì)算復(fù)雜性是線性的，這是因?yàn)闆Q策樹中的每個(gè)非葉子結(jié)點(diǎn)只需要訪問(wèn)一次就可以評(píng)估其子樹被修剪的概率。l （3）由于使用獨(dú)立的測(cè)試數(shù)據(jù)集，和原始決策樹相比，修剪后的決策樹對(duì)未來(lái)新事例的預(yù)測(cè)偏差較小。第9章決策樹算法47悲觀錯(cuò)誤剪枝PEP(Pessimistic Error Pruning)l正是由于REP方法出現(xiàn)的一系列問(wèn)題，隨后

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

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

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

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

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

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

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

33、應(yīng)用實(shí)例分析l 屬性值Outlook在各個(gè)屬性中具有最高的增益，被選作分裂屬性。則第一個(gè)根節(jié)點(diǎn)T被用標(biāo)記，并對(duì)于每個(gè)屬性值生長(zhǎng)一個(gè)分支：根據(jù)信息增益結(jié)果生成的以O(shè)utlook為根節(jié)點(diǎn)的初級(jí)決策樹圖 第9章決策樹算法589.5 應(yīng)用實(shí)例分析應(yīng)用實(shí)例分析l A分析圖中的sunny分支，計(jì)算其子屬性的信息增益值來(lái)決定子分裂屬性形成子分支之一。l 針對(duì)sunny中的子訓(xùn)練數(shù)據(jù)集分支，有兩個(gè)類別，該分支中有3個(gè)實(shí)例屬于n類，有2個(gè)實(shí)例屬于p類，因此針對(duì)分支的信息熵為：l 若以 ：sunny分支中的屬性Temperature為測(cè)試屬性，則測(cè)試屬性Temperature的信息量為 ：1T1TbitnpIT9

34、71. 053log5352log52),(2211TbiteTemperaturET400. 0)10log1011log11(51)21log2121log21(52)20log2022log22(52)(2222221第9章決策樹算法599.5 應(yīng)用實(shí)例分析應(yīng)用實(shí)例分析l 其信息增益為：l 若以：sunny分支中的屬性Humidity為測(cè)試屬性，則測(cè)試屬性Humidity的信息量為 ： l 0.00bit l 其信息增益為：l 若以：sunny分支中的屬性Wind為測(cè)試屬性 ，則測(cè)試屬性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 應(yīng)用實(shí)例分析應(yīng)用實(shí)例分析l 這時(shí)生成的決策樹如圖所示：決策樹構(gòu)造圖2第9章決策樹算法619.5 應(yīng)用實(shí)例分析應(yīng)用實(shí)例分析l B分析圖9-8中的：rain分支，計(jì)算其子屬性的信息增益值來(lái)確定子分裂屬性形成子分支之三。 l 針對(duì)：rain中的子訓(xùn)練數(shù)據(jù)集分支，有兩個(gè)類別，該分支中有3個(gè)實(shí)例屬于n類，有2個(gè)實(shí)例屬于p類，因此針對(duì)分支的信息熵為：l 若以：rain分支中的屬性Temperature為測(cè)試屬性，則測(cè)試屬性Temperature的信息量為：l 其信息增益值為： l 0.9710.2850.696bit bitn