培訓資料決策樹算法及應用拓展(41頁)-管理培訓-資料下載頁
2025-08-09 18:19本頁面
【導讀】傳統(tǒng)挖掘方法的局限性。只重視從數據庫中提取規(guī)則，忽視了庫中。挖掘所用的數據來自穩(wěn)定的環(huán)境，人為干。捕捉新舊數據變化的目的：。阻止/延緩不利變化的發(fā)生。差異挖掘算法的主要思想：。合理比較新/舊數據的挖掘結果，并清晰的。每個分叉都是分割的一個部分。決策樹生成算法分成兩個步驟。去掉一些可能是噪音或者異常的數據。按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點。自上而下分而治之的方法。屬性都是種類字段。屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量。能夠適用于種類和數值字段。Ci為某分類標號，Pi為任意樣本屬于Ci的概率，由A劃分為子集的熵：。A為屬性，具有V個不同的取值。信息增益：Gain=I(s1,s2,……集合T包含N個類別的記錄，那么其Gini指標就是。消除決策樹的過適應問題。最小描述長度原則。期望錯誤率最小原則。確定分類屬性的代價
【正文】 j算法比較 ? Sprint: 傳統(tǒng)的二階段“構造－剪枝”算法 ? Public(1):用保守的估計值 1取代欲擴展節(jié)點的代價下界 ? Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界 ? Public(V):比前者準確，需計算確定結點上屬性值的代價下界 實驗數據 (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 2020 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 產生的節(jié)點數目 實驗結果 (二 ) Dateset DS1 DS2 DS3 DS4 DS5 DS6 DS7 Sprint Public1 PublicS PublicV Max rat 9% 0% 17% 11% 2% 2% 3% 執(zhí)行時間 (S) 算法結果分析 ? 總體上，比 Sprint算法有較大改進 ? 相對于最后的剪枝樹仍有多余的結點，有待改進 ? 挖掘效率與數據分布及噪聲有關 言歸正傳 —捕捉數據變化的挖掘方法 ? 新生成一棵決策樹 ? 與舊樹完全沒有關系 ? 生成一棵相關的樹 ? 未達到舊樹中葉節(jié)點的深度 ? 超出了舊樹中相應節(jié)點的深度 ? 相同的屬性，最好的劃分 (best cut) ? 相同的屬性，相同的劃分 方法三的對應算法 ? 使新樹與舊樹有相同的屬性和劃分，且能及早停止 ? 測試在舊樹中每個葉子節(jié)點的錯誤變化的情況 ? 進一步生成新的樹 ? 剪枝移除那些無預測特性的分枝 ? 比較新、舊樹，識別變化部分 標識幾種不同的變化類型 ? 區(qū)域的連接：舊樹中的劃分不必要 ? 邊界的移動：舊樹中的劃分移到了新的位置 ? 進一步細化 (Refinement):舊樹中的葉結點不足以描述新生成數據 ? 類標號變化：舊樹中的節(jié)點類標號發(fā)生了變化 ? 錯誤率 的變化 ? 覆蓋率 的變化：某個節(jié)點具有的數據量的比率 小結 ? Building Decision Tree算法 ? Pruning Decision Tree算法 ? Public 算法 ? Public(1)算法 ? Public(s)算法 ? Public(v)算法 ? 識別數據變化的挖掘算法 個人觀點 計算分裂點屬性代價下界的算法代碼 2?sn2?snProcedure ComputeMinCostS(Node N) If K=1 return (C(S)+1) S=1 tmpCost=2*S+1+S*log a +∑ni i=s+1..k While S+1k and 2+log a do{ tmpCost=tmpCost+2+log a – s++ } Return min {C(S)+1,tmpCost } }
高考資料相關推薦
鄂ICP備17016276號-1