分類挖掘決策樹課件

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

開始，數(shù)據(jù)都在根節(jié)點(diǎn)遞歸的進(jìn)行數(shù)據(jù)分片2修剪決策樹

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

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

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

訓(xùn)練集b.使用模型分類階段評(píng)估準(zhǔn)確率（測試集）對類標(biāo)號(hào)未知的新數(shù)據(jù)分類

分類的兩個(gè)階段2022/11/22a.模型訓(xùn)練階段分類的兩個(gè)階段2022/11/218基本算法自上而下分而治之的方法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)所有記錄用所選屬性遞歸的進(jìn)行分割屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量(如,informationgain)停止分割的條件一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割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屬性選擇度量標(biāo)準(zhǔn)－－分支指標(biāo)信息增益——Informationgain

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

(SLIQ，SPRINT)

…………2022/11/22屬性選擇度量標(biāo)準(zhǔn)－－分支指標(biāo)信息增益——Informatio11

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

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

2022/11/2113

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

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

ID3算法2022/11/22

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

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

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

用決策樹考察某顧客是否會(huì)購買PC年齡收入是否學(xué)生信用購買PC<=30高否中否<=30高否優(yōu)否31~40高否中是>40中否中是>40低是中是>40低是優(yōu)否31~40低是優(yōu)是<=30中否中否<=30低是中是>40中是中是<=30中是優(yōu)是31~40中否優(yōu)是31~40高是中是>40中否優(yōu)否顧客數(shù)據(jù)表2022/11/22用決策樹考察某顧客是否會(huì)購買PC年齡收入是17

類標(biāo)號(hào)屬性為購買PC，它有兩個(gè)不同的值(“是”、“否”)，即有兩個(gè)不同的類，m=2；設(shè)p對應(yīng)“是”，n對應(yīng)“否”，則p=9，n=5。1)創(chuàng)建根結(jié)點(diǎn)先計(jì)算對給定樣本分類所需的期望信息。

=0.94下面計(jì)算每個(gè)屬性的熵。從年齡開始計(jì)算。年齡=“<=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如果樣本按年齡劃分，對一個(gè)給定的樣本分類所需的期望信息如下

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

在所有的屬性中，年齡的信息增益最高，被選作測試屬性。創(chuàng)建一個(gè)根結(jié)點(diǎn)，用年齡標(biāo)記，并對每個(gè)屬性值引出一個(gè)分支。2022/11/22類標(biāo)號(hào)屬性為購買PC，它有兩個(gè)不同的值(“是182)分支建立考慮分支“年齡=‘<=30’”的結(jié)點(diǎn)。因?yàn)镚ain(收入)=0.571Gain(學(xué)生)=0.971Gain(信用)=0.02所以分支“年齡=‘<=30’”結(jié)點(diǎn)的測試屬性為“學(xué)生”?？紤]分支“年齡=31~40”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“年齡=‘31~40’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)。考慮分支“年齡=‘>40’”的結(jié)點(diǎn)。因?yàn)镚ain(收入)=0.02Gain(學(xué)生)=0.02Gain(信用)=0.971所以分支“年齡=‘>40’”結(jié)點(diǎn)的測試屬性為“信用”。考慮分支“學(xué)生=‘否’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“否”，所以分支“學(xué)生=‘否’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)?？紤]分支“學(xué)生=‘是’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“學(xué)生=‘是’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)?？紤]分支“信用=‘優(yōu)’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“否”，所以分支“信用=‘否’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)?？紤]分支“信用=‘中’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“信用=‘是’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)。2022/11/222)分支建立2022/11/2119建立的決策樹：2022/11/22建立的決策樹：2022/11/21202022/11/222022/11/2121C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)來選擇屬性?？朔蜻x擇取值較多屬性的缺點(diǎn)用閾值對屬性劃分，即把訓(xùn)練集中該屬性的所有值劃分到不同的區(qū)間中。用最常見值代替未知值規(guī)則存于二維數(shù)組中如：視為youth;視為middle_aged;

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

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

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

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

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

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

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

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

根據(jù)Ci對X做預(yù)測，結(jié)果為Ci(X)Endfor統(tǒng)計(jì)各類別得票，得票數(shù)最高的為C(X)，或計(jì)算平均值

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

