第四章-決策樹

決策樹1大綱什么是決策樹決策樹算法ID3C4.5剪枝樹連續(xù)屬性處理缺失值處理可解釋性

總結(jié)2決策樹預(yù)備知識(shí):根節(jié)點(diǎn),葉子節(jié)點(diǎn),非葉子節(jié)點(diǎn)每個(gè)非葉子節(jié)點(diǎn)代表一個(gè)屬性的劃分每次劃分的結(jié)果要么導(dǎo)致下一個(gè)的決策問題要么導(dǎo)致最終結(jié)論

決策樹通過從根節(jié)點(diǎn)開始沿著分支直到葉子節(jié)點(diǎn)結(jié)束來對樣本進(jìn)行分類決策樹最終的結(jié)論（葉子節(jié)點(diǎn)）對應(yīng)一個(gè)目標(biāo)值3構(gòu)建決策樹的要素構(gòu)建決策樹的要素1、屬性及屬性值2、預(yù)定義的類別（目標(biāo)值）3、充足的標(biāo)記數(shù)據(jù)4訓(xùn)練集5訓(xùn)練集對應(yīng)三個(gè)要素構(gòu)建決策樹的三個(gè)問題（3）什么時(shí)候停止并得到目標(biāo)值？（1）

從哪個(gè)屬性開始或者說選擇哪個(gè)屬性作為根節(jié)點(diǎn)？6（2）選擇哪個(gè)屬性作為后繼節(jié)點(diǎn)？決策樹決策樹算法的基本思想：選擇最優(yōu)屬性劃分當(dāng)前樣本集合并把這個(gè)屬性作為決策樹的一個(gè)節(jié)點(diǎn)不斷重復(fù)這個(gè)過程構(gòu)造后繼節(jié)點(diǎn)直到滿足下面三個(gè)條件之一停止:對于當(dāng)前節(jié)點(diǎn)，所有樣本屬于同一類或者沒有屬性可以選擇了或者沒有樣本可以劃分了7屬性選擇決策樹算法的一個(gè)關(guān)鍵問題：屬性選擇不同決策樹算法的差異：屬性選擇方法不同下面以

ID3

算法為例講解怎么構(gòu)造決策樹(ID3:

InteractiveDichotomize3[RossQuinlan/1975])8ID3ID3依據(jù)信息增益來選擇最優(yōu)屬性信息增益是通過信息熵計(jì)算而來信息熵衡量一個(gè)集合的純度例如：集合1:10個(gè)好瓜集合2:8個(gè)好瓜和2個(gè)壞瓜集合3:5個(gè)好瓜和5個(gè)壞瓜純度：集合1>集合2>集合39信息熵pi

是當(dāng)前集合里類別為i

的樣本所占的比例,則：Entropy({p1,…,pk})=-sum(pilog(pi))如果一個(gè)集合里的樣本只有兩個(gè)類別，那么：

Entropy=-p1log(p1)-(1-p1)log(1-p1)當(dāng)集合里的所有樣本都屬于同一類時(shí),信息熵

是

0例如：

集合1:10個(gè)好瓜當(dāng)集合里所有樣本均勻混合時(shí),信息熵是

1例如：

集合2:5個(gè)好瓜，5個(gè)壞瓜p1=1orp1=0p1=0.510p1entropy信息熵當(dāng)集合里所有樣本屬于同一類時(shí)（純度最高時(shí)），信息熵最小。當(dāng)集合里所有樣本均勻混合時(shí)（純度最低時(shí)），信息熵最大純度越低，信息熵越大；純度越高，信息熵越小11信息增益一個(gè)屬性的信息增益是本屬性對樣本集合進(jìn)行劃分所帶來的信息熵下降Di是集合D的第i個(gè)子集,a是一個(gè)屬性，則:

Gain(D,a)=Entropy(D)-∑(i=1tok)

|Di|/|D|Entropy(Di)劃分:劃分后信息熵越低

信息增益越大例如：D:

5

個(gè)好西瓜，5個(gè)壞瓜

D1:

2個(gè)好瓜,1個(gè)壞瓜D2

:3個(gè)好瓜,4個(gè)壞瓜

12舉例色澤：D1(色澤=青綠)={1+,4+,6+,10-,13-,17-}D2(色澤=烏黑)={2+,3+,7+,8+,9-,15-}D3(色澤=淺白)={5+,11-,12-,14-,16-}=13訓(xùn)練集舉例同理：14舉例D1={1+,2+,3+,4+,5+,6+,8+,10-,15-}15紋理=？{1+,2+,3+,4+,5+,6+,8+,10-,15-}{7+,9-,13-,14-,17-}{11-,12-,16-}清晰稍糊模糊ID3的缺陷例如：如果我們把“編號(hào)”作為一個(gè)屬性，那么“編號(hào)”將會(huì)被選為最優(yōu)屬性

