分類挖掘：決策樹ppt課件

1、分類發(fā)掘：決策樹 2022/7/15.決策樹算法概述決策樹算法最早源于人工智能的機器學(xué)習(xí)技術(shù)，用以實現(xiàn)數(shù)據(jù)內(nèi)在規(guī)律的探求和新數(shù)據(jù)對象的分類預(yù)測。決策樹算法屬于有指點的學(xué)習(xí)。根結(jié)點葉結(jié)點內(nèi)部結(jié)點兄弟結(jié)點2叉樹多叉樹.分類預(yù)測分類預(yù)測，就是經(jīng)過向現(xiàn)有數(shù)據(jù)學(xué)習(xí)，使模型具備對未來新數(shù)據(jù)的分類預(yù)測才干。數(shù)據(jù)包含：輸入變量輸出變量分類和預(yù)測分類：分類型輸出變量預(yù)測：數(shù)值型輸出變量.決策樹算法概述決策樹的種類：分類決策樹：樹葉結(jié)點所含樣本的輸出變量的眾數(shù)就是分類結(jié)果?；貧w決策樹：樹葉結(jié)點所含樣本的輸出變量的平均值就是預(yù)測結(jié)果。利用決策樹進展分類預(yù)測：對新數(shù)據(jù)進展分類預(yù)測時，只需按照決策樹的層次，從根結(jié)點開場

2、依次對新數(shù)據(jù)輸入變量值進展判別并進入不同的決策樹分支，直至葉結(jié)點為止 。特點：分類預(yù)測是基于邏輯的 。IF THEN每個葉節(jié)點對應(yīng)一條推理規(guī)那么.1 建立決策樹，利用訓(xùn)練樣本生成決策樹模型。 開場，數(shù)據(jù)都在根節(jié)點遞歸的進展數(shù)據(jù)分片2 修剪決策樹 去掉一些能夠是噪音或者異常的數(shù)據(jù)3 運用決策樹對未知數(shù)據(jù)進展分類 按照決策樹上采用的分割屬性逐層往下，直 到一個葉子節(jié)點運用決策樹進展分類斷定樹分類算法output訓(xùn)練集決策樹input2022/7/15.決策樹的中心問題第一，決策樹的生長，即利用訓(xùn)練樣本集完成決策樹的建立過程；1.如何從眾多的輸入變量中選擇一個當(dāng)前最正確的分組變量；2.如何從分組變量

3、的眾多取值中找到一個最正確的分割點 。.決策樹的中心問題第二，決策樹的修剪，即利用檢驗樣本集對構(gòu)成的決策樹進展優(yōu)化處。過度擬和Overfitting預(yù)修剪pre-pruning、后修剪post-pruning .訓(xùn)練集(Train)：數(shù)據(jù)庫中為建立模型而被分析的數(shù)據(jù)元組構(gòu)成訓(xùn)練集。訓(xùn)練集中的單個元組稱為訓(xùn)練樣本,每個訓(xùn)練樣本有一個類別標(biāo)志。一個詳細樣本的方式可為:( v1, v2, ., vn; c );其中vi表示屬性值,c表示類別。測試集(Test)：用于模型參數(shù)的估計，評價分類模型的準(zhǔn)確率。 驗證集(Validation):用于模型誤差的估計。訓(xùn)練集與測試集2022/7/15.a.模型訓(xùn)

