決策樹算法概述決策樹算法最早源于人工智能的機器學習技術，用以實現數據內在規律的探究和新數據對象的分類預測。決策樹算法屬于有指導的學習。根結點葉結點內部結點兄弟結點2叉樹多叉樹決策樹算法概述決策樹算法最早源于人工智能的機器學習技術，用以1分類預測分類預測，就是通過向現有數據學習，使模型具備對未來新數據的分類預測能力。數據包含：輸入變量輸出變量分類和預測分類：分類型輸出變量預測：數值型輸出變量分類預測分類預測，就是通過向現有數據學習，使模型具備對未來新2決策樹算法概述決策樹的種類：分類決策樹：樹葉結點所含樣本的輸出變量的眾數就是分類結果。回歸決策樹：樹葉結點所含樣本的輸出變量的平均值就是預測結果。利用決策樹進行分類預測：對新數據進行分類預測時，只需按照決策樹的層次，從根結點開始依次對新數據輸入變量值進行判斷并進入不同的決策樹分支，直至葉結點為止。特點：分類預測是基于邏輯的。IFTHEN每個葉節點對應一條推理規則決策樹算法概述決策樹的種類：31建立決策樹，利用訓練樣本生成決策樹模型。

開始，數據都在根節點遞歸的進行數據分片2修剪決策樹

去掉一些可能是噪音或者異常的數據3使用決策樹對未知數據進行分類

按照決策樹上采用的分割屬性逐層往下，直到一個葉子節點使用決策樹進行分類判定樹分類算法output訓練集決策樹input2022/11/221建立決策樹，利用訓練樣本生成決策樹模型。使用決策樹進4決策樹的核心問題第一，決策樹的生長，即利用訓練樣本集完成決策樹的建立過程；1.如何從眾多的輸入變量中選擇一個當前最佳的分組變量；2.如何從分組變量的眾多取值中找到一個最佳的分割點。決策樹的核心問題第一，決策樹的生長，即利用訓練樣本集完成決策5決策樹的核心問題第二，決策樹的修剪，即利用檢驗樣本集對形成的決策樹進行優化處。過度擬和（Overfitting）預修剪（pre-pruning）、后修剪（post-pruning）決策樹的核心問題第二，決策樹的修剪，即利用檢驗樣本集對形成的6訓練集(Train)：數據庫中為建立模型而被分析的數據元組形成訓練集。訓練集中的單個元組稱為訓練樣本,每個訓練樣本有一個類別標記。一個具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測試集(Test)：用于模型參數的估計，評估分類模型的準確率。

驗證集(Validation):用于模型誤差的估計。訓練集與測試集2022/11/22訓練集(Train)：數據庫中為建立模型而被分析的數據元組形7a.模型訓練階段

訓練集b.使用模型分類階段評估準確率（測試集）對類標號未知的新數據分類

分類的兩個階段2022/11/22a.模型訓練階段分類的兩個階段2022/11/218基本算法自上而下分而治之的方法開始時，所有的數據都在根節點所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發式規則或者一個統計的度量(如,informationgain)停止分割的條件一個節點上的數據都是屬于同一個類別沒有屬性可以再用于對數據進行分割2022/11/22基本算法2022/11/219建樹階段MakeTree(TrainingDataT)

Partition(T);

Partition(DataS)

if(allpointsinSareinthesameclass)thenreturn;

evaluatesplitsforeachattributeA

UsebestsplitfoundtopartitionSintoS1andS2;

Partition(S1);

Partition(S2);2022/11/222022/11/2110屬性選擇度量標準－－分支指標信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5,C5.0）基尼指數——Giniindex

(SLIQ，SPRINT)

…………2022/11/22屬性選擇度量標準－－分支指標信息增益——Informatio11

1、信息是用來消除隨機不確定性的度量。信息量的大小可由所消除的不確定性大小來計量。信息量的數學定義：2、信息熵是信息量的數學期望，是信源發出信息前的平均不確定性，也稱先驗熵，信息熵的數學定義為：信息論的基本概念1、信息是用來消除隨機不確定性的度量。信息量的大小可由121、信源熵H(X)信源熵是度量整個信源X整體的平均不確定性，也稱先驗熵。2、條件熵H(X/Y)條件熵是一個確定值，表示收信者在收到Y后，信源X仍然存在的不確定度，也稱為后驗熵。3、互信息量熵差H(X)－H(X/Y)是不確定性的消除，即互信息才是接收端所獲得的信息量。信息論的基本概念

2022/11/221、信源熵H(X)信息論的基本概念

2022/11/2113

ID3算法是借用信息論中的互信息尋找訓練集具有最大信息量的屬性字段，建立決策樹的一個節點，再根據該屬性字段的不同取值建立樹的分支;在每個分支子集中重復建立樹的下層節點和分支過程。

