第三章決策樹(shù)

1決策樹(shù)(DecisionTree)2023/1/1921、分類的意義數(shù)據(jù)庫(kù)了解類別屬性與特征預(yù)測(cè)分類模型—決策樹(shù)分類模型—聚類一、分類(Classification)2023/1/193數(shù)據(jù)庫(kù)分類標(biāo)記性別年齡婚姻否是否是FemaleMale<35≧35未婚已婚2023/1/192、分類的技術(shù)（1）決策樹(shù)4（2）聚類2023/1/193、分類的程序5模型建立(ModelBuilding)模型評(píng)估(ModelEvaluation)使用模型(UseModel)2023/1/19決策樹(shù)分類的步驟6數(shù)據(jù)庫(kù)2023/1/19訓(xùn)練樣本(trainingsamples)建立模型測(cè)試樣本(testingsamples)評(píng)估模型例：7資料訓(xùn)練樣本婚姻年齡

家庭

所得否是否是未婚已婚<35≧35低高否小康1.建立模型測(cè)試樣本2.模型評(píng)估錯(cuò)誤率為66.67%修改模型3.使用模型2023/1/194、分類算法的評(píng)估8預(yù)測(cè)的準(zhǔn)確度：指模型正確地預(yù)測(cè)新的或先前未見(jiàn)過(guò)的數(shù)據(jù)的類標(biāo)號(hào)的能力。訓(xùn)練測(cè)試法(training-and-testing)交叉驗(yàn)證法(cross-validation)例如，十折交叉驗(yàn)證。即是將數(shù)據(jù)集分成十分，輪流將其中9份做訓(xùn)練1份做測(cè)試，10次的結(jié)果的均值作為對(duì)算法精度的估計(jì)，一般還需要進(jìn)行多次10倍交叉驗(yàn)證求均值，例如10次10倍交叉驗(yàn)證，更精確一點(diǎn)。2023/1/192023/1/199速度：指產(chǎn)生和使用模型的計(jì)算花費(fèi)。建模的速度、預(yù)測(cè)的速度強(qiáng)壯性：指給定噪聲數(shù)據(jù)或具有缺失值的數(shù)據(jù)，模型正確預(yù)測(cè)的能力?？稍忈屝裕褐改Ｐ偷慕忉屇芰Α?02023/1/19決策樹(shù)歸納的基本算法是貪心算法，它以自頂向下遞歸各個(gè)擊破的方式構(gòu)造決策樹(shù)。貪心算法：在每一步選擇中都采取在當(dāng)前狀態(tài)下最好/優(yōu)的選擇。在其生成過(guò)程中，分割方法即屬性選擇度量是關(guān)鍵。通過(guò)屬性選擇度量，選擇出最好的將樣本分類的屬性。根據(jù)分割方法的不同，決策樹(shù)可以分為兩類：基于信息論的方法（較有代表性的是ID3、C4.5算法等）和最小GINI指標(biāo)方法（常用的有CART、SLIQ及SPRINT算法等）。二、決策樹(shù)(DecisionTree)（一）決策樹(shù)的結(jié)結(jié)構(gòu)11根部節(jié)點(diǎn)(rootnode)中間節(jié)點(diǎn)(non-leafnode)(代表測(cè)試的的條件)分支(branches)(代表測(cè)試的的結(jié)果)葉節(jié)點(diǎn)(leafnode)(代表分類后后所獲得的分類標(biāo)記記)2023/1/12023/1/112（二）決策策樹(shù)的形成成例：13根部節(jié)點(diǎn)中間節(jié)點(diǎn)停止分支？2023/1/1（三）ID3算法(C4.5,C5.0)142023/1/1Quinlan(1979)提出，以以Shannon(1949)的信息論論為依據(jù)據(jù)。ID3算法的屬屬性選擇擇度量就就是使用用信息增增益，選選擇最高高信息增增益的屬屬性作為為當(dāng)前節(jié)節(jié)點(diǎn)的測(cè)測(cè)試屬性性。信息論：若一事件件有k種結(jié)果，對(duì)應(yīng)的的概率為為Pi。則此事事件發(fā)生生后所得得到的信息量量I(視為Entropy)為：I=-(p1*log2(p1)+p2*log2(p2)+…+pk*log2(pk))Example1：設(shè)k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25I=-(.25*log2(.25)*4)=2Example2：設(shè)k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1Example3：設(shè)k=4p1=1,p2=0,p3=0,p4=0I=-(1*log2(1))=02023/1/1152023/1/116信息增增益17Example(Gain)n=16n1=4I(16,4)=－((4/16)*log2(4/16)+(12/16)*log2(12/16))=0.8113E(年齡)=(6/16)*I(6,1)+(10/16)*I(10,3)=0.7946Gain(年齡)=I(16,4)-E(年齡)=0.0167Gain(年齡)=0.0167Max:作為第一個(gè)個(gè)分類依據(jù)據(jù)2023/1/1Gain(性別)=0.0972Gain(家庭所得)=0.0177Example(續(xù))18Gain(家庭所得)=0.688I(7,3)=-((3/7)*log2(3/7)+(4/7)*log2(4/7))=0.9852Gain(年齡)=0.9852Gain(年齡)=0.2222I(9,1)=-((1/9)*log2(1/9)+(8/9)*log2(8/9))=0.5032Gain(家庭所得)=0.50322023/1/1Example(end)ID3算法19分類規(guī)則：IF性別=FemaleAND家庭所得=低所得THEN購(gòu)買RV房車=否IF性別=FemaleAND家庭所得=小康THEN購(gòu)買RV房車=否IF性別=FemaleAND家庭所得=高所得THEN購(gòu)買RV房車=是IF性別=MaleAND年齡<35THEN購(gòu)買RV房車=否IF性別=MaleAND年齡≧35