4、練階段 訓(xùn)練集b.運用模型 分類階段評價準(zhǔn)確率測試集對類標(biāo)號未知的新數(shù)據(jù)分類 分類的兩個階段2022/7/15.根本算法自上而下分而治之的方法開場時，一切的數(shù)據(jù)都在根節(jié)點一切記錄用所選屬性遞歸的進展分割屬性的選擇是基于一個啟發(fā)式規(guī)那么或者一個統(tǒng)計的度量 (如, information gain)停頓分割的條件一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別沒有屬性可以再用于對數(shù)據(jù)進展分割2022/7/15.建樹階段MakeTree (Training Data T) Partition (T);Partition (Data S) if (all points in S are in the same cl

5、ass) then return; evaluate splits for each attribute A Use best split found to partition S into S1 and S2; Partition (S1); Partition (S2);2022/7/15.屬性選擇度量規(guī)范分支目的信息增益Information gain ID3增益比率Gain rationC4.5,C5.0基尼指數(shù)Gini index (SLIQ，SPRINT) 2022/7/15. 1、信息是用來消除隨機不確定性的度量。信息量的大小可由所消除的不確定性大小來計量。信息量的數(shù)學(xué)定義：2、

6、信息熵是信息量的數(shù)學(xué)期望，是信源發(fā)出信息前的平均不確定性，也稱先驗熵，信息熵的數(shù)學(xué)定義為：信息論的根本概念.1、信源熵H(X)信源熵是度量整個信源X整體的平均不確定性，也稱先驗熵。 2、條件熵H(X/Y)條件熵是一個確定值，表示收信者在收到Y(jié)后，信源X依然存在的不確定度，也稱為后驗熵。 3、互信息量熵差H(X)H(X/Y)是不確定性的消除，即互信息才是接納端所獲得的信息量。 信息論的根本概念 2022/7/15. ID3算法是借用信息論中的互信息尋覓訓(xùn)練集具有最大信息量的屬性字段，建立決策樹的一個節(jié)點，再根據(jù)該屬性字段的不同取值建立樹的分支;在每個分支子集中反復(fù)建立樹的下層節(jié)點和分支過程。 I

7、D3算法2022/7/15. ID3算法2022/7/15.ID3Tree (T，T-attributelist)T為樣本空間，T-attributelist為屬性集。(1) 創(chuàng)建根結(jié)點N。(2) IF T都屬于同一類C，那么前往N為葉結(jié)點，標(biāo)志為類C。(3) IF T-attributelist為空或T中所剩的樣本數(shù)少于某給定值，那么前往N為葉結(jié)點，標(biāo)志為T中出現(xiàn)最多的類。(4)FOR EACH T-attributelist中的屬性，計算信息增益information gain。(5) 結(jié)點N的分裂屬性為T-attributelist中具有最高信息增益的屬性。(6)FOR EACH由結(jié)點N

8、長出的新結(jié)點IF 該結(jié)點對應(yīng)的樣本子集只需獨一的一種決策類別，那么將該結(jié)點標(biāo)志為該類別的葉結(jié)點;ELSE在該結(jié)點上執(zhí)行ID3Tree (T，T-attributelist)，對它繼續(xù)進展分裂;其中，T為由結(jié)點N劃分而來的子集，T-attributeslit為去除被選分裂屬性后的屬性集。 2.ID3算法描畫2022/7/15. 用決策樹調(diào)查某顧客能否會購買PC年 齡收 入是否學(xué)生信 用購買PC=30高否中否40中否中是40低是中是40低是優(yōu)否3140低是優(yōu)是=30中否中否40中是中是40中否優(yōu)否顧客數(shù)據(jù)表2022/7/15. 類標(biāo)號屬性為購買PC，它有兩個不同的值(“是、“否)，即有兩個不同的類

9、，m=2；設(shè)p對應(yīng)“是，n對應(yīng)“否，那么p=9，n=5。1) 創(chuàng)建根結(jié)點先計算對給定樣本分類所需的期望信息。 = 0.94下面計算每個屬性的熵。從年齡開場計算。年齡=“40： p13=3，n13=2 I (p13，n13)=0.971假設(shè)樣本按年齡劃分，對一個給定的樣本分類所需的期望信息如下 =0.694 因此，這種劃分的信息增益是：Gain(年齡)= I(P，N) - E(年齡)=0.246。同理可得Gain(收入)=0.029 Gain(能否學(xué)生)=0.151 Gain(信譽)=0.048 在一切的屬性中，年齡的信息增益最高，被選作測試屬性。創(chuàng)建一個根結(jié)點，用年齡標(biāo)志，并對每個屬性值引出一