ID3算法2022/11/22ID3算法是借用信息論中的互信息尋找訓練集具有最大14

ID3算法2022/11/22

ID3算法2022/11/2115ID3Tree(T，T-attributelist)T為樣本空間，T-attributelist為屬性集。(1)創建根結點N。(2)IFT都屬于同一類C，則返回N為葉結點，標記為類C。(3)IFT-attributelist為空或T中所剩的樣本數少于某給定值，則返回N為葉結點，標記為T中出現最多的類。(4)

FOREACHT-attributelist中的屬性，計算信息增益informationgain。(5)結點N的分裂屬性為T-attributelist中具有最高信息增益的屬性。(6)

FOREACH由結點N長出的新結點{IF該結點對應的樣本子集只有唯一的一種決策類別，則將該結點標記為該類別的葉結點;ELSE在該結點上執行ID3Tree(T’，T’-attributelist)，對它繼續進行分裂;}其中，T’為由結點N劃分而來的子集，T’-attributeslit為去除被選分裂屬性后的屬性集。2.ID3算法描述2022/11/22ID3Tree(T，T-attributelist)2.I16

用決策樹考察某顧客是否會購買PC年齡收入是否學生信用購買PC<=30高否中否<=30高否優否31~40高否中是>40中否中是>40低是中是>40低是優否31~40低是優是<=30中否中否<=30低是中是>40中是中是<=30中是優是31~40中否優是31~40高是中是>40中否優否顧客數據表2022/11/22用決策樹考察某顧客是否會購買PC年齡收入是17

類標號屬性為購買PC，它有兩個不同的值(“是”、“否”)，即有兩個不同的類，m=2；設p對應“是”，n對應“否”，則p=9，n=5。1)創建根結點先計算對給定樣本分類所需的期望信息。

=0.94下面計算每個屬性的熵。從年齡開始計算。年齡=“<=30”： p11=2，n11=3I(p11，n11)=0.971年齡=“30~40”： p12=4，n12=0I(p12，n12)=0年齡=“>40”： p13=3，n13=2I(p13，n13)=0.971如果樣本按年齡劃分，對一個給定的樣本分類所需的期望信息如下

=0.694因此，這種劃分的信息增益是：Gain(年齡)=I(P，N)-E(年齡)=0.246。同理可得Gain(收入)=0.029Gain(是否學生)=0.151Gain(信用)=0.048

在所有的屬性中，年齡的信息增益最高，被選作測試屬性。創建一個根結點，用年齡標記，并對每個屬性值引出一個分支。2022/11/22類標號屬性為購買PC，它有兩個不同的值(“是182)分支建立考慮分支“年齡=‘<=30’”的結點。因為Gain(收入)=0.571Gain(學生)=0.971Gain(信用)=0.02所以分支“年齡=‘<=30’”結點的測試屬性為“學生”。考慮分支“年齡=31~40”的結點，由于所有記錄屬于同一類別“是”，所以分支“年齡=‘31~40’”的結點為葉結點。考慮分支“年齡=‘>40’”的結點。因為Gain(收入)=0.02Gain(學生)=0.02Gain(信用)=0.971所以分支“年齡=‘>40’”結點的測試屬性為“信用”。考慮分支“學生=‘否’”的結點，由于所有記錄屬于同一類別“否”，所以分支“學生=‘否’”的結點為葉結點。考慮分支“學生=‘是’”的結點，由于所有記錄屬于同一類別“是”，所以分支“學生=‘是’”的結點為葉結點。考慮分支“信用=‘優’”的結點，由于所有記錄屬于同一類別“否”，所以分支“信用=‘否’”的結點為葉結點。考慮分支“信用=‘中’”的結點，由于所有記錄屬于同一類別“是”，所以分支“信用=‘是’”的結點為葉結點。2022/11/222)分支建立2022/11/2119建立的決策樹：2022/11/22建立的決策樹：2022/11/21202022/11/222022/11/2121C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)來選擇屬性。克服偏向選擇取值較多屬性的缺點用閾值對屬性劃分，即把訓練集中該屬性的所有值劃分到不同的區間中。用最常見值代替未知值規則存于二維數組中如：視為youth;視為middle_aged;

視為senior.C4.5(C5.0)算法1993年由Quinlan提出，采用22LOGO1、增益率Why？信息增益度量偏向于有許多輸出的測試，即它傾向于選擇具有大量值的屬性。舉個極端的例子：考慮充當唯一標識的屬性PID。對PID的分裂將產生大量劃分（與樣本個數一樣多），每個分類只包含一個樣本，且每個劃分都是純的。對屬性PID劃分得到的信息增益最大，顯然，這種劃分對分類沒有用處。LOGO1、增益率W23LOGO

