培訓(xùn)資料決策樹算法及應(yīng)用拓展(41頁)-管理培訓(xùn)(參考版)
2024-08-22 18:19本頁面
【正文】 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ì)算子樹代價(jià)下界 ? Public(1) ? 假設(shè)節(jié)點(diǎn) N的代價(jià)至少是 1 ? Public(S) S —— split ? 計(jì)算以 N為根且包含 S個(gè)分裂點(diǎn)的子樹代價(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)的子樹的代價(jià)至少是 2*S+1+S*log a+∑ ni i=s+2..k ? 證明： ?編碼樹結(jié)構(gòu)代價(jià) 2*S+1 ?確定節(jié)點(diǎn)分裂屬性的代價(jià) S*log a ?編碼 S+1個(gè)葉子結(jié)點(diǎn)的代價(jià) ∑ ni i=s+2..k Public(S)算法 (證明一 ) ? 證明：編碼 S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為 ∑ ni i=s+2..k ?相關(guān)概念： (Majority Class):if , 有 ，則 Ci為主要類 (Minority Class): if then Cj為少數(shù)類 Ci? CCk ??kjij nn ?m a jo r ityCCj ?Public(S)算法 (證明二 ) ? 題設(shè)：子樹 N有 S個(gè)分裂點(diǎn) (Split),K個(gè)類 ? S+1個(gè)葉子節(jié)點(diǎn) ? 至多有 S+1個(gè)主要類 ? 至少有 KS1個(gè)少數(shù)類 ? 取 Ci為某少數(shù)類 ,C(Sj)為編碼葉子節(jié)點(diǎn) j上記錄的代價(jià) ? ? 又有 C(S) ∑nij ? 編碼具有類 i 且位于葉子節(jié)點(diǎn) j 的記錄的代價(jià)是 nij ? 所有少數(shù)類的代價(jià) Cost= ∑ni i∈ 少數(shù)類 ???????ijijijijijij nnnnnSjEnSjC ???? ?? l o g**)(*)(2??jijnin計(jì)算 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,sports,high] 1+log2 1+1 1 N [65,family,low] [34,truck,low] [32,sports,medi] N 1+log2 1+log2 1
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1