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