分類技術(shù)-決策樹算法

決策樹教師：***學(xué)生：***分類技術(shù)

電子科技大學(xué)●What’sthat?●初印象(簡例)●基本步驟●量化純度●信息增益●停止條件電子科技大學(xué)●過度擬合●過度擬合修正●實例詳解●準(zhǔn)確率估計What’sthat?●決策樹（DecisionTree）是一種簡單但是廣泛使用的分類器。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹，可以高效的對未知的數(shù)據(jù)進(jìn)行分類。●決策樹兩大優(yōu)點(diǎn)：1）決策樹模型可以讀性好，具有描述性，有助于人工分析；2）效率高，決策樹只需要一次構(gòu)建，反復(fù)使用，每一次預(yù)測的最大計算次數(shù)不超過決策樹的深度。電子科技大學(xué)What’sthat?●決策樹（DecisionTree）是一種簡單但是廣泛使用的分類器。通過訓(xùn)練數(shù)據(jù)構(gòu)建決策樹，可以高效的對未知的數(shù)據(jù)進(jìn)行分類。●決策樹兩大優(yōu)點(diǎn)：1）決策樹模型可以讀性好，具有描述性，有助于人工分析；2）效率高，決策樹只需要一次構(gòu)建，反復(fù)使用，每一次預(yù)測的最大計算次數(shù)不超過決策樹的深度。電子科技大學(xué)電子科技大學(xué)ID擁有房產(chǎn)（是/否）婚姻情況（單身，已婚，離婚）年收入（單位：千元）無法償還債務(wù)（是/否）1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是初印象電子科技大學(xué)ID擁有房產(chǎn)（是/否）婚姻情況（單身，已婚，離婚）年收入（單位：千元）無法償還債務(wù)（是/否）1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是初印象上表根據(jù)歷史數(shù)據(jù)，記錄已有的用戶是否可以償還債務(wù)，以及相關(guān)的信息。通過該數(shù)據(jù)，構(gòu)建的決策樹如下：電子科技大學(xué)比如新來一個用戶：無房產(chǎn)，單身，年收入55K，那么根據(jù)上面的決策樹，可以預(yù)測他無法償還債務(wù)（藍(lán)色虛線路徑）。電子科技大學(xué)基本步驟●決策樹構(gòu)建的基本步驟如下：1.開始，所有記錄看作一個節(jié)點(diǎn)2.遍歷每個變量的每一種分割方式，找到最好的分割點(diǎn)3.分割成兩個節(jié)點(diǎn)N1和N24.對N1和N2分別繼續(xù)執(zhí)行2-3步，直到每個節(jié)點(diǎn)足夠“純”為止●決策樹的變量可以有兩種：1）數(shù)字型（Numeric）：變量類型是整數(shù)或浮點(diǎn)數(shù)，如前面例子中的“年收入”。用“>=”，“>”,“<”或“<=”作為分割條件（排序后，利用已有的分割情況，可以優(yōu)化分割算法的時間復(fù)雜度）。2）名稱型（Nominal）：類似編程語言中的枚舉類型，變量只能重有限的選項中選取，比如前面例子中的“婚姻情況”，只能是“單身”，“已婚”或“離婚”。使用“=”來分割。電子科技大學(xué)量化純度Gini純度：熵（Entropy）：誤分類差錯：上面的三個公式均是值越大，表示越“不純”，越小表示越“純”。三種公式只需要取一種即可，實踐證明三種公式的選擇對最終分類準(zhǔn)確率的影響并不大，一般使用熵公式。轉(zhuǎn)至示例電子科技大學(xué)信息增益信息增益（InformationGain）：I(.)是給定節(jié)點(diǎn)的不純性度量，N是父節(jié)點(diǎn)上的記錄總數(shù)，k是屬性值的個數(shù)，N(Vj)是與子女節(jié)點(diǎn)Vj相關(guān)聯(lián)的記錄個數(shù)。轉(zhuǎn)至示例電子科技大學(xué)停止條件決策樹的構(gòu)建過程是一個遞歸的過程，所以需要確定停止條件，否則過程將不會結(jié)束。一種最直觀的方式是當(dāng)每個子節(jié)點(diǎn)只有一種類型的記錄時停止，但是這樣往往會使得樹的節(jié)點(diǎn)過多，導(dǎo)致過擬合問題（Overfitting）。另一種可行的方法是當(dāng)前節(jié)點(diǎn)中的記錄數(shù)低于一個最小的閥值，那么就停止分割，將max(P(i))對應(yīng)的分類作為當(dāng)前葉節(jié)點(diǎn)的分類。電子科技大學(xué)過度擬合某決策樹對訓(xùn)練數(shù)據(jù)可以得到很低的錯誤率，但是運(yùn)用到測試數(shù)據(jù)上卻得到非常高的錯誤率。過渡擬合的原因有以下幾點(diǎn)：?噪音數(shù)據(jù)：訓(xùn)練數(shù)據(jù)中存在噪音數(shù)據(jù)，決策樹的某些節(jié)點(diǎn)有噪音數(shù)據(jù)作為分割標(biāo)準(zhǔn)，導(dǎo)致決策樹無法代表真實數(shù)據(jù)。?缺少代表性數(shù)據(jù)：訓(xùn)練數(shù)據(jù)沒有包含所有具有代表性的數(shù)據(jù)，導(dǎo)致某一類數(shù)據(jù)無法很好的匹配，這一點(diǎn)可以通過觀察混淆矩陣（ConfusionMatrix）分析得出。?多重比較（MulitpleComparition）：電子科技大學(xué)過度擬合修正優(yōu)化方案1：修剪枝葉前置裁剪：在構(gòu)建決策樹的過程時，提前停止。那么，會將切分節(jié)點(diǎn)的條件設(shè)置的很苛刻，導(dǎo)致決策樹很短小。結(jié)果就是決策樹無法達(dá)到最優(yōu)。實踐證明這中策略無法得到較好的結(jié)果。后置裁剪：決策樹構(gòu)建好后，才開始裁剪。采用兩種方法：1）用單一葉節(jié)點(diǎn)代替整個子樹，葉節(jié)點(diǎn)的分類采用子樹中最主要的分類；2）將一個字?jǐn)?shù)完全替代另外一顆子樹。后置裁剪有個問題就是計算效率，有些節(jié)點(diǎn)計算后就被裁剪了，導(dǎo)致有點(diǎn)浪費(fèi)。電子科技大學(xué)過度擬合修正優(yōu)化方案2：K-FoldCrossValidation首先計算出整體的決策樹T，葉節(jié)點(diǎn)個數(shù)記作N，設(shè)i屬于[1,N]。對每個i，使用K-FoldValidataion方法計算決策樹，并裁剪到i個節(jié)點(diǎn)，計算錯誤率，最后求出平均錯誤率。這樣可以用具有最小錯誤率對應(yīng)的i作為最終決策樹的大小，對原始決策樹進(jìn)行裁剪，得到最優(yōu)決策樹。電子科技大學(xué)過度擬合修正優(yōu)化方案3：RandomForestRandomForest是用訓(xùn)練數(shù)據(jù)隨機(jī)的計算出許多決策樹，形成了一個森林。然后用這個森林對未知數(shù)據(jù)進(jìn)行預(yù)測，選取投票最多的分類。實踐證明，此算法的錯誤率得到了經(jīng)一步的降低。這種方法背后的原理可以用“三個臭皮匠定一個諸葛亮”這句諺語來概括。一顆樹預(yù)測正確的概率可能不高，但是集體預(yù)測正確的概率卻很高。電子科技大學(xué)準(zhǔn)確率估計設(shè)T的準(zhǔn)確率p是一個客觀存在的值，X的概率分布為X~B(N,p)，即X遵循概率為p，次數(shù)為N的二項分布（BinomialDistribution），期望E(X)=N*p，方差Var(X)=N*p*(1-p)。由于當(dāng)N很大時，二項分布可以近似有正態(tài)分布（NormalDistribution）計算，一般N會很大，所以X~N(np,n*p*(1-p))?？梢运愠?，acc=X/N的期望E(acc)=E(X/N)=E(X)/N=p，方差Var(acc)=Var(X/N)=Var(X)/N2=p*(1-p)/N，所以acc~N(p,p*(1-p)/N)。這樣，就可以通過正態(tài)分布的置信區(qū)間的計算方式計算置信區(qū)間了。電子科技大學(xué)準(zhǔn)確率估計正態(tài)分布的置信區(qū)間求解如下：1）將acc標(biāo)準(zhǔn)化，即2）選擇置信水平α=95%，或其他值，這取決于你需要對這個區(qū)間有多自信。一般來說，α越大，區(qū)間越大。3）求出α/2和1-α/2對應(yīng)的標(biāo)準(zhǔn)正態(tài)分布的統(tǒng)計量image和image（均為常量）。然后解下面關(guān)于p的不等式。acc可以有樣本估計得出。即可以得到關(guān)于p的執(zhí)行區(qū)間電子科技大學(xué)實例詳解ID擁有房產(chǎn)（是/否）婚姻情況（單身，已婚，離婚）年收入（單位：千元）無法償還債務(wù)（是/否）1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是電子科技大學(xué)實例詳解ID擁有房產(chǎn)（是/否）婚姻情況（單身，已婚，離婚）年收入（單位：千元）無法償還債務(wù)（是/否）1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是1、選取第一個測試條件1）計算每個測試條件的熵2）計算每個測試條件的信息增益，選取值最大的電子科技大學(xué)

電子科技大學(xué)2）計算信息增益擁有房產(chǎn)可以償還債務(wù)待定是否

電子科技大學(xué)ID擁有房產(chǎn)（是/否）婚姻情況（單身，已婚，離婚）年收入（單位：千元）無法償還債務(wù)（是/否）1是單身125否2否已婚100否3否單身70否4是已婚120否5否離婚95是6否已婚60否7是離婚220否8否單身85是9否已婚75否10否單身90是2、選取余下測試條件1）不再考慮“擁有房產(chǎn)”的影響，計算余下測試條件的熵2）計算余下測試條件的信息增益，選取值最大的2、選取余下測試條件