機(jī)器學(xué)習(xí)-決策樹 -ppt

1、決策樹,主講人：王二,主要內(nèi)容,決策樹基本概念,基本流程,劃分選擇,剪枝處理,決策樹基本概念,決策樹,決策樹是數(shù)據(jù)挖掘分類算法的一個(gè)重要方法。在各種分類算法中，決策樹是最直觀的一種。在機(jī)器學(xué)習(xí)中也是一種常用方法。 我們希望從給定的訓(xùn)練集中學(xué)得一個(gè)模型用來(lái)對(duì)新示例進(jìn)行分類，這一分類過(guò)程稱為“決策”過(guò)程。決策樹是基于樹結(jié)構(gòu)進(jìn)行決策的,基本流程,構(gòu)造過(guò)程： 決策樹是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法。它從一組無(wú)次序、無(wú)規(guī)則的元組中推理出決策樹表示形式的分類規(guī)則；采用自頂向下遞歸方式，在決策樹的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較，并根據(jù)不同的屬性值從該節(jié)點(diǎn)向下分支，而葉節(jié)點(diǎn)是要學(xué)習(xí)劃分的類。從根節(jié)點(diǎn)到葉節(jié)點(diǎn)的一條路徑就

2、對(duì)應(yīng)著一條合取規(guī)則，整個(gè)決策樹就對(duì)應(yīng)著一組析取表達(dá)式規(guī)則,例如：我們要對(duì)“這是好瓜嗎”這樣的問(wèn)題進(jìn)行決策時(shí)，通常 會(huì)進(jìn)行一系列的判斷：我們先看“它是什么顏色”，如果是“青 綠色”再看“它的根蒂是什么形態(tài)”，如果是“蜷縮”，我們?cè)谂?斷“它敲起來(lái)是什么聲音”，最后，我們得出最終的決策：這是 個(gè)好瓜，這個(gè)過(guò)程如下： 決策樹的基本組成部分：決策結(jié)點(diǎn)、分支和葉子,決策樹算法 目前已有多種決策樹算法：CLS、ID3、CHAID、C4.5、CART、 SLIQ、SPRINT等。 著名的ID3（Iterative Dichotomiser3）算法是J.R.Quinlan在1986 年提出的，該算法引入了信息

3、論中的理論，是基于信息熵的決策樹分類算法,決策樹ID3算法,最后得到一棵決策樹，它可以用來(lái)對(duì)新的樣本進(jìn)行分類,ID3算法的核心是：在決策樹各級(jí)節(jié)點(diǎn)上選擇屬性時(shí)，用信息增益作為屬性的選擇標(biāo)準(zhǔn)，以使得在每一個(gè)非葉節(jié)點(diǎn)進(jìn)行測(cè)試時(shí)能獲得關(guān)于被測(cè)試記錄最大的類別信息。 具體方法：檢測(cè)所有的屬性，選擇信息增益最大的屬性產(chǎn)生決策樹結(jié)點(diǎn)，由該屬性的不同取值建立分枝，再對(duì)各分支的子集遞歸調(diào)用該方法建立決策樹結(jié)點(diǎn)的分枝，直到所有子集僅包含同一類別的數(shù)據(jù)為止，最后得到一棵決策樹，它可以用來(lái)對(duì)新的樣本進(jìn)行分類,Ent（D）的值越小，則D的純度越高,假定屬性a有V個(gè)可能的取值a1 .av,若使用a來(lái)對(duì)樣本集D進(jìn)行劃分，

4、則會(huì)產(chǎn)生V個(gè)分支節(jié)點(diǎn)，其中第V個(gè)分支節(jié)點(diǎn)包含了D中所有在屬性a上取值為av的樣本，記為Dv。在考慮到不同的分支節(jié)點(diǎn)所包含的樣本不同，給分支節(jié)點(diǎn)賦予權(quán)重Dv/D,即樣本數(shù)越多的分支節(jié)點(diǎn)的影響越大，于是計(jì)算出屬性 a對(duì)樣本D進(jìn)行劃分所獲得的“信息增益”（information gain）。 一般而言，信息增益越大，則意味著使用屬性a來(lái)進(jìn)行劃分所獲得的“純度”（即分支節(jié)點(diǎn)所包含的樣本盡可能屬于同一類別,以下表的西瓜數(shù)據(jù)為例,以屬性“色澤”為例，它有三個(gè)可能取值青綠，烏黑，淺白，記為：D1=青綠，D2=烏黑，D3=淺白算D1包含1，4，6,10,13,176個(gè)樣例，其中正比例P1=3/6，反比例P2=

5、3/6；D2包含2,3,7,8,9，156個(gè)樣例，其中正比例P1=4/6，反比例P2=2/6；D3包含5,11,12,14,165個(gè)樣例，其中正比例P1=1/5，反比例P2=4/5,由此可計(jì)算出用“色澤”劃分之后的三個(gè)分支節(jié)點(diǎn)的信息熵為,于是可計(jì)算出屬性“色澤”的信息增益為,然后，決策樹學(xué)習(xí)算法將對(duì)每個(gè)分支節(jié)點(diǎn)作進(jìn)一步的劃分。最終得到的決策樹如下所示,剪枝處理 剪枝（pruning）是決策樹學(xué)習(xí)算法對(duì)付“過(guò)合”的主要手段，為了盡可能正確的分類訓(xùn)練樣本，節(jié)點(diǎn)劃分過(guò)程將不斷重復(fù)，有時(shí)會(huì)造成決策樹分支太多，這時(shí)就可能因訓(xùn)練樣本學(xué)得“太好”了，以至于把訓(xùn)練集自身的一些特點(diǎn)當(dāng)做所有數(shù)據(jù)的特點(diǎn)而導(dǎo)致過(guò)擬合。因此，可通過(guò)主動(dòng)去掉一些分支來(lái)降低過(guò)擬合的風(fēng)險(xiǎn)。 剪枝分為“預(yù)剪枝”和“后剪枝”。預(yù)剪枝是在決策樹生成過(guò)程中，對(duì)每個(gè)節(jié)點(diǎn)在劃分之前先進(jìn)行估計(jì)，若當(dāng)前節(jié)點(diǎn)的劃分不能帶來(lái)決策樹的泛化性能的提升，則停止劃分并將當(dāng)前節(jié)點(diǎn)標(biāo)記