咨詢工具：決策樹算法及應(yīng)用拓展-文庫吧在線文庫
【正文】 i=s+2..k While s+1k and ns+22+log a do{ tmpCost=tmpCost+2+log ans+2 S++} Return min{C(S)+1,tmpCost} } Public(S)示例 age Car type label 16 truck high 24 sports high 32 sports Medi 34 truck low 65 family low [16,truck,high] [24,sports,high] 1+log2 1+1 1 N [65,family,low] [34,truck,low] [32,sports,medi] N 1+log2 1+log2 1 1 [16,truck,high] [24,sports,high] [32,sports,medi] [65,family,low] [34,truck,low] 1 Public(V)算法 ? 計(jì)算分類節(jié)點(diǎn)值的代價(jià)： ? 編碼葉子節(jié)點(diǎn)記錄的代價(jià) i=1..k (1) ? 在所有內(nèi)部節(jié)點(diǎn)編碼分裂節(jié)點(diǎn)值的代價(jià) (2) 總代價(jià) (1)+(2) 其中， Cj是葉子節(jié)點(diǎn) j上的主要類； M是 S+1個(gè)葉子節(jié)點(diǎn)上的主要類的集合 ??? ??????11||SjjMiiMii jSn }11:)(min{)(11?????SjjScVjScV jSj 算法比較 ? Sprint: 傳統(tǒng)的二階段“構(gòu)造－剪枝”算法 ? Public(1):用保守的估計(jì)值 1取代欲擴(kuò)展節(jié)點(diǎn)的代價(jià)下界 ? Public(S):考慮具有分裂點(diǎn)的子樹，同時(shí)計(jì)算為確定分裂節(jié)點(diǎn)及其屬性的代價(jià)下界 ? Public(V):比前者準(zhǔn)確，需計(jì)算確定結(jié)點(diǎn)上屬性值的代價(jià)下界 實(shí)驗(yàn)數(shù)據(jù) (Reallife) DataSet Canner Car Letter Satimage shuttle vehicle yeast NO_CA 0 6 0 0 0 0 0 NO_NA 9 0 16 36 9 18 8 N_Class 2 4 26 7 5 4 10 N_R(Te) 214 567 6632 2023 14500 559 1001 N_R(Tr) 496 1161 13368 4435 43500 559 1001 實(shí)驗(yàn)結(jié)果 (一 ) Dateset DS1 DS2 DS3 DS4 DS5 DS6 DS7 Sprint 21 97 3265 657 53 189 325 Public1 17 83 3215 565 53 141 237 PublicS 15 71 2979 457 53 115 169 PublicV 15 65 2875 435 53 107 163 Max rat 40% 48% 14% 51% 0% 77% 99% Nodes 9 37 1991 185 51 35 43 產(chǎn)生的節(jié)點(diǎn)數(shù)目 實(shí)驗(yàn)結(jié)果 (二 ) Dateset DS1 DS2 DS3 DS4 DS5 DS6 DS7 Sprint 5 2 Public1 6 8 1 PublicS 0 4 6 PublicV 8 3 6 Max rat 9% 0% 17% 11% 2% 2% 3% 執(zhí)行時(shí)間 (S) 算法結(jié)果分析 ? 總體上，比 Sprint算法有較大改進(jìn) ? 相對(duì)于最后的剪枝樹仍有多余的結(jié)點(diǎn)，有待改進(jìn) ? 挖掘效率與數(shù)據(jù)分布及噪聲有關(guān) 言歸正傳 —捕捉數(shù)據(jù)變化的挖掘方法 ? 新生成一棵決策樹 ? 與舊樹完全沒有關(guān)系 ? 生成一棵相關(guān)的樹 ? 未達(dá)到舊樹中葉節(jié)點(diǎn)的深度 ? 超出了舊樹中相應(yīng)節(jié)點(diǎn)的深度 ? 相同的屬性，最好的劃分 (best cut) ? 相同的屬性，相同的劃分 方法三的對(duì)應(yīng)算法 ? 使新樹與舊樹有相同的屬性和劃分，且能及早停止 ? 測(cè)試在舊樹中每個(gè)葉子節(jié)點(diǎn)的錯(cuò)誤變化的情況 ? 進(jìn)一步生成新的樹 ? 剪枝移除那些無預(yù)測(cè)特性的分枝 ? 比較新、舊樹，識(shí)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1