1、決策樹算法及應(yīng)用拓展n內(nèi)容簡(jiǎn)介：n概述n預(yù)備知識(shí)n決策樹生成(Building Decision Tree)n決策樹剪枝(Pruning Decision Tree)n捕捉變化數(shù)據(jù)的挖掘方法n小結(jié)概述(一)n傳統(tǒng)挖掘方法的局限性n只重視從數(shù)據(jù)庫(kù)中提取規(guī)則，忽視了庫(kù)中數(shù)據(jù)的變化n挖掘所用的數(shù)據(jù)來(lái)自穩(wěn)定的環(huán)境，人為干預(yù)較少概述(二)n捕捉新舊數(shù)據(jù)變化的目的：n挖掘出變化的趨勢(shì)n例：啤酒尿布n阻止/延緩不利變化的發(fā)生n例：金融危機(jī)銀行的信貸策略n差異挖掘算法的主要思想：n合理合理比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分預(yù)備知識(shí)一(Building Tree)n基本思想：n用途：提取分類規(guī)則，

2、進(jìn)行分類預(yù)測(cè)判定樹分類算法output訓(xùn)練集決策樹input使用決策樹進(jìn)行分類n決策樹 n一個(gè)樹性的結(jié)構(gòu)n內(nèi)部節(jié)點(diǎn)上選用一個(gè)屬性進(jìn)行分割n每個(gè)分叉都是分割的一個(gè)部分n葉子節(jié)點(diǎn)表示一個(gè)分布n決策樹生成算法分成兩個(gè)步驟n樹的生成n開(kāi)始，數(shù)據(jù)都在根節(jié)點(diǎn)n遞歸的進(jìn)行數(shù)據(jù)分片n樹的修剪n去掉一些可能是噪音或者異常的數(shù)據(jù)n決策樹使用: 對(duì)未知數(shù)據(jù)進(jìn)行分割n按照決策樹上采用的分割屬性逐層往下，直到一個(gè)葉子節(jié)點(diǎn)決策樹算法n基本算法（貪心算法）n自上而下分而治之的方法n開(kāi)始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn)n屬性都是種類字段 (如果是連續(xù)的，將其離散化)n所有記錄用所選屬性遞歸的進(jìn)行分割n屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或

3、者一個(gè)統(tǒng)計(jì)的度量 (如, information gain)n停止分割的條件n一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類別n沒(méi)有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割偽代碼(Building Tree)Procedure BuildTree(S)用數(shù)據(jù)集S初始化根節(jié)點(diǎn)R 用根結(jié)點(diǎn)R初始化隊(duì)列QWhile Q is not Empty do 取出隊(duì)列Q中的第一個(gè)節(jié)點(diǎn)Nif N 不純 (Pure) for 每一個(gè)屬性 A估計(jì)該節(jié)點(diǎn)在A上的信息增益 選出最佳的屬性，將N分裂為N1、N2屬性選擇的統(tǒng)計(jì)度量n信息增益Information gain (ID3/C4.5)n所有屬性假設(shè)都是種類字段n經(jīng)過(guò)修改之后可以適用于數(shù)值

4、字段n基尼指數(shù)Gini index (IBM IntelligentMiner)n能夠適用于種類和數(shù)值字段信息增益度度量(ID3/C4.5)n任意樣本分類的期望信息：nI(s1,s2,sm)=Pi log2(pi) (i=1.m)n其中，數(shù)據(jù)集為S，m為S的分類數(shù)目， PinCi為某分類標(biāo)號(hào)，Pi為任意樣本屬于Ci的概率， si為分類Ci上的樣本數(shù)n由A劃分為子集的熵：nE(A)= (s1j+ +smj)/s * I(s1j+ +smj)nA為屬性，具有V個(gè)不同的取值n信息增益：Gain(A)= I(s1,s2,sm) E(A)|SSi訓(xùn)練集(舉例)ageincome studentcredi

5、t_ratingbuys_computer=30highnofairno40mediumnofairyes40lowyesfairyes40lowyesexcellentno3140 lowyesexcellentyes=30mediumnofairno40mediumyesfairyes40mediumnoexcellentnoID3算法使用信息增益進(jìn)行屬性選擇gClass P: buys_computer = “yes”gClass N: buys_computer = “no”gI(p, n) = I(9, 5) =0.940gCompute the entropy for age:He

