咨詢工具：決策樹算法及應用拓展-在線瀏覽
2025-02-28 01:11本頁面
【正文】 要類 ? 至少有 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:)(min{)(11?????SjjScVjScV jSj 算法比較 ? Sprint: 傳統(tǒng)的二階段“構造－剪枝”算法 ? Public(1):用保守的估計值 1取代欲擴展節(jié)點的代價下界 ? Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界 ? Public(V):比前者準確，需計算確定結點上屬性值的代價下界 實驗數(shù)據(jù) (Reallife) DataSet Canner Car Letter Satimage shuttle vehicle yeast NO_CA 0 6 0 0 0 0 0 NO_NA 9 0 16 36 9 18 8 N_Class 2 4 26 7 5 4 10 N_R(Te) 214 567 6632 2023 14500 559 1001 N_R(Tr) 496 1161 13368 4435 43500 559 1001 實驗結果 (一 ) Dateset DS1 DS2 DS3 DS4 DS5 DS6 DS7 Sprint 21 97 3265 657 53 189 325 Public1 17 83 3215 565 53 141 237 PublicS 15 71 2979 457 53 115 169 PublicV 15 65 2875 435 53 107 163 Max rat 40% 48% 14% 51% 0% 77% 99% Nodes 9 37 1991 185 51 35 43 產(chǎn)生的節(jié)點數(shù)目 實驗結果 (二 ) Dateset DS1 DS2 DS3 DS4 DS5 DS6 DS7 Sprint 5 2 Public1 6 8 1
教學課件相關推薦
鄂ICP備17016276號-1