咨詢工具：決策樹算法及應(yīng)用拓展課件

決策樹算法及應(yīng)用拓展內(nèi)容簡介：概述預備知識決策樹生成(BuildingDecisionTree)決策樹剪枝(PruningDecisionTree)捕捉變化數(shù)據(jù)的挖掘方法小結(jié)決策樹算法及應(yīng)用拓展內(nèi)容簡介：1概述(一)傳統(tǒng)挖掘方法的局限性只重視從數(shù)據(jù)庫中提取規(guī)則，忽視了庫中數(shù)據(jù)的變化挖掘所用的數(shù)據(jù)來自穩(wěn)定的環(huán)境，人為干預較少概述(一)傳統(tǒng)挖掘方法的局限性2概述(二)捕捉新舊數(shù)據(jù)變化的目的：挖掘出變化的趨勢例：啤酒——尿布阻止/延緩不利變化的發(fā)生例：金融危機——銀行的信貸策略差異挖掘算法的主要思想：合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分概述(二)捕捉新舊數(shù)據(jù)變化的目的：3預備知識一(BuildingTree)基本思想：用途：提取分類規(guī)則，進行分類預測判定樹分類算法output訓練集決策樹input預備知識一(BuildingTree)基本思想：判定樹分類4使用決策樹進行分類決策樹一個樹性的結(jié)構(gòu)內(nèi)部節(jié)點上選用一個屬性進行分割每個分叉都是分割的一個部分葉子節(jié)點表示一個分布決策樹生成算法分成兩個步驟樹的生成開始，數(shù)據(jù)都在根節(jié)點遞歸的進行數(shù)據(jù)分片樹的修剪去掉一些可能是噪音或者異常的數(shù)據(jù)決策樹使用:對未知數(shù)據(jù)進行分割按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點使用決策樹進行分類決策樹5決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時，所有的數(shù)據(jù)都在根節(jié)點屬性都是種類字段(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量(如,informationgain)停止分割的條件一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別沒有屬性可以再用于對數(shù)據(jù)進行分割決策樹算法基本算法（貪心算法）6偽代碼(BuildingTree)ProcedureBuildTree(S) 用數(shù)據(jù)集S初始化根節(jié)點R 用根結(jié)點R初始化隊列Q WhileQisnotEmptydo{ 取出隊列Q中的第一個節(jié)點N ifN不純(Pure){ for每一個屬性A 估計該節(jié)點在A上的信息增益 選出最佳的屬性，將N分裂為N1、N2 } }偽代碼(BuildingTree)ProcedureBu7屬性選擇的統(tǒng)計度量信息增益——Informationgain(ID3/C4.5)所有屬性假設(shè)都是種類字段經(jīng)過修改之后可以適用于數(shù)值字段基尼指數(shù)——Giniindex

(IBMIntelligentMiner)能夠適用于種類和數(shù)值字段屬性選擇的統(tǒng)計度量信息增益——Informationgai8信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，PiCi為某分類標號，Pi為任意樣本屬于Ci的概率，si為分類Ci上的樣本數(shù)由A劃分為子集的熵：E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A為屬性，具有V個不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：9訓練集(舉例)ID3算法訓練集(舉例)ID3算法10使用信息增益進行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly使用信息增益進行屬性選擇ClassP:buys_comp11DecisionTree(結(jié)果輸出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40DecisionTree(結(jié)果輸出)age?overca12基尼指數(shù)GiniIndex(IBMIntelligentMiner)集合T包含N個類別的記錄，那么其Gini指標就是 pj類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2。那么這個分割的Gini就是提供最小Ginisplit就被選擇作為分割的標準(對于每個屬性都要遍歷所有可以的分割方法).基尼指數(shù)GiniIndex(IBMIntellig13預備知識二(PruningTree)目的：消除決策樹的過適應(yīng)(OverFitting)問題實質(zhì)：消除訓練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)預備知識二(PruningTree)目的：14兩種剪枝標準最小描述長度原則(MDL)思想：最簡單的解釋最期望的做法：對Decision-Tree進行二進位編碼，編碼所需二進位最少的樹即為“最佳剪枝樹”期望錯誤率最小原則思想：選擇期望錯誤率最小的子樹進行剪枝對樹中的內(nèi)部節(jié)點計算其剪枝/不剪枝可能出現(xiàn)的期望錯誤率，比較后加以取舍兩種剪枝標準最小描述長度原則(MDL)15CostofEncodingDataRecords對n條記錄進行分類編碼的代價(2種方法)n——記錄數(shù)，k——類數(shù)目，ni——屬于類i的記錄數(shù)CostofEncodingDataRecords對16CostofEncodingTree編碼樹結(jié)構(gòu)本身的代價編碼每個分裂節(jié)點的代價確定分類屬性的代價確定分類屬性值的代價 &其中，v是該節(jié)點上不同屬性值的個數(shù)編碼每個樹葉上的記錄分類的代價CostofEncodingTree編碼樹結(jié)構(gòu)本身的代17剪枝算法設(shè)N為欲計算其最小代價的節(jié)點兩種情形：N是葉結(jié)點——C(S)+1——Cost1N是內(nèi)部節(jié)點，有兩個子節(jié)點N1、N2已剪去N1、N2，N成為葉子節(jié)點——Cost1計算N節(jié)點及其子樹的代價，使用遞歸過程Csplit(N)+1+minCost1+minCost2——Cost2比較Cost1和Cost2，選取代價較小者作為返回值剪枝算法設(shè)N為欲計算其最小代價的節(jié)點18計算最小子樹代價的偽代碼ProcedureComputeCost&Prune(NodeN)

ifN是葉子節(jié)點，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計算最小子樹代價的偽代碼ProcedureComputeC19引入Public算法一般做法：先建樹，后剪枝Public算法：建樹的同時進行剪枝思想：在一定量(用戶定義參數(shù))的節(jié)點分裂后/周期性的進行部分樹的剪枝存在的問題：可能高估(Over-Estimate)被剪節(jié)點的值改進：采納低估(Under-Estimate)節(jié)點代價的策略引入Public算法一般做法：先建樹，后剪枝20具體思路三種葉節(jié)點：有待擴展：需計算子樹代價下界不能擴展(純節(jié)點)剪枝后的結(jié)點C(S)+1具體思路三種葉節(jié)點：C(S)+121改進算法的偽代碼ProcedureComputCoste&Prune(NodeN)IfN是仍待擴展的結(jié)點，returnN節(jié)點的代價下界IfN是純節(jié)點或不可擴展的葉節(jié)點，return(C(S)+1)兩個子節(jié)點N1、N2minCost1=Compute&Prune(NodeN1)minCost2=Compute&Prune(NodeN2)minCostN=min{C(S)+1,Csplit(N)+1+minCost1+minCost2}ifminCostN=C(S)+1PrunechildnodesN1andN2returnminCostN改進算法的偽代碼ProcedureComputCoste&22計算子樹代價下界Public(1)假設(shè)節(jié)點N的代價至少是1Public(S)S——split計算以N為根且包含S個分裂點的子樹代價的下界(包括確定分裂節(jié)點屬性的代價)Public(V)V——splitvalue同上，還包括確定分裂節(jié)點值的代價計算子樹代價下界Public(1)23Public(S)算法(一)相關(guān)概念Public(S)算法(一)相關(guān)概念24Public(S)算法(二)定理：任何以N為根結(jié)點且有S個分裂點的子樹的代價至少是2*S+1+S*loga+∑nii=s+2..k證明：編碼樹結(jié)構(gòu)代價2*S+1確定節(jié)點分裂屬性的代價S*loga編碼S+1個葉子結(jié)點的代價∑nii=s+2..kPublic(S)算法(二)定理：25Public(S)算法(證明一)證明：編碼S+1個葉子節(jié)點的代價至少為∑nii=s+2..k相關(guān)概念：1.主要類(MajorityClass):if,有，則Ci為主要類2.少數(shù)類(MinorityClass):ifthenCj為少數(shù)類Public(S)算法(證明一)證明：編碼S+1個葉子節(jié)點的26Public(S)算法(證明二)題設(shè)：子樹N有S個分裂點(Split),K個類S+1個葉子節(jié)點至多有S+1個主要類至少有K-S-1個少數(shù)類取Ci為某少數(shù)類,C(Sj)為編碼葉子節(jié)點j上記錄的代價

又有C(S)>∑nij編碼具有類i且位于葉子節(jié)點j的記錄的代價是nij所有少數(shù)類的代價Cost=∑nii∈少數(shù)類Public(S)算法(證明二)題設(shè)：子樹N有S個分裂點(S27計算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}}計算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)算法計算分類節(jié)點值的代價：編碼葉子節(jié)點記錄的代價i=1..k(1)在所有內(nèi)部節(jié)點編碼分裂節(jié)點值的代價

