決策樹算法及應(yīng)用拓展內(nèi)容簡(jiǎn)介：概述預(yù)備知識(shí)決策樹生成(BuildingDecisionTree)決策樹剪枝(PruningDecisionTree)捕捉變化數(shù)據(jù)的挖掘方法小結(jié)決策樹算法及應(yīng)用拓展內(nèi)容簡(jiǎn)介：1概述(一)傳統(tǒng)挖掘方法的局限性只重視從數(shù)據(jù)庫(kù)中提取規(guī)則，忽視了庫(kù)中數(shù)據(jù)的變化挖掘所用的數(shù)據(jù)來(lái)自穩(wěn)定的環(huán)境，人為干預(yù)較少概述(一)傳統(tǒng)挖掘方法的局限性2概述(二)捕捉新舊數(shù)據(jù)變化的目的：挖掘出變化的趨勢(shì)例：啤酒——尿布阻止/延緩不利變化的發(fā)生例：金融危機(jī)——銀行的信貸策略差異挖掘算法的主要思想：合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分概述(二)捕捉新舊數(shù)據(jù)變化的目的：3預(yù)備知識(shí)一(BuildingTree)基本思想：用途：提取分類規(guī)則，進(jìn)行分類預(yù)測(cè)判定樹分類算法output訓(xùn)練集決策樹input預(yù)備知識(shí)一(BuildingTree)基本思想：判定樹分類4使用決策樹進(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)使用決策樹進(jìn)行分類決策樹5決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時(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偽代碼(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 } }偽代碼(BuildingTree)ProcedureBu7屬性選擇的統(tǒng)計(jì)度量信息增益——Informationgain(ID3/C4.5)所有屬性假設(shè)都是種類字段經(jīng)過修改之后可以適用于數(shù)值字段基尼指數(shù)——Giniindex