THEN購(gòu)買RV房車=是資料DecisionTree2023/1/1（四）DecisionTree的建立過(guò)程201、決策樹(shù)的停停止決策樹(shù)是通過(guò)過(guò)遞歸分割(recursivepartitioning)建立而成，遞遞歸分割是一一種把數(shù)據(jù)分分割成不同小小的部分的迭代過(guò)程。如果有以下情情況發(fā)生，決決策樹(shù)將停止分割：該群數(shù)據(jù)的每每一筆數(shù)據(jù)都都已經(jīng)歸類到到同一類別。。該群數(shù)據(jù)已經(jīng)經(jīng)沒(méi)有辦法再再找到新的屬該群數(shù)據(jù)已經(jīng)沒(méi)有任何尚未處理的數(shù)據(jù)。2023/1/12、決策樹(shù)的剪剪枝(pruning)21決策樹(shù)學(xué)習(xí)可可能遭遇模型過(guò)度擬合（overfitting）的問(wèn)題，過(guò)度度擬合是指模模型過(guò)度訓(xùn)練練，導(dǎo)致模型型記住的不是是訓(xùn)練集的一一般性，反而而是訓(xùn)練集的的局部特性。。如何處理過(guò)度度擬合呢？對(duì)對(duì)決策樹(shù)進(jìn)行行修剪。樹(shù)的修剪有幾幾種解決的方方法，主要為為先剪枝和后后剪枝方法。。2023/1/1（1）先剪剪枝方方法22在先剪剪枝方方法中中，通通過(guò)提提前停停止樹(shù)樹(shù)的構(gòu)構(gòu)造（（例如如，確定閥值法：在構(gòu)造樹(shù)時(shí)，可將信息增益用于評(píng)估岔的優(yōu)良性。如果在一個(gè)節(jié)點(diǎn)劃分樣本將導(dǎo)致低于預(yù)定義閥值的分裂，則給定子集的進(jìn)一步劃分將停止。測(cè)試組修剪法：在使用訓(xùn)練組樣本產(chǎn)生新的分岔時(shí)，就立刻使用測(cè)試組樣本去測(cè)試這個(gè)分岔規(guī)則是否能夠再現(xiàn)，如果不能，就被視作過(guò)度擬合而被修剪掉，如果能夠再現(xiàn)，則該分岔予以保留而繼續(xù)向下分岔。2023/1/1（2）后剪剪枝方方法23后剪剪枝枝方方法法案例數(shù)修剪是在產(chǎn)生完全生長(zhǎng)的樹(shù)后，根據(jù)最小案例數(shù)閥值，將案例數(shù)小于閥值的樹(shù)節(jié)點(diǎn)剪掉。成本復(fù)雜性修剪法是當(dāng)決策樹(shù)成長(zhǎng)完成后，演算法計(jì)算所有葉節(jié)點(diǎn)的總和錯(cuò)誤率，然后計(jì)算去除某一葉節(jié)點(diǎn)后的總和錯(cuò)誤率，當(dāng)去除該葉節(jié)點(diǎn)的錯(cuò)誤率降低或者不變時(shí)，則剪掉該節(jié)點(diǎn)。反之，保留。2023/1/1應(yīng)用案例例：在農(nóng)農(nóng)業(yè)中的的應(yīng)用2023/1/124第一步：：屬性離離散化2023/1/125第二步：概化化（泛化）2023/1/126第三步：計(jì)計(jì)算各屬性性的期望信信息2023/1/127=(17/30)*LOG((17/30),2)+(10/30)*LOG((10/30),2)+(3/30)*LOG((3/30),2)計(jì)算各屬性性的信息增增益2023/1/128第四四步步：：決決策策樹(shù)樹(shù)2023/1/129案例2：銀行違違約率2023/1/1302023/1/131案例3對(duì)電電信信客客戶戶的的流流失失率率分分析析2023/1/132數(shù)據(jù)據(jù)倉(cāng)倉(cāng)庫(kù)庫(kù)條件件屬屬性性類別別屬屬性性客戶戶是是否否流流失失案例例4：在在銀銀行行中中的的應(yīng)應(yīng)用用2023/1/133案例例5：個(gè)個(gè)人人信信用用評(píng)評(píng)級(jí)級(jí)2023/1/134個(gè)人信用評(píng)級(jí)級(jí)決策樹(shù)（五）其他算法35C4.5與C5.0算法GiniIndex算法CART算法PRISM算法CHAID算法2023/1/11、C4.5與C5.0算法36C5.0算法則是C4.5算法的修訂版版，適用在在處理大數(shù)據(jù)據(jù)集，采用Boosting（提升）方式式提高模型準(zhǔn)準(zhǔn)確率，又稱稱為BoostingTrees，在軟件上的的計(jì)算速度比比較快，占用用的內(nèi)存資源源較少。2023/1/1類別屬性性的信息息熵2、GiniIndex算法37ID3andPRISM適用于類類別屬性性的分類類方法。。GiniIndex能數(shù)值型型屬性的的變量來(lái)來(lái)做分類類。著重重解決當(dāng)當(dāng)訓(xùn)練集集數(shù)據(jù)量量巨大，，無(wú)法全全部放人人內(nèi)存時(shí)時(shí)，如何何高速準(zhǔn)準(zhǔn)確地生生成更快快的，更更小的決決策樹(shù)。。2023/1/1集合T包含N個(gè)類別的的記錄，，那么其其Gini指標(biāo)就是是如果集合合T分成兩部部分N1和N2。則此分分割的Gini就是提供最小小Ginisplit就被選擇擇作為分分割的標(biāo)標(biāo)準(zhǔn)(對(duì)于每個(gè)個(gè)屬性都都要經(jīng)過(guò)過(guò)所有可可以的分分割方法法)。GiniIndex算法382023/1/1案例：在在汽車銷銷售中的的應(yīng)用2023/1/1392023/1/1402023/1/141NNYYYNYYYNNN3、CART算法42由Friedman等人提出，，1980年以來(lái)就開(kāi)開(kāi)始發(fā)展