單擊此處編輯母版標題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,*,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,2024/11/29,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,概述(一),傳統(tǒng)挖掘方法的局限性,只重視從數(shù)據(jù)庫中提取規(guī)則，忽視了庫中數(shù)據(jù)的變化,挖掘所用的數(shù)據(jù)來自穩(wěn)定的環(huán)境，人為干預較少,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,概述(二),捕捉新舊數(shù)據(jù)變化的目的：,挖掘出變化的趨勢,例：啤酒尿布,阻止/延緩不利變化的發(fā)生,例：金融危機銀行的信貸策略,差異挖掘算法的主要思想：,合理,比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,預備知識一(Building Tree),基本思想：,用途：提取分類規(guī)則，進行分類預測,判定樹分類算法,output,訓練集,決策樹,input,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,使用決策樹進行分類,決策樹,一個樹性的結(jié)構,內(nèi)部節(jié)點上選用一個屬性進行分割,每個分叉都是分割的一個部分,葉子節(jié)點表示一個分布,決策樹生成算法分成兩個步驟,樹的生成,開始，數(shù)據(jù)都在根節(jié)點,遞歸的進行數(shù)據(jù)分片,樹的修剪,去掉一些可能是噪音或者異常的數(shù)據(jù),決策樹使用:對未知數(shù)據(jù)進行分割,按照決策樹上采用的分割屬性逐層往下，直到一個葉子節(jié)點,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,決策樹算法,基本算法（貪心算法）,自上而下分而治之的方法,開始時，所有的數(shù)據(jù)都在根節(jié)點,屬性都是種類字段(如果是連續(xù)的，將其離散化),所有記錄用所選屬性遞歸的進行分割,屬性的選擇是基于一個啟發(fā)式規(guī)則或者一個統(tǒng)計的度量(如,information gain,),停止分割的條件,一個節(jié)點上的數(shù)據(jù)都是屬于同一個類別,沒有屬性可以再用于對數(shù)據(jù)進行分割,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,偽代碼(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,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,屬性選擇的統(tǒng)計度量,信息增益Information gain,(ID3/C4.5),所有屬性假設都是種類字段,經(jīng)過修改之后可以適用于數(shù)值字段,基尼指數(shù)Gini index,(IBM IntelligentMiner),能夠適用于種類和數(shù)值字段,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,信息增益度度量(ID3,/,C4.5),任意樣本分類的期望信息：,I(s,1,s,2,s,m,)=P,i,log,2,(p,i,)(i=1.m),其中，數(shù)據(jù)集為S，m為S的分類數(shù)目，P,i,Ci為某分類標號，P,i,為任意樣本屬于Ci的概率，,s,i,為分類Ci上的樣本數(shù),由A劃分為子集的熵：,E(A)=(,s,1j,+,s,mj,)/,s*,I(,s,1j,+,s,mj,),A為屬性，具有V個不同的取值,信息增益：Gain(A)=I(s,1,s2,sm)E(A),數(shù)據(jù)挖掘算法決策樹算法及應用擴展,訓練集(舉例),ID3算法,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,使用信息增益進行屬性選擇,Class P:buys_computer=“yes”,Class N:buys_computer=“no”,I(p,n)=I(9,5)=0.940,Compute the entropy for,age,:,Hence,Similarly,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Decision Tree(結(jié)果輸出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,基尼指數(shù) Gini,Index(IBM IntelligentMiner),集合T包含N個類別的記錄，那么其Gini指標就是,p,j,類別j出現(xiàn)的頻率,如果集合T分成兩部分,N,1,and,N,2,。那么這個分割的Gini就是,提供最小Gini,split,就被選擇作為分割的標準(,對于每個屬性都要遍歷所有可以的分割方法,).,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,預備知識二(Pruning Tree),目的：,消除決策樹的過適應(OverFitting)問題,實質(zhì)：消除訓練集中的異常和噪聲,兩種方法：,先剪枝法(Public 算法),后剪枝法(Sprint 算法),數(shù)據(jù)挖掘算法決策樹算法及應用擴展,兩種剪枝標準,最小描述長度原則(MDL),思想：最簡單的解釋最期望的,做法：對Decision-Tree 進行二進位編碼，編碼所需二進位最少的樹即為“最佳剪枝樹”,期望錯誤率最小原則,思想：選擇期望錯誤率最小的子樹進行剪枝,對樹中的,內(nèi)部節(jié)點,計算其剪枝/不剪枝可能出現(xiàn)的期望錯誤率，比較后加以取舍,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Cost of Encoding Data Records,對n條記錄進行分類編碼的代價(2種方法),n 記錄數(shù)，k 類數(shù)目，n,i,屬于類i的記錄數(shù),數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Cost of Encoding Tree,編碼樹結(jié)構本身的代價,編碼每個分裂節(jié)點的代價,確定分類屬性的代價,確定分類屬性值的代價,&,其中，v是該節(jié)點上不同屬性值的個數(shù),編碼每個樹葉上的記錄分類的代價,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,剪枝算法,設N為欲計算其最小代價的節(jié)點,兩種情形：,N是葉結(jié)點C(S)+1 Cost1,N是內(nèi)部節(jié)點，有兩個子節(jié)點N1、N2,已剪去N1、N2，N成為葉子節(jié)點,Cost1,計算N節(jié)點及其子樹的代價，使用遞歸過程,Csplit(N)+1+minCost1+minCost2 ,Cost2,比較Cost1和Cost2，選取,代價較小者,作為返回值,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,計算最小子樹代價的偽代碼,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 child nodes N1 and N2,return minCostN,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,引入Public算法,一般做法：先建樹，后剪枝,Public算法：建樹的同時進行剪枝,思想：在一定量(用戶定義參數(shù))的節(jié)點分裂后/周期性的進行部分樹的剪枝,存在的問題：可能高估(Over-Estimate)被剪節(jié)點的值,改進：采納低估(Under-Estimate)節(jié)點代價的策略,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,具體思路,三種葉節(jié)點：,有待擴展：需計算子樹代價下界,不能擴展(純節(jié)點),剪枝后的結(jié)點,C(S)+1,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,改進算法的偽代碼,Procedure ComputCoste&Prune(Node N),If N是仍待擴展的結(jié)點，return N節(jié)點的代價下界,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,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,計算子樹代價下界,Public(1),假設節(jié)點N的代價至少是1,Public(S)S split,計算以N為根且包含S個分裂點的子樹代價的下界(包括確定分裂節(jié)點屬性的代價),Public(V)V split value,同上，還包括確定分裂節(jié)點值的代價,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(S)算法(一),相關概念,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(S)算法(二),定理：,任何以N為根結(jié)點且有S個分裂點的子樹的代價至少是2*S+1+S*log a+n,i,i=s+2.k,證明：,編碼樹結(jié)構代價 2*S+1,確定節(jié)點分裂屬性的代價 S*log a,編碼S+1個葉子結(jié)點的代價,n,i,i=s+2.k,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(S)算法(證明一),證明：編碼S+1個葉子節(jié)點的代價至少為,n,i,i=s+2.k,相關概念：,1.主要類(Majority Class):if ,有 ，則Ci為主要類,2.少數(shù)類(Minority Class):if then,Cj為少數(shù)類,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(S)算法(證明二),題設：子樹N有S個分裂點(Split),K個類,S+1個葉子節(jié)點,至多有S+1個主要類,至少有K-S-1個少數(shù)類,取Ci為某少數(shù)類,C(Sj)為編碼葉子節(jié)點j上記錄的代價,又有 C(S),n,ij,編碼具有類,i,且位于葉子節(jié)點,j,的記錄的代價是,n,ij,所有少數(shù)類的代價 Cost=,n,i i少數(shù)類,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,計算minCost_S的代碼,Procedure computeMinCostS(Node N),If k=1 return(C(S)+1),S=1,tmpCost=2*S+1+S*log 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,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(S)示例,age,Car type,label,16,truck,high,24,sports,high,32,sports,Medi,34,truck,low,65,family,low,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,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,Public(V)算法,計算分類節(jié)點值的代價：,編碼葉子節(jié)點記錄的代價,i=1.k (1),在所有內(nèi)部節(jié)點編碼分裂節(jié)點值的代價,(2),總代價 (1)+(2),其中，Cj是葉子節(jié)點j上的主要類；M是S+1個葉子節(jié)點上的主要類的集合,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,算法比較,Sprint:傳統(tǒng)的二階段“構造剪枝”算法,Public(1):用保守的估計值1取代欲擴展節(jié)點的代價下界,Public(S):考慮具有分裂點的子樹，同時計算為確定分裂節(jié)點及其屬性的代價下界,Public(V):比前者準確，需計算確定結(jié)點上屬性值的代價下界,數(shù)據(jù)挖掘算法決策樹算法及應用擴展,實驗數(shù)據(jù)(Real-life),DataSet,Canner,Car,Letter,Satimage,shuttle,vehicle,yeast,NO_CA,0,6,0,0,0,0,0,NO_NA,9,0,16,36,9,18,8,N_Class,2,4,26,7,5,4,10,N_R(Te),214,567,6632,2000,14500,559,1001,N_R(Tr),496,1161,13368,4435,43500,