10、個分支。2022/7/15.2) 分支建立思索分支“年齡=30的結(jié)點。由于Gain(收入)= 0.571Gain(學(xué)生)=0.971 Gain(信譽)= 0.02所以分支“年齡=40的結(jié)點。由于Gain (收入)= 0.02Gain(學(xué)生)= 0.02Gain(信譽)= 0.971所以分支“年齡=40結(jié)點的測試屬性為“信譽。思索分支“學(xué)生=否的結(jié)點，由于一切記錄屬于同一類別“否，所以分支“學(xué)生=否的結(jié)點為葉結(jié)點。思索分支“學(xué)生=是的結(jié)點，由于一切記錄屬于同一類別“是，所以分支“學(xué)生=是的結(jié)點為葉結(jié)點。思索分支“信譽=優(yōu)的結(jié)點，由于一切記錄屬于同一類別“否，所以分支“信譽=否的結(jié)點為葉結(jié)點。思索

11、分支“信譽=中的結(jié)點，由于一切記錄屬于同一類別“是，所以分支“信譽=是的結(jié)點為葉結(jié)點。2022/7/15.建立的決策樹：2022/7/15.2022/7/15.C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)來選擇屬性。抑制偏向選擇取值較多屬性的缺陷用閾值對屬性劃分，即把訓(xùn)練集中該屬性的一切值劃分到不同的區(qū)間中。用最常見值替代未知值規(guī)那么存于二維數(shù)組中如： 視為youth; 視為middle_aged; 視為senior.themegalleryLOGO1、增益率Why？信息增益度量偏向于有許多輸出的測試，即它傾向于選擇具有大量值的屬性。舉個極端的例子：思索充任

12、獨一標(biāo)識的屬性PID。對PID的分裂將產(chǎn)生大量劃分與樣本個數(shù)一樣多，每個分類只包含一個樣本，且每個劃分都是純的。對屬性PID劃分得到的信息增益最大，顯然，這種劃分對分類沒有用途。.themegalleryLOGO 運用分裂信息(split information)將信息增益規(guī)范化。該值表示數(shù)據(jù)集 按屬性 測試的 個劃分產(chǎn)生的信息。 增益率：選擇具有最大信息率的屬性作為分裂屬性。.增益率income其他屬性的信息率可類似求出。.在實踐通訊之前決策樹建立之前，輸出變量對信宿來講是完全隨機的，其平均不確定性為：決策樹建立過程中，隨著信宿接納到信息輸入變量如T1，那么條件熵為：信息增益：T1作為最正確

13、分組變量而非T3將輸出變量能否購買看作信源發(fā)出的信息U輸入變量看作是信宿接納到的一系列信息V.類別值多的輸入變量比少的有更多的時機成為當(dāng)前最正確分組變量C5.0算法:信息增益率信息增益率的數(shù)學(xué)定義為：.數(shù)值型輸入變量首先對它進展分組處置，分組方法采用基于MDLP的熵分組方法2、C5.0算法：數(shù)值型輸入變量.把延續(xù)值屬性的值域分割為離散的區(qū)間集合?；贛DLP的熵分組方法。Minimun DescriptionLength Principle信息增益大于編碼長度合并延續(xù)值屬性2022/7/15.選擇最正確分組變量時，通常將帶有缺失值的樣本當(dāng)暫時剔除樣本對待，并進展權(quán)數(shù)調(diào)整 3、C5.0算法:對缺