6、nceSimilarlyagepiniI(pi, ni)40320.971971.0)2, 3(145)0 ,4(144)3 ,2(145)(IIIageE048. 0)_(151. 0)(029. 0)(ratingcreditGainstudentGainincomeGain)(),()(ageEnpIageGainDecision Tree (結(jié)果輸出結(jié)果輸出)age?overcaststudent?credit rating?noyesfairexcellent40nonoyesyesyes30.40基尼指數(shù) Gini Index (IBM IntelligentMiner)n集合T包

7、含N個(gè)類別的記錄，那么其Gini指標(biāo)就是pj 類別j出現(xiàn)的頻率n如果集合T分成兩部分 N1 and N2 。那么這個(gè)分割的Gini就是n提供最小Ginisplit 就被選擇作為分割的標(biāo)準(zhǔn)(對(duì)于每個(gè)屬性都要遍歷所有可以的分割方法).njpjTgini121)()()()(2211TginiNNTginiNNTginisplit預(yù)備知識(shí)二(Pruning Tree)n目的：n消除決策樹的過(guò)適應(yīng)(OverFitting)問(wèn)題n實(shí)質(zhì)：消除訓(xùn)練集中的異常和噪聲n兩種方法：n先剪枝法(Public 算法)n后剪枝法(Sprint 算法)兩種剪枝標(biāo)準(zhǔn)n最小描述長(zhǎng)度原則(MDL)n思想：最簡(jiǎn)單的解釋最期望的n

8、做法：對(duì)Decision-Tree 進(jìn)行二進(jìn)位編碼，編碼所需二進(jìn)位最少的樹即為“最佳剪枝樹”n期望錯(cuò)誤率最小原則n思想：選擇期望錯(cuò)誤率最小的子樹進(jìn)行剪枝n對(duì)樹中的內(nèi)部節(jié)點(diǎn)計(jì)算其剪枝/不剪枝可能出現(xiàn)的期望錯(cuò)誤率，比較后加以取舍Cost of Encoding Data Recordsn對(duì)n條記錄進(jìn)行分類編碼的代價(jià)(2種方法)nn 記錄數(shù)，k 類數(shù)目，ni屬于類i的記錄數(shù)!1!log)11log(nknnkkn)2/(log2log21log*)(2/knknniniSCkiCost of Encoding Treen編碼樹結(jié)構(gòu)本身的代價(jià)n編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià)n確定分類屬性的代價(jià)n確定分類屬性值

