決策樹培訓(xùn)課件(PPT-60張)

1、Clementine的決策樹1主要內(nèi)容決策樹算法概述從學(xué)習(xí)角度看，決策樹屬有指導(dǎo)學(xué)習(xí)算法目標(biāo)：用于分類和回歸C5.0算法及應(yīng)用分類回歸樹及應(yīng)用CHAID算法及應(yīng)用QUEST算法及應(yīng)用模型的對比分析2決策樹算法概述：基本概念得名其分析結(jié)論的展示方式類似一棵倒置的樹根節(jié)點(diǎn)葉節(jié)點(diǎn)中間節(jié)點(diǎn)2叉樹和多叉樹3決策樹算法概述：特點(diǎn)體現(xiàn)了對樣本數(shù)據(jù)的不斷分組過程決策樹分為分類樹和回歸樹體現(xiàn)了輸入變量和輸出變量取值的邏輯關(guān)系邏輯比較形式表述的是一種推理規(guī)則每個(gè)葉節(jié)點(diǎn)都對應(yīng)一條推理規(guī)則對新數(shù)據(jù)對象的分類預(yù)測4決策樹算法概述：幾何理解決策樹建立的過程就是決策樹各個(gè)分枝依次形成的過程決策樹的每個(gè)分枝在一定規(guī)則下完成對

2、n維特征空間的區(qū)域劃分決策樹建立好后，n維特征空間會被劃分成若干個(gè)小的邊界平行或垂直于坐標(biāo)軸的矩形區(qū)域5確定每一步特征空間劃分標(biāo)準(zhǔn)時(shí)，都同時(shí)兼顧由此將形成的兩個(gè)區(qū)域，希望劃分形成的兩個(gè)區(qū)域所包含的樣本點(diǎn)盡可能同時(shí)“純正”6決策樹算法概述：核心問題第一，決策樹的生長利用訓(xùn)練樣本集完成決策樹的建立過程第二，決策樹的剪枝利用測試樣本集對所形成的決策樹進(jìn)行精簡7決策樹算法概述：樹生長決策樹的生長是對訓(xùn)練樣本集的不斷分組分枝準(zhǔn)則的確定涉及：第一，如何從眾多的輸入變量中選擇一個(gè)當(dāng)前最佳的分組變量第二，如何從分組變量的眾多取值中找到一個(gè)最佳的分割點(diǎn)8決策樹算法概述：樹剪枝樹剪枝的原因：完整的決策樹對訓(xùn)練樣本

3、特征的捕捉“過于精確”- 過擬和（Overfitting）常用的修剪技術(shù)：預(yù)修剪（pre-pruning）：用來限制決策樹的充分生長。策略：事先指定決策樹生長的最大深度事先指定樹節(jié)點(diǎn)樣本量的最小值后修剪（post-pruning）：待決策樹充分生長完畢后再進(jìn)行剪枝9決策樹算法概述：樹剪枝后修剪：待決策樹生長完畢，根據(jù)一定規(guī)則，剪去不具一般代表性的子樹。策略：事先指定允許的最大誤差值通常依據(jù)測試樣本集剪枝10C5.0算法C5.0是在ID3(J R Quinlan,1979)基礎(chǔ)上發(fā)展起來。C5.0是C4.5算法的商業(yè)化版本特點(diǎn)：C5.0用于建立多叉分類樹輸入變量是分類型或數(shù)值型，輸出變量應(yīng)為分類

4、型以信息增益率確定最佳分組變量和分割點(diǎn)11C5.0算法：熵信息熵是信息論(C.E.Shannon,1948)中的基本概念。信息論主要用于解決信息傳遞過程中的問題，也稱統(tǒng)計(jì)通信理論信息論的基本出發(fā)點(diǎn)認(rèn)為：信息傳遞通過由信源、信道和信宿組成的傳遞系統(tǒng)實(shí)現(xiàn)信道信源(發(fā)送端)信宿(接收端)12C5.0算法：熵信息論的基本出發(fā)點(diǎn)認(rèn)為：傳遞系統(tǒng)存在于一個(gè)隨機(jī)干擾環(huán)境之中將發(fā)送的信息記為U，接收的信息記為V，那么信道可看作為信道模型，記為P(U|V)信道信源(發(fā)送端)Uu1,u2,.ur信宿(接收端)Vv1,v2,.vqP(U|V)13C5.0算法：熵信道模型是一個(gè)條件概率矩陣P(U|V)，稱為信道傳輸概率

