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