使用分裂信息(splitinformation)將信息增益規范化。該值表示數據集按屬性測試的個劃分產生的信息。增益率：選擇具有最大信息率的屬性作為分裂屬性。LOGO使用分24增益率income其他屬性的信息率可類似求出。增益率income其他屬性的信息率可類似求出。25在實際通信之前（決策樹建立之前），輸出變量對信宿來講是完全隨機的，其平均不確定性為：決策樹建立過程中，隨著信宿接收到信息（輸入變量如T1），則條件熵為：信息增益：T1作為最佳分組變量而非T3將輸出變量（是否購買）看作信源發出的信息U輸入變量看作是信宿接收到的一系列信息V在實際通信之前（決策樹建立之前），輸出變量對信宿來講是完全隨26類別值多的輸入變量比少的有更多的機會成為當前最佳分組變量C5.0算法:信息增益率信息增益率的數學定義為：類別值多的輸入變量比少的有更多的機會成為當前最佳分組變量C527數值型輸入變量首先對它進行分組處理，分組方法采用基于MDLP的熵分組方法2、C5.0算法：數值型輸入變量數值型輸入變量2、C5.0算法：數值型輸入變量28把連續值屬性的值域分割為離散的區間集合。基于MDLP的熵分組方法。（MinimunDescriptionLengthPrinciple）信息增益大于編碼長度合并連續值屬性2022/11/22把連續值屬性的值域合并連續值屬性2022/11/2129選擇最佳分組變量時，通常將帶有缺失值的樣本當臨時剔除樣本看待，并進行權數調整

3、C5.0算法:對缺失值問題的處理計算輸出變量熵計算關于T1的條件熵計算經權數調整的T1信息增益計算信息增益率選擇最佳分組變量時，通常將帶有缺失值的樣本當臨時剔除樣本看待30不繼續確定關于分組變量的最佳分割點分類型輸入變量：K叉樹數值型輸入變量：2叉樹Clementine：ChiMerge分箱法在分組變量上取缺失值：第1個樣本被分配到各組中的權數分別為5/13、3/13、5/13，之后各組的樣本數分別為5＋5/13、3＋3/13、5＋5/13

4、C5.0算法:最佳分割點不繼續確定關于分組變量的最佳分割點4、C5.0算法:最佳分割31后修剪方法從葉結點向上逐層剪枝，關鍵是錯誤率即誤差的估計問題通常應在檢驗樣本集上估計誤差并進行剪枝利用統計中置信度的思想直接在訓練樣本集中估計誤差：當為0.25時，5、C5.0算法：剪枝后修剪方法從葉結點向上逐層剪枝，關鍵是錯誤率即誤差的估計問題32按照“減少－誤差（reduce-error）”法判斷是否剪枝C5.0算法：剪枝考慮是否可以剪掉最下層的3個葉結點3個結點的錯誤率：分別為：0.55、0.91、0.55；加權：計算父結點C的誤差估計為0.50。由于0.60大于0.50，因此可以剪掉3個葉結點。按照“減少－誤差（reduce-error）”法判斷是否剪枝33預測的置信度（或誤差）會影響決策，錯判的損失也會影響決策損失矩陣：6、C5.0算法：損失矩陣預測值YesNo實際值Yes0mNon0預測的置信度（或誤差）會影響決策，錯判的損失也會影響決策6、34從損失角度決策，在各類錯判損失不相等時（不能僅從置信角度判斷。事實上，默認在損失相同時才考慮置信度）：

c(i|j)是將j類錯判為i類的損失，p(j|t)是被節點t判為j類的歸一化概率C5.0算法：損失矩陣從損失角度決策，在各類錯判損失不相等時（不能僅從置信角度判斷35C5.0僅在剪枝時考慮損失，以二分類為例：C5.0算法：損失矩陣示例：取偽損失較大，給出yes判斷的置信度都很高。模型復雜，決策樹修剪程度低；如果取偽損失指定為10，則模型都判為NoC5.0僅在剪枝時考慮損失，以二分類為例：C5.0算法：損失36偏差和方差決策樹算法具有一定的不穩健性，可以考慮利用多組樣本建立多個模型，形成模型“委員會”制度Bagging技術Boosting技術C5.0算法：

模型“委員會”偏差和方差C5.0算法：模型“委員會”37建模過程（輸入：訓練樣本集T，訓練次數k；輸出：多個決策樹模型C1,C2,…Ck)Fori=1,2,…,kdo

從T中隨機有放回抽取樣本，形成有相同樣本容量的樣本集合Ti

以Ti為訓練集構造模型CiEndfor決策過程（輸入：新數據X，多個決策樹模型C1,C2,…Ck；輸出：分類預測結果C(X)）Fori=1,2,…,kdo

