決策樹培訓(xùn)講義(PPT 50頁).ppt

決策樹 上 武承羲 內(nèi)容 決策樹基礎(chǔ)經(jīng)典決策樹剪枝 決策樹 決策樹 用來表示決策和相應(yīng)的決策結(jié)果對應(yīng)關(guān)系的樹 樹中每一個非葉節(jié)點表示一個決策 該決策的值導(dǎo)致不同的決策結(jié)果 葉節(jié)點 或者影響后面的決策選擇 示例 決策樹 決策樹類型分類樹 葉節(jié)點對應(yīng)于一類別回歸樹 葉節(jié)點對應(yīng)于一連續(xù)值ID3 C4 5andC5 0 RossQuinlan CART L Breiman J Friedman R Olshen和C Stone 思想 空間劃分 比如 用變量y表示因變量 分類變量 用x1 x2 x3 xm表示自變量 通過遞歸的方式把關(guān)于自變量的m維空間劃分為不重疊的矩形 圖示 決策樹 ID3 C4 5 C5 0 RossQuinlanID31986年C4 51993年C5 01998年2011年獲得KDD創(chuàng)新獎 ID3 C4 5 C5 0的分類基礎(chǔ) 信息熵1948年 香農(nóng)提出了 信息熵 的概念 解決了對系統(tǒng)信息的量化度量問題 香農(nóng)認(rèn)為信息的準(zhǔn)確信息量可以用下面的信息熵公式計算 一個系統(tǒng)越是有序 信息熵就越低 反之 一個系統(tǒng)越亂 信息熵就越高 所以 信息熵也可以說是系統(tǒng)有序化程度的一個衡量 信息增益 informationgain 是指期望信息或者信息熵的有效減少量 信息增益率 informationgainratio 由劃分個數(shù)引起的偏置問題 劃分越多 引起每個劃分內(nèi)部數(shù)據(jù)純度的變化 分塊越小 數(shù)據(jù)純度可能越高 進(jìn)而引起偏置問題 設(shè)樣本集S按離散屬性F的V個不同的取值劃分為 共V個子集定義Split S F 則用F對S進(jìn)行劃分的信息增益率為 ID3 1986年由Quilan提出的ID3算法選擇具有最高信息增益的屬性作為測試屬性 ID3 DataSet featureList 創(chuàng)建根節(jié)點R如果當(dāng)前DataSet中的數(shù)據(jù)都屬于同一類 則標(biāo)記R的類別為該類如果當(dāng)前featureList集合為空 則標(biāo)記R的類別為當(dāng)前DataSet中樣本最多的類別遞歸情況 從featureList中選擇屬性F 選擇Gain DataSet F 最大的屬性 根據(jù)F的每一個值v 將DataSet劃分為不同的子集DS 對于每一個DS 創(chuàng)建節(jié)點C如果DS為空 節(jié)點C標(biāo)記為DataSet中樣本最多的類別如果DS不為空 節(jié)點C ID3 DS featureList F 將節(jié)點C添加為R的子節(jié)點C源碼 http id3alg altervista org 示例 1屬性及值域 outlook sunny overcast rain temperature hot mild cool humidity high normal wind weak strong Gain S Temperature 0 029Gain S Humidity 0 151Gain S Wind 0 048由此選擇根節(jié)點劃分屬性為outlook 參考 http www cise ufl edu ddd cap6635 Fall 97 Short papers 2 htmhttp en wikipedia org wiki ID3 algorithm C4 5 1993年由Quilan提出的C4 5算法 對ID3的改進(jìn) 信息增益率連續(xù)值屬性缺失值后剪枝基于錯誤剪枝EBP Error BasedPruning C4 5 連續(xù)型屬性 離散化處理 將連續(xù)型的屬性變量進(jìn)行離散化處理 形成決策樹的訓(xùn)練集把需要處理的樣本 對應(yīng)根節(jié)點 或樣本子集 對應(yīng)子樹 按照連續(xù)變量的大小從小到大進(jìn)行排序假設(shè)該屬性對應(yīng)的不同的屬性值一共有N個 那么總共有N 1個可能的候選分割閾值點 每個候選的分割閾值點的值為上述排序后的屬性值中兩兩前后連續(xù)元素的中點用信息增益率選擇最佳劃分 C4 5 缺失值 缺失值 在某些情況下 可供使用的數(shù)據(jù)可能缺少某些屬性的值 例如 X y 是樣本集S中的一個訓(xùn)練實例 X F1 v F2 v Fn v 但是其屬性Fi的值Fi v未知 處理策略 處理缺少屬性值的一種策略是賦給它結(jié)點t所對應(yīng)的訓(xùn)練實例中該屬性的最常見值另外一種更復(fù)雜的策略是為Fi的每個可能值賦予一個概率 例如 給定一個布爾屬性Fi 如果結(jié)點t包含6個已知Fi v 1和4個Fi v 0的實例 那么Fi v 1的概率是0 6 而Fi v 0的概率是0 4 于是 實例x的60 被分配到Fi v 1的分支 40 被分配到另一個分支 這些片斷樣例 fractionalexamples 的目的是計算信息增益 另外 如果有第二個缺少值的屬性必須被測試 這些樣例可以在后繼的樹分支中被進(jìn)一步細(xì)分 C4 5中使用 簡單處理策略就是丟棄這些樣本 C4 5 算法步驟示意 C4 5 DataSet featureList 創(chuàng)建根節(jié)點R如果當(dāng)前DataSet中的數(shù)據(jù)都屬于同一類 則標(biāo)記R的類別為該類如果當(dāng)前featureList集合為空 則標(biāo)記R的類別為當(dāng)前DataSet中樣本最多的類別遞歸情況 從featureList中選擇屬性F 選擇GainRatio DataSet F 最大的屬性 連續(xù)屬性參見上面的離散化過程 根據(jù)F的每一個值v 將DataSet劃分為不同的子集DS 對于每一個DS 創(chuàng)建節(jié)點C如果DS為空 節(jié)點C標(biāo)記為DataSet中樣本最多的類別如果DS不為空 節(jié)點C C4 5 DS featureList F 將節(jié)點C添加為R的子節(jié)點源碼 C4 5 C4 5算法優(yōu)點 產(chǎn)生的分類規(guī)則易于理解準(zhǔn)確率較高 C4 5算法缺點 在構(gòu)造樹的過程中 需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序 因而導(dǎo)致算法的低效 C5 0 思想 加入Boosting算法框架特點 更快內(nèi)存使用更有效更小的決策樹商業(yè)機(jī)密C5 0教程 CART 分類回歸樹CART ClassificationandRegressionTrees 1984 L Breiman J Friedman R Olshen和C Stonehttp www stat berkeley edu breiman http www stat stanford edu jhf http www stat stanford edu olshen 目標(biāo)變量是類別的 分類樹目標(biāo)變量是連續(xù)的 回歸樹 CART 二元劃分二叉樹不易產(chǎn)生數(shù)據(jù)碎片 精確度往往也會高于多叉樹 所以在CART算法中 采用了二元劃分不純性度量分類目標(biāo) Gini指標(biāo) Towing orderTowing連續(xù)目標(biāo) 最小平方殘差 最小絕對殘差剪枝 用獨立的驗證數(shù)據(jù)集對訓(xùn)練集生長的樹進(jìn)行剪枝 Gini指標(biāo) Giniindex Gini指標(biāo)用來度量數(shù)據(jù)集的不純度 Gini越小 數(shù)據(jù)越純CART中計算Gini指標(biāo)考慮每個屬性上的二元劃分 根據(jù)訓(xùn)練數(shù)據(jù)集S中的屬性F將S分成的S1和S2 則給定劃分的Gini指標(biāo)如下公式所示 最小化Gini指標(biāo) 離散屬性outlook sunny overcast rain Outlook值的子集有 8個 sunny overcast rain sunny overcast overcast rain sunny rain sunny overcast rain 去除不代表任何分裂的集合 空集 和全集 sunny overcast rain 則基于Outlook的劃分方式有3種 分別計算每種劃分的Gini指標(biāo) 選擇劃分 CART 分類樹 對于離散值屬性 在算法中遞歸的選擇該屬性產(chǎn)生最小Gini指標(biāo)的子集作為它的分裂子集 或使用其他不純度 對于連續(xù)值屬性 必須考慮所有可能的劃分點 其策略類似于C4 5中介紹的方法 利用Gini指數(shù)最小原則 選擇劃分點 CART 分類樹 節(jié)點t的類classify t CART classification DataSet featureList alpha 創(chuàng)建根節(jié)點R如果當(dāng)前DataSet中的數(shù)據(jù)的類別相同 則標(biāo)記R的類別標(biāo)記為該類如果決策樹高度大于alpha 則不再分解 標(biāo)記R的類別classify DataSet 遞歸情況 標(biāo)記R的類別classify DataSet 從featureList中選擇屬性F 選擇Gini DataSet F 最小的屬性劃分 連續(xù)屬性參考C4 5的離散化過程 以Gini最小作為劃分標(biāo)準(zhǔn) 根據(jù)F 將DataSet做二元劃分DS L和DS R 如果DS L或DS R為空 則不再分解如果DS L和DS R都不為空 節(jié)點C L CART classification DS L featureList alpha C R CART classification DS RfeatureList alpha 將節(jié)點C L和C R添加為R的左右子節(jié)點 CART 分類樹算法步驟示意 CART 回歸樹 樣本 X y y為分類 分類樹y為實數(shù) 回歸樹設(shè)t代表樹的某個節(jié)點 t中的樣本集合為 X1 y1 X2 y2 應(yīng)變量為實數(shù) N t 是節(jié)點t中的樣本個數(shù) 節(jié)點t的應(yīng)變量的均值 節(jié)點t內(nèi)的平方殘差最小化 squaredresidualsminimizationalgorithm CART 回歸樹 劃分 屬性 F將t劃分成左右節(jié)點tL和tR phi值 能最大化上式的就是最佳的 屬性 劃分 CART regression DataSet featureList alpha delta 創(chuàng)建根節(jié)點R如果當(dāng)前DataSet中的數(shù)據(jù)的值都相同 則標(biāo)記R的值為該值如果最大的phi值小于設(shè)定閾值delta 則標(biāo)記R的值為DataSet應(yīng)變量均值如果其中一個要產(chǎn)生的節(jié)點的樣本數(shù)量小于alpha 則不再分解 標(biāo)記R的值為DataSet應(yīng)變量均值遞歸情況 從featureList中選擇屬性F 選擇phi DataSet F 最大的屬性 連續(xù)屬性 或使用多個屬性的線性組合 參考C4 5的離散化過程 以phi最大作為劃分標(biāo)準(zhǔn) 根據(jù)F 將DataSet做二元劃分DS L和DS R 如果DS L或DS R為空 則標(biāo)記節(jié)點R的值為DataSet應(yīng)變量均值如果DS L和DS R都不為空 節(jié)點C L CART regression DS L featureList alpha delta C R CART regression DS RfeatureList alpha delta 將節(jié)點C L和C R添加為R的左右子節(jié)點 CART 回歸樹算法步驟示意 CART 后剪枝 代價 復(fù)雜度剪枝CCP Cost ComplexityPruning CART 回歸樹與多元線性回歸的區(qū)別 空間劃分 非線性 線性 其他決策樹 Quest quickunbiasedefficientstatisticaltree 算法Gini系數(shù)SLIQ SupervisedLearningInQuest 算法Gini系數(shù)SPRINT ScalableParallelizableInductionofClassificationTree 算法Gini系數(shù)并行PUBLIC PruningandBuildingIntegratedinClassification 算法Gini系數(shù)預(yù)剪枝 MDL剪枝算法CHAID Chi squaredAutomaticInteractionDetector 算法Chi square 決策樹剪枝 數(shù)據(jù)噪音訓(xùn)練數(shù)據(jù)量少過擬合 決策樹剪枝 預(yù)剪枝 前剪枝 通過提前停止樹的構(gòu)造來對決策樹進(jìn)行剪枝一旦停止該節(jié)點下樹的繼續(xù)構(gòu)造 該節(jié)點就成了葉節(jié)點 該葉節(jié)點持有其數(shù)據(jù)集中樣本最多的類或者其概率分布后剪枝首先構(gòu)造完整的決策樹 允許決策樹過度擬合訓(xùn)練數(shù)據(jù) 然后對那些置信度不夠的結(jié)點的子樹用葉結(jié)點來替代該葉節(jié)點持有其子樹的數(shù)據(jù)集中樣本最多的類或者其概率分布 預(yù)剪枝 預(yù)剪枝判斷停止樹生長的方法可以歸納為以下幾種 最為簡單的方法就是在決策樹到達(dá)一定高度的情況下就停止樹的生長 到達(dá)此結(jié)點的實例個數(shù)小于某一個閾值也可停止樹的生長 到達(dá)此結(jié)點的實例具有相同的特征向量 而不必一定屬于同一類 也可停止生長 這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問題 計算每次生長對系統(tǒng)性能的增益 如果這個增益值小于某個閾值則不進(jìn)行生長 如果在最好情況下的生長增益都小于閾值 即使有些葉子結(jié)點的實例不屬于同一類 也停止樹的增長 后剪枝 降低錯誤剪枝REP ReducedErrorPruning 悲觀錯誤剪枝PEP PessimisticErrorPruning 基于錯誤剪枝EBP Error BasedPruning 代價 復(fù)雜度剪枝CCP Cost ComplexityPruning 最小錯誤剪枝MEP MinimumErrorPruning 降低錯誤剪枝REP ReducedErrorPruning Quinlan獨立的剪枝集D基本思路 對于決策樹T的每棵非葉子樹s 用葉子替代這棵子樹 如果s被葉子替代后形成的新樹關(guān)于D的誤差等于或小于s關(guān)于D所產(chǎn)生的誤差 則用葉子替代子樹s優(yōu)點 計算復(fù)雜性低對未知示例預(yù)測偏差較小 悲觀錯誤剪枝PEP PessimisticErrorPruning Quinlan克服REP需要獨立剪枝集的缺點誤差估計的連續(xù)性校正自上而下悲觀 基于訓(xùn)練集建立的樹 對訓(xùn)練集合的錯誤率 對于未知集合來說是不可信的 設(shè)原始決策樹T 葉節(jié)點z z節(jié)點訓(xùn)練實例個數(shù)為n z 其中錯分個數(shù)為e z定義誤差率為 偏向性 訓(xùn)練數(shù)據(jù) 增加連續(xù)性校正 相應(yīng)的誤差數(shù) E z e z 0 5對于子樹t 誤差數(shù) 標(biāo)準(zhǔn)錯誤 剪枝條件 符合此條件 剪掉t 基于錯誤剪枝EBP Error BasedPruning QuinlanPEP的改進(jìn) C4 5中應(yīng)用 更加悲觀自下而上無需獨立剪枝集概率角度 置信區(qū)間 描述一個隨機(jī)變量的可能的值域范疇可能的取值范圍可能性 置信水平取值范圍 置信區(qū)間例如 x有95 的可能取值在 25 75 中 25 75 中 25是置信區(qū)間下限 25 75 中 75是置信區(qū)間上限從概率角度描述錯分樣本率統(tǒng)計檢驗 概率角度錯分樣本率r t 可看成是n t 次試驗中某事件發(fā)生e t 次的概率 二項分布得到關(guān)于錯分樣本率在置信水平為CF的置信區(qū)間計算置信區(qū)間上限 二項式置信區(qū)間的最簡單和最常用的公式依賴于逼近二項式分布的正態(tài)分布C4 5中使用Wilsonscoreinterval http en wikipedia org wiki Binomial proportion confidence interval Normal approximation interval EBP步驟 第一步 計算葉節(jié)點的錯分樣本率估計的置信區(qū)間上限U第二步 計算葉節(jié)點的預(yù)測錯分樣本數(shù)葉節(jié)點的預(yù)測錯分樣本數(shù) 到達(dá)該葉節(jié)點的樣本數(shù) 該葉節(jié)點的預(yù)測錯分樣本率U第三步 判斷是否剪枝及如何剪枝分別計算三種預(yù)測錯分樣本數(shù) 計算子樹t的所有葉節(jié)點預(yù)測錯分樣本數(shù)之和 記為E1計算子樹t被剪枝以葉節(jié)點代替時的預(yù)測錯分樣本數(shù) 記為E2計算子樹t的最大分枝的預(yù)測錯分樣本數(shù) 記為E3比較E1 E2 E3 如下 E1最小時 不剪枝E2最小時 進(jìn)行剪枝 以一個葉節(jié)點代替tE3最小時 采用 嫁接 grafting 策略 即用這個最大分枝代替t 代價 復(fù)雜度剪枝CCP Cost ComplexityPruning CCP又叫CART剪枝法代價 cost 樣本錯分率復(fù)雜度 complexity 樹t的葉節(jié)點數(shù) Breiman 定義t的代價復(fù)雜度 cost complexity 參數(shù) 用于衡量代價與復(fù)雜度之間關(guān)系表示剪枝后樹的復(fù)雜度降低程度與代價間的關(guān)系如何定義 對t來說 剪掉它的子樹s 以t中最優(yōu)葉節(jié)點代替 得到新樹new t new t可能會比t對于訓(xùn)練數(shù)據(jù)分錯M個 但是new t包含的葉節(jié)點數(shù) 卻比t少 Leaf s 1 個 復(fù)雜度降低了代價可能升高了如何平衡 令替換之后代價復(fù)雜度相等 增加了M個錯分樣本 但是減少了 leafs 1 個葉節(jié)點 negative M N Leaf sub 1 1 2514 3 0 000133 CCP剪枝步驟 第一步 計算完全