決策樹算法及應(yīng)用拓展(完整版)
【正文】 g 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 jo ri 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,sports,high] 1+log2 1+1 1 N [65,family,low] [34,truck,low] [32,sports,medi] N 1+log2 1+log2 1 1 [16,truck,high] [24,sports,high] [32,sports,medi] [65,family,low] [34,truck,low] 1 Public(V)算法 ? 計算分類節(jié)點值的代價： ? 編碼葉子節(jié)點記錄的代價 i=1..k (1) ? 在所有內(nèi)部節(jié)點編碼分裂節(jié)點值的代價 (2) 總代價 (1)+(2) 其中， Cj是葉子節(jié)點 j上的主要類； M是 S+1個葉子節(jié)點上的主要類的集合 ??? ??????11||SjjMiiMii jSn }11:)(m in{)(11?????SjjScVjScV jSj 算法比較 ? Sprint: 傳統(tǒng)的二階段“構(gòu)造－剪
試題試卷相關(guān)推薦
鄂ICP備17016276號-1