根據Ci對X做預測，結果為Ci(X)Endfor統計各類別得票，得票數最高的為C(X)，或計算平均值

C5.0算法：Bagging技術建模過程（輸入：訓練樣本集T，訓練次數k；輸出：多個決策樹模38兩個階段：建立k個模型；k個模型投票C5.0算法：Boosting技術兩個階段：建立k個模型；k個模型投票C5.0算法：Boos39Boosting技術：建模過程初試化樣本權數：wj(i)=1/n對每次迭代：根據樣本權數wj(i)，從T中有放回地抽取n個樣本形成訓練樣本集Ti；根據訓練集Ti得到模型Ci；計算模型的誤差e(i)如果e(i)>0.5或者e(i)=0，則終止建模過程；C5.0算法：Boosting技術Boosting技術：建模過程C5.0算法：Boosting40Boosting技術：建模過程初試化樣本權數：wj(i)=1/n對每次迭代：根據誤差更新每個樣本的權數：正確分類的樣本權數：wj(i+1)=wj(i)*?(i)，?(i)＝e(i)/(1-e(i))；錯誤分類的樣本權數保持不變：wj(i+1)=wj(i)；調整wj(i+1)使得各樣本的權重之和等于1經過k次迭代，將得到k個模型和k個誤差C5.0算法：Boosting技術Boosting技術：建模過程C5.0算法：Boosting41Boosting技術：投票過程（決策過程）采用加權投票，給不同的模型賦予不同的權數，權數與模型的誤差成反比，具體為：對新樣本X，每個模型Ci都給出預測值Ci(X)，給預測類Ci(X)加權：求各類權數的總和，總權數最高的類即為最終的分類結果Bagging與Boosting技術的比較Boosting示例C5.0算法：Boosting技術Boosting技術：投票過程（決策過程）C5.0算法：Bo42交叉驗證：對于n折交叉驗證，則在訓練樣本集合中重抽樣n組樣本建立n個模型，并計算每個模型訓練樣本集上的預測精度，且給出n個模型預測精度的平均值和標準差未剪枝的決策樹Pruningseverity中輸入置信度。默認為100%－25%。值越大樹越精簡，預測精度會不理想（誤差較高）；需要反復嘗試C5.0算法：其他交叉驗證：對于n折交叉驗證，則在訓練樣本集合中重抽樣n組樣本43C5.0算法：推理規則直接從決策樹得到推理規則很容易決策樹對邏輯關系的表述不是最簡潔的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEnoC5.0算法：推理規則直接從決策樹得到推理規則很容易abcc44生成推理規則的一般算法是PRISM(PatientRuleInductionSpaceMethod)算法，Cendrowska于1987年提出.是一種“覆蓋”算法,所生成的規則在訓練樣本集上是100％正確的