5、矩陣P(ui|vj)是信宿收到vj而信源發(fā)出ui的概率 ，且信源也同樣被看做是某種隨機(jī)過程，有：14C5.0算法：熵例如：二元信道模型15C5.0算法：熵先驗(yàn)不確定性：通信發(fā)生前，信宿對信源的狀態(tài)具有不確定性后驗(yàn)不確定性：通信發(fā)生后，信宿收到發(fā)自信源的信息，先驗(yàn)不確定性部分被消除，信宿對信源仍有一定程度的不確定性后驗(yàn)不確定性等于先驗(yàn)不確定性，表示信宿沒有收到信息；后驗(yàn)不確定性等于零，表示信宿收到了全部信息信息是用來消除隨機(jī)不確定性的，信息量的大小可由所消除的不確定性大小來計(jì)量16C5.0算法：熵信息量的數(shù)學(xué)定義：信息熵是信息量的數(shù)學(xué)期望，是信源發(fā)出信息前的平均不確定性，也稱先驗(yàn)熵。信息熵的數(shù)學(xué)

6、定義：信息熵等于0，表示只存在唯一的信息發(fā)送可能，P(ui)=1，沒有發(fā)送的不確定性；如果信源的k個(gè)信號有相同的發(fā)送概率，P(ui)=1/k，則信息發(fā)送的不確定性最大，信息熵達(dá)到最大P(ui)差別小，信息熵大，平均不確定性大；反之17C5.0算法：信息增益已知信號U的概率分布P(U)且收到信號V=vj，發(fā)出信號的概率分布為P(U|vj)，信源的平均不確定性：稱為后驗(yàn)熵。后驗(yàn)熵的期望(條件熵或信道疑義度)：信息增益信息消除隨機(jī)不確定性的程度18C5.0：生長算法如何從眾多輸入變量中選擇一個(gè)最佳分組變量：C5.0以信息增益率為標(biāo)準(zhǔn)。例如：決策樹建立之前：19決策樹建立過程中，考察輸入變量，如T1：

7、20問題：類別值多的輸入變量比類別值少的輸入變量有更多的機(jī)會成為當(dāng)前最佳分組變量21信息增益率：如何評價(jià)數(shù)值型輸入變量消除平均不確定性的能力首先分箱： Clementine的C5.0節(jié)點(diǎn)包含了MDLP分箱算法然后再根據(jù)上述方法判定C5.0：生長算法22如何從分組變量的眾多取值中找到最佳分割點(diǎn)默認(rèn)策略：對分類型分組變量：有k個(gè)類別，將樣本分成k組，形成樹的k個(gè)分支對數(shù)值型分組變量：以MDLP分箱所得的最小組限值為界，將小于組限的樣本劃為一組，大于的劃為另一組，形成兩個(gè)分叉數(shù)值型其他策略：ChiMerge分箱法，合并分組變量的多個(gè)類別后再分支C5.0：生長算法23C5.0：剪枝算法采用后修剪方法，

