第四講Modeler分類預(yù)測：決策樹算法(一)

分類預(yù)測：決策樹算法

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

特點：分類預(yù)測是基于邏輯的

IFTHEN每個葉節(jié)點對應(yīng)一條推理規(guī)則決策樹的幾何意義在確定每一步空間劃分標準時都同時兼顧由此將形成的兩個區(qū)域；希望在兩個區(qū)域同時實現(xiàn)：同一區(qū)域中的盡可能多的樣本輸出變量取同一類別值決策樹的核心問題第一，決策樹的生長，即利用訓(xùn)練樣本集完成決策樹的建立過程；第一，如何從眾多的輸入變量中選擇一個當前最佳的分組變量；第二，如何從分組變量的眾多取值中找到一個最佳的分割點

決策樹的核心問題第二，決策樹的修剪，即利用檢驗樣本集對形成的決策樹進行優(yōu)化處理過度擬和（Overfitting）預(yù)修剪（pre-pruning）、后修剪（post-pruning）C5.0算法ID3（1979年由JRQuinlan），C4.5，C5.0C5.0的特點：生成多叉樹輸入變量可以是分類型也可以是數(shù)值型輸出變量為分類型以信息增益率為標準確定最佳分組變量和分割點C5.0算法:熵信息熵是信息論中的基本概念。信息論是C.E.Shannon于1948年提出而發(fā)展起來的，主要用于解決信息傳遞過程中的問題，也稱統(tǒng)計通信理論信息論把通信過程看作是在隨機干擾的環(huán)境中通過傳遞系統(tǒng)傳遞信息的過程。一個傳遞信息的系統(tǒng)是由：信道信源(發(fā)送端)Uu1,u2,..ur信宿(接收端)Vv1,v2,..vqP(U|V)信道模型是一個條件概率矩陣P(U|V)，稱為信道傳輸概率信道模型：是一個條件概率矩陣P(U|V)，稱為信道傳輸概率。P(uj|vi)表示信宿收到信息vj信源發(fā)出信息ui

的概率二元信道模型為例：傳輸概率矩陣P為：

P11

P21

P12

P22u1u2v1v2P11P12P21P22C5.0算法:熵信源也同樣理解被理解為某種隨機過程。信息ui(i=1,2,…r)的發(fā)生概率P(ui)組成了信源的數(shù)學(xué)模型，且信宿對信源具有先驗不確定性信宿對信源具有后驗不確定性如果后驗不確定性等于先驗不確定性，表示信宿根本沒有收到信息；如果后驗不確定性等于零，表示信宿收到了全部信息。信息是用來消除隨機不確定性的度量。信息量的大小可由所消除的不確定性大小來計量信息量的數(shù)學(xué)定義：信息熵是信息量的數(shù)學(xué)期望，是信源發(fā)出信息前的平均不確定性，也稱先驗熵，信息熵的數(shù)學(xué)定義為：C5.0算法:熵信息熵：如果信息熵等于0，表示只存在唯一的信息發(fā)送可能，即P(ui)=1，沒有發(fā)送的不確定性；如果信源的k個信號有相同的發(fā)送概率，即所有的ui有P(ui)=1/k，則信息熵達到最大，不確定性最大。P(ui)差別越小，信息熵越大，平均不確定性越大。P(ui)差別大，信息熵就越小，平均不確定性越小

C5.0算法:熵當已知信號U的概率分布P(U)且收到信號V=vj后，發(fā)出信號的概率分布變?yōu)镻(U|vj)，于是信源的平均不確定性變?yōu)椋汉篁烄氐钠谕麨椋盒畔⒃鲆妫篊5.0算法:信息增益后驗熵

條件熵：后驗不確定性（平均）反映信息消除隨機不確定性程度

在實際通信之前（決策樹建立之前），輸出變量對信宿來講是完全隨機的，其平均不確定性為：決策樹建立過程中，隨著信宿接收到信息（輸入變量如T1），則條件熵為：信息增益：T1作為最佳分組變量而非T3將輸出變量（是否購買）看作信源發(fā)出的信息U輸入變量看作是信宿接收到的一系列信息V類別值多的輸入變量比少的有更多的機會成為當前最佳分組變量C5.0算法:信息增益率信息增益率的數(shù)學(xué)定義為：數(shù)值型輸入變量首先對它進行分組處理，分組方法采用基于MDLP的熵分組方法C5.0算法：數(shù)值型輸入變量選擇最佳分組變量時，通常將帶有缺失值的樣本當臨時剔除樣本看待，并進行權(quán)數(shù)調(diào)整

C5.0算法:對缺失值問題的處理計算輸出變量熵計算關(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ù)分別為5＋5/13、3＋3/13、5＋5/13

C5.0算法:最佳分割點后修剪方法從葉結(jié)點向上逐層剪枝，關(guān)鍵是錯誤率即誤差的估計問題通常應(yīng)在檢驗樣本集上估計誤差并進行剪枝利用統(tǒng)計中置信度的思想直接在訓(xùn)練樣本集中估計誤差：當為0.25時，C5.0算法：剪枝按照“減少－誤差（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é)點。最簡單的模型（默認選項）partitionedDecisiontreeGroupsymbolicsMode:simple（置信度1-0.25）計算結(jié)果規(guī)則置信度樣本預(yù)測置信度：經(jīng)拉普拉斯估計器（Laplaceestimator）調(diào)整后的結(jié)果

C5.0算法：示例研究哪些因素將顯著影響到學(xué)生參與社會公益活動樸素貝葉斯分類法y:是否購買(1/0)、x1:性別(1/2)、x2:職業(yè)(A/B/C)預(yù)測：X=(x1=1,x2=A)先驗概率預(yù)測的置信度（或誤差）會影響決策，錯判的損失也會影響決策損失矩陣：C5.0算法：損失矩陣預(yù)測值YesNo實際值Yes0mNon0從損失角度決策，在各類錯判損失不相等時（不能僅從置信角度判斷。事實上，默認在損失相同時才考慮置信度）：

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

模型“委員會”建模過程（輸入：訓(xùn)練樣本集T，訓(xùn)練次數(shù)k；輸出：多個決策樹模型C1,C2,…Ck)Fori=1,2,…,kdo

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

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

根據(jù)Ci對X做預(yù)測，結(jié)果為Ci(X)Endfor統(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個樣本形成訓(xùn)練樣本集Ti；根據(jù)訓(xùn)練集Ti得到模型Ci；計算模型的誤差e(i)如果e(i)>0.5或者e(i)=0，則終止建模過程；C5.0算法：Boosting技術(shù)Boosting技術(shù)：建模過程初試化樣本權(quán)數(shù)：wj(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ù)的比較Boosting示例C5.0算法：Boosting技術(shù)交叉驗證：對于n折交叉驗證，則在訓(xùn)練樣本集合中重抽樣n組樣本建立n個模型，并計算每個模型訓(xùn)練樣本集上的預(yù)測精度，且給出n個模型預(yù)測精度的平均值和標準差未剪枝的決策樹Pruningseverity中輸入置信度。默認為100%－25%。值越大樹越精簡，預(yù)測精度會不理想（誤差較高）；需要反復(fù)嘗試C5.0算法：其他C5.0算法：推理規(guī)則直接從決策樹得到推理規(guī)則很容易決策樹對邏輯關(guān)系的表述不是最簡潔的abccddyesnoyesnoyesnonoyyyyyynnnnnnIFaANDbTHENyesIFcANDdTHENyesOTHERWISEno生成推理規(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ī)則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年齡段=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(略去)C5.0算法：推理規(guī)