培訓(xùn)資料決策樹算法及應(yīng)用拓展(41頁)-管理培訓(xùn)(編輯修改稿)
2024-09-23 18:19 本頁面
【文章內(nèi)容簡介】 )2/(l o g2l o g21l o g*)( 2/knknniniSC ki Γπ???? ?Cost of Encoding Tree ? 編碼樹結(jié)構(gòu)本身的代價 ? 編碼每個分裂節(jié)點(diǎn)的代價 ? 確定分類屬性的代價 ? 確定分類屬性值的代價 amp。 其中， v是該節(jié)點(diǎn)上不同屬性值的個數(shù) ? 編碼每個樹葉上的記錄分類的代價 )22lo g ( ?v)1log ( ?v剪枝算法 ? 設(shè) N為欲計(jì)算其最小代價的節(jié)點(diǎn) ? 兩種情形： ? N是葉結(jié)點(diǎn) ——C(S)+1 ——Cost1 ? N是內(nèi)部節(jié)點(diǎn)，有兩個子節(jié)點(diǎn) N N2 ?已剪去 N N2， N成為葉子節(jié)點(diǎn) ——Cost1 ?計(jì)算 N節(jié)點(diǎn)及其子樹的代價，使用遞歸過程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比較 Cost1和 Cost2，選取 代價較小者 作為返回值 計(jì)算最小子樹代價的偽代碼 Procedure ComputeCostamp。Prune(Node N) if N 是葉子節(jié)點(diǎn)， return (C(S)+1) minCost1= Computeamp。Prune(Node N1) minCost2= Computeamp。Prune(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算法 ? 一般做法：先建樹，后剪枝 ? Public算法：建樹的同時進(jìn)行剪枝 ? 思想：在一定量 (用戶定義參數(shù) )的節(jié)點(diǎn)分裂后 /周期性的進(jìn)行部分樹的剪枝 ? 存在的問題：可能高估 (OverEstimate)被剪節(jié)點(diǎn)的值 ? 改進(jìn)：采納低估 (UnderEstimate)節(jié)點(diǎn)代價的策略 具體思路 ? 三種葉節(jié)點(diǎn)： ? 有待擴(kuò)展：需計(jì)算子樹代價下界 ? 不能擴(kuò)展 (純節(jié)點(diǎn) ) ? 剪枝后的結(jié)點(diǎn) C(S)+1 改進(jìn)算法的偽代碼 Procedure ComputCosteamp。Prune(Node N) If N是仍待擴(kuò)展的結(jié)點(diǎn)， return N節(jié)點(diǎn)的代價下界 If N是純節(jié)點(diǎn)或不可擴(kuò)展的葉節(jié)點(diǎn) ， return (C(S)+1) 兩個子節(jié)點(diǎn) N N2 minCost1= Computeamp。Prune(Node N1) minCost2= Computeamp。Prune(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ì)算子樹代價下界 ? Public(1) ? 假設(shè)節(jié)點(diǎn) N的代價至少是 1 ? Public(S) S —— split ? 計(jì)算以 N為根且包含 S個分裂點(diǎn)的子樹代價的下界 (包括確定分裂節(jié)點(diǎn)屬性的代價 ) ? Public(V) V ——split value ? 同上，還包括確定分裂節(jié)點(diǎn)值的代價 Public(S)算法 (一 ) ? 相關(guān)概念 Public(S)算法 (二 ) ? 定理： ? 任何以 N為根結(jié)點(diǎn)且有 S個分裂點(diǎn)的子樹的代價至少是 2*S+1+S*log a+∑ ni i=s+2..k ? 證明： ?編碼樹結(jié)構(gòu)代價 2*S+
高考資料相關(guān)推薦
鄂ICP備17016276號-1