(2)總代價(1)+(2)其中，Cj是葉子節(jié)點j上的主要類；M是S+1個葉子節(jié)點上的主要類的集合Public(V)算法計算分類節(jié)點值的代價：30算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法Public(1):用保守的估計值1取代欲擴展節(jié)點的代價下界Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界Public(V):比前者準確，需計算確定結(jié)點上屬性值的代價下界算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法31實驗數(shù)據(jù)(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001實驗數(shù)據(jù)(Real-life)DataSetCanner32實驗結(jié)果(一)DatesetDS1DS2DS3DS4DS5DS6DS7Sprint2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV1565287543553107163Maxrat40%48%14%51%0%77%99%Nodes9371991185513543產(chǎn)生的節(jié)點數(shù)目實驗結(jié)果(一)DatesetDS1DS2DS3DS4DS533實驗結(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í)行時間(S)實驗結(jié)果(二)DatesetDS1DS2DS3DS4DS534算法結(jié)果分析總體上，比Sprint算法有較大改進相對于最后的剪枝樹仍有多余的結(jié)點，有待改進挖掘效率與數(shù)據(jù)分布及噪聲有關(guān)算法結(jié)果分析總體上，比Sprint算法有較大改進35言歸正傳—捕捉數(shù)據(jù)變化的挖掘方法新生成一棵決策樹與舊樹完全沒有關(guān)系生成一棵相關(guān)的樹未達到舊樹中葉節(jié)點的深度超出了舊樹中相應(yīng)節(jié)點的深度相同的屬性，最好的劃分(bestcut)相同的屬性，相同的劃分言歸正傳—捕捉數(shù)據(jù)變化的挖掘方法新生成一棵決策樹36方法三的對應(yīng)算法使新樹與舊樹有相同的屬性和劃分，且能及早停止測試在舊樹中每個葉子節(jié)點的錯誤變化的情況進一步生成新的樹剪枝移除那些無預測特性的分枝比較新、舊樹，識別變化部分方法三的對應(yīng)算法使新樹與舊樹有相同的屬性和劃分，且能及早停止37標識幾種不同的變化類型區(qū)域的連接：舊樹中的劃分不必要邊界的移動：舊樹中的劃分移到了新的位置進一步細化(Refinement):舊樹中的葉結(jié)點不足以描述新生成數(shù)據(jù)類標號變化：舊樹中的節(jié)點類標號發(fā)生了變化錯誤率的變化覆蓋率的變化：某個節(jié)點具有的數(shù)據(jù)量的比率標識幾種不同的變化類型區(qū)域的連接：舊樹中的劃分不必要38小結(jié)BuildingDecisionTree算法PruningDecisionTree算法Public算法Public(1)算法Public(s)算法Public(v)算法識別數(shù)據(jù)變化的挖掘算法小結(jié)BuildingDecisionTree算法39個人觀點個人觀點40計算分裂點屬性代價下界的算法代碼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}}計算分裂點屬性代價下界的算法代碼ProcedureComp41決策樹算法及應(yīng)用拓展內(nèi)容簡介：概述預備知識決策樹生成(BuildingDecisionTree)決策樹剪枝(PruningDecisionTree)捕捉變化數(shù)據(jù)的挖掘方法小結(jié)決策樹算法及應(yīng)用拓展內(nèi)容簡介：42概述(一)傳統(tǒng)挖掘方法的局限性只重視從數(shù)據(jù)庫中提取規(guī)則，忽視了庫中數(shù)據(jù)的變化挖掘所用的數(shù)據(jù)來自穩(wěn)定的環(huán)境，人為干預較少概述(一)傳統(tǒng)挖掘方法的局限性43概述(二)捕捉新舊數(shù)據(jù)變化的目的：挖掘出變化的趨勢例：啤酒——尿布阻止/延緩不利變化的發(fā)生例：金融危機——銀行的信貸策略差異挖掘算法的主要思想：合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分概述(二)捕捉新舊數(shù)據(jù)變化的目的：44預備知識一(BuildingTree)基本思想：用途：提取分類規(guī)則，進行分類預測判定樹分類算法output訓練集決策樹input預備知識一(BuildingTree)基本思想：判定樹分類45使用決策樹進行分類決策樹一個樹性的結(jié)構(gòu)內(nèi)部節(jié)點上選用一個屬性進行分割每個分叉都是分割的一個部分葉子節(jié)點表示一個分布決策樹生成算法分成兩個步驟樹的生成開始，數(shù)據(jù)都在根節(jié)點遞歸的進行數(shù)據(jù)分片樹的修剪去掉一些可能是噪音或者異常的數(shù)據(jù)決策樹使用:對未知數(shù)據(jù)進行分割按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點使用決策樹進行分類決策樹46決策樹算法基本算法（貪心算法）自上而下分而治之的方法開始時，所有的數(shù)據(jù)都在根節(jié)點屬性都是種類字段(如果是連續(xù)的，將其離散化)所有記錄用所選屬性遞歸的進行分割屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量(如,informationgain)停止分割的條件一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別沒有屬性可以再用于對數(shù)據(jù)進行分割決策樹算法基本算法（貪心算法）47偽代碼(BuildingTree)ProcedureBuildTree(S) 用數(shù)據(jù)集S初始化根節(jié)點R 用根結(jié)點R初始化隊列Q WhileQisnotEmptydo{ 取出隊列Q中的第一個節(jié)點N ifN不純(Pure){ for每一個屬性A 估計該節(jié)點在A上的信息增益 選出最佳的屬性，將N分裂為N1、N2 } }偽代碼(BuildingTree)ProcedureBu48屬性選擇的統(tǒng)計度量信息增益——Informationgain(ID3/C4.5)所有屬性假設(shè)都是種類字段經(jīng)過修改之后可以適用于數(shù)值字段基尼指數(shù)——Giniindex

