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

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

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

4、dex (IBM IntelligentMiner) 能夠適用于種類和數(shù)值字段,信息增益度度量(ID3/C4.5),任意樣本分類的期望信息： I(s1,s2,sm)=Pi log2(pi) (i=1.m) 其中，數(shù)據(jù)集為S，m為S的分類數(shù)目， Pi Ci為某分類標(biāo)號，Pi為任意樣本屬于Ci的概率， si為分類Ci上的樣本數(shù) 由A劃分為子集的熵： E(A)= (s1j+ +smj)/s * I(s1j+ +smj) A為屬性，具有V個不同的取值 信息增益：Gain(A)= I(s1,s2,sm) E(A),訓(xùn)練集(舉例),ID3算法,使用信息增益進(jìn)行屬性選擇,Class P: buys_comp

5、uter = “yes” Class N: buys_computer = “no” I(p, n) = I(9, 5) =0.940 Compute the entropy for age:,Hence Similarly,Decision Tree (結(jié)果輸出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,=30,40,no,no,yes,yes,yes,30.40,基尼指數(shù) Gini Index (IBM IntelligentMiner),集合T包含N個類別的記錄，那么其Gini指標(biāo)就是 pj 類別j出現(xiàn)的頻率

6、 如果集合T分成兩部分 N1 and N2 。那么這個分割的Gini就是 提供最小Ginisplit 就被選擇作為分割的標(biāo)準(zhǔn)(對于每個屬性都要遍歷所有可以的分割方法).,預(yù)備知識二(Pruning Tree),目的： 消除決策樹的過適應(yīng)(OverFitting)問題 實質(zhì)：消除訓(xùn)練集中的異常和噪聲 兩種方法： 先剪枝法(Public 算法) 后剪枝法(Sprint 算法),兩種剪枝標(biāo)準(zhǔn),最小描述長度原則(MDL) 思想：最簡單的解釋最期望的 做法：對Decision-Tree 進(jìn)行二進(jìn)位編碼，編碼所需二進(jìn)位最少的樹即為“最佳剪枝樹” 期望錯誤率最小原則 思想：選擇期望錯誤率最小的子樹進(jìn)行剪枝

7、對樹中的內(nèi)部節(jié)點計算其剪枝/不剪枝可能出現(xiàn)的期望錯誤率，比較后加以取舍,Cost of Encoding Data Records,對n條記錄進(jìn)行分類編碼的代價(2種方法) n 記錄數(shù)，k 類數(shù)目，ni屬于類i的記錄數(shù),Cost of Encoding Tree,編碼樹結(jié)構(gòu)本身的代價 編碼每個分裂節(jié)點的代價 確定分類屬性的代價 確定分類屬性值的代價 & 其中，v是該節(jié)點上不同屬性值的個數(shù) 編碼每個樹葉上的記錄分類的代價,剪枝算法,設(shè)N為欲計算其最小代價的節(jié)點 兩種情形： N是葉結(jié)點C(S)+1 Cost1 N是內(nèi)部節(jié)點，有兩個子節(jié)點N1、N2 已剪去N1、N2，N成為葉子節(jié)點 Cost1 計算

8、N節(jié)點及其子樹的代價，使用遞歸過程 Csplit(N)+1+minCost1+minCost2 Cost2 比較Cost1和Cost2，選取代價較小者作為返回值,計算最小子樹代價的偽代碼,Procedure ComputeCost&Prune(Node N) if N 是葉子節(jié)點，return (C(S)+1) 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 ch

9、ild nodes N1 and N2 return minCostN,引入Public算法,一般做法：先建樹，后剪枝 Public算法：建樹的同時進(jìn)行剪枝 思想：在一定量(用戶定義參數(shù))的節(jié)點分裂后/周期性的進(jìn)行部分樹的剪枝 存在的問題：可能高估(Over-Estimate)被剪節(jié)點的值 改進(jìn)：采納低估(Under-Estimate)節(jié)點代價的策略,具體思路,三種葉節(jié)點： 有待擴展：需計算子樹代價下界 不能擴展(純節(jié)點) 剪枝后的結(jié)點,C(S)+1,改進(jìn)算法的偽代碼,Procedure ComputCoste&Prune(Node N) If N是仍待擴展的結(jié)點，return N節(jié)點的代價下

10、界 If N是純節(jié)點或不可擴展的葉節(jié)點， return (C(S)+1) 兩個子節(jié)點N1、N2 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(1) 假設(shè)節(jié)點N的代價至少是1 Public(S) S split 計算以N為根且包含S個分裂點的子樹代價的下界(

11、包括確定分裂節(jié)點屬性的代價) Public(V) V split value 同上，還包括確定分裂節(jié)點值的代價,Public(S)算法(一),相關(guān)概念,Public(S)算法(二),定理： 任何以N為根結(jié)點且有S個分裂點的子樹的代價至少是2*S+1+S*log a+ ni i=s+2.k 證明： 編碼樹結(jié)構(gòu)代價 2*S+1 確定節(jié)點分裂屬性的代價 S*log a 編碼S+1個葉子結(jié)點的代價 ni i=s+2.k,Public(S)算法(證明一),證明：編碼S+1個葉子節(jié)點的代價至少為 ni i=s+2.k 相關(guān)概念： 1.主要類(Majority Class):if , 有 ，則Ci為主要類

12、2.少數(shù)類(Minority Class): if then Cj為少數(shù)類,Public(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= ni i少數(shù)類,計算minCost_S的代碼,Procedure computeMinCostS(Node N) If k=1 return (C(S)+1) S=1 tmpCost=2*S+1+S*log

13、 a +i ni i=s+2.k While s+12+log a do tmpCost=tmpCost+2+log a-ns+2 S+ Return minC(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)算法,計算

14、分類節(jié)點值的代價： 編碼葉子節(jié)點記錄的代價 i=1.k (1) 在所有內(nèi)部節(jié)點編碼分裂節(jié)點值的代價 (2) 總代價 (1)+(2) 其中，Cj是葉子節(jié)點j上的主要類；M是S+1個葉子節(jié)點上的主要類的集合,算法比較,Sprint: 傳統(tǒng)的二階段“構(gòu)造剪枝”算法 Public(1):用保守的估計值1取代欲擴展節(jié)點的代價下界 Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界 Public(V):比前者準(zhǔn)確，需計算確定結(jié)點上屬性值的代價下界,實驗數(shù)據(jù)(Real-life),實驗結(jié)果(一),產(chǎn)生的節(jié)點數(shù)目,實驗結(jié)果(二),執(zhí)行時間(S),算法結(jié)果分析,總體上，比Spri

15、nt算法有較大改進(jìn) 相對于最后的剪枝樹仍有多余的結(jié)點，有待改進(jìn) 挖掘效率與數(shù)據(jù)分布及噪聲有關(guān),言歸正傳捕捉數(shù)據(jù)變化的挖掘方法,新生成一棵決策樹 與舊樹完全沒有關(guān)系 生成一棵相關(guān)的樹 未達(dá)到舊樹中葉節(jié)點的深度 超出了舊樹中相應(yīng)節(jié)點的深度 相同的屬性，最好的劃分(best cut) 相同的屬性，相同的劃分,方法三的對應(yīng)算法,使新樹與舊樹有相同的屬性和劃分，且能及早停止 測試在舊樹中每個葉子節(jié)點的錯誤變化的情況 進(jìn)一步生成新的樹 剪枝移除那些無預(yù)測特性的分枝 比較新、舊樹，識別變化部分,標(biāo)識幾種不同的變化類型,區(qū)域的連接：舊樹中的劃分不必要 邊界的移動：舊樹中的劃分移到了新的位置 進(jìn)一步細(xì)化(Refinement):舊樹中的葉結(jié)點不足以描述新生成數(shù)據(jù) 類標(biāo)號變化：舊樹中的節(jié)點類標(biāo)號發(fā)生了變化 錯誤率的變化 覆蓋率的變化：某個節(jié)點具有的數(shù)據(jù)量的比率,小結(jié),Building Decision Tree算法 Pruning Decision Tree算法 Public