決策樹-上-id3c45cart及剪枝-文庫吧在線文庫
【正文】 而上 無需獨立剪枝集 概率角度 置信區(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 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ù) α：用于衡 量代價與復雜度之間關(guān) 系 表示剪枝后樹的復雜度降低程度與代價間的關(guān) 系 如 何定義 α? 對 t來說，剪掉它的子樹 s，以 t中最優(yōu)葉節(jié)點代替，得到新樹new_t。39。 否則 , 剪裁 它 不需 要獨立的剪枝集 references 。 39。這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問題 ； 計 算每 次 生長 對 系統(tǒng)性能的增益，如果這個增益值小于某個閾值則不進行生長。（或使用其他不純度） 對于連續(xù)值屬性，必須考慮所有可能的劃分點。 處 理策略： 處 理缺少屬性值的一種策略是賦給它結(jié) 點 t所 對應的訓練實例中該屬性的最常見 值 另 外一種更復雜的策略是 為 Fi的 每個可能值賦予一個概率。 圖 示： 決策樹 ID3== ID3/信息 熵 1948年，香農(nóng)提出了“信息熵”的概念，解決了對系統(tǒng)信息的量化度量問題。通過遞歸的方式把關(guān) 于自變量的 m維空間劃分為不重疊的矩形 。但 是其屬 性 Fi的值 Fi_v未 知 。則基于 Outlook的劃分方式有 3種： 分別計算每種劃分的 Gini指標： 32 3( 2 2) / 2 = 3? ?? ?? ?, ,( { } { }2 2 2 2, ,){}( { } )( { } , )()95= ( ) ( )14 149 6 3 5 2 3( 1 ( ( ) ( ) ) ) ( 1 ( ( ) ( ) ) )14 9 9 14 5 5 10() .3571(sun ny ov e rc ast rainsun ny ov e rc ast rainsun n ov e rc astov e rc asty rainsun ny rainG ini SG ini S G ini SG iniG iniS????? ? ? ? ? ???劃 分劃 分劃 分0. 7) 393S ?選擇劃分 CART 分類樹 對 于離散值屬性，在算法中遞歸的選擇該屬性產(chǎn)生最小 Gini指標的子集作為它的
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1