8、從葉節(jié)點(diǎn)向上逐層剪枝，關(guān)鍵：誤差的估計(jì)、剪枝標(biāo)準(zhǔn)的設(shè)置誤差估計(jì)：利用統(tǒng)計(jì)學(xué)置信區(qū)間的估計(jì)方法，直接在訓(xùn)練樣本集上估計(jì)誤差Clementine中1-默認(rèn)75%。置信度用于控制剪枝的程度，決定了所允許的誤差上限24C5.0：剪枝算法剪枝標(biāo)準(zhǔn)：“減少誤差（reduce -error）”法k為待剪子樹中葉節(jié)點(diǎn)的個(gè)數(shù)，pi為第i個(gè)葉節(jié)點(diǎn)所含樣本占子樹所含樣本的比例，ei為第i個(gè)葉節(jié)點(diǎn)的估計(jì)誤差，e為父節(jié)點(diǎn)的估計(jì)誤差25C5.0：剪枝算法例：能否剪掉C節(jié)點(diǎn)下的3個(gè)葉節(jié)點(diǎn)（E、F、G）估計(jì)3個(gè)節(jié)點(diǎn)的誤差：0.55、0.91、0.55加權(quán)求和：計(jì)算C節(jié)點(diǎn)的誤差估計(jì)：0.50可剪掉葉節(jié)點(diǎn)E、F、G第一個(gè)數(shù)字是本

9、節(jié)點(diǎn)所含樣本量N，第二個(gè)數(shù)為錯(cuò)判樣本數(shù)E26C5.0的推理規(guī)則集決策樹對邏輯關(guān)系的表述并非是最簡潔的IF a AND b THEN yesELSE IF c AND d THEN yesOTHERWISE no27推理規(guī)則集的生成算法PRISM（Patient Rule Induction Space Method，Cendrowska，1987），“覆蓋”算法，規(guī)則在訓(xùn)練樣本集上100正確基本思路：確定輸出變量的某個(gè)類別為期望類別在當(dāng)前樣本范圍內(nèi)，尋找能最大限度“覆蓋”期望類別樣本的推理規(guī)則在M個(gè)樣本范圍內(nèi)，按照正確覆蓋率最大原則確定附加條件，得到一個(gè)再小些的樣本范圍，直到推理規(guī)則不再“覆蓋

10、”屬于期望類別外的樣本從當(dāng)前樣本集合中剔除已經(jīng)被正確“覆蓋”的樣本，檢查剩余樣本中是否還有屬于期望類別的樣本。如果有則回到第一步。否則結(jié)束。28年齡段=A(2/5)，年齡段=B(4/4)，年齡段=C(3/5)，性別=0(6/8)，性別=1(3/6)，推理規(guī)則為：IF 年齡段=B THEN 是否購買=yes。剔除已被正確覆蓋的4個(gè)樣本年齡段=A(2/5)，年齡段=C(3/5)，性別=0(4/6)，性別=1(1/4)，推理規(guī)則為：IF 性別=0 THEN 是否購買=yes需附加邏輯與條件，樣本范圍為表中灰色部分。年齡段=A(1/3)，年齡段=C(3/3)。推理規(guī)則修正為：IF 性別=0 AND 年

11、齡段=C THEN 是否購買=yesYes為期望類別29C5.0其他：損失矩陣不同錯(cuò)誤類型所造成的實(shí)際損失可能不同，置信度會影響決策，錯(cuò)判損失同樣會影響決策損失矩陣使用損失矩陣的策略：數(shù)據(jù)建模型階段使用損失矩陣樣本預(yù)測時(shí)使用損失矩陣30C5.0其他：損失矩陣C5.0對損失矩陣的使用剪枝時(shí)采用“減少損失”法，判斷待剪子樹中葉節(jié)點(diǎn)的加權(quán)損失是否大于父層節(jié)點(diǎn)的損失，如果大于則可以剪掉31C5.0其他：損失矩陣損失矩陣對預(yù)測的影響：c(i|j)是損失矩陣中將j類錯(cuò)判為i類的損失，p(j|t)是被節(jié)點(diǎn)t判為j類的歸一化概率，定義為：例如：預(yù)測值123實(shí)際值1c(2|1)c(3|1)2c(1|2)c(3|

12、2)3c(1|3)c(2|3)32C5.0其他：N折交叉驗(yàn)證偏差和方差：預(yù)測的差異性來自兩個(gè)方面，定義輸出變量Y的均方誤差（Mean Squared Error）為：模型復(fù)雜度是導(dǎo)致偏差大小的重要因素：常數(shù)預(yù)測和復(fù)雜模型的預(yù)測方差較大的預(yù)測仍是無法令人滿意的方差測度了模型對訓(xùn)練樣本的敏感程度偏差總是未知的，方差的測度顯得較為重要N折交叉驗(yàn)證：估計(jì)模型參數(shù)的方差，估計(jì)預(yù)測精度的方差33C5.0其他偏差和方差的存在，使建立在一組訓(xùn)練樣本集上的一個(gè)模型，所給出的預(yù)測往往缺乏穩(wěn)健性數(shù)據(jù)挖掘中的策略Boosting技術(shù)均包括建模和投票兩個(gè)階段34C5.0其他：Boosting技術(shù)建立k個(gè)模型； k個(gè)模型

