決策樹算法及應用拓展(文件)
【正文】 log2log21log*)( 2/knknniniSC ki Γπ???? ? Cost of Encoding Tree ? 編碼樹結構本身的代價 ? 編碼每個分裂節(jié)點的代價 ? 確定分類屬性的代價 ? 確定分類屬性值的代價 其中， v是該節(jié)點上不同屬性值的個數(shù) ? 編碼每個樹葉上的記錄分類的代價 )22log( ?v)1log( ?v 剪枝算法 ? 設 N為欲計算其最小代價的節(jié)點 ? 兩種情形： ? N是葉結點 ——C(S)+1 ——Cost1 ? N是內部節(jié)點，有兩個子節(jié)點 N N2 ?已剪去 N N2， N成為葉子節(jié)點 ——Cost1 ?計算 N節(jié)點及其子樹的代價，使用遞歸過程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比較 Cost1和 Cost2，選取 代價較小者 作為返回值 計算最小子樹代價的偽代碼 Procedure ComputeCostPrune(Node N) if N 是葉子節(jié)點， 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算法 ? 一般做法：先建樹，后剪枝 ? Public算法：建樹的同時進行剪枝 ? 思想：在一定量 (用戶定義參數(shù) )的節(jié)點分裂后 /周期性的進行部分樹的剪枝 ? 存在的問題：可能高估 (OverEstimate)被剪節(jié)點的值 ? 改進：采納低估 (UnderEstimate)節(jié)點代價的策略 具體思路 ? 三種葉節(jié)點： ? 有待擴展：需計算子樹代價下界 ? 不能擴展 (純節(jié)點 ) ? 剪枝后的結點 C(S)+1 改進算法的偽代碼 Procedure ComputCostePrune(Node N) If N是仍待擴展的結點， 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) ? 假設節(jié)點 N的代價至少是 1 ? Public(S) S —— split ? 計算以 N為根且包含 S個分裂點的子樹代價的下界 (包括確定分裂節(jié)點屬性的代價 ) ? Public(V) V ——split value ? 同上，還包括確定分裂節(jié)點值的代價 Public(S)算法 (一 ) ? 相關概念 Public(S)算法 (二 ) ? 定理： ? 任何以 N為根結點且有 S個分裂點的子樹的代價至少是 2*S+1+S*log a+∑ ni i=s+2..k ? 證明： ?編碼樹結構代價 2*S+1 ?確定節(jié)點分裂屬性的代價 S*lo
試題試卷相關推薦
鄂ICP備17016276號-1