決策樹-上-id3c45cart及剪枝(文件)
【正文】 置信區(qū)間 描 述一個隨機變量的可能的值域范疇 可能的 取值范圍 可能性：置信水平 取值范圍：置信區(qū)間 例如： x 有 95%的可能取值在 [25,75]中 [25,75]中， 25是 置信區(qū)間下限 [25,75]中， 75是 置信區(qū)間上限 從概率角度描述 錯分樣本 率 統(tǒng) 計檢驗 概率角度 錯分樣本率 r(t)可看成是 n(t)次試驗中某事件發(fā)生 e(t)次的概率 二項分布 得到關于錯分樣本率在置信水平為 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 CFntNCF 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) 中是 給 定 顯 著 水 平 時 ， 對 應 的 臨 界 值 （ 查 表 ）EBP步驟 第一步：計算葉節(jié)點的錯分樣本率估計的置 信區(qū)間上限 U 第二步：計算葉節(jié)點的預測錯分樣本數(shù) 葉節(jié) 點的預測錯分樣本數(shù) =到達該葉節(jié)點的樣本數(shù) *該葉節(jié)點的預測錯分樣本率 U 第三步：判斷是否剪枝及如何剪枝 分別計算三種預測錯分樣本數(shù)： 計算子樹 t的所有葉節(jié)點預測錯分樣本數(shù)之和，記為 E1 計 算子樹 t被剪枝以葉節(jié)點代替時的預測錯分樣本數(shù)，記為 E2 計 算子樹 t的最大分枝的預測錯分樣本數(shù)，記為 E3 比較 E1， E2， E3，如下： E1最小時，不剪 枝 E2最小時，進行剪枝，以一個葉節(jié)點代替 t E3最小時，采用“嫁接” (grafting)策略，即用 這 個最大分枝代替 t 代價 復雜度剪枝 CCP(CostComplexity Pruning) CCP又叫 CART剪枝法 代 價 (cost) 樣本錯分率 復 雜 度 (plexity) 樹 t的葉節(jié)點數(shù) (Breiman…)定義 t的代價復雜度 (costplexity): ( ) *ttEc c t L e afNNl e af t???其 中 ， 是 決 策 樹 訓 練 樣 本 個 數(shù)E 是 決 策 樹 錯 分 樣 本 數(shù)是 子 樹 的 葉 子 樹參 數(shù) α：用于衡 量代價與復雜度之間關 系 表示剪枝后樹的復雜度降低程度與代價間的關 系 如 何定義 α? 對 t來說，剪掉它的子樹 s，以 t中最優(yōu)葉節(jié)點代替，得到新樹new_t。 C_R= CART_regression(DS_R featureList, alpha, delta) 將節(jié)點 C_L和 C_R添 加為 R的左右子 節(jié)點 CART 回歸 樹算法步驟示意 CART 后剪枝： 代 價 復雜度剪枝 CCP(CostComplexity Pruning) CART回 歸 樹 與 多 元線性回歸的區(qū)別 ： 空間劃分！非 線性 /線性 其他決策樹 Quest(quick unbiased efficient statistical tree)算法 Gini系 數(shù) SLIQ (Supervised Learning In Quest)算 法 Gini系數(shù) SPRINT (Scalable Parallelizable Induction of Classification Tree)算法 Gini系數(shù) 并行 PUBLIC(Pruning and Building Integrated in Classification)算法 Gini系數(shù) 預剪枝、 MDL剪枝算 法 CHAID(Chisquared Automatic Interaction Detector)算法 Chisquare 決策樹剪枝 數(shù)據(jù)噪音 訓練數(shù)據(jù)量少 過擬合 決策樹剪枝 預 剪 枝（前剪枝） 通過提前停止樹的構(gòu)造來對決策樹進行剪枝 一 旦停止該節(jié)點下樹的繼續(xù)構(gòu)造，該節(jié)點就成了葉 節(jié)點。 CART 分類樹 ? 節(jié)點 t的類 classify(t): c os ( | ) ( ) ( )()c os ( | ) ( ) ( )()( | )iijjiit j i p i N t Nc ost jc las si fy tt i j p j N t Nitiiijj??
黨政相關相關推薦
鄂ICP備17016276號-1