確定期望類別:yes年齡段=A(2/5)，年齡段=B(4/4)，年齡段=C(3/5)，性別=0(6/8)，性別=1(3/6)IF年齡段=BTHEN是否購買=yes規則100％正確，更新數據集：生成推理規則的一般算法是PRISM(PatientRule45規則100％正確，更新數據集年齡段=A(2/5)，年齡段=C(3/5)，性別=0(4/6)，性別=1(1/4)IF性別=0THEN是否購買=yes

年齡段=A(1/3),年齡段=C(3/3)IF性別=0AND年齡段=CTHEN是否購買=yes規則100％正確，更新數據集年齡段=A(2/5)，年齡段=C46年齡段=A(2/5)，年齡段=C(0/2)，性別=0(1/3)，性別=1(1/4)IF年齡段=ATHEN是否購買=yes性別=0(1/3)，性別=1(1/2)IF年齡段=AAND性別=1THEN是否購買=yes(略去)年齡段=A(2/5)，年齡段=C(0/2)，性別=0(1/347C5.0算法：推理規則利用規則集合對樣本進行分類可能產生的問題：樣本可能符合多個分類結果相同的規則樣本可能符合多個分類結果不相同的規則樣本不符合任何規則示例：推理規則的預測置信度是普拉斯估計器調整后的結果

C5.0算法：推理規則利用規則集合對樣本進行分類可能產生的問48模型評價Analysis結點對比模型在訓練樣本集和檢驗樣本集上的性能差異對比不同模型的性能確定相對合理的置信水平折：如果總體的正確率為90%，錯誤率為10%，則2折表示10%的一半，即錯誤率下降一半（2折，3折為33%）。如果改進2折，則總體正確率為95%，C5.0算法：模型的評價模型評價C5.0算法：模型的評價492022/11/22R中的實現R中決策樹的實現，主要用到四個軟件包：1、rpart:用于建立二分類樹及相關遞歸劃分算法的實現；2、rpart.plot：專用來對rpart模型繪制決策樹；3、maptree：用來修剪、繪制不僅僅局限于rpart模型的樹型結構圖；4、Rweka：提供了R與Weka的連接，Weka中集合了用Java編寫的一系列機器學習的算法。5、C50:運用C5.0算法建立決策樹算法名稱軟件包核心函數CARTrpartrpart()、prune.rpart()、post()rpart.plotrpart.plot()maptreedraw.tree()C4.5RWekaJ48()C5.0C50C5.0()2022/11/21R中的實現R中決策樹的實現，主要用到四個502022/11/22R中的實現2022/11/21R中的實現51R中的實現

C5.0：識別高分險客戶2022/11/22R中的實現

C5.0：識別高分險客戶2022/11/21522022/11/22R中的實現

C5.0：識別高分險客戶探索分類變量：table()函數用來產生單個類別變量的不同類別取值及對應的數量2022/11/21R中的實現

C5.0：識別高分險客戶探索532022/11/22R中的實現

C5.0：識別高分險客戶創建隨機的訓練集和測試集2022/11/21R中的實現

C5.0：識別高分險客戶創建542022/11/22R中的實現

C5.0：識別高分險客戶2022/11/21R中的實現

C5.0：識別高分險客戶552022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客562022/11/22R中的實現

C5.0：識別高分險客戶2022/11/21R中的實現

C5.0：識別高分險客戶572022/11/22R中的實現

C5.0：識別高分險客戶2022/11/21R中的實現

C5.0：識別高分險客戶582022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客戶592022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客戶602022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客戶612022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客戶622022/11/22R中的實現C5.0：識別高分險客戶2022/11/21R中的實現C5.0：識別高分險客戶632022/11/222022/11/2164決策樹算法概述決策樹算法最早源于人工智能的機器學習技術，用以實現數據內在規律的探究和新數據對象的分類預測。決策樹算法屬于有指導的學習。根結點葉結點內部結點兄弟結點2叉樹多叉樹決策樹算法概述決策樹算法最早源于人工智能的機器學習技術，用以65分類預測分類預測，就是通過向現有數據學習，使模型具備對未來新數據的分類預測能力。數據包含：輸入變量輸出變量分類和預測分類：分類型輸出變量預測：數值型輸出變量分類預測分類預測，就是通過向現有數據學習，使模型具備對未來新66決策樹算法概述決策樹的種類：分類決策樹：樹葉結點所含樣本的輸出變量的眾數就是分類結果。回歸決策樹：樹葉結點所含樣本的輸出變量的平均值就是預測結果。利用決策樹進行分類預測：對新數據進行分類預測時，只需按照決策樹的層次，從根結點開始依次對新數據輸入變量值進行判斷并進入不同的決策樹分支，直至葉結點為止。特點：分類預測是基于邏輯的。IFTHEN每個葉節點對應一條推理規則決策樹算法概述決策樹的種類：671建立決策樹，利用訓練樣本生成決策樹模型。

開始，數據都在根節點遞歸的進行數據分片2修剪決策樹

去掉一些可能是噪音或者異常的數據3使用決策樹對未知數據進行分類

按照決策樹上采用的分割屬性逐層往下，直到一個葉子節點使用決策樹進行分類判定樹分類算法output訓練集決策樹input2022/11/221建立決策樹，利用訓練樣本生成決策樹模型。使用決策樹進68決策樹的核心問題第一，決策樹的生長，即利用訓練樣本集完成決策樹的建立過程；1.如何從眾多的輸入變量中選擇一個當前最佳的分組變量；2.如何從分組變量的眾多取值中找到一個最佳的分割點。決策樹的核心問題第一，決策樹的生長，即利用訓練樣本集完成決策69決策樹的核心問題第二，決策樹的修剪，即利用檢驗樣本集對形成的決策樹進行優化處。過度擬和（Overfitting）預修剪（pre-pruning）、后修剪（post-pruning）決策樹的核心問題第二，決策樹的修剪，即利用檢驗樣本集對形成的70訓練集(Train)：數據庫中為建立模型而被分析的數據元組形成訓練集。訓練集中的單個元組稱為訓練樣本,每個訓練樣本有一個類別標記。一個具體樣本的形式可為:(v1,v2,...,vn;c);其中vi表示屬性值,c表示類別。測試集(Test)：用于模型參數的估計，評估分類模型的準確率。

驗證集(Validation):用于模型誤差的估計。訓練集與測試集2022/11/22訓練集(Train)：數據庫中為建立模型而被分析的數據元組形71a.模型訓練階段

訓練集b.使用模型分類階段評估準確率（測試集）對類標號未知的新數據分類

分類的兩個階段2022/11/22a.模型訓練階段分類的兩個階段2022/11/2172基本算法自上而下分而治之的方法開始時，所有的數據都在根節點所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發式規則或者一個統計的度量(如,informationgain)停止分割的條件一個節點上的數據都是屬于同一個類別沒有屬性可以再用于對數據進行分割2022/11/22基本算法2022/11/2173建樹階段MakeTree(TrainingDataT)

Partition(T);

Partition(DataS)

if(allpointsinSareinthesameclass)thenreturn;

evaluatesplitsforeachattributeA

UsebestsplitfoundtopartitionSintoS1andS2;

Partition(S1);

Partition(S2);2022/11/222022/11/2174屬性選擇度量標準－－分支指標信息增益——Informationgain

（ID3）增益比率——Gainration（C4.5,C5.0）基尼指數——Giniindex

(SLIQ，SPRINT)

…………2022/11/22屬性選擇度量標準－－分支指標信息增益——Informatio75

1、信息是用來消除隨機不確定性的度量。信息量的大小可由所消除的不確定性大小來計量。信息量的數學定義：2、信息熵是信息量的數學期望，是信源發出信息前的平均不確定性，也稱先驗熵，信息熵的數學定義為：信息論的基本概念1、信息是用來消除隨機不確定性的度量。信息量的大小可由761、信源熵H(X)信源熵是度量整個信源X整體的平均不確定性，也稱先驗熵。2、條件熵H(X/Y)條件熵是一個確定值，表示收信者在收到Y后，信源X仍然存在的不確定度，也稱為后驗熵。3、互信息量熵差H(X)－H(X/Y)是不確定性的消除，即互信息才是接收端所獲得的信息量。信息論的基本概念

2022/11/221、信源熵H(X)信息論的基本概念

2022/11/2177

ID3算法是借用信息論中的互信息尋找訓練集具有最大信息量的屬性字段，建立決策樹的一個節點，再根據該屬性字段的不同取值建立樹的分支;在每個分支子集中重復建立樹的下層節點和分支過程。

ID3算法2022/11/22ID3算法是借用信息論中的互信息尋找訓練集具有最大78

ID3算法2022/11/22

ID3算法2022/11/2179ID3Tree(T，T-attributelist)T為樣本空間，T-attributelist為屬性集。(1)創建根結點N。(2)IFT都屬于同一類C，則返回N為葉結點，標記為類C。(3)IFT-attributelist為空或T中所剩的樣本數少于某給定值，則返回N為葉結點，標記為T中出現最多的類。(4)

FOREACHT-attributelist中的屬性，計算信息增益informationgain。(5)結點N的分裂屬性為T-attributelist中具有最高信息增益的屬性。(6)

FOREACH由結點N長出的新結點{IF該結點對應的樣本子集只有唯一的一種決策類別，則將該結點標記為該類別的葉結點;ELSE在該結點上執行ID3Tree(T’，T’-attributelist)，對它繼續進行分裂;}其中，T’為由結點N劃分而來的子集，T’-attributeslit為去除被選分裂屬性后的屬性集。2.ID3算法描述2022/11/22ID3Tree(T，T-attributelist)2.I80

用決策樹考察某顧客是否會購買PC年齡收入是否學生信用購買PC<=30高否中否<=30高否優否31~40高否中是>40中否中是>40低是中是>40低是優否31~40低是優是<=30中否中否<=30低是中是>40中是中是<=30中是優是31~40中否優是31~40高是中是>40中否優否顧客數據表2022/11/22用決策樹考察某顧客是否會購買PC年齡收入是81

類標號屬性為購買PC，它有兩個不同的值(“是”、“否”)，即有兩個不同的類，m=2；設p對應“是”，n對應“否”，則p=9，n=5。1)創建根結點先計算對給定樣本分類所需的期望信息。

=0.94下面計算每個屬性的熵。從年齡開始計算。年齡=“<=30”： p11=2，n11=3I(p11，n11)=0.971年齡=“30~40”： p12=4，n12=0I(p12，n12)=0年齡=“>40”： p13=3，n13=2I(p13，n13)=0.971如果樣本按年齡劃分，對一個給定的樣本分類所需的期望信息如下

=0.694因此，這種劃分的信息增益是：Gain(年齡)=I(P，N)-E(年齡)=0.246。同理可得Gain(收入)=0.029Gain(是否學生)=0.151Gain(信用)=0.048

在所有的屬性中，年齡的信息增益最高，被選作測試屬性。創建一個根結點，用年齡標記，并對每個屬性值引出一個分支。2022/11/22類標號屬性為購買PC，它有兩個不同的值(“是822)分支建立考慮分支“年齡=‘<=30’”的結點。因為Gain(收入)=0.571Gain(學生)=0.971Gain(信用)=0.02所以分支“年齡=‘<=30’”結點的測試屬性為“學生”。考慮分支“年齡=31~40”的結點，由于所有記錄屬于同一類別“是”，所以分支“年齡=‘31~40’”的結點為葉結點。考慮分支“年齡=‘>40’”的結點。因為Gain(收入)=0.02Gain(學生)=0.02Gain(信用)=0.971所以分支“年齡=‘>40’”結點的測試屬性為“信用”。考慮分支“學生=‘否’”的結點，由于所有記錄屬于同一類別“否”，所以分支“學生=‘否’”的結點為葉結點。考慮分支“學生=‘是’”的結點，由于所有記錄屬于同一類別“是”，所以分支“學生=‘是’”的結點為葉結點。考慮分支“信用=‘優’”的結點，由于所有記錄屬于同一類別“否”，所以分支“信用=‘否’”的結點為葉結點。考慮分支“信用=‘中’”的結點，由于所有記錄屬于同一類別“是”，所以分支“信用=‘是’”的結點為葉結點。2022/11/222)分支建立2022/11/2183建立的決策樹：2022/11/22建立的決策樹：2022/11/21842022/11/222022/11/2185C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)來選擇屬性。克服偏向選擇取值較多屬性的缺點用閾值對屬性劃分，即把訓練集中該屬性的所有值劃分到不同的區間中。用最常見值代替未知值規則存于二維數組中如：視為youth;視為middle_aged;