9、的代價(jià)&其中，v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù)n編碼每個(gè)樹葉上的記錄分類的代價(jià))22log(v) 1log( v剪枝算法n設(shè)N為欲計(jì)算其最小代價(jià)的節(jié)點(diǎn)n兩種情形：nN是葉結(jié)點(diǎn)C(S)+1 Cost1nN是內(nèi)部節(jié)點(diǎn)，有兩個(gè)子節(jié)點(diǎn)N1、N2n已剪去N1、N2，N成為葉子節(jié)點(diǎn) Cost1n計(jì)算N節(jié)點(diǎn)及其子樹的代價(jià)，使用遞歸過(guò)程 Csplit(N)+1+minCost1+minCost2 Cost2 比較Cost1和Cost2，選取代價(jià)較小者代價(jià)較小者作為返回值計(jì)算最小子樹代價(jià)的偽代碼Procedure ComputeCost&Prune(Node N) if N 是葉子節(jié)點(diǎn)，return (C(S)+1

10、) minCost1= Compute&Prune(Node N1) minCost2= Compute&Prune(Node N2) minCostN=minC(S)+1,Csplit(N)+1+minCost1 +minCost2 if minCostN=C(S)+1 Prune child nodes N1 and N2 return minCostN引入Public算法n一般做法：先建樹，后剪枝nPublic算法：建樹的同時(shí)進(jìn)行剪枝n思想：在一定量(用戶定義參數(shù))的節(jié)點(diǎn)分裂后/周期性的進(jìn)行部分樹的剪枝n存在的問(wèn)題：可能高估(Over-Estimate)被剪節(jié)點(diǎn)的值n改進(jìn)：采納低估(Un

11、der-Estimate)節(jié)點(diǎn)代價(jià)的策略具體思路n三種葉節(jié)點(diǎn)：n有待擴(kuò)展：需計(jì)算子樹代價(jià)下界n不能擴(kuò)展(純節(jié)點(diǎn))n剪枝后的結(jié)點(diǎn)C(S)+1改進(jìn)算法的偽代碼Procedure ComputCoste&Prune(Node N)If N是仍待擴(kuò)展的結(jié)點(diǎn)，return N節(jié)點(diǎn)的代價(jià)下界 If N是純節(jié)點(diǎn)或不可擴(kuò)展的葉節(jié)點(diǎn)， return (C(S)+1) 兩個(gè)子節(jié)點(diǎn)N1、N2 minCost1= Compute&Prune(Node N1) minCost2= Compute&Prune(Node N2) minCostN=minC(S)+1,Csplit(N)+1+minCost1 +minCos

12、t2 if minCostN=C(S)+1 Prune child nodes N1 and N2 return minCostN計(jì)算子樹代價(jià)下界nPublic(1) n假設(shè)節(jié)點(diǎn)N的代價(jià)至少是1nPublic(S) S splitn計(jì)算以N為根且包含S個(gè)分裂點(diǎn)的子樹代價(jià)的下界(包括確定分裂節(jié)點(diǎn)屬性的代價(jià))nPublic(V) V split valuen同上，還包括確定分裂節(jié)點(diǎn)值的代價(jià)Public(S)算法(一)n相關(guān)概念Public(S)算法(二)n定理：n任何以N為根結(jié)點(diǎn)且有S個(gè)分裂點(diǎn)的子樹的代價(jià)至少是2*S+1+S*log a+ ni i=s+2.k n證明：n編碼樹結(jié)構(gòu)代價(jià) 2*S+1

13、n確定節(jié)點(diǎn)分裂屬性的代價(jià) S*log a n編碼S+1個(gè)葉子結(jié)點(diǎn)的代價(jià) ni i=s+2.k Public(S)算法(證明一)n證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為 ni i=s+2.k n相關(guān)概念：1.主要類(Majority Class):if ,有 ，則Ci為主要類2.少數(shù)類(Minority Class): if thenCj為少數(shù)類CiCCkkjijnn majorityCCjPublic(S)算法(證明二)n題設(shè)：子樹N有S個(gè)分裂點(diǎn)(Split),K個(gè)類n S+1個(gè)葉子節(jié)點(diǎn)n 至多有S+1個(gè)主要類n 至少有K-S-1個(gè)少數(shù)類n 取Ci為某少數(shù)類,C(Sj)為編碼葉子節(jié)點(diǎn)j上記錄的

14、代價(jià)n n 又有 C(S) nij n 編碼具有類 i 且位于葉子節(jié)點(diǎn) j 的記錄的代價(jià)是nijn 所有少數(shù)類的代價(jià) Cost= ni i少數(shù)類ijijijijijijnnnnnSjEnSjClog*)(*)(2jijnin計(jì)算minCost_S的代碼Procedure computeMinCostS(Node N)If k=1 return (C(S)+1)S=1tmpCost=2*S+1+S*log a +i ni i=s+2.k While s+12+log a dotmpCost=tmpCost+2+log a-ns+2S+Return minC(S)+1,tmpCostPublic(

15、S)示例 ageCar type label 16 truck high 24 sports high 32 sportsMedi 34 truck low 65 family low16,truck,high24,sports,high1+log21+11N65,family,low34,truck,low32,sports,mediN1+log21+log21116,truck,high24,sports,high32,sports,medi65,family,low34,truck,low1Public(V)算法n計(jì)算分類節(jié)點(diǎn)值的代價(jià)：n編碼葉子節(jié)點(diǎn)記錄的代價(jià) i=1.k (1)n在所有

16、內(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)上的主要類的集合11|SjjMiiMiijScnn11: )(min)(11SjjScVjScVjSj算法比較nSprint: 傳統(tǒng)的二階段“構(gòu)造剪枝”算法nPublic(1):用保守的估計(jì)值1取代欲擴(kuò)展節(jié)點(diǎn)的代價(jià)下界nPublic(S):考慮具有分裂點(diǎn)的子樹，同時(shí)計(jì)算為確定分裂節(jié)點(diǎn)及其屬性的代價(jià)下界nPublic(V):比前者準(zhǔn)確，需計(jì)算確定結(jié)點(diǎn)上屬性值的代價(jià)下界實(shí)驗(yàn)數(shù)據(jù)(Real-life)DataSet Canner CarLetterSatimageshuttlevehic

17、leyeastNO_CA0600000NO_NA9016369188N_Class242675410N_R(Te)21456766322000145005591001N_R(Tr)4961161133684435435005591001實(shí)驗(yàn)結(jié)果(一)Dateset DS1DS2DS3DS4DS5DS6DS7Sprint 2197326565753189325Public11783321556553141237PublicS1571297945753115169PublicV 1565287543553107163Max rat40%48%14%51%0%77%99%Nodes937199118

18、5513543產(chǎn)生的節(jié)點(diǎn)數(shù)目產(chǎn)生的節(jié)點(diǎn)數(shù)目實(shí)驗(yàn)結(jié)果(二)Dateset DS1DS2DS3DS4DS5DS6DS7Sprint0.871.59334.9177.65230.6211.986.65Public10.821.51285.56 167.78229.2110.585.55PublicS0.831.44289.70 166.44230.269.814.94PublicV 0.811.45300.48 159.83227.269.644.89Max rat9%0%17%11%2%2%3%執(zhí)行時(shí)間執(zhí)行時(shí)間(S)算法結(jié)果分析n總體上，比Sprint算法有較大改進(jìn)n相對(duì)于最后的剪枝樹仍有多余的結(jié)點(diǎn)，有待改進(jìn)n挖掘效率與數(shù)據(jù)分布及噪聲有關(guān)言歸正傳捕捉數(shù)據(jù)變化的挖掘方法n新生成一