(IBMIntelligentMiner)能夠適用于種類和數(shù)值字段屬性選擇的統(tǒng)計(jì)度量信息增益——Informationgai8信息增益度度量(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)信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：9訓(xùn)練集(舉例)ID3算法訓(xùn)練集(舉例)ID3算法10使用信息增益進(jìn)行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly使用信息增益進(jìn)行屬性選擇ClassP:buys_comp11DecisionTree(結(jié)果輸出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40DecisionTree(結(jié)果輸出)age?overca12基尼指數(shù)GiniIndex(IBMIntelligentMiner)集合T包含N個(gè)類別的記錄，那么其Gini指標(biāo)就是 pj類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2。那么這個(gè)分割的Gini就是提供最小Ginisplit就被選擇作為分割的標(biāo)準(zhǔn)(對(duì)于每個(gè)屬性都要遍歷所有可以的分割方法).基尼指數(shù)GiniIndex(IBMIntellig13預(yù)備知識(shí)二(PruningTree)目的：消除決策樹的過適應(yīng)(OverFitting)問題實(shí)質(zhì)：消除訓(xùn)練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)預(yù)備知識(shí)二(PruningTree)目的：14兩種剪枝標(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ò)誤率，比較后加以取舍兩種剪枝標(biāo)準(zhǔn)最小描述長(zhǎng)度原則(MDL)15CostofEncodingDataRecords對(duì)n條記錄進(jìn)行分類編碼的代價(jià)(2種方法)n——記錄數(shù)，k——類數(shù)目，ni——屬于類i的記錄數(shù)CostofEncodingDataRecords對(duì)16CostofEncodingTree編碼樹結(jié)構(gòu)本身的代價(jià)編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià)確定分類屬性的代價(jià)確定分類屬性值的代價(jià) &其中，v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù)編碼每個(gè)樹葉上的記錄分類的代價(jià)CostofEncodingTree編碼樹結(jié)構(gòu)本身的代17剪枝算法設(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à)較小者作為返回值剪枝算法設(shè)N為欲計(jì)算其最小代價(jià)的節(jié)點(diǎn)18計(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計(jì)算最小子樹代價(jià)的偽代碼ProcedureComputeC19引入Public算法一般做法：先建樹，后剪枝Public算法：建樹的同時(shí)進(jìn)行剪枝思想：在一定量(用戶定義參數(shù))的節(jié)點(diǎn)分裂后/周期性的進(jìn)行部分樹的剪枝存在的問題：可能高估(Over-Estimate)被剪節(jié)點(diǎn)的值改進(jìn)：采納低估(Under-Estimate)節(jié)點(diǎn)代價(jià)的策略引入Public算法一般做法：先建樹，后剪枝20具體思路三種葉節(jié)點(diǎn)：有待擴(kuò)展：需計(jì)算子樹代價(jià)下界不能擴(kuò)展(純節(jié)點(diǎn))剪枝后的結(jié)點(diǎn)C(S)+1具體思路三種葉節(jié)點(diǎn)：C(S)+121改進(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ìn)算法的偽代碼ProcedureComputCoste&22計(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à)計(jì)算子樹代價(jià)下界Public(1)23Public(S)算法(一)相關(guān)概念Public(S)算法(一)相關(guān)概念24Public(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..kPublic(S)算法(二)定理：25Public(S)算法(證明一)證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為∑nii=s+2..k相關(guān)概念：1.主要類(MajorityClass):if,有，則Ci為主要類2.少數(shù)類(MinorityClass):ifthenCj為少數(shù)類Public(S)算法(證明一)證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的26Public(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ù)類Public(S)算法(證明二)題設(shè)：子樹N有S個(gè)分裂點(diǎn)(S27計(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}}計(jì)算minCost_S的代碼Procedurecomput28Public(S)示例ageCartypelabel16truckhigh24sportshigh32sportsMedi34trucklow65familylow[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]1Public(S)示例ageCartypelabel29Public(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)上的主要類的集合Public(V)算法計(jì)算分類節(jié)點(diǎn)值的代價(jià)：30算法比較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à)下界算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法31實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSetCanner32實(shí)驗(yàn)結(jié)果(一)DatesetDS1DS2DS3DS4DS5DS6DS7Sprint2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV1565287543553107163Maxrat40%48%14%51%0%77%99%Nodes9371991185513543產(chǎn)生的節(jié)點(diǎn)數(shù)目實(shí)驗(yàn)結(jié)果(一)DatesetDS1DS2DS3DS4DS533實(shí)驗(yàn)結(jié)果(二)DatesetDS1DS2DS3DS4DS5DS6DS7Sprint0.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)實(shí)驗(yàn)結(jié)果(二)DatesetDS1DS2DS3DS4DS534算法結(jié)果分析總體上，比Sprint算法有較大改進(jìn)相對(duì)于最后的剪枝樹仍有多余的結(jié)點(diǎn)，有待改進(jìn)挖掘效率與數(shù)據(jù)分布及噪聲有關(guān)算法結(jié)果分析總體上，比Sprint算法有較大改進(jìn)35言歸正傳—捕捉數(shù)據(jù)變化的挖掘方法新生成一棵決策樹與舊樹完全沒有關(guān)系生成一棵相關(guān)的樹未達(dá)到舊樹中葉節(jié)點(diǎn)的深度超出了舊樹中相應(yīng)節(jié)點(diǎn)的深度相同的屬性，最好的劃分(bestcut)相同的屬性，相同的劃分言歸正傳—捕捉數(shù)據(jù)變化的挖掘方法新生成一棵決策樹36方法三的對(duì)應(yīng)算法使新樹與舊樹有相同的屬性和劃分，且能及早停止測(cè)試在舊樹中每個(gè)葉子節(jié)點(diǎn)的錯(cuò)誤變化的情況進(jìn)一步生成新的樹剪枝移除那些無(wú)預(yù)測(cè)特性的分枝比較新、舊樹，識(shí)別變化部分方法三的對(duì)應(yīng)算法使新樹與舊樹有相同的屬性和劃分，且能及早停止37標(biāo)識(shí)幾種不同的變化類型區(qū)域的連接：舊樹中的劃分不必要邊界的移動(dòng)：舊樹中的劃分移到了新的位置進(jìn)一步細(xì)化(Refinement):舊樹中的葉結(jié)點(diǎn)不足以描述新生成數(shù)據(jù)類標(biāo)號(hào)變化：舊樹中的節(jié)點(diǎn)類標(biāo)號(hào)發(fā)生了變化錯(cuò)誤率的變化覆蓋率的變化：某個(gè)節(jié)點(diǎn)具有的數(shù)據(jù)量的比率標(biāo)識(shí)幾種不同的變化類型區(qū)域的連接：舊樹中的劃分不必要38小結(jié)BuildingDecisionTree算法PruningDecisionTree算法Public算法Public(1)算法Public(s)算法Public(v)算法識(shí)別數(shù)據(jù)變化的挖掘算法小結(jié)BuildingDecisionTree算法39個(gè)人觀點(diǎn)個(gè)人觀點(diǎn)40計(jì)算分裂點(diǎn)屬性代價(jià)下界的算法代碼ProcedureComputeMinCostS(NodeN)IfK=1return(C(S)+1)S=1tmpCost=2*S+1+S*loga+∑nii=s+1..kWhileS+1<kand>2+logado{tmpCost=tmpCost+2+loga–s++}Returnmin{C(S)+1,tmpCost}}計(jì)算分裂點(diǎn)屬性代價(jià)下界的算法代碼ProcedureComp41決策樹算法及應(yīng)用拓展內(nèi)容簡(jiǎn)介：概述預(yù)備知識(shí)決策樹生成(BuildingDecisionTree)決策樹剪枝(PruningDecisionTree)捕捉變化數(shù)據(jù)的挖掘方法小結(jié)決策樹算法及應(yīng)用拓展內(nèi)容簡(jiǎn)介：42概述(一)傳統(tǒng)挖掘方法的局限性只重視從數(shù)據(jù)庫(kù)中提取規(guī)則，忽視了庫(kù)中數(shù)據(jù)的變化挖掘所用的數(shù)據(jù)來(lái)自穩(wěn)定的環(huán)境，人為干預(yù)較少概述(一)傳統(tǒng)挖掘方法的局限性43概述(二)捕捉新舊數(shù)據(jù)變化的目的：挖掘出變化的趨勢(shì)例：啤酒——尿布阻止/延緩不利變化的發(fā)生例：金融危機(jī)——銀行的信貸策略差異挖掘算法的主要思想：合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分概述(二)捕捉新舊數(shù)據(jù)變化的目的：44預(yù)備知識(shí)一(BuildingTree)基本思想：用途：提取分類規(guī)則，進(jìn)行分類預(yù)測(cè)判定樹分類算法output訓(xùn)練集決策樹input預(yù)備知識(shí)一(BuildingTree)基本思想：判定樹分類45使用決策樹進(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)使用決策樹進(jìn)行分類決策樹46決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時(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)行分割決策樹算法基本算法（貪心算法）47偽代碼(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 } }偽代碼(BuildingTree)ProcedureBu48屬性選擇的統(tǒng)計(jì)度量信息增益——Informationgain(ID3/C4.5)所有屬性假設(shè)都是種類字段經(jīng)過修改之后可以適用于數(shù)值字段基尼指數(shù)——Giniindex

