決策樹算法及應(yīng)用拓展

決策樹算法及應(yīng)用拓展第1頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月概述(一)傳統(tǒng)挖掘方法的局限性只重視從數(shù)據(jù)庫(kù)中提取規(guī)則，忽視了庫(kù)中數(shù)據(jù)的變化挖掘所用的數(shù)據(jù)來自穩(wěn)定的環(huán)境，人為干預(yù)較少第2頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月概述(二)捕捉新舊數(shù)據(jù)變化的目的：挖掘出變化的趨勢(shì)例：啤酒——尿布阻止/延緩不利變化的發(fā)生例：金融危機(jī)——銀行的信貸策略差異挖掘算法的主要思想：合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分第3頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月預(yù)備知識(shí)一(BuildingTree)基本思想：用途：提取分類規(guī)則，進(jìn)行分類預(yù)測(cè)判定樹分類算法output訓(xùn)練集決策樹input第4頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月使用決策樹進(jìn)行分類決策樹一個(gè)樹性的結(jié)構(gòu)內(nèi)部節(jié)點(diǎn)上選用一個(gè)屬性進(jìn)行分割每個(gè)分叉都是分割的一個(gè)部分葉子節(jié)點(diǎn)表示一個(gè)分布決策樹生成算法分成兩個(gè)步驟樹的生成開始，數(shù)據(jù)都在根節(jié)點(diǎn)遞歸的進(jìn)行數(shù)據(jù)分片樹的修剪去掉一些可能是噪音或者異常的數(shù)據(jù)決策樹使用:對(duì)未知數(shù)據(jù)進(jìn)行分割按照決策樹上采用的分割屬性逐層往下，直到一個(gè)葉子節(jié)點(diǎn)第5頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)屬性都是種類字段(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進(jìn)行分割屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量(如,informationgain)停止分割的條件一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別沒有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割第6頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月偽代碼(BuildingTree)ProcedureBuildTree(S)

用數(shù)據(jù)集S初始化根節(jié)點(diǎn)R

用根結(jié)點(diǎn)R初始化隊(duì)列Q WhileQisnotEmptydo{

取出隊(duì)列Q中的第一個(gè)節(jié)點(diǎn)N ifN不純(Pure){ for每一個(gè)屬性A

估計(jì)該節(jié)點(diǎn)在A上的信息增益 選出最佳的屬性，將N分裂為N1、N2 } }第7頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月屬性選擇的統(tǒng)計(jì)度量信息增益——Informationgain(ID3/C4.5)所有屬性假設(shè)都是種類字段經(jīng)過修改之后可以適用于數(shù)值字段基尼指數(shù)——Giniindex

(IBMIntelligentMiner)能夠適用于種類和數(shù)值字段第8頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，PiCi為某分類標(biāo)號(hào)，Pi為任意樣本屬于Ci的概率，si為分類Ci上的樣本數(shù)由A劃分為子集的熵：E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A為屬性，具有V個(gè)不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)第9頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月訓(xùn)練集(舉例)ID3算法第10頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月使用信息增益進(jìn)行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly第11頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月DecisionTree(結(jié)果輸出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40第12頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月基尼指數(shù)GiniIndex(IBMIntelligentMiner)集合T包含N個(gè)類別的記錄，那么其Gini指標(biāo)就是

pj

類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2

。那么這個(gè)分割的Gini就是提供最小Ginisplit

就被選擇作為分割的標(biāo)準(zhǔn)(對(duì)于每個(gè)屬性都要遍歷所有可以的分割方法).第13頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月預(yù)備知識(shí)二(PruningTree)目的：消除決策樹的過適應(yīng)(OverFitting)問題實(shí)質(zhì)：消除訓(xùn)練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)第14頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月兩種剪枝標(biāo)準(zhǔn)最小描述長(zhǎng)度原則(MDL)思想：最簡(jiǎn)單的解釋最期望的做法：對(duì)Decision-Tree進(jìn)行二進(jìn)位編碼，編碼所需二進(jìn)位最少的樹即為“最佳剪枝樹”期望錯(cuò)誤率最小原則思想：選擇期望錯(cuò)誤率最小的子樹進(jìn)行剪枝對(duì)樹中的內(nèi)部節(jié)點(diǎn)計(jì)算其剪枝/不剪枝可能出現(xiàn)的期望錯(cuò)誤率，比較后加以取舍第15頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月CostofEncodingDataRecords對(duì)n條記錄進(jìn)行分類編碼的代價(jià)(2種方法)n——記錄數(shù)，k——類數(shù)目，ni——屬于類i的記錄數(shù)第16頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月CostofEncodingTree編碼樹結(jié)構(gòu)本身的代價(jià)編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià)確定分類屬性的代價(jià)確定分類屬性值的代價(jià)

&其中，v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù)編碼每個(gè)樹葉上的記錄分類的代價(jià)第17頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月剪枝算法設(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)及其子樹的代價(jià)，使用遞歸過程

Csplit(N)+1+minCost1+minCost2——Cost2