13、投票35C5.0其他：Boosting技術(shù)建模過程（輸入：訓(xùn)練樣本集T，訓(xùn)練次數(shù)k；輸出：多個(gè)決策樹模型C1,C2,Ck)初始化樣本權(quán)數(shù)：wj(1)=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，則終止建模過程；36C5.0其他：Boosting技術(shù)建模過程對每次迭代：根據(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)使得各樣

14、本的權(quán)重之和等于1經(jīng)過k次迭代，將得到k個(gè)模型和k個(gè)誤差37C5.0其他：Boosting技術(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é)果嵌套建模技術(shù)，弱(Weak）模型到強(qiáng)（Strong）模型38分類回歸樹分類回歸樹（Classification And Regression Tree，CART,Breiman,1984)特點(diǎn)：既可建立分類樹也可建立回歸樹只能建立2叉樹以Gini系數(shù)和方差作為建樹依據(jù)依據(jù)測試樣本集進(jìn)行剪枝

15、39CART：生長算法選擇當(dāng)前最佳分組變量分類樹和回歸樹、數(shù)值型輸入變量和分類型輸入變量，計(jì)算策略存在差異分類樹數(shù)值型輸入變量：分成兩組（2叉樹）依次以相鄰數(shù)值的中間值為組限分組計(jì)算兩組樣本輸出變量值的異質(zhì)性分組應(yīng)盡量使兩組的異質(zhì)性總和較小，使兩組異質(zhì)性隨著分組而快速下降40CART：生長算法(分類樹)異質(zhì)性指標(biāo)：GINI系數(shù)p(j|t)是節(jié)點(diǎn)t中樣本輸出變量取第j類的歸一化概率異質(zhì)性最小時(shí)，Gini系數(shù)為0；異質(zhì)性最大時(shí)，Gini系數(shù)為11/k異質(zhì)性下降指標(biāo)：使上式達(dá)到最大的組限應(yīng)為當(dāng)前最佳分割點(diǎn)41CART：生長算法(分類樹)分類型輸入變量：形成2個(gè)超類（2叉樹）多分類型輸入變量：合并為超

16、類同上，應(yīng)使兩組的異質(zhì)性總和達(dá)到最小，異質(zhì)性下降最快Twoing策略：找到使兩個(gè)超類差異足夠大的合并點(diǎn)sOrdered策略：適用于定序型輸入變量，只有兩個(gè)連續(xù)的別類才可合并成超類42CART：生長算法(回歸樹)異質(zhì)性指標(biāo)：方差異質(zhì)性下降指標(biāo)：從分組變量的眾多取值中找到最佳分割點(diǎn)：同上43CART：剪枝算法預(yù)修剪策略決策樹最大深度父節(jié)點(diǎn)和子節(jié)點(diǎn)所包含的最少樣本量或比例樹節(jié)點(diǎn)中輸出變量的最小異質(zhì)性減少量后修剪策略根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉節(jié)點(diǎn)或子樹CART依次給出所有可能子樹，從中挑選一棵如何得到這些子樹？挑選標(biāo)準(zhǔn)是什么？44CART：剪枝算法最小代價(jià)復(fù)雜性剪枝法（Mi