14、失值問題的處置計算輸出變量熵計算關(guān)于T1的條件熵 計算經(jīng)權(quán)數(shù)調(diào)整的T1信息增益 計算信息增益率 .不繼續(xù)確定關(guān)于分組變量的最正確分割點分類型輸入變量：K叉樹數(shù)值型輸入變量：2叉樹Clementine：ChiMerge分箱法在分組變量上取缺失值：第1個樣本被分配到各組中的權(quán)數(shù)分別為5/13、3/13、5/13，之后各組的樣本數(shù)分別為55/13、33/13、55/13 4、C5.0算法:最正確分割點.后修剪方法從葉結(jié)點向上逐層剪枝，關(guān)鍵是錯誤率即誤差的估計問題通常應(yīng)在檢驗樣本集上估計誤差并進展剪枝利用統(tǒng)計中置信度的思想直接在訓(xùn)練樣本集中估計誤差：當(dāng)為0.25時，5、C5.0算法：剪枝.按照“減少誤

15、差reduce-error法判別能否剪枝C5.0算法：剪枝思索能否可以剪掉最下層的3個葉結(jié)點3個結(jié)點的錯誤率：分別為：0.55、0.91、0.55；加權(quán)：計算父結(jié)點C的誤差估計為0.50。由于0.60大于0.50，因此可以剪掉3個葉結(jié)點。.預(yù)測的置信度或誤差會影響決策，錯判的損失也會影響決策損失矩陣：6、C5.0算法：損失矩陣預(yù)測值YesNo實際值Yes0mNon0.從損失角度決策，在各類錯判損失不相等時不能僅從置信角度判別?，F(xiàn)實上，默許在損失一樣時才思索置信度： c(i|j)是將j類錯判為i類的損失，p(j|t)是被節(jié)點t判為j類的歸一化概率C5.0算法：損失矩陣.C5.0僅在剪枝時思索損失

16、，以二分類為例：C5.0算法：損失矩陣?yán)纾喝螕p失較大，給出yes判別的置信度都很高。模型復(fù)雜，決策樹修剪程度低；假設(shè)取偽損失指定為10，那么模型都判為No.偏向和方差決策樹算法具有一定的不穩(wěn)健性，可以思索利用多組樣本建立多個模型，構(gòu)成模型“委員會制度Bagging技術(shù)Boosting技術(shù)C5.0算法： 模型“委員會.建模過程輸入：訓(xùn)練樣本集T，訓(xùn)練次數(shù)k；輸出：多個決策樹模型C1,C2,Ck)For i=1,2,k do 從T中隨機有放回抽取樣本，構(gòu)成有一樣樣本容量的樣本集合Ti 以Ti為訓(xùn)練集構(gòu)造模型CiEnd for決策過程輸入：新數(shù)據(jù)X，多個決策樹模型C1,C2,Ck；輸出：分類預(yù)測

