決策樹(shù)算法及其應(yīng)用(ppt 41頁(yè)).ppt

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