(IBMIntelligentMiner)能夠適用于種類和數(shù)值字段屬性選擇的統(tǒng)計度量信息增益——Informationgai49信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：I(s1,s2,……,sm)=－∑Pilog2(pi)(i=1..m)其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，PiCi為某分類標號，Pi為任意樣本屬于Ci的概率，si為分類Ci上的樣本數(shù)由A劃分為子集的熵：E(A)=∑(s1j+……+smj)/s*I(s1j+……+smj)A為屬性，具有V個不同的取值信息增益：Gain(A)=I(s1,s2,……,sm)－E(A)信息增益度度量(ID3/C4.5)任意樣本分類的期望信息：50訓練集(舉例)ID3算法訓練集(舉例)ID3算法51使用信息增益進行屬性選擇ClassP:buys_computer=“yes”ClassN:buys_computer=“no”I(p,n)=I(9,5)=0.940Computetheentropyforage:HenceSimilarly使用信息增益進行屬性選擇ClassP:buys_comp52DecisionTree(結(jié)果輸出)age?overcaststudent?creditrating?noyesfairexcellent<=30>40nonoyesyesyes30..40DecisionTree(結(jié)果輸出)age?overca53基尼指數(shù)GiniIndex(IBMIntelligentMiner)集合T包含N個類別的記錄，那么其Gini指標就是 pj類別j出現(xiàn)的頻率如果集合T分成兩部分N1andN2。那么這個分割的Gini就是提供最小Ginisplit就被選擇作為分割的標準(對于每個屬性都要遍歷所有可以的分割方法).基尼指數(shù)GiniIndex(IBMIntellig54預備知識二(PruningTree)目的：消除決策樹的過適應(yīng)(OverFitting)問題實質(zhì)：消除訓練集中的異常和噪聲兩種方法：先剪枝法(Public算法)后剪枝法(Sprint算法)預備知識二(PruningTree)目的：55兩種剪枝標準最小描述長度原則(MDL)思想：最簡單的解釋最期望的做法：對Decision-Tree進行二進位編碼，編碼所需二進位最少的樹即為“最佳剪枝樹”期望錯誤率最小原則思想：選擇期望錯誤率最小的子樹進行剪枝對樹中的內(nèi)部節(jié)點計算其剪枝/不剪枝可能出現(xiàn)的期望錯誤率，比較后加以取舍兩種剪枝標準最小描述長度原則(MDL)56CostofEncodingDataRecords對n條記錄進行分類編碼的代價(2種方法)n——記錄數(shù)，k——類數(shù)目，ni——屬于類i的記錄數(shù)CostofEncodingDataRecords對57CostofEncodingTree編碼樹結(jié)構(gòu)本身的代價編碼每個分裂節(jié)點的代價確定分類屬性的代價確定分類屬性值的代價 &其中，v是該節(jié)點上不同屬性值的個數(shù)編碼每個樹葉上的記錄分類的代價CostofEncodingTree編碼樹結(jié)構(gòu)本身的代58剪枝算法設(shè)N為欲計算其最小代價的節(jié)點兩種情形：N是葉結(jié)點——C(S)+1——Cost1N是內(nèi)部節(jié)點，有兩個子節(jié)點N1、N2已剪去N1、N2，N成為葉子節(jié)點——Cost1計算N節(jié)點及其子樹的代價，使用遞歸過程Csplit(N)+1+minCost1+minCost2——Cost2比較Cost1和Cost2，選取代價較小者作為返回值剪枝算法設(shè)N為欲計算其最小代價的節(jié)點59計算最小子樹代價的偽代碼ProcedureComputeCost&Prune(NodeN)

ifN是葉子節(jié)點，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計算最小子樹代價的偽代碼ProcedureComputeC60引入Public算法一般做法：先建樹，后剪枝Public算法：建樹的同時進行剪枝思想：在一定量(用戶定義參數(shù))的節(jié)點分裂后/周期性的進行部分樹的剪枝存在的問題：可能高估(Over-Estimate)被剪節(jié)點的值改進：采納低估(Under-Estimate)節(jié)點代價的策略引入Public算法一般做法：先建樹，后剪枝61具體思路三種葉節(jié)點：有待擴展：需計算子樹代價下界不能擴展(純節(jié)點)剪枝后的結(jié)點C(S)+1具體思路三種葉節(jié)點：C(S)+162改進算法的偽代碼ProcedureComputCoste&Prune(NodeN)IfN是仍待擴展的結(jié)點，returnN節(jié)點的代價下界IfN是純節(jié)點或不可擴展的葉節(jié)點，return(C(S)+1)兩個子節(jié)點N1、N2minCost1=Compute&Prune(NodeN1)minCost2=Compute&Prune(NodeN2)minCostN=min{C(S)+1,Csplit(N)+1+minCost1+minCost2}ifminCostN=C(S)+1PrunechildnodesN1andN2returnminCostN改進算法的偽代碼ProcedureComputCoste&63計算子樹代價下界Public(1)假設(shè)節(jié)點N的代價至少是1Public(S)S——split計算以N為根且包含S個分裂點的子樹代價的下界(包括確定分裂節(jié)點屬性的代價)Public(V)V——splitvalue同上，還包括確定分裂節(jié)點值的代價計算子樹代價下界Public(1)64Public(S)算法(一)相關(guān)概念Public(S)算法(一)相關(guān)概念65Public(S)算法(二)定理：任何以N為根結(jié)點且有S個分裂點的子樹的代價至少是2*S+1+S*loga+∑nii=s+2..k證明：編碼樹結(jié)構(gòu)代價2*S+1確定節(jié)點分裂屬性的代價S*loga編碼S+1個葉子結(jié)點的代價∑nii=s+2..kPublic(S)算法(二)定理：66Public(S)算法(證明一)證明：編碼S+1個葉子節(jié)點的代價至少為∑nii=s+2..k相關(guān)概念：1.主要類(MajorityClass):if,有，則Ci為主要類2.少數(shù)類(MinorityClass):ifthenCj為少數(shù)類Public(S)算法(證明一)證明：編碼S+1個葉子節(jié)點的67Public(S)算法(證明二)題設(shè)：子樹N有S個分裂點(Split),K個類S+1個葉子節(jié)點至多有S+1個主要類至少有K-S-1個少數(shù)類取Ci為某少數(shù)類,C(Sj)為編碼葉子節(jié)點j上記錄的代價

又有C(S)>∑nij編碼具有類i且位于葉子節(jié)點j的記錄的代價是nij所有少數(shù)類的代價Cost=∑nii∈少數(shù)類Public(S)算法(證明二)題設(shè)：子樹N有S個分裂點(S68計算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}}計算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)算法計算分類節(jié)點值的代價：編碼葉子節(jié)點記錄的代價i=1..k(1)在所有內(nèi)部節(jié)點編碼分裂節(jié)點值的代價

(2)總代價(1)+(2)其中，Cj是葉子節(jié)點j上的主要類；M是S+1個葉子節(jié)點上的主要類的集合Public(V)算法計算分類節(jié)點值的代價：71算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法Public(1):用保守的估計值1取代欲擴展節(jié)點的代價下界Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界Public(V):比前者準確，需計算確定結(jié)點上屬性值的代價下界算法比較Sprint:傳統(tǒng)的二階段“構(gòu)造－剪枝”算法72實驗數(shù)據(jù)(Real-life)DataSetCannerCarLetterSatimageshuttlevehicleyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001實驗數(shù)據(jù)(Real-life)DataSetCanner73實驗結(jié)果(一)DatesetD