決策樹培訓(xùn)講義

1、2022-2-141決策樹(Decision Tree)2022-2-1421、分類的意義數(shù)據(jù)庫數(shù)據(jù)庫了解類別屬性了解類別屬性與特征與特征預(yù)測(cè)預(yù)測(cè)分類模型決策樹分類模型聚類一、分類(Classification)2022-2-143數(shù)據(jù)庫數(shù)據(jù)庫分類標(biāo)記分類標(biāo)記性別性別年齡年齡婚姻婚姻否否是是否否是是FemaleFemaleMaleMale35353535未婚未婚已婚已婚2、分類的技術(shù)（1）決策樹2022-2-144（2）聚類2022-2-1453、分類的程序模型建立(Model Building)模型評(píng)估(Model Evaluation)使用模型(Use Model)2022-2-146決策

2、樹分類的步驟數(shù)據(jù)庫訓(xùn)練樣本(training samples)建立模型測(cè)試樣本(testing samples)評(píng)估模型2022-2-147例：資料訓(xùn)練樣本訓(xùn)練樣本婚姻年齡 家庭 所得否是否是未婚已婚3535低高否小康1.建立模型測(cè)試樣本2.模型評(píng)估錯(cuò)誤率為66.67%修改模型3.使用模型2022-2-1484、分類算法的評(píng)估預(yù)測(cè)的準(zhǔn)確度：指模型正確地預(yù)測(cè)新的或先前未見過的數(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ì)算法精

3、度的估計(jì)，一般還需要進(jìn)行多次10倍交叉驗(yàn)證求均值，例如10次10倍交叉驗(yàn)證，更精確一點(diǎn)。2022-2-149速度：指產(chǎn)生和使用模型的計(jì)算花費(fèi)。建模的速度、預(yù)測(cè)的速度強(qiáng)壯性：指給定噪聲數(shù)據(jù)或具有缺失值的數(shù)據(jù)，模型正確預(yù)測(cè)的能力?？稍忈屝裕褐改Ｐ偷慕忉屇芰Α?022-2-1410決策樹歸納的基本算法是貪心算法，它以自頂向下遞歸各個(gè)擊破的方式構(gòu)造決策樹。貪心算法：在每一步選擇中都采取在當(dāng)前狀態(tài)下最好/優(yōu)的選擇。在其生成過程中，分割方法即屬性選擇度量是關(guān)鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性。根據(jù)分割方法的不同，決策樹可以分為兩類：基于信息論的方法（較有代表性的是ID3、C4.5算法等）和

4、最小GINI指標(biāo)方法（常用的有CART、SLIQ及SPRINT算法等）。二、決策樹(Decision Tree)2022-2-1411（一）決策樹的結(jié)構(gòu)根部節(jié)點(diǎn)(root node)中間節(jié)點(diǎn)(non-leaf node)(代表測(cè)試的條件)分支(branches)(代表測(cè)試的結(jié)果)葉節(jié)點(diǎn)(leaf node)(代表分類后所獲得的分類標(biāo)記)2022-2-1412（二）決策樹的形成2022-2-1413例：n根部節(jié)點(diǎn)n中間節(jié)點(diǎn)n停止分支？2022-2-1414（三）ID3算法(C4.5,C5.0)Quinlan(1979)提出，以Shannon(1949)的信息論為依據(jù)。ID3算法的屬性選擇度量就是