(IBMIntelligentMiner)能夠適用于種類和數(shù)值字段屬性選擇的統(tǒng)計(jì)度量信息增益——Informationgai49信息增益度度量(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)信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：50訓(xùn)練集(舉例)ID3算法訓(xùn)練集(舉例)ID3算法51使用信息增益進(jìn)行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly使用信息增益進(jìn)行屬性選擇ClassP:buys_comp52DecisionTree(結(jié)果輸出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40DecisionTree(結(jié)果輸出)age?overca53基尼指數(shù)GiniIndex(IBMIntelligentMiner)集合T包含N個(gè)類別的記錄，那么其Gini指標(biāo)就是 pj類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2。那么這個(gè)分割的Gini就是提供最小Ginisplit就被選擇作為分割的標(biāo)準(zhǔn)(對(duì)于每個(gè)屬性都要遍歷所有可以的分割方法).基尼指數(shù)GiniIndex(IBMIntellig54預(yù)備知識(shí)二(PruningTree)目的：消除決策樹的過適應(yīng)(OverFitting)問題實(shí)質(zhì)：消除訓(xùn)練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)預(yù)備知識(shí)二(PruningTree)目的：55兩種剪枝標(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ò)誤率，比較后加以取舍兩種剪枝標(biāo)準(zhǔn)最小描述長(zhǎng)度原則(MDL)56CostofEncodingDataRecords對(duì)n條記錄進(jìn)行分類編碼的代價(jià)(2種方法)n——記錄數(shù)，k——類數(shù)目，ni——屬于類i的記錄數(shù)CostofEncodingDataRecords對(duì)57CostofEncodingTree編碼樹結(jié)構(gòu)本身的代價(jià)編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià)確定分類屬性的代價(jià)確定分類屬性值的代價(jià) &其中，v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù)編碼每個(gè)樹葉上的記錄分類的代價(jià)CostofEncodingTree編碼樹結(jié)構(gòu)本身的代58剪枝算法設(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à)較小者作為返回值剪枝算法設(shè)N為欲計(jì)算其最小代價(jià)的節(jié)點(diǎn)59計(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計(jì)算最小子樹代價(jià)的偽代碼ProcedureComputeC60引入Public算法一般做法：先建樹，后剪枝Public算法：建樹的同時(shí)進(jìn)行剪枝思想：在一定量(用戶定義參數(shù))的節(jié)點(diǎn)分裂后/周期性的進(jìn)行部分樹的剪枝存在的問題：可能高估(Over-Estimate)被剪節(jié)點(diǎn)的值改進(jìn)：采納低估(Under-Estimate)節(jié)點(diǎn)代價(jià)的策略引入Public算法一般做法：先建樹，后剪枝61具體思路三種葉節(jié)點(diǎn)：有待擴(kuò)展：需計(jì)算子樹代價(jià)下界不能擴(kuò)展(純節(jié)點(diǎn))剪枝后的結(jié)點(diǎn)C(S)+1具體思路三種葉節(jié)點(diǎn)：C(S)+162改進(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ìn)算法的偽代碼ProcedureComputCoste&63計(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à)計(jì)算子樹代價(jià)下界Public(1)64Public(S)算法(一)相關(guān)概念Public(S)算法(一)相關(guān)概念65Public(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..kPublic(S)算法(二)定理：66Public(S)算法(證明一)證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為∑nii=s+2..k相關(guān)概念：1.主要類(MajorityClass):if,有，則Ci為主要類2.少數(shù)類(MinorityClass):ifthenCj為少數(shù)類Public(S)算法(證明一)證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的67Public(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ù)類Public(S)算法(證明二)題設(shè)：子樹N有S個(gè)分裂點(diǎn)(S68計(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}}計(jì)算minCost_S的代碼Procedurecomput69Public(S)示例ageCartypelabel16truckhigh24sportshigh32sportsMedi34trucklow65familylow[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]1Public(S)示例ageCartypelabel70Public(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)上的主要類的集合Public(V)算法計(jì)算分類節(jié)點(diǎn)值的代價(jià)：71算法比較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à)下界算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法72實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSetCanner73實(shí)驗(yàn)結(jié)果(一)DatesetD