咨詢工具：決策樹(shù)算法及應(yīng)用拓展(編輯修改稿)
2025-02-14 01:11 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 return minCostN 引入 Public算法 ? 一般做法：先建樹(shù)，后剪枝 ? Public算法：建樹(shù)的同時(shí)進(jìn)行剪枝 ? 思想：在一定量 (用戶定義參數(shù) )的節(jié)點(diǎn)分裂后 /周期性的進(jìn)行部分樹(shù)的剪枝 ? 存在的問(wèn)題：可能高估 (OverEstimate)被剪節(jié)點(diǎn)的值 ? 改進(jìn)：采納低估 (UnderEstimate)節(jié)點(diǎn)代價(jià)的策略 具體思路 ? 三種葉節(jié)點(diǎn)： ? 有待擴(kuò)展：需計(jì)算子樹(shù)代價(jià)下界 ? 不能擴(kuò)展 (純節(jié)點(diǎn) ) ? 剪枝后的結(jié)點(diǎn) C(S)+1 改進(jìn)算法的偽代碼 Procedure ComputCostePrune(Node N) If N是仍待擴(kuò)展的結(jié)點(diǎn)， return N節(jié)點(diǎn)的代價(jià)下界 If N是純節(jié)點(diǎn)或不可擴(kuò)展的葉節(jié)點(diǎn) ， return (C(S)+1) 兩個(gè)子節(jié)點(diǎn) N N2 minCost1= ComputePrune(Node N1) minCost2= ComputePrune(Node N2) minCostN=min{C(S)+1,Csplit(N)+1+minCost1 +minCost2} if minCostN=C(S)+1 Prune child nodes N1 and N2 return minCostN 計(jì)算子樹(shù)代價(jià)下界 ? Public(1) ? 假設(shè)節(jié)點(diǎn) N的代價(jià)至少是 1 ? Public(S) S —— split ? 計(jì)算以 N為根且包含 S個(gè)分裂點(diǎn)的子樹(shù)代價(jià)的下界 (包括確定分裂節(jié)點(diǎn)屬性的代價(jià) ) ? Public(V) V ——split value ? 同上，還包括確定分裂節(jié)點(diǎn)值的代價(jià) Public(S)算法 (一 ) ? 相關(guān)概念 Public(S)算法 (二 ) ? 定理： ? 任何以 N為根結(jié)點(diǎn)且有 S個(gè)分裂點(diǎn)的子樹(shù)的代價(jià)至少是 2*S+1+S*log a+∑ ni i=s+2..k ? 證明： ?編碼樹(shù)結(jié)構(gòu)代價(jià) 2*S+1 ?確定節(jié)點(diǎn)分裂屬性的代價(jià) S*log a ?編碼 S+1個(gè)葉子結(jié)點(diǎn)的代價(jià) ∑ ni i=s+2..k Public(S)算法 (證明一 ) ? 證明：編碼 S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為 ∑ ni i=s+2..k ?相關(guān)概念： (Majority Class):if , 有 ，則 Ci為主要類 (Minority Class): if then Cj為少數(shù)類 Ci? CCk ?? kjij nn ? ma jori tyCCj ? Public(S)算法 (證明二 ) ? 題設(shè)：子樹(shù) N有 S個(gè)分裂點(diǎn) (Split),K個(gè)類 ? S+1個(gè)葉子節(jié)點(diǎn) ? 至多有 S+1個(gè)主要類 ? 至少有 KS1個(gè)少數(shù)類 ? 取 Ci為某少數(shù)類 ,C(Sj)為編碼葉子節(jié)點(diǎn) j上記錄的代價(jià) ? ? 又有 C(S) ∑nij ? 編碼具有類 i 且位于葉子節(jié)點(diǎn) j 的記錄的代價(jià)是 nij ? 所有少數(shù)類的代價(jià) Cost= ∑ni i∈ 少數(shù)類 ???? ijijijijijij nnnnnSjEnSjC ???? ?? log**)(*)(2?? j ijnin 計(jì)算 minCost_S的代碼 Procedure puteMinCostS(Node N) If k=1 return (C(S)+1) S=1 tmpCost=2*S+1+S*log a +∑i ni 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,sport
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1