決策樹很詳細的算法介紹-課件

決策樹(DecisionTree)2023/7/311決策樹(DecisionTree)2023/7/2511、分類的意義數(shù)據(jù)庫了解類別屬性與特征預測分類模型—決策樹分類模型—聚類一、分類(Classification)2023/7/3121、分類的意義數(shù)據(jù)庫了解類別屬性與特征預測分類模型—分類模型數(shù)據(jù)庫分類標記性別年齡婚姻否是否是FemaleMale<35≧35未婚已婚2、分類的技術（1）決策樹2023/7/313數(shù)據(jù)庫分類標記性別年齡婚姻否是否是FemaleMale<35（2）聚類2023/7/314（2）聚類2023/7/2543、分類的程序模型建立(ModelBuilding)模型評估(ModelEvaluation)使用模型(UseModel)2023/7/3153、分類的程序模型建立(ModelBuilding)202決策樹分類的步驟數(shù)據(jù)庫訓練樣本(trainingsamples)建立模型測試樣本(testingsamples)評估模型2023/7/316決策樹分類的步驟數(shù)據(jù)庫訓練樣本(trainingsampl例：資料訓練樣本婚姻年齡

家庭

所得否是否是未婚已婚<35≧35低高否小康1.建立模型測試樣本2.模型評估錯誤率為66.67%修改模型3.使用模型2023/7/317例：資料訓練樣本婚姻年齡家庭

所得否是否是未婚已婚<354、分類算法的評估預測的準確度：指模型正確地預測新的或先前未見過的數(shù)據(jù)的類標號的能力。訓練測試法(training-and-testing)交叉驗證法(cross-validation)例如，十折交叉驗證。即是將數(shù)據(jù)集分成十分，輪流將其中9份做訓練1份做測試，10次的結果的均值作為對算法精度的估計，一般還需要進行多次10倍交叉驗證求均值，例如10次10倍交叉驗證，更精確一點。2023/7/3184、分類算法的評估預測的準確度：指模型正確地預測新的或先前未速度：指產(chǎn)生和使用模型的計算花費。建模的速度、預測的速度強壯性：指給定噪聲數(shù)據(jù)或具有缺失值的數(shù)據(jù)，模型正確預測的能力?？稍忈屝裕褐改Ｐ偷慕忉屇芰?。2023/7/319速度：指產(chǎn)生和使用模型的計算花費。2023/7/259決策樹歸納的基本算法是貪心算法，它以自頂向下遞歸各個擊破的方式構造決策樹。貪心算法：在每一步選擇中都采取在當前狀態(tài)下最好/優(yōu)的選擇。在其生成過程中，分割方法即屬性選擇度量是關鍵。通過屬性選擇度量，選擇出最好的將樣本分類的屬性。根據(jù)分割方法的不同，決策樹可以分為兩類：基于信息論的方法（較有代表性的是ID3、C4.5算法等）和最小GINI指標方法（常用的有CART、SLIQ及SPRINT算法等）。二、決策樹(DecisionTree)2023/7/3110決策樹歸納的基本算法是貪心算法，它以自頂向下遞歸各個擊破的方

（一）決策樹的結構根部節(jié)點(rootnode)中間節(jié)點(non-leafnode)(代表測試的條件)分支(branches)(代表測試的結果)葉節(jié)點(leafnode)(代表分類后所獲得的分類標記)2023/7/3111

（一）決策樹的結構根部節(jié)點(rootnode)中間節(jié)點(（二）決策樹的形成2023/7/3112（二）決策樹的形成2023/7/2512例：根部節(jié)點中間節(jié)點停止分支？2023/7/3113例：根部節(jié)點？2023/7/2513（三）ID3算法(C4.5,C5.0)Quinlan(1979)提出，以Shannon(1949)的信息論為依據(jù)。ID3算法的屬性選擇度量就是使用信息增益，選擇最高信息增益的屬性作為當前節(jié)點的測試屬性。信息論：若一事件有k種結果，對應的概率為Pi。則此事件發(fā)生后所得到的信息量I(視為Entropy)為：

I=-(p1*log2(p1)+p2*log2(p2)+…+pk*log2(pk))2023/7/3114（三）ID3算法(C4.5,C5.0)Quinlan(197Example1：設k=4p1=0.25,p2=0.25,p3=0.25,p4=0.25

I=-(.25*log2(.25)*4)=2Example2：設k=4p1=0,p2=0.5,p3=0,p4=0.5

I=-(.5*log2(.5)*2)=1Example3：設k=4p1=1,p2=0,p3=0,p4=0

I=-(1*log2(1))=02023/7/3115Example1：2023/7/2515信息增益2023/7/3116信息增益2023/7/2516Example(Gain)n=16n1=4 I(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:作為第一個分類依據(jù)Gain(性別)=0.0972Gain(家庭所得)=0.01772023/7/3117Example(Gain)n=16I(16,4)=－((Example(續(xù))Gain(家庭所得)=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/7/3118Example(續(xù))Gain(家庭所得)=0.688I(7,Example(end)ID3算法分類規(guī)則：IF性別=FemaleAND家庭所得=

低所得THEN購買RV房車=否IF性別=FemaleAND家庭所得=

小康THEN購買RV房車=否IF性別=FemaleAND家庭所得=

高所得THEN購買RV房車=是IF性別=MaleAND年齡<35

THEN購買RV房車=否IF性別=MaleAND年齡≧35

THEN購買RV房車=是資料DecisionTree2023/7/3119Example(end)ID3算法分類規(guī)則：資料Decisi（四）DecisionTree的建立過程1、決策樹的停止決策樹是通過遞歸分割(recursivepartitioning)建立而成，遞歸分割是一種把數(shù)據(jù)分割成不同小的部分的迭代過程。

如果有以下情況發(fā)生，決策樹將停止分割：該群數(shù)據(jù)的每一筆數(shù)據(jù)都已經(jīng)歸類到同一類別。該群數(shù)據(jù)已經(jīng)沒有辦法再找到新的屬性來進行節(jié)點分割。該群數(shù)據(jù)已經(jīng)沒有任何尚未處理的數(shù)據(jù)。2023/7/3120（四）DecisionTree的建立過程1、決策樹的停止22、決策樹的剪枝(pruning)決策樹學習可能遭遇模型過度擬合（overfitting）的問題，過度擬合是指模型過度訓練，導致模型記住的不是訓練集的一般性，反而是訓練集的局部特性。如何處理過度擬合呢？對決策樹進行修剪。樹的修剪有幾種解決的方法，主要為先剪枝和后剪枝方法。2023/7/31212、決策樹的剪枝(pruning)決策樹學習可能遭遇模型過度（1）先剪枝方法在先剪枝方法中，通過提前停止樹的構造（例如，通過決定在給定的節(jié)點上不再分裂或劃分訓練樣本的子集）而對樹“剪枝”。一旦停止，節(jié)點成為樹葉。確定閥值法：在構造樹時，可將信息增益用于評估岔的優(yōu)良性。如果在一個節(jié)點劃分樣本將導致低于預定義閥值的分裂，則給定子集的進一步劃分將停止。測試組修剪法：在使用訓練組樣本產(chǎn)生新的分岔時，就立刻使用測試組樣本去測試這個分岔規(guī)則是否能夠再現(xiàn)，如果不能，就被視作過度擬合而被修剪掉，如果能夠再現(xiàn)，則該分岔予以保留而繼續(xù)向下分岔。2023/7/3122（1）先剪枝方法在先剪枝方法中，通過提前停止樹的構造（例如，（2）后剪枝方法后剪枝方法是由“完全生長”的樹剪去分枝。通過刪除節(jié)點的分枝，剪掉葉節(jié)點。案例數(shù)修剪是在產(chǎn)生完全生長的樹后，根據(jù)最小案例數(shù)閥值，將案例數(shù)小于閥值的樹節(jié)點剪掉。成本復雜性修剪法是當決策樹成長完成后，演算法計算所有葉節(jié)點的總和錯誤率，然后計算去除某一葉節(jié)點后的總和錯誤率，當去除該葉節(jié)點的錯誤率降低或者不變時，則剪掉該節(jié)點。反之，保留。2023/7/3123（2）后剪枝方法后剪枝方法是由“完全生長”的樹剪去分枝。通過應用案例：在農(nóng)業(yè)中的應用2023/7/3124應用案例：在農(nóng)業(yè)中的應用2023/7/2524第一步：屬性離散化2023/7/3125第一步：屬性離散化2023/7/2525第二步：概化（泛化）2023/7/3126第二步：概化（泛化）2023/7/2526第三步：計算各屬性的期望信息=(17/30)*LOG((17/30),2)+(10/30)*LOG((10/30),2)+(3/30)*LOG((3/30),2)2023/7/3127第三步：計算各屬性的期望信息=(17/30)*LOG((17計算各屬性的信息增益2023/7/3128計算各屬性的信息增益2023/7/2528第四步：決策樹2023/7/3129第四步：決策樹2023/7/2529案例2：銀行違約率2023/7/3130案例2：銀行違約率2023/7/25302023/7/31312023/7/2531案例3對電信客戶的流失率分析數(shù)據(jù)倉庫條件屬性類別屬性客戶是否流失2023/7/3132案例3對電信客戶的流失率分析數(shù)據(jù)倉庫條件屬性類別屬性客戶案例4：在銀行中的應用2023/7/3133案例4：在銀行中的應用2023/7/2533案例5：個人信用評級個人信用評級決策樹2023/7/3134案例5：個人信用評級個人信用評級決策樹2023/7/2534（五）其他算法C4.5與C5.0算法GiniIndex算法CART算法PRISM算法CHAID算法2023/7/3135（五）其他算法C4.5與C5.0算法2023/7/25351、C4.5與C5.0算法C5.0算法則是C4.5算法的修訂版，適用在處理大數(shù)據(jù)集，采用Boosting（提升）方式提高模型準確率，又稱為BoostingTrees，在軟件上的計算速度比較快，占用的內存資源較少。類別屬性的信息熵2023/7/31361、C4.5與C5.0算法C5.0算法則是C4.5算法的修訂2、GiniIndex算法ID3andPRISM適用于類別屬性的分類方法。GiniIndex能數(shù)值型屬性的變量來做分類。著重解決當訓練集數(shù)據(jù)量巨大，無法全部放人內存時，如何高速準確地生成更快的，更小的決策樹。2023/7/31372、GiniIndex算法ID3andPRISM適用于集合T包含N個類別的記錄，那么其Gini指標就是

如果集合T分成兩部分N1和N2。則此分割的Gini就是提供最小Ginisplit就被選擇作為分割的標準(對于每個屬性都要經(jīng)過所有可以的分割方法)。GiniIndex算法2023/7/3138集合T包含N個類別的記錄，那么其Gini指標就是GiniI案例：在汽車銷售中的應用2023/7/3139案例：在汽車銷售中的應用2023/7/25392023/7/31402023/7/2540NNYYYNYYYNNN2023/7/3141NNYYYNYYYNNN2