確定期望類別:yes年齡段=A(2/5)，年齡段=B(4/4)，年齡段=C(3/5)，性別=0(6/8)，性別=1(3/6)IF年齡段=BTHEN是否購買=yes規(guī)則100％正確，更新數(shù)據(jù)集：生成推理規(guī)則的一般算法是PRISM(PatientRule45規(guī)則100％正確，更新數(shù)據(jù)集年齡段=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規(guī)則100％正確，更新數(shù)據(jù)集年齡段=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算法：推理規(guī)則利用規(guī)則集合對樣本進(jìn)行分類可能產(chǎn)生的問題：樣本可能符合多個(gè)分類結(jié)果相同的規(guī)則樣本可能符合多個(gè)分類結(jié)果不相同的規(guī)則樣本不符合任何規(guī)則示例：推理規(guī)則的預(yù)測置信度是普拉斯估計(jì)器調(diào)整后的結(jié)果

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

C5.0：識(shí)別高分險(xiǎn)客戶2022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶2022/11/21522022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶探索分類變量：table()函數(shù)用來產(chǎn)生單個(gè)類別變量的不同類別取值及對應(yīng)的數(shù)量2022/11/21R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶探索532022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶創(chuàng)建隨機(jī)的訓(xùn)練集和測試集2022/11/21R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶創(chuàng)建542022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶2022/11/21R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶552022/11/22R中的實(shí)現(xiàn)C5.0：識(shí)別高分險(xiǎn)客戶2022/11/21R中的實(shí)現(xiàn)C5.0：識(shí)別高分險(xiǎn)客562022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶2022/11/21R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶572022/11/22R中的實(shí)現(xiàn)

C5.0：識(shí)別高分險(xiǎn)客戶2022/11/21R中的實(shí)現(xiàn)

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

開始，數(shù)據(jù)都在根節(jié)點(diǎn)遞歸的進(jìn)行數(shù)據(jù)分片2修剪決策樹

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

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

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

訓(xùn)練集b.使用模型分類階段評(píng)估準(zhǔn)確率（測試集）對類標(biāo)號(hào)未知的新數(shù)據(jù)分類

分類的兩個(gè)階段2022/11/22a.模型訓(xùn)練階段分類的兩個(gè)階段2022/11/2172基本算法自上而下分而治之的方法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)所有記錄用所選屬性遞歸的進(jìn)行分割屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量(如,informationgain)停止分割的條件一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別沒有屬性可以再用于對數(shù)據(jù)進(jìn)行分割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屬性選擇度量標(biāo)準(zhǔn)－－分支指標(biāo)信息增益——Informationgain

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

(SLIQ，SPRINT)

…………2022/11/22屬性選擇度量標(biāo)準(zhǔn)－－分支指標(biāo)信息增益——Informatio75

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

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

2022/11/2177

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

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

ID3算法2022/11/22

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

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

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

用決策樹考察某顧客是否會(huì)購買PC年齡收入是否學(xué)生信用購買PC<=30高否中否<=30高否優(yōu)否31~40高否中是>40中否中是>40低是中是>40低是優(yōu)否31~40低是優(yōu)是<=30中否中否<=30低是中是>40中是中是<=30中是優(yōu)是31~40中否優(yōu)是31~40高是中是>40中否優(yōu)否顧客數(shù)據(jù)表2022/11/22用決策樹考察某顧客是否會(huì)購買PC年齡收入是81

類標(biāo)號(hào)屬性為購買PC，它有兩個(gè)不同的值(“是”、“否”)，即有兩個(gè)不同的類，m=2；設(shè)p對應(yīng)“是”，n對應(yīng)“否”，則p=9，n=5。1)創(chuàng)建根結(jié)點(diǎn)先計(jì)算對給定樣本分類所需的期望信息。

=0.94下面計(jì)算每個(gè)屬性的熵。從年齡開始計(jì)算。年齡=“<=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如果樣本按年齡劃分，對一個(gè)給定的樣本分類所需的期望信息如下

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

在所有的屬性中，年齡的信息增益最高，被選作測試屬性。創(chuàng)建一個(gè)根結(jié)點(diǎn)，用年齡標(biāo)記，并對每個(gè)屬性值引出一個(gè)分支。2022/11/22類標(biāo)號(hào)屬性為購買PC，它有兩個(gè)不同的值(“是822)分支建立考慮分支“年齡=‘<=30’”的結(jié)點(diǎn)。因?yàn)镚ain(收入)=0.571Gain(學(xué)生)=0.971Gain(信用)=0.02所以分支“年齡=‘<=30’”結(jié)點(diǎn)的測試屬性為“學(xué)生”?？紤]分支“年齡=31~40”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“年齡=‘31~40’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)?？紤]分支“年齡=‘>40’”的結(jié)點(diǎn)。因?yàn)镚ain(收入)=0.02Gain(學(xué)生)=0.02Gain(信用)=0.971所以分支“年齡=‘>40’”結(jié)點(diǎn)的測試屬性為“信用”。考慮分支“學(xué)生=‘否’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“否”，所以分支“學(xué)生=‘否’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)。考慮分支“學(xué)生=‘是’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“學(xué)生=‘是’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)。考慮分支“信用=‘優(yōu)’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“否”，所以分支“信用=‘否’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)?？紤]分支“信用=‘中’”的結(jié)點(diǎn)，由于所有記錄屬于同一類別“是”，所以分支“信用=‘是’”的結(jié)點(diǎn)為葉結(jié)點(diǎn)。2022/11/222)分支建立2022/11/2183建立的決策樹：2022/11/22建立的決策樹：2022/11/21842022/11/222022/11/2185C4.5(C5.0)算法1993年由Quinlan提出，采用信息增益比(信息率)來選擇屬性?？朔蜻x擇取值較多屬性的缺點(diǎn)用閾值對屬性劃分，即把訓(xùn)練集中該屬性的所有值劃分到不同的區(qū)間中。用最常見值代替未知值規(guī)則存于二維數(shù)組中如：視為youth;視為middle_aged;

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

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

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

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

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

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

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

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

根據(jù)Ci對X做預(yù)測，結(jié)果為Ci(X)Endfor統(tǒng)計(jì)各類別得票，得票數(shù)最高的為C(X)，或計(jì)算平均值

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