視為senior.C4.5(C5.0)算法1993年由Quinlan提出，采用86LOGO1、增益率Why？信息增益度量偏向于有許多輸出的測試，即它傾向于選擇具有大量值的屬性。舉個極端的例子：考慮充當唯一標識的屬性PID。對PID的分裂將產生大量劃分（與樣本個數一樣多），每個分類只包含一個樣本，且每個劃分都是純的。對屬性PID劃分得到的信息增益最大，顯然，這種劃分對分類沒有用處。LOGO1、增益率W87LOGO

使用分裂信息(splitinformation)將信息增益規范化。該值表示數據集按屬性測試的個劃分產生的信息。增益率：選擇具有最大信息率的屬性作為分裂屬性。LOGO使用分88增益率income其他屬性的信息率可類似求出。增益率income其他屬性的信息率可類似求出。89在實際通信之前（決策樹建立之前），輸出變量對信宿來講是完全隨機的，其平均不確定性為：決策樹建立過程中，隨著信宿接收到信息（輸入變量如T1），則條件熵為：信息增益：T1作為最佳分組變量而非T3將輸出變量（是否購買）看作信源發出的信息U輸入變量看作是信宿接收到的一系列信息V在實際通信之前（決策樹建立之前），輸出變量對信宿來講是完全隨90類別值多的輸入變量比少的有更多的機會成為當前最佳分組變量C5.0算法:信息增益率信息增益率的數學定義為：類別值多的輸入變量比少的有更多的機會成為當前最佳分組變量C591數值型輸入變量首先對它進行分組處理，分組方法采用基于MDLP的熵分組方法2、C5.0算法：數值型輸入變量數值型輸入變量2、C5.0算法：數值型輸入變量92把連續值屬性的值域分割為離散的區間集合。基于MDLP的熵分組方法。（MinimunDescriptionLengthPrinciple）信息增益大于編碼長度合并連續值屬性2022/11/22把連續值屬性的值域合并連續值屬性2022/11/2193選擇最佳分組變量時，通常將帶有缺失值的樣本當臨時剔除樣本看待，并進行權數調整