17、nimal Cost Complexity Pruning，MCCP）目標(biāo)：得到恰當(dāng)?shù)臉?，具有一定的預(yù)測精度，且復(fù)雜程度恰當(dāng)代價(jià)（誤差）和復(fù)雜度之間的權(quán)衡是必要的為復(fù)雜度系數(shù)基于最小代價(jià)復(fù)雜性原則 等于0時(shí)怎樣？ 很大時(shí)怎樣？45t的代價(jià)復(fù)雜度t的子樹Tt的代價(jià)復(fù)雜度判斷能否剪掉一個(gè)中間節(jié)點(diǎn)t下的子樹Tt保留子樹，此時(shí)：剪掉子樹剪掉子樹越小且小于剪掉確定可算，關(guān)鍵是46CART：剪枝算法 是一個(gè)不斷調(diào)整過程從0到的過程中:此時(shí)應(yīng)剪掉子樹Tt47剪枝過程：產(chǎn)生子樹序列T1，T2，T3，Tk。T1為最大樹，Tk只包含根節(jié)點(diǎn)初始為0，無枝可剪增大找到 小于的所有子樹中最小值對應(yīng)的子樹，剪掉，計(jì)算剪枝

18、后樹的代價(jià)復(fù)雜度值在當(dāng)前值下判斷是否仍有小于的子樹，有則依從小到大順序剪掉，并計(jì)算代價(jià)復(fù)雜度；否則，繼續(xù)增大，直到得到Tk隨著值增大，得到子樹序列。它們的復(fù)雜度依次降低，但代價(jià)復(fù)雜度的變化情況并不確定CART：剪枝算法48剪枝過程選擇k個(gè)子樹中代價(jià)復(fù)雜度最低的子樹，也可以允許考慮誤差項(xiàng)CART：剪枝算法放大因子代價(jià)復(fù)雜度最小子樹在測試樣本集上的預(yù)測誤差的誤差4950CART應(yīng)用示例以Telephone.sav為例，目標(biāo)：找到影響客戶流失的重要因素分類回歸樹的交互建?？梢允箾Q策樹的實(shí)際含義更貼近業(yè)務(wù)51交互建模中的模型評價(jià)交互建模中分類樹的評價(jià)風(fēng)險(xiǎn)評價(jià)和收益評價(jià)風(fēng)險(xiǎn)評價(jià)：模型誤差效益評價(jià)收益(G

19、ains)：模型對數(shù)據(jù)規(guī)律提煉的能力利潤(Profit)：財(cái)務(wù)角度反映模型價(jià)值角度：每條推理規(guī)則、決策樹整體52效益評價(jià)：收益評價(jià)(單個(gè)節(jié)點(diǎn))收益：對具有某類特征的數(shù)據(jù)，輸入和輸出變量取值規(guī)律的提煉的能力針對用戶關(guān)心的“目標(biāo)”類別。例：流失yes收益評價(jià)指標(biāo)【收益:n】：節(jié)點(diǎn)中樣本屬目標(biāo)類別的樣本量【響應(yīng)(%)】：節(jié)點(diǎn)中樣本屬目標(biāo)類別的樣本量占本節(jié)點(diǎn)樣本的百分比（置信程度）【收益(%)】：節(jié)點(diǎn)中樣本屬目標(biāo)類別的樣本量占目標(biāo)類別總樣本的百分比（適用廣泛性）53效益評價(jià)：收益評價(jià)(單個(gè)節(jié)點(diǎn))響應(yīng)%和收益%：意味追求高響應(yīng)%嗎？低響應(yīng)%和低收益%的規(guī)則，不理想例：甲殼蟲人群100人，90人購買，10