比較Cost1和Cost2，選取代價(jià)較小者作為返回值第18頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月計(jì)算最小子樹代價(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第19頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月引入Public算法一般做法：先建樹，后剪枝Public算法：建樹的同時(shí)進(jìn)行剪枝思想：在一定量(用戶定義參數(shù))的節(jié)點(diǎn)分裂后/周期性的進(jìn)行部分樹的剪枝存在的問題：可能高估(Over-Estimate)被剪節(jié)點(diǎn)的值改進(jìn)：采納低估(Under-Estimate)節(jié)點(diǎn)代價(jià)的策略第20頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月具體思路三種葉節(jié)點(diǎn)：有待擴(kuò)展：需計(jì)算子樹代價(jià)下界不能擴(kuò)展(純節(jié)點(diǎn))剪枝后的結(jié)點(diǎn)C(S)+1第21頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月改進(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第22頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月計(jì)算子樹代價(jià)下界Public(1)假設(shè)節(jié)點(diǎn)N的代價(jià)至少是1Public(S)S——split計(jì)算以N為根且包含S個(gè)分裂點(diǎn)的子樹代價(jià)的下界(包括確定分裂節(jié)點(diǎn)屬性的代價(jià))Public(V)V——splitvalue同上，還包括確定分裂節(jié)點(diǎn)值的代價(jià)第23頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(S)算法(一)相關(guān)概念第24頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(S)算法(二)定理：任何以N為根結(jié)點(diǎn)且有S個(gè)分裂點(diǎn)的子樹的代價(jià)至少是2*S+1+S*loga+∑nii=s+2..k證明：編碼樹結(jié)構(gòu)代價(jià)2*S+1確定節(jié)點(diǎn)分裂屬性的代價(jià)S*loga編碼S+1個(gè)葉子結(jié)點(diǎn)的代價(jià)∑nii=s+2..k第25頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(S)算法(證明一)證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為∑nii=s+2..k相關(guān)概念：1.主要類(MajorityClass):if,有，則Ci為主要類2.少數(shù)類(MinorityClass):ifthenCj為少數(shù)類第26頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(S)算法(證明二)題設(shè)：子樹N有S個(gè)分裂點(diǎn)(Split),K個(gè)類

S+1個(gè)葉子節(jié)點(diǎn)至多有S+1個(gè)主要類至少有K-S-1個(gè)少數(shù)類取Ci為某少數(shù)類,C(Sj)為編碼葉子節(jié)點(diǎn)j上記錄的代價(jià)

又有C(S)>∑nij

編碼具有類i

且位于葉子節(jié)點(diǎn)j

的記錄的代價(jià)是nij

所有少數(shù)類的代價(jià)Cost=∑nii∈少數(shù)類第27頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月計(jì)算minCost_S的代碼ProcedurecomputeMinCostS(NodeN)Ifk=1return(C(S)+1)S=1tmpCost=2*S+1+S*loga+∑inii=s+2..k

Whiles+1<kandns+2>2+logado{tmpCost=tmpCost+2+loga-ns+2S++}Returnmin{C(S)+1,tmpCost}}第28頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(S)示例

ageCartype

label

16

truck

high

24

sports

high

32

sportsMedi

34

truck

low

65

family

low[16,truck,high][24,sports,high]1+log21+11N[65,family,low][34,truck,low][32,sports,medi]N1+log21+log211[16,truck,high][24,sports,high][32,sports,medi][65,family,low][34,truck,low]1第29頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月Public(V)算法計(jì)算分類節(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上的主要類；M是S+1個(gè)葉子節(jié)點(diǎn)上的主要類的集合第30頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法Public(1):用保守的估計(jì)值1取代欲擴(kuò)展節(jié)點(diǎn)的代價(jià)下界Public(S):考慮具有分裂點(diǎn)的子樹，同時(shí)計(jì)算為確定分裂節(jié)點(diǎn)及其屬性的代價(jià)下界Public(V):比前者準(zhǔn)確，需計(jì)算確定結(jié)點(diǎn)上屬性值的代價(jià)下界第31頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSetCanner

CarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001第32頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月實(shí)驗(yàn)結(jié)果(一)Dateset

DS1DS2DS3DS4DS5DS6DS7Sprint

2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV1565287543553107163Maxrat40%48%14%51%0%77%99%Nodes9371991185513543產(chǎn)生的節(jié)點(diǎn)數(shù)目第33頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月實(shí)驗(yàn)結(jié)果(二)Dateset

DS1DS2DS3DS4DS5DS6DS7Sprint0.871.59334.9177.65230.6211.986.65Public10.821.51285.56167.78229.2110.585.55PublicS0.831.44289.70166.44230.269.814.94PublicV0.811.45300.48159.83227.269.644.89Maxrat9%0%17%11%2%2%3%執(zhí)行時(shí)間(S)第34頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月算法結(jié)果分析總體上，比Sprint算法有較大改進(jìn)相對(duì)于最后的剪枝樹仍有多余的結(jié)點(diǎn)，有待改進(jìn)挖掘效率與數(shù)據(jù)分布及噪聲有關(guān)第35頁(yè)，課件共41頁(yè)，創(chuàng)作于2023年2月言歸正傳—捕捉數(shù)據(jù)變化的挖掘方法新生成一棵決策樹與舊樹完全沒有關(guān)系生成一棵相關(guān)的樹未達(dá)到舊樹中葉節(jié)點(diǎn)的深度超出了舊樹中相應(yīng)節(jié)點(diǎn)的深度相同的屬性