3、C5.0算法:對缺失值問題的處理計算輸出變量熵計算關于T1的條件熵計算經權數調整的T1信息增益計算信息增益率選擇最佳分組變量時，通常將帶有缺失值的樣本當臨時剔除樣本看待94不繼續確定關于分組變量的最佳分割點分類型輸入變量：K叉樹數值型輸入變量：2叉樹Clementine：ChiMerge分箱法在分組變量上取缺失值：第1個樣本被分配到各組中的權數分別為5/13、3/13、5/13，之后各組的樣本數分別為5＋5/13、3＋3/13、5＋5/13

4、C5.0算法:最佳分割點不繼續確定關于分組變量的最佳分割點4、C5.0算法:最佳分割95后修剪方法從葉結點向上逐層剪枝，關鍵是錯誤率即誤差的估計問題通常應在檢驗樣本集上估計誤差并進行剪枝利用統計中置信度的思想直接在訓練樣本集中估計誤差：當為0.25時，5、C5.0算法：剪枝后修剪方法從葉結點向上逐層剪枝，關鍵是錯誤率即誤差的估計問題96按照“減少－誤差（reduce-error）”法判斷是否剪枝C5.0算法：剪枝考慮是否可以剪掉最下層的3個葉結點3個結點的錯誤率：分別為：0.55、0.91、0.55；加權：計算父結點C的誤差估計為0.50。由于0.60大于0.50，因此可以剪掉3個葉結點。按照“減少－誤差（reduce-error）”法判斷是否剪枝97預測的置信度（或誤差）會影響決策，錯判的損失也會影響決策損失矩陣：6、C5.0算法：損失矩陣預測值YesNo實際值Yes0mNon0預測的置信度（或誤差）會影響決策，錯判的損失也會影響決策6、98從損失角度決策，在各類錯判損失不相等時（不能僅從置信角度判斷。事實上，默認在損失相同時才考慮置信度）：

