單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,*,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,2024/11/29,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,概述(一),傳統(tǒng)挖掘方法的局限性,只重視從數(shù)據(jù)庫(kù)中提取規(guī)則，忽視了庫(kù)中數(shù)據(jù)的變化,挖掘所用的數(shù)據(jù)來(lái)自穩(wěn)定的環(huán)境，人為干預(yù)較少,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,概述(二),捕捉新舊數(shù)據(jù)變化的目的：,挖掘出變化的趨勢(shì),例：啤酒尿布,阻止/延緩不利變化的發(fā)生,例：金融危機(jī)銀行的信貸策略,差異挖掘算法的主要思想：,合理,比較新/舊數(shù)據(jù)的挖掘結(jié)果，并清晰的描述其變化部分,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,預(yù)備知識(shí)一(Building Tree),基本思想：,用途：提取分類(lèi)規(guī)則，進(jìn)行分類(lèi)預(yù)測(cè),判定樹(shù)分類(lèi)算法,output,訓(xùn)練集,決策樹(shù),input,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,使用決策樹(shù)進(jìn)行分類(lèi),決策樹(shù),一個(gè)樹(shù)性的結(jié)構(gòu),內(nèi)部節(jié)點(diǎn)上選用一個(gè)屬性進(jìn)行分割,每個(gè)分叉都是分割的一個(gè)部分,葉子節(jié)點(diǎn)表示一個(gè)分布,決策樹(shù)生成算法分成兩個(gè)步驟,樹(shù)的生成,開(kāi)始，數(shù)據(jù)都在根節(jié)點(diǎn),遞歸的進(jìn)行數(shù)據(jù)分片,樹(shù)的修剪,去掉一些可能是噪音或者異常的數(shù)據(jù),決策樹(shù)使用:對(duì)未知數(shù)據(jù)進(jìn)行分割,按照決策樹(shù)上采用的分割屬性逐層往下，直到一個(gè)葉子節(jié)點(diǎn),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,決策樹(shù)算法,基本算法（貪心算法）,自上而下分而治之的方法,開(kāi)始時(shí)，所有的數(shù)據(jù)都在根節(jié)點(diǎn),屬性都是種類(lèi)字段(如果是連續(xù)的，將其離散化),所有記錄用所選屬性遞歸的進(jìn)行分割,屬性的選擇是基于一個(gè)啟發(fā)式規(guī)則或者一個(gè)統(tǒng)計(jì)的度量(如,information gain,),停止分割的條件,一個(gè)節(jié)點(diǎn)上的數(shù)據(jù)都是屬于同一個(gè)類(lèi)別,沒(méi)有屬性可以再用于對(duì)數(shù)據(jù)進(jìn)行分割,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,偽代碼(Building Tree),Procedure BuildTree(S),用數(shù)據(jù)集S初始化根節(jié)點(diǎn)R,用根結(jié)點(diǎn)R初始化隊(duì)列Q,While Q is not Empty do,取出隊(duì)列Q中的第一個(gè)節(jié)點(diǎn)N,if N 不純(Pure),for 每一個(gè)屬性 A,估計(jì)該節(jié)點(diǎn)在A上的信息增益,選出最佳的屬性，將N分裂為N1、N2,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,屬性選擇的統(tǒng)計(jì)度量,信息增益Information gain,(ID3/C4.5),所有屬性假設(shè)都是種類(lèi)字段,經(jīng)過(guò)修改之后可以適用于數(shù)值字段,基尼指數(shù)Gini index,(IBM IntelligentMiner),能夠適用于種類(lèi)和數(shù)值字段,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,信息增益度度量(ID3,/,C4.5),任意樣本分類(lèi)的期望信息：,I(s,1,s,2,s,m,)=P,i,log,2,(p,i,)(i=1.m),其中，數(shù)據(jù)集為S，m為S的分類(lèi)數(shù)目，P,i,Ci為某分類(lèi)標(biāo)號(hào)，P,i,為任意樣本屬于Ci的概率，,s,i,為分類(lèi)Ci上的樣本數(shù),由A劃分為子集的熵：,E(A)=(,s,1j,+,s,mj,)/,s*,I(,s,1j,+,s,mj,),A為屬性，具有V個(gè)不同的取值,信息增益：Gain(A)=I(s,1,s2,sm)E(A),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,訓(xùn)練集(舉例),ID3算法,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,使用信息增益進(jìn)行屬性選擇,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ù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Decision Tree(結(jié)果輸出),age?,overcast,student?,credit rating?,no,yes,fair,excellent,40,no,no,yes,yes,yes,30.40,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,基尼指數(shù) Gini,Index(IBM IntelligentMiner),集合T包含N個(gè)類(lèi)別的記錄，那么其Gini指標(biāo)就是,p,j,類(lèi)別j出現(xiàn)的頻率,如果集合T分成兩部分,N,1,and,N,2,。

