決策樹培訓(xùn)講義(ppt50頁)(參考版)
2025-01-15 19:35本頁面
【正文】 否則 , 剪裁 它 不需 要獨立的剪枝集 references 。39。39。39。 39。 39。leaf 是 子 樹 的 葉 節(jié) 點 數(shù):negative α= M/(N*(Leaf_sub1))=1/(2514*3)= CCP剪枝步驟： 第 一步： 計算 完 全決策樹 T_max的每個非葉節(jié) 點 的 α值； 循環(huán)剪掉具有最小 α值的子樹，直到剩下根節(jié)點 得到一系列剪枝 (嵌套 )樹 {T_0,T_1,T_2,…T_m}，其中 T_0就是完全決策樹T_max。 后剪枝 降低錯誤剪枝 REP ( Reduced Error Pruning) 悲觀錯誤剪枝 PEP (Pessimistic Error Pruning) 基于錯誤剪枝 EBP (ErrorBased Pruning) 代價 復(fù)雜度剪枝 CCP (CostComplexity Pruning) 最小錯誤剪枝 MEP (Minimum Error Pruning) … 降低錯誤剪 枝 REP( Reduced Error Pruning) Quinlan 獨立的剪枝集 D 基本思路 : 對于決策 樹 T 的每棵非葉子 樹 s, 用葉子替代這棵子樹 . 如 果 s 被葉子替代后形成的新樹關(guān)于 D 的誤差等于或小 于 s關(guān) 于 D 所產(chǎn)生的誤差 , 則用葉子替代子 樹 s 優(yōu) 點： 計算復(fù)雜 性低 對未知示例預(yù)測偏差較小 悲觀錯誤剪枝 PEP( Pessimistic Error Pruning ) 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 + 對 于子樹 t，誤差數(shù)： 標(biāo)準(zhǔn)錯誤 : 剪 枝條件： /z z zpe e n? ( ) /z z zpe e n??/2t s sE e le af???其 中 ,s 是 t 的 子 樹* ( )() t t tttttE N ESE ENN??其 中 , 是 當(dāng) 前 訓(xùn) 練 數(shù) 據(jù) 量 ,E 是 對 當(dāng) 前 訓(xùn) 練 數(shù) 據(jù) 錯 分 數(shù) ( )tttE E se EE? ? ?是 此 決 策 樹 對 訓(xùn) 練 集 的 錯 分 數(shù)E 見 上 面 式 子符合此條件，剪掉 t 基于錯誤剪枝 EBP(ErrorBased Pruning) Quinlan PEP的改進(jìn)（ ） 更加悲 觀 自下而上 無需獨立剪枝集 概率角度 置信區(qū)間 描 述一個隨機變量的可能的值域范疇 可能的 取值范圍 可能性：置信水平 取值范圍：置信區(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ū)間上限： ( | , ) ( , ) * * ( 1 )!( , )! * ( ) !k n kP e k n p C n k p pn nC n kk k n k?? ? ??????? ???0()()()( 1 )CFex N xxetP U C FntNC F p px???? ??????????即[ , ]CF CFLU二項式置信區(qū)間的最簡單和最常用的公式依賴于逼近二項式分布的正態(tài)分 布 Wilson score interval: ntervalNormal_approximation_interval 22 1 / 21 / 2 1 / 2 221 / 21 / 21 ( 1 )2411, , zppp z zn n nzneep p C pnnzz????????????? ? ????其 中 ,n 是 樣 本 量= 或 者 平 滑 后 的 比 如 的 實 現(xiàn) 中是 給 定 顯 著 水 平 時 ， 對 應(yīng) 的 臨 界 值 （ 查 表 ）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é)點代替 t
化學(xué)相關(guān)推薦
鄂ICP備17016276號-1