。但實(shí)際上“編號(hào)”是無關(guān)屬性，它對西瓜分類并沒有太大作用。16ID3傾向于選擇取值比較多的屬性缺陷：

有些屬性可能會(huì)對分類任務(wù)沒有太大作用，但是他們可能會(huì)被選為最優(yōu)屬性。C4.5信息增益比：17該項(xiàng)是對屬性取值個(gè)數(shù)的度量屬性屬性的取值個(gè)數(shù)樣本集合剪枝樹太多的屬性和分支可能會(huì)導(dǎo)致過擬合一種減少?zèng)Q策樹中屬性的技術(shù)：剪枝兩種剪枝類型：預(yù)剪枝（前向剪枝）后剪枝

（后向剪枝）18剪枝泛化能力：用驗(yàn)證集精度來衡量預(yù)剪枝：在建造決策樹的過程中停止添加屬性后剪枝：決策樹構(gòu)建完成后剪掉一些屬性預(yù)剪枝和

后剪枝：都依據(jù)泛化能力19預(yù)剪枝舉例如果我們停止添加這個(gè)屬性，那么當(dāng)前節(jié)點(diǎn)的標(biāo)記是好瓜：驗(yàn)證集精度:3/7=42.9%如果我們添加這個(gè)屬性到?jīng)Q策樹，則驗(yàn)證集精度：(1+1+1+1+1)/7=71.4%>42.9%所以我們添加此屬性。20訓(xùn)練集驗(yàn)證集預(yù)剪枝舉例預(yù)剪枝能夠減少過擬合的風(fēng)險(xiǎn)，

但它可能導(dǎo)致欠擬合預(yù)剪枝每次僅考慮了一個(gè)屬性可能會(huì)帶來泛化能力的下降，沒有考慮后續(xù)多個(gè)屬性的組合可能會(huì)帶來的泛化能力的提升21后剪枝舉例剪去紋理屬性前驗(yàn)證集精度：3/7=42.9%當(dāng)我們剪去紋理屬性（節(jié)點(diǎn)6）:新的葉子節(jié)點(diǎn)包含：{7+,15-}，標(biāo)記：

好瓜驗(yàn)證集精度：

57.1%>42.9%所以剪枝。22好瓜訓(xùn)練集驗(yàn)證集剪枝舉例后剪枝：預(yù)剪枝：23計(jì)算代價(jià)：高計(jì)算代價(jià)：

低可能導(dǎo)致欠擬合連續(xù)屬性處理每個(gè)非葉子節(jié)點(diǎn)代表一個(gè)屬性的劃分（對于離散屬性很容易）對于連續(xù)屬性：把連續(xù)屬性Ac

劃分成多個(gè)離散的區(qū)間例如：找到一個(gè)閾值

Ta

把連續(xù)屬性Ac

轉(zhuǎn)化成具有兩個(gè)取值的離散屬性Ad怎么選擇閾值Ta?24

ifAd<

Taotherwise連續(xù)屬性處理訓(xùn)練集25(對應(yīng)可能的劃分)我們選擇具有最高信息增益的劃分所對應(yīng)的閾值。缺失值處理26Q1：如何在屬性值缺失的情況下進(jìn)行屬性選擇？Q2：給定劃分屬性,若樣本在該屬性上的值缺失，如何對樣本進(jìn)行劃分？缺失值處理27

缺失值處理28基于上述定義，可得

其中

對于Q2：若樣本在劃分屬性

上的取值已知，則將

劃入與其取值對應(yīng)的子結(jié)點(diǎn)，且樣本權(quán)值在子結(jié)點(diǎn)中保持為若樣本在劃分屬性上的取值未知，則將

同時(shí)劃入所有子結(jié)點(diǎn)，且樣本權(quán)值在與屬性值對應(yīng)的子結(jié)點(diǎn)中調(diào)整為

(直觀來看，相當(dāng)于讓同一個(gè)樣本以不同概率劃入不同的子結(jié)點(diǎn)中去)缺失值處理舉例色澤：

={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}29Trainingset在色澤屬性有取值的樣本：首先初始化訓(xùn)練集每個(gè)樣本的權(quán)重為1（后面會(huì)用到）。缺失值處理舉例色澤：

={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}

青綠：

={4+,6+,10-,17-}