5、使用信息增益，選擇最高信息增益的屬性作為當(dāng)前節(jié)點(diǎn)的測(cè)試屬性。信息論：若一事件有k種結(jié)果，對(duì)應(yīng)的概率為Pi。則此事件發(fā)生后所得到的信息量I(視為Entropy)為：I=-(p1*log2(p1)+ p2*log2(p2)+ pk*log2(pk)2022-2-1415Example 1：設(shè) k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25 I=-(.25*log2(.25)*4)=2Example 2：設(shè)k=4p1=0,p2=0.5,p3=0,p4=0.5I=-(.5*log2(.5)*2)=1Example 3：設(shè) k=4p1=1,p2=0,p3=0,p4=0 I=-(1*

6、log2(1)=02022-2-1416信息增益2022-2-1417Example(Gain) n=16 n1=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.0167nGain(年齡)=0.0167nMax:作為第一個(gè)分類依據(jù)nGain(性別)=0.0972nGain(家庭所得)=0.01772022-2-1418Example(續(xù))nGain(家庭所得)=0.688I(7,3)=-(3/7)*log

7、2(3/7)+(4/7)*log2(4/7)=0.9852nGain(年齡)=0.9852nGain(年齡)=0.2222I(9,1)=-(1/9)*log2(1/9)+(8/9)*log2(8/9)=0.5032nGain(家庭所得)=0.50322022-2-1419Example(end)ID3算法分類規(guī)則：IF性別=Female AND家庭所得= 低所得THEN購買RV房車=否IF性別=Female AND家庭所得= 小康THEN購買RV房車=否IF性別=Female AND家庭所得= 高所得THEN購買RV房車=是IF性別=Male AND年齡35 THEN購買RV房車=否IF性別=

8、Male AND年齡35 THEN購買RV房車=是n資料nDecision Tree2022-2-1420（四）Decision Tree的建立過程1、決策樹的停止決策樹是通過遞歸分割(recursive partitioning)建立而成，遞歸分割是一種把數(shù)據(jù)分割成不同小的部分的迭代過程。 如果有以下情況發(fā)生，決策樹將停止分割：該群數(shù)據(jù)的每一筆數(shù)據(jù)都已經(jīng)歸類到同一類別。該群數(shù)據(jù)已經(jīng)沒有辦法再找到新的屬性來進(jìn)行節(jié)點(diǎn)分割。該群數(shù)據(jù)已經(jīng)沒有任何尚未處理的數(shù)據(jù)。2022-2-14212、決策樹的剪枝(pruning)決策樹學(xué)習(xí)可能遭遇模型過度擬合（over fitting）的問題，過度擬合是指模型過

9、度訓(xùn)練，導(dǎo)致模型記住的不是訓(xùn)練集的一般性，反而是訓(xùn)練集的局部特性。如何處理過度擬合呢？對(duì)決策樹進(jìn)行修剪。樹的修剪有幾種解決的方法，主要為先剪枝和后剪枝方法。2022-2-1422（1）先剪枝方法在先剪枝方法中，通過提前停止樹的構(gòu)造（例如，通過決定在給定的節(jié)點(diǎn)上不再分裂或劃分訓(xùn)練樣本的子集）而對(duì)樹“剪枝”。一旦停止，節(jié)點(diǎn)成為樹葉。確定閥值法：在構(gòu)造樹時(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)，如果不能，就被視作過度擬合而被修剪掉

10、，如果能夠再現(xiàn)，則該分岔予以保留而繼續(xù)向下分岔。2022-2-1423（2）后剪枝方法后剪枝方法是由“完全生長(zhǎng)”的樹剪去分枝。通過刪除節(jié)點(diǎn)的分枝，剪掉葉節(jié)點(diǎn)。案例數(shù)修剪是在產(chǎn)生完全生長(zhǎng)的樹后，根據(jù)最小案例數(shù)閥值，將案例數(shù)小于閥值的樹節(jié)點(diǎn)剪掉。成本復(fù)雜性修剪法是當(dāng)決策樹成長(zhǎng)完成后，演算法計(jì)算所有葉節(jié)點(diǎn)的總和錯(cuò)誤率，然后計(jì)算去除某一葉節(jié)點(diǎn)后的總和錯(cuò)誤率，當(dāng)去除該葉節(jié)點(diǎn)的錯(cuò)誤率降低或者不變時(shí)，則剪掉該節(jié)點(diǎn)。反之，保留。2022-2-1424應(yīng)用案例：在農(nóng)業(yè)中的應(yīng)用2022-2-1425第一步：屬性離散化2022-2-1426第二步：概化（泛化）2022-2-1427第三步：計(jì)算各屬性的期望信息=(1

11、7/30)*LOG(17/30),2)+(10/30)*LOG(10/30),2)+(3/30)*LOG(3/30),2)2022-2-1428計(jì)算各屬性的信息增益2022-2-1429第四步：決策樹2022-2-1430案例2：銀行違約率2022-2-14312022-2-1432案例3 對(duì)電信客戶的流失率分析數(shù)據(jù)倉庫條件屬性類別屬性客戶是否流失2022-2-1433案例4：在銀行中的應(yīng)用2022-2-1434案例5：個(gè)人信用評(píng)級(jí)個(gè)人信用評(píng)級(jí)決策樹2022-2-1435（五）其他算法C4.5與C5.0算法Gini Index算法CART算法PRISM算法CHAID算法2022-2-14361

12、、C4.5與C5.0算法C5.0算法則是C4.5算法的修訂版 ，適用在處理大數(shù)據(jù)集，采用Boosting（提升）方式提高模型準(zhǔn)確率，又稱為Boosting Trees，在軟件上的計(jì)算速度比較快，占用的內(nèi)存資源較少。類別屬性的信息熵2022-2-14372、Gini Index算法ID3 and PRISM適用于類別屬性的分類方法。Gini Index能數(shù)值型屬性的變量來做分類。著重解決當(dāng)訓(xùn)練集數(shù)據(jù)量巨大，無法全部放人內(nèi)存時(shí)，如何高速準(zhǔn)確地生成更快的，更小的決策樹。2022-2-1438集合T包含N個(gè)類別的記錄，那么其Gini指標(biāo)就是如果集合T分成兩部分N1 和 N2。則此分割的Gini就是提供最小Gini split就被選擇作為分割的標(biāo)準(zhǔn)(對(duì)于每個(gè)屬性都要經(jīng)過所有可以的分割方法)。Gini Index算法2( ) 11jNgini Tpjpjj 為類別出現(xiàn)的頻率)()()(2211TginiNNTginiNNTginisplit2022-2-1439案例：在汽車銷售中的應(yīng)用2022-2-14402022-2-1441NNYYYNYYYNNN20