決策樹(shù)算法及應(yīng)用拓展(編輯修改稿)
2025-02-01 19:43 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 og2log21log*)( 2/knknniniSC ki Γπ???? ? Cost of Encoding Tree ? 編碼樹(shù)結(jié)構(gòu)本身的代價(jià) ? 編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià) ? 確定分類(lèi)屬性的代價(jià) ? 確定分類(lèi)屬性值的代價(jià) 其中， v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù) ? 編碼每個(gè)樹(shù)葉上的記錄分類(lèi)的代價(jià) )22log( ?v)1log( ?v 剪枝算法 ? 設(shè) N為欲計(jì)算其最小代價(jià)的節(jié)點(diǎn) ? 兩種情形： ? N是葉結(jié)點(diǎn) ——C(S)+1 ——Cost1 ? N是內(nèi)部節(jié)點(diǎn)，有兩個(gè)子節(jié)點(diǎn) N N2 ?已剪去 N N2， N成為葉子節(jié)點(diǎn) ——Cost1 ?計(jì)算 N節(jié)點(diǎn)及其子樹(shù)的代價(jià)，使用遞歸過(guò)程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比較 Cost1和 Cost2，選取 代價(jià)較小者 作為返回值 計(jì)算最小子樹(shù)代價(jià)的偽代碼 Procedure ComputeCostPrune(Node N) if N 是葉子節(jié)點(diǎn)， return (C(S)+1) 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 引入 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*
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1