烏黑：={2+,3+,7+,8+,9-,15-}30Trainingset

淺白：={11-,12-14-,16-}

=缺失值處理舉例Informationgain：

31我們這里把含有色澤屬性樣本集的權(quán)重所占的比例考慮進(jìn)去（每個(gè)樣本的初始權(quán)重為1）：色澤：

={2+,3+,4+,6+,7+,8+,9-,10-,11-,12-,14-,15-,16-,17-}

缺失值處理舉例32Similarly,缺失值處理舉例33

{1,2,3,4,5,6,15,8,10}{7,9,13,14,17,8,10}{11,12,16,8,10}紋理(15個(gè)樣本)

:{1,2,3,4,5,6,7,9,11,12,13,14,15,16,17}稍糊(5個(gè)樣本):{7,9,13,14,17}清晰(7個(gè)樣本):{1,2,3,4,5,6,15}模糊(3個(gè)樣本):{11,12,16}缺失紋理屬性取值的樣本：{8,10}Dt1Dt2Dt3缺失值處理舉例34{1,2,3,4,5,6,15,8,10}{7,9,13,14,17,8,10}{11,12,16,8,10}Dt1Dt2Dt3對于后續(xù)節(jié)點(diǎn)同理可求信息增益：

可解釋性決策邊界是平行坐標(biāo)軸的對于過于復(fù)雜的問題，會(huì)導(dǎo)致很多小的劃分35總結(jié)優(yōu)點(diǎn)

生成可理解的規(guī)則分類時(shí)計(jì)算代價(jià)很小能夠選出對分類比較重要的屬性對長方形分布的樣本處理很好缺點(diǎn)決策樹可能經(jīng)歷錯(cuò)誤傳播對于非長方形分布的樣本處理不是很好（例如弧形）36++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++實(shí)驗(yàn)介紹實(shí)驗(yàn)任務(wù)：實(shí)現(xiàn)ID3決策樹，并在給定的數(shù)據(jù)集上進(jìn)行5折交叉驗(yàn)證。并觀測訓(xùn)所得到的決策樹在訓(xùn)練集和測試集的準(zhǔn)確率，從而判斷該決策樹是否存在過擬合。在此基礎(chǔ)上實(shí)現(xiàn)預(yù)剪枝和后剪枝，并比較預(yù)剪枝樹與后剪枝樹在訓(xùn)練集和測試集上的準(zhǔn)確率。數(shù)據(jù)集：鳶尾花卉Iris數(shù)據(jù)集描述：iris是鳶尾植物，這里存儲(chǔ)了其萼片和花瓣的長寬，共4個(gè)屬性，鳶尾植物分三類，分別是山鳶尾(Iris-setosa)，變色鳶尾(Iris-versicolor)和維吉尼亞鳶尾(Iris-virginica)。所以我們的數(shù)據(jù)集里每個(gè)樣本含有四個(gè)屬性，并且我們的任務(wù)是個(gè)三分類問題。。例如：樣本一：5.1,3.5,1.4,0.2,Iris-setosa其中“5.1，3.5，1.4，0.2”代表當(dāng)前樣本的四個(gè)屬性的取值，“Iris-setosa”代表當(dāng)前樣本的類別。37作業(yè)請闡述ID3和C4.5異同點(diǎn)?請闡述預(yù)剪枝和后剪枝的異同點(diǎn)?闡述如何解決構(gòu)建決策樹過程中遇到的連續(xù)屬性問題?就你的理解，決策樹存在哪些優(yōu)缺點(diǎn)并闡述原因？討論如何使用決策樹技術(shù)對某校的男女生進(jìn)行分類。并討論你的方案可能存在的問題。38資源C4.5package:/Personal/c4.5r8.tar.gzWikipediapagefordecisiontree:/wiki/Decision_tree_learningRandomForests(LeoBreimanandAdeleCutler):/~breiman/RandomForests/ICCV2013tutorial:DecisionForestsandFieldsforComputerVision:/enus/um/cambridge/projects/iccv2013tutorial/39引用[Rastogi,etal.,1998]R.RastogiandK.Shim.PUBLIC:ADecisionTreeClassifierthatIntegratesBuildingandPruning.InProceedingsofthe24thInternationalConferenceonVeryLargeDataBases(VLDB’98),pp.404–415,Aug.1998.[Shafer,etal.,1996]J.C.Shafer,R.Agrawal,andM.Mehta.SPRINT:AScalableParallelClassifierforDataMining.InProceedingsofthe22thInternationalConferenceonVeryLargeDataBases(