決策樹算法及應用拓展 內容簡介 概述預備知識決策樹生成 BuildingDecisionTree 決策樹剪枝 PruningDecisionTree 捕捉變化數據的挖掘方法小結 概述 一 傳統挖掘方法的局限性只重視從數據庫中提取規則 忽視了庫中數據的變化挖掘所用的數據來自穩定的環境 人為干預較少 概述 二 捕捉新舊數據變化的目的 挖掘出變化的趨勢例 啤酒 尿布阻止 延緩不利變化的發生例 金融危機 銀行的信貸策略差異挖掘算法的主要思想 合理比較新 舊數據的挖掘結果 并清晰的描述其變化部分 預備知識一 BuildingTree 基本思想 用途 提取分類規則 進行分類預測 使用決策樹進行分類 決策樹一個樹性的結構內部節點上選用一個屬性進行分割每個分叉都是分割的一個部分葉子節點表示一個分布決策樹生成算法分成兩個步驟樹的生成開始 數據都在根節點遞歸的進行數據分片樹的修剪去掉一些可能是噪音或者異常的數據決策樹使用 對未知數據進行分割按照決策樹上采用的分割屬性逐層往下 直到一個葉子節點 決策樹算法 基本算法 貪心算法 自上而下分而治之的方法開始時 所有的數據都在根節點屬性都是種類字段 如果是連續的 將其離散化 所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發式規則或者一個統計的度量 如 informationgain 停止分割的條件一個節點上的數據都是屬于同一個類別沒有屬性可以再用于對數據進行分割 偽代碼 BuildingTree ProcedureBuildTree S 用數據集S初始化根節點R用根結點R初始化隊列QWhileQisnotEmptydo 取出隊列Q中的第一個節點NifN不純 Pure for每一個屬性A估計該節點在A上的信息增益選出最佳的屬性 將N分裂為N1 N2 屬性選擇的統計度量 信息增益 Informationgain ID3 C4 5 所有屬性假設都是種類字段經過修改之后可以適用于數值字段基尼指數 Giniindex IBMIntelligentMiner 能夠適用于種類和數值字段 信息增益度度量 ID3 C4 5 任意樣本分類的期望信息 I s1 s2 sm Pilog2 pi i 1 m 其中 數據集為S m為S的分類數目 PiCi為某分類標號 Pi為任意樣本屬于Ci的概率 si為分類Ci上的樣本數由A劃分為子集的熵 E A s1j smj s I s1j smj A為屬性 具有V個不同的取值信息增益 Gain A I s1 s2 sm E A 訓練集 舉例 ID3算法 使用信息增益進行屬性選擇 ClassP buys computer yes ClassN buys computer no I p n I 9 5 0 940Computetheentropyforage HenceSimilarly DecisionTree 結果輸出 age overcast student creditrating no yes fair excellent 30 40 no no yes yes yes 30 40 基尼指數GiniIndex IBMIntelligentMiner 集合T包含N個類別的記錄 那么其Gini指標就是pj類別j出現的頻率如果集合T分成兩部分N1andN2 那么這個分割的Gini就是提供最小Ginisplit就被選擇作為分割的標準 對于每個屬性都要遍歷所有可以的分割方法 預備知識二 PruningTree 目的 消除決策樹的過適應 OverFitting 問題實質 消除訓練集中的異常和噪聲兩種方法 先剪枝法 Public算法 后剪枝法 Sprint算法 兩種剪枝標準 最小描述長度原則 MDL 思想 最簡單的解釋最期望的做法 對Decision Tree進行二進位編碼 編碼所需二進位最少的樹即為 最佳剪枝樹 期望錯誤率最小原則思想 選擇期望錯誤率最小的子樹進行剪枝對樹中的內部節點計算其剪枝 不剪枝可能出現的期望錯誤率 比較后加以取舍 CostofEncodingDataRecords 對n條記錄進行分類編碼的代價 2種方法 n 記錄數 k 類數目 ni 屬于類i的記錄數 CostofEncodingTree 編碼樹結構本身的代價編碼每個分裂節點的代價確定分類屬性的代價確定分類屬性值的代價 其中 v是該節點上不同屬性值的個數編碼每個樹葉上的記錄分類的代價 剪枝算法 設N為欲計算其最小代價的節點兩種情形 N是葉結點 C S 1 Cost1N是內部節點 有兩個子節點N1 N2已剪去N1 N2 N成為葉子節點 Cost1計算N節點及其子樹的代價 使用遞歸過程Csplit N 1 minCost1 minCost2 Cost2比較Cost1和Cost2 選取代價較小者作為返回值 計算最小子樹代價的偽代碼 ProcedureComputeCost Prune NodeN ifN是葉子節點 return C S 1 minCost1 Compute Prune NodeN1 minCost2 Compute Prune NodeN2 minCostN min C S 1 Csplit N 1 minCost1 minCost2 ifminCostN C S 1PrunechildnodesN1andN2returnminCostN 引入Public算法 一般做法 先建樹 后剪枝Public算法 建樹的同時進行剪枝思想 在一定量 用戶定義參數 的節點分裂后 周期性的進行部分樹的剪枝存在的問題 可能高估 Over Estimate 被剪節點的值改進 采納低估 Under Estimate 節點代價的策略 具體思路 三種葉節點 有待擴展 需計算子樹代價下界不能擴展 純節點 剪枝后的結點 C S 1 改進算法的偽代碼 ProcedureComputCoste Prune NodeN IfN是仍待擴展的結點 returnN節點的代價下界IfN是純節點或不可擴展的葉節點 return C S 1 兩個子節點N1 N2minCost1 Compute Prune NodeN1 minCost2 Compute Prune NodeN2 minCostN min C S 1 Csplit N 1 minCost1 minCost2 ifminCostN C S 1PrunechildnodesN1andN2returnminCostN 計算子樹代價下界 Public 1 假設節點N的代價至少是1Public S S split計算以N為根且包含S個分裂點的子樹代價的下界 包括確定分裂節點屬性的代價 Public V V splitvalue同上 還包括確定分裂節點值的代價 Public S 算法 一 相關概念 Public S 算法 二 定理 任何以N為根結點且有S個分裂點的子樹的代價至少是2 S 1 S loga nii s 2 k證明 編碼樹結構代價2 S 1確定節點分裂屬性的代價S loga編碼S 1個葉子結點的代價 nii s 2 k Public S 算法 證明一 證明 編碼S 1個葉子節點的代價至少為 nii s 2 k相關概念 1 主要類 MajorityClass if 有 則Ci為主要類2 少數類 MinorityClass ifthenCj為少數類 Public S 算法 證明二 題設 子樹N有S個分裂點 Split K個類S 1個葉子節點至多有S 1個主要類至少有K S 1個少數類取Ci為某少數類 C Sj 為編碼葉子節點j上記錄的代價又有C S nij編碼具有類i且位于葉子節點j的記錄的代價是nij所有少數類的代價Cost nii 少數類 計算minCost S的代碼 ProcedurecomputeMinCostS NodeN Ifk 1return C S 1 S 1tmpCost 2 S 1 S loga inii s 2 kWhiles 12 logado tmpCost tmpCost 2 loga ns 2S Returnmin C S 1 tmpCost Public S 示例 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 算法 計算分類節點值的代價 編碼葉子節點記錄的代價i 1 k 1 在所有內部節點編碼分裂節點值的代價 2 總代價 1 2 其中 Cj是葉子節點j上的主要類 M是S 1個葉子節點上的主要類的集合 算法比較 Sprint 傳統的二階段 構造 剪枝 算法Public 1 用保守的估計值1取代欲擴展節點的代價下界Public S 考慮具有分裂點的子樹 同時計算為確定分裂節點及其屬性的代價下界Public V 比前者準確 需計算確定結點上屬性值的代價下界 實驗數據 Real life 實驗結果 一 產生的節點數目 實驗結果 二 執行時間 S 算法結果分析 總體上 比Sprint算法有較大改進相對于最后的剪枝樹仍有多余的結點 有待改進挖掘效率與數據分布及噪聲有關 言歸正傳 捕捉數據變化的挖掘方法 新生成一棵決策樹與舊樹完全沒有關系生成一棵相關的樹未達到舊樹中葉節點的深度超出了舊樹中相應節點的深度相同的屬性 最好的劃分 bestcut 相同的屬性 相同的劃分 方法三的對應算法 使新樹與舊樹有相同的屬性和劃分 且能及早停止測試在舊樹中每個葉子節點的錯誤變化的情況進一步生成新的樹剪枝移除那些無預測特性的分枝比較新 舊樹 識別變化部分 標識幾種不同的變化類型 區域的連接 舊樹中的劃分不必要邊界的移動 舊樹中的劃分移到了新的位置進一步細化 Refinement 舊樹中的葉結點不足以描述新生成數據類標號變化 舊樹中的節點類標號發生了變化錯誤率的變化覆蓋率的變化 某個節點具有的數據量的比率 小結 BuildingDecisionTree算法PruningDecisionTree算