決策樹(shù)-上-id3c45cart及剪枝-文庫(kù)吧在線(xiàn)文庫(kù)
【正文】 而上 無(wú)需獨(dú)立剪枝集 概率角度 置信區(qū)間 描 述一個(gè)隨機(jī)變量的可能的值域范疇 可能的 取值范圍 可能性：置信水平 取值范圍：置信區(qū)間 例如： x 有 95%的可能取值在 [25,75]中 [25,75]中， 25是 置信區(qū)間下限 [25,75]中， 75是 置信區(qū)間上限 從概率角度描述 錯(cuò)分樣本 率 統(tǒng) 計(jì)檢驗(yàn) 概率角度 錯(cuò)分樣本率 r(t)可看成是 n(t)次試驗(yàn)中某事件發(fā)生 e(t)次的概率 二項(xiàng)分布 得到關(guān)于錯(cuò)分樣本率在置信水平為 CF的置信區(qū)間 計(jì)算置信區(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二項(xiàng)式置信區(qū)間的最簡(jiǎn)單和最常用的公式依賴(lài)于逼近二項(xiàng)式分布的正態(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 是 樣 本 量= 或 者 平 滑 后 的 比 如 的 實(shí) 現(xiàn) 中是 給 定 顯 著 水 平 時(shí) ， 對(duì) 應(yīng) 的 臨 界 值 （ 查 表 ）EBP步驟 第一步：計(jì)算葉節(jié)點(diǎn)的錯(cuò)分樣本率估計(jì)的置 信區(qū)間上限 U 第二步：計(jì)算葉節(jié)點(diǎn)的預(yù)測(cè)錯(cuò)分樣本數(shù) 葉節(jié) 點(diǎn)的預(yù)測(cè)錯(cuò)分樣本數(shù) =到達(dá)該葉節(jié)點(diǎn)的樣本數(shù) *該葉節(jié)點(diǎn)的預(yù)測(cè)錯(cuò)分樣本率 U 第三步：判斷是否剪枝及如何剪枝 分別計(jì)算三種預(yù)測(cè)錯(cuò)分樣本數(shù)： 計(jì)算子樹(shù) t的所有葉節(jié)點(diǎn)預(yù)測(cè)錯(cuò)分樣本數(shù)之和，記為 E1 計(jì) 算子樹(shù) t被剪枝以葉節(jié)點(diǎn)代替時(shí)的預(yù)測(cè)錯(cuò)分樣本數(shù)，記為 E2 計(jì) 算子樹(shù) t的最大分枝的預(yù)測(cè)錯(cuò)分樣本數(shù)，記為 E3 比較 E1， E2， E3，如下： E1最小時(shí)，不剪 枝 E2最小時(shí)，進(jìn)行剪枝，以一個(gè)葉節(jié)點(diǎn)代替 t E3最小時(shí)，采用“嫁接” (grafting)策略，即用 這 個(gè)最大分枝代替 t 代價(jià) 復(fù)雜度剪枝 CCP(CostComplexity Pruning) CCP又叫 CART剪枝法 代 價(jià) (cost) 樣本錯(cuò)分率 復(fù) 雜 度 (plexity) 樹(shù) t的葉節(jié)點(diǎn)數(shù) (Breiman…)定義 t的代價(jià)復(fù)雜度 (costplexity): ( ) *ttEc c t L e afNNl e af t???其 中 ， 是 決 策 樹(shù) 訓(xùn) 練 樣 本 個(gè) 數(shù)E 是 決 策 樹(shù) 錯(cuò) 分 樣 本 數(shù)是 子 樹(shù) 的 葉 子 樹(shù)參 數(shù) α：用于衡 量代價(jià)與復(fù)雜度之間關(guān) 系 表示剪枝后樹(shù)的復(fù)雜度降低程度與代價(jià)間的關(guān) 系 如 何定義 α? 對(duì) t來(lái)說(shuō)，剪掉它的子樹(shù) s，以 t中最優(yōu)葉節(jié)點(diǎn)代替，得到新樹(shù)new_t。39。 否則 , 剪裁 它 不需 要獨(dú)立的剪枝集 references 。 39。這種情況可以處理數(shù)據(jù)中的數(shù)據(jù)沖突問(wèn)題 ； 計(jì) 算每 次 生長(zhǎng) 對(duì) 系統(tǒng)性能的增益，如果這個(gè)增益值小于某個(gè)閾值則不進(jìn)行生長(zhǎng)。（或使用其他不純度） 對(duì)于連續(xù)值屬性，必須考慮所有可能的劃分點(diǎn)。 處 理策略： 處 理缺少屬性值的一種策略是賦給它結(jié) 點(diǎn) t所 對(duì)應(yīng)的訓(xùn)練實(shí)例中該屬性的最常見(jiàn) 值 另 外一種更復(fù)雜的策略是 為 Fi的 每個(gè)可能值賦予一個(gè)概率。 圖 示： 決策樹(shù) ID3== ID3/信息 熵 1948年，香農(nóng)提出了“信息熵”的概念，解決了對(duì)系統(tǒng)信息的量化度量問(wèn)題。通過(guò)遞歸的方式把關(guān) 于自變量的 m維空間劃分為不重疊的矩形 。但 是其屬 性 Fi的值 Fi_v未 知 。則基于 Outlook的劃分方式有 3種： 分別計(jì)算每種劃分的 Gini指標(biāo)： 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 分類(lèi)樹(shù) 對(duì) 于離散值屬性，在算法中遞歸的選擇該屬性產(chǎn)生最小 Gini指標(biāo)的子集作為它的
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1