那么這個(gè)分割的Gini就是,提供最小Gini,split,就被選擇作為分割的標(biāo)準(zhǔn)(,對(duì)于每個(gè)屬性都要遍歷所有可以的分割方法,).,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,預(yù)備知識(shí)二(Pruning Tree),目的：,消除決策樹(shù)的過(guò)適應(yīng)(OverFitting)問(wèn)題,實(shí)質(zhì)：消除訓(xùn)練集中的異常和噪聲,兩種方法：,先剪枝法(Public 算法),后剪枝法(Sprint 算法),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,兩種剪枝標(biāo)準(zhǔn),最小描述長(zhǎng)度原則(MDL),思想：最簡(jiǎn)單的解釋最期望的,做法：對(duì)Decision-Tree 進(jìn)行二進(jìn)位編碼，編碼所需二進(jìn)位最少的樹(shù)即為“最佳剪枝樹(shù)”,期望錯(cuò)誤率最小原則,思想：選擇期望錯(cuò)誤率最小的子樹(shù)進(jìn)行剪枝,對(duì)樹(shù)中的,內(nèi)部節(jié)點(diǎn),計(jì)算其剪枝/不剪枝可能出現(xiàn)的期望錯(cuò)誤率，比較后加以取舍,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Cost of Encoding Data Records,對(duì)n條記錄進(jìn)行分類(lèi)編碼的代價(jià)(2種方法),n 記錄數(shù)，k 類(lèi)數(shù)目，n,i,屬于類(lèi)i的記錄數(shù),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Cost of Encoding Tree,編碼樹(shù)結(jié)構(gòu)本身的代價(jià),編碼每個(gè)分裂節(jié)點(diǎn)的代價(jià),確定分類(lèi)屬性的代價(jià),確定分類(lèi)屬性值的代價(jià),&,其中，v是該節(jié)點(diǎn)上不同屬性值的個(gè)數(shù),編碼每個(gè)樹(shù)葉上的記錄分類(lèi)的代價(jià),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,剪枝算法,設(shè)N為欲計(jì)算其最小代價(jià)的節(jié)點(diǎn),兩種情形：,N是葉結(jié)點(diǎn)C(S)+1 Cost1,N是內(nèi)部節(jié)點(diǎn)，有兩個(gè)子節(jié)點(diǎn)N1、N2,已剪去N1、N2，N成為葉子節(jié)點(diǎn),Cost1,計(jì)算N節(jié)點(diǎn)及其子樹(shù)的代價(jià)，使用遞歸過(guò)程,Csplit(N)+1+minCost1+minCost2 ,Cost2,比較Cost1和Cost2，選取,代價(jià)較小者,作為返回值,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,計(jì)算最小子樹(shù)代價(jià)的偽代碼,Procedure ComputeCost&Prune(Node N),if N 是葉子節(jié)點(diǎn)，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ù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,引入Public算法,一般做法：先建樹(shù)，后剪枝,Public算法：建樹(shù)的同時(shí)進(jìn)行剪枝,思想：在一定量(用戶(hù)定義參數(shù))的節(jié)點(diǎn)分裂后/周期性的進(jìn)行部分樹(shù)的剪枝,存在的問(wèn)題：可能高估(Over-Estimate)被剪節(jié)點(diǎn)的值,改進(jìn)：采納低估(Under-Estimate)節(jié)點(diǎn)代價(jià)的策略,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,具體思路,三種葉節(jié)點(diǎn)：,有待擴(kuò)展：需計(jì)算子樹(shù)代價(jià)下界,不能擴(kuò)展(純節(jié)點(diǎn)),剪枝后的結(jié)點(diǎn),C(S)+1,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,改進(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,+minCost2,if minCostN=C(S)+1 Prune child nodes N1 and N2,return minCostN,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,計(jì)算子樹(shù)代價(jià)下界,Public(1),假設(shè)節(jié)點(diǎn)N的代價(jià)至少是1,Public(S)S split,計(jì)算以N為根且包含S個(gè)分裂點(diǎn)的子樹(shù)代價(jià)的下界(包括確定分裂節(jié)點(diǎn)屬性的代價(jià)),Public(V)V split value,同上，還包括確定分裂節(jié)點(diǎn)值的代價(jià),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Public(S)算法(一),相關(guān)概念,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Public(S)算法(二),定理：,任何以N為根結(jié)點(diǎn)且有S個(gè)分裂點(diǎn)的子樹(shù)的代價(jià)至少是2*S+1+S*log a+n,i,i=s+2.k,證明：,編碼樹(shù)結(jié)構(gòu)代價(jià) 2*S+1,確定節(jié)點(diǎn)分裂屬性的代價(jià) S*log a,編碼S+1個(gè)葉子結(jié)點(diǎn)的代價(jià),n,i,i=s+2.k,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Public(S)算法(證明一),證明：編碼S+1個(gè)葉子節(jié)點(diǎn)的代價(jià)至少為,n,i,i=s+2.k,相關(guān)概念：,1.主要類(lèi)(Majority Class):if ,有 ，則Ci為主要類(lèi),2.少數(shù)類(lèi)(Minority Class):if then,Cj為少數(shù)類(lèi),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Public(S)算法(證明二),題設(shè)：子樹(shù)N有S個(gè)分裂點(diǎn)(Split),K個(gè)類(lèi),S+1個(gè)葉子節(jié)點(diǎn),至多有S+1個(gè)主要類(lèi),至少有K-S-1個(gè)少數(shù)類(lèi),取Ci為某少數(shù)類(lèi),C(Sj)為編碼葉子節(jié)點(diǎn)j上記錄的代價(jià),又有 C(S),n,ij,編碼具有類(lèi),i,且位于葉子節(jié)點(diǎn),j,的記錄的代價(jià)是,n,ij,所有少數(shù)類(lèi)的代價(jià) Cost=,n,i i少數(shù)類(lèi),數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,計(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ù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,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ù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,Public(V)算法,計(jì)算分類(lèi)節(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上的主要類(lèi)；M是S+1個(gè)葉子節(jié)點(diǎn)上的主要類(lèi)的集合,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,算法比較,Sprint:傳統(tǒng)的二階段“構(gòu)造剪枝”算法,Public(1):用保守的估計(jì)值1取代欲擴(kuò)展節(jié)點(diǎn)的代價(jià)下界,Public(S):考慮具有分裂點(diǎn)的子樹(shù)，同時(shí)計(jì)算為確定分裂節(jié)點(diǎn)及其屬性的代價(jià)下界,Public(V):比前者準(zhǔn)確，需計(jì)算確定結(jié)點(diǎn)上屬性值的代價(jià)下界,數(shù)據(jù)挖掘算法決策樹(shù)算法及應(yīng)用擴(kuò)展,實(shí)驗(yàn)數(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,。