17、結(jié)果C(X) For i=1,2,k do 根據(jù)Ci對X做預(yù)測，結(jié)果為Ci(X)End for統(tǒng)計各類別得票，得票數(shù)最高的為C(X)，或計算平均值 C5.0算法： Bagging技術(shù).兩個階段：建立k個模型； k個模型投票C5.0算法：Boosting技術(shù).Boosting技術(shù)：建模過程初試化樣本權(quán)數(shù)：wj(i)=1/n對每次迭代：根據(jù)樣本權(quán)數(shù)wj(i)，從T中有放回地抽取n個樣本構(gòu)成訓(xùn)練樣本集Ti；根據(jù)訓(xùn)練集Ti得到模型Ci；計算模型的誤差e(i) 假設(shè)e(i)0.5 或者e(i)=0，那么終止建模過程；C5.0算法：Boosting技術(shù).Boosting技術(shù)：建模過程初試化樣本權(quán)數(shù)：wj(

18、i)=1/n對每次迭代：根據(jù)誤差更新每個樣本的權(quán)數(shù)：正確分類的樣本權(quán)數(shù)：wj(i+1)= wj(i)*(i)，(i)e(i)/(1- e(i)；錯誤分類的樣本權(quán)數(shù)堅持不變：wj(i+1)= wj(i)；調(diào)整wj(i+1)使得各樣本的權(quán)重之和等于1經(jīng)過k次迭代，將得到k個模型和k個誤差C5.0算法：Boosting技術(shù).Boosting技術(shù)：投票過程決策過程采用加權(quán)投票，給不同的模型賦予不同的權(quán)數(shù)，權(quán)數(shù)與模型的誤差成反比，詳細為：對新樣本X，每個模型Ci都給出預(yù)測值Ci(X)，給預(yù)測類Ci(X)加權(quán)：求各類權(quán)數(shù)的總和，總權(quán)數(shù)最高的類即為最終的分類結(jié)果Bagging與Boosting技術(shù)的比較Bo

19、osting例如C5.0算法：Boosting技術(shù).交叉驗證：對于n折交叉驗證，那么在訓(xùn)練樣本集合中重抽樣n組樣本建立n個模型，并計算每個模型訓(xùn)練樣本集上的預(yù)測精度，且給出n個模型預(yù)測精度的平均值和規(guī)范差未剪枝的決策樹Pruning severity中輸入置信度。默以為100%25%。值越大樹越精簡，預(yù)測精度會不理想誤差較高；需求反復(fù)嘗試 C5.0算法：其他.C5.0算法：推理規(guī)那么直接從決策樹得到推理規(guī)那么很容易決策樹對邏輯關(guān)系的表述不是最簡約的abccddyesnoyesnoyesnonoyyyyyynnnnnnIF a AND b THEN yesIF c AND d THEN yesO

20、THERWISE no.生成推理規(guī)那么的普通算法是PRISM(Patient Rule Induction Space Method )算法，Cendrowska于1987年提出.是一種“覆蓋算法,所生成的規(guī)那么在訓(xùn)練樣本集上是100正確的 確定期望類別:yes年齡段=A(2/5)，年齡段=B(4/4)，年齡段=C(3/5)，性別=0(6/8)，性別=1(3/6)IF 年齡段=B THEN 能否購買=yes 規(guī)那么100正確，更新數(shù)據(jù)集：.規(guī)那么100正確，更新數(shù)據(jù)集年齡段=A(2/5)，年齡段=C(3/5)，性別=0(4/6)，性別=1(1/4) IF 性別=0 THEN 能否購買=yes

21、年齡段=A(1/3),年齡段=C(3/3)IF 性別=0 AND 年齡段=C THEN 能否購買=yes .年齡段=A(2/5)，年齡段=C(0/2)，性別=0(1/3)，性別=1(1/4) IF 年齡段=A THEN 能否購買=yes 性別=0(1/3)，性別=1(1/2) IF 年齡段=A AND 性別=1 THEN 能否購買=yes(略去).C5.0算法：推理規(guī)那么利用規(guī)那么集合對樣本進展分類能夠產(chǎn)生的問題：樣本能夠符合多個分類結(jié)果一樣的規(guī)那么樣本能夠符合多個分類結(jié)果不一樣的規(guī)那么樣本不符合任何規(guī)那么例如：推理規(guī)那么的預(yù)測置信度是普拉斯估計器調(diào)整后的結(jié)果 .模型評價Analysis結(jié)點對比模型在訓(xùn)練樣本集和檢驗樣本集上的性能差別對比不同模型的性能確定相對合理的置信程度折：假設(shè)總體的正確率為90%，錯誤率為10%，那么2折表示10%的一半，即錯誤率下降一半2折，3折為33%。假設(shè)改良2折，那么總體正確率為95%，C5.0算法：模型的評價.2022/7/15R中的實現(xiàn)R中決策樹的實現(xiàn)，主要用到四個軟件包：1、rpart:用于建立二分類樹及相關(guān)遞歸劃分算法的實現(xiàn)；2、rpart.plot：公用來對rpart模型繪制決策樹；3、maptree：用來修剪、繪制不僅僅局限于rpart模型的樹型構(gòu)造圖；4、Rweka：提供了R與Weka的銜接，Wek