c(i|j)是將j類錯判為i類的損失，p(j|t)是被節點t判為j類的歸一化概率C5.0算法：損失矩陣從損失角度決策，在各類錯判損失不相等時（不能僅從置信角度判斷99C5.0僅在剪枝時考慮損失，以二分類為例：C5.0算法：損失矩陣示例：取偽損失較大，給出yes判斷的置信度都很高。模型復雜，決策樹修剪程度低；如果取偽損失指定為10，則模型都判為NoC5.0僅在剪枝時考慮損失，以二分類為例：C5.0算法：損失100偏差和方差決策樹算法具有一定的不穩健性，可以考慮利用多組樣本建立多個模型，形成模型“委員會”制度Bagging技術Boosting技術C5.0算法：

模型“委員會”偏差和方差C5.0算法：模型“委員會”101建模過程（輸入：訓練樣本集T，訓練次數k；輸出：多個決策樹模型C1,C2,…Ck)Fori=1,2,…,kdo

從T中隨機有放回抽取樣本，形成有相同樣本容量的樣本集合Ti

以Ti為訓練集構造模型CiEndfor決策過程（輸入：新數據X，多個決策樹模型C1,C2,…Ck；輸出：分類預測結果C(X)）Fori=1,2,…,kdo

根據Ci對X做預測，結果為Ci(X)Endfor統計各類別得票，得票數最高的為C(X)，或計算平均值

C5.0算法：Bagging技術建模過程（輸入：訓練樣本集T，訓練次數k；輸出：多個決策樹模102兩個階段：建立k個模型；k個模型投票C5.0算法：Boosting技術兩個階段：建立k個模型；k個模型投票C5.0算法：Boos103Boosting技術：建模過程初試化樣本權數：wj(i)=1/n對每次迭代：根據樣本權數wj(i)，從T中有放回地抽取n個樣本形成訓練樣本集Ti；根據訓練集Ti得到模型Ci；計算模型的誤差e(i)如果e(i)>0.5或者e(i)=0，則終止建模過程；C5.0算法：Boosting技術Boosting技術：建模過程C5.0算法：Boosting104Boosting技術：建模過程初試化樣本權數：wj(i)=1/n對每次迭代：根據誤差更新每個樣本的權數：正確分類的樣本權數：wj(i+1)=wj(i)*?(i)，?(i)＝e(i)/(1-e(i))；錯誤分類的樣本權數保持不變：wj(i+1)=wj(i)；調整wj(i+1)使得各樣本的權重之和等于1經過k次迭代，將得到k個模型和k個誤差C5.0算法：Boosting技術Boosting技術：建模過程C5.0算法：Boosting105Boosting技術：投票過程（決策過程）采用加權投票，給不同的模型賦予不同的權數，權數與模型的誤差成反比，具體為：對新樣本X，每個模型Ci都給出預測值Ci(X)，給預測類Ci(X)加權：求各類權數的總和，總權數最高的類即為最終的分類結果Bagging與Boosting技術的比較Boosting示例C5.0算法：Boosting技術Boosting技術：投票過程（決策過程）C5.0算法：Bo106交叉驗證：對于n折交叉驗證，則在訓練樣本集合中重抽樣n組樣本建立n個模型，并計算每個模型訓練樣本集上的預測精度，且給出n個模型預測精度的平均值和標準差未剪枝的決策樹Pruningseverity中輸入置信度。默認為100%－25%。值越大樹越精簡，預測精度會不理想（誤差較高）；需要反復嘗試C5.0算法：其他交叉驗證：對于n折交叉驗證，則在訓練樣本集合中重抽樣n組樣本107C5.0算法：推理規則直接從決策樹得到推理規則很容易決策樹對邏輯關系的表述不是最簡潔的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEnoC5.0算法：推理規則直接從決策樹得到推理規則很容易abcc108生成推理規則的一般算法是PRISM(PatientRuleInductionSpaceMethod)算法，Cendrowska于1987年提出.是一種“覆蓋”算法,所生成的規則在訓練樣本集上是100％正確