20、不購買IF 年輕富婆 THNE 買10人，響應(yīng)%=100%(高)，收益%=10/90(低)90人，響應(yīng)%=70%(中低),收益%=63/90(高)高響應(yīng)%和低收益%的規(guī)則，可能是沒有意義的低響應(yīng)%和高收益%的規(guī)則，可能是值得的54效益評價(jià)：收益評價(jià)(單個(gè)節(jié)點(diǎn))響應(yīng)%和收益%：意味追求高響應(yīng)%嗎？高響應(yīng)%和高收益%的規(guī)則，可能并沒有太多價(jià)值55效益評價(jià)：收益評價(jià)(單個(gè)節(jié)點(diǎn))收益評價(jià)指標(biāo)【指數(shù)(%)】：節(jié)點(diǎn)的響應(yīng)(%)是同類別樣本占總樣本比例的百分之幾倍，稱為提升度(lift)（價(jià)值）56效益評價(jià)：利潤評價(jià)(單個(gè)節(jié)點(diǎn))總體利潤：正利潤和負(fù)利潤（針對輸出變量所有類別計(jì)算）定義單位利潤利潤評價(jià)指標(biāo)【利

21、潤:】:節(jié)點(diǎn)的平均利潤【投資回報(bào)率】：總利潤/總投資【指數(shù)(%)】：節(jié)點(diǎn)的投資回報(bào)率是總投資回報(bào)率的倍數(shù)57效益評價(jià)(整體)累計(jì)收益圖：橫坐標(biāo)分位點(diǎn)，縱坐標(biāo)累計(jì)收益(%)累計(jì)響應(yīng)圖：橫坐標(biāo)分位點(diǎn)，縱坐標(biāo)累積響應(yīng)(%)累計(jì)提升圖：橫坐標(biāo)分位點(diǎn)，縱坐標(biāo)累計(jì)提升度累計(jì)利潤圖：橫坐標(biāo)分位點(diǎn)，縱坐標(biāo)累積利潤累計(jì)投資回報(bào)率圖：橫坐標(biāo)分位點(diǎn)，縱坐標(biāo)累積ROI58決策樹說明決策樹算法在處理不同類型數(shù)據(jù)時(shí)的優(yōu)勢和劣勢數(shù)值型的優(yōu)勢和劣勢不受數(shù)量級的影響忽略分布特征分類型的優(yōu)勢和劣勢建樹效率高類別較多時(shí)，樹太茂盛容易處理“混合類型”的輸入變量59謝 謝！601、不是井里沒有水，而是你挖的不夠深。不是成功來得慢，而是

22、你努力的不夠多。2、孤單一人的時(shí)間使自己變得優(yōu)秀，給來的人一個(gè)驚喜，也給自己一個(gè)好的交代。3、命運(yùn)給你一個(gè)比別人低的起點(diǎn)是想告訴你，讓你用你的一生去奮斗出一個(gè)絕地反擊的故事，所以有什么理由不努力!4、心中沒有過分的貪求，自然苦就少?？诶锊徽f多余的話，自然禍就少。腹內(nèi)的食物能減少，自然病就少。思緒中沒有過分欲，自然憂就少。大悲是無淚的，同樣大悟無言。緣來盡量要惜，緣盡就放。人生本來就空，對人家笑笑，對自己笑笑，笑著看天下，看日出日落，花謝花開，豈不自在，哪里來的塵埃!5、心情就像衣服，臟了就拿去洗洗，曬曬，陽光自然就會蔓延開來。陽光那么好，何必自尋煩惱，過好每一個(gè)當(dāng)下，一萬個(gè)美麗的未來抵不過一個(gè)溫暖的現(xiàn)在。6、無論你正遭遇著什么，你都要從落魄中站起來重振旗鼓，要繼續(xù)保持熱忱，要繼續(xù)保持微笑，就像從未受傷過一樣。7、生命的美麗，永遠(yuǎn)展現(xiàn)在她的進(jìn)取之中;就像大樹的美麗，是展現(xiàn)在它負(fù)勢向上高聳入云的蓬勃生機(jī)中;像雄鷹的美麗，是展現(xiàn)在它搏風(fēng)擊雨如蒼天之魂的翱翔中;像江河的美麗，是展現(xiàn)在它波濤洶涌一瀉千里的奔流中。8、有些事，不可避免地發(fā)生，陰晴圓缺皆有規(guī)律，我們只能