決策樹算法及應用拓展(編輯修改稿)
2025-08-28 16:30 本頁面
【文章內(nèi)容簡介】 l o g21l o g*)( 2/knknniniSC ki Γπ???? ?Cost of Encoding Tree ? 編碼樹結(jié)構(gòu)本身的代價 ? 編碼每個分裂節(jié)點的代價 – 確定分類屬性的代價 – 確定分類屬性值的代價 amp。 其中， v是該節(jié)點上丌同屬性值的個數(shù) ? 編碼每個樹葉上的記錄分類的代價 )22lo g ( ?v)1log ( ?v剪枝算法 ? 設 N為欲計算其最小代價的節(jié)點 ? 兩種情形： – N是葉結(jié)點 ——C(S)+1 ——Cost1 – N是內(nèi)部節(jié)點，有兩個子節(jié)點 N N2 ? 已剪去 N N2， N成為葉子節(jié)點 ——Cost1 ? 計算 N節(jié)點及其子樹的代價，使用遞歸過程 Csplit(N)+1+minCost1+minCost2 ——Cost2 比較 Cost1和 Cost2，選取 代價較小者 作為返回值 計算最小子樹代價的偽代碼 Procedure ComputeCostamp。Prune(Node N) if N 是葉子節(jié)點， 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算法：建樹的同時迚行剪枝 – 思想：在一定量 (用戶定義參數(shù) )的節(jié)點分裂后 /周期性的迚行部分樹的剪枝 – 存在的問題：可能高估 (OverEstimate)被剪節(jié)點的值 – 改迚：采納低估 (UnderEstimate)節(jié)點代價的策略 具體思路 ? 三種葉節(jié)點： – 有待擴展：需計算子樹代價下界 – 丌能擴展 (純節(jié)點 ) – 剪枝后的結(jié)點 C(S)+1 改進算法的偽代碼 Procedure ComputCosteamp。Prune(Node N) If N是仍待擴展的結(jié)點， return N節(jié)點的代價下界 If N是純節(jié)點或丌可擴展的葉節(jié)點 ， return (C(S)+1) 兩個子節(jié)點 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 計算子樹代價下界 ? Public(1) – 假設節(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
畢業(yè)設計相關(guān)推薦
鄂ICP備17016276號-1