決策樹與分類器

決策樹與分類器

0基于決策樹的數(shù)據(jù)挖掘算法數(shù)據(jù)挖掘是提取具有價(jià)值的知識(shí)（模型或規(guī)則）的過程。數(shù)據(jù)挖掘分析包括關(guān)聯(lián)規(guī)則、分類、聚類等方法。分類是數(shù)據(jù)挖掘中的一個(gè)重要的目標(biāo)和任務(wù)。決策樹數(shù)據(jù)挖掘算法作為數(shù)據(jù)挖掘分類的一種重要方法,其著眼于從一組無次序、規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則,具有數(shù)據(jù)分析效率較高、直觀易懂等特點(diǎn)。構(gòu)建決策樹的算法很多,其中最具代表性的是ID3和C4.5算法,C4.5算法是Quinlan在1993年以ID3算法為基礎(chǔ)進(jìn)行改進(jìn)的。由于C4.5算法對(duì)ID3算法做出的較大的改進(jìn),并且憑借其獨(dú)特的特點(diǎn)和突出的優(yōu)勢,C4.5算法已經(jīng)在金融、醫(yī)療等行業(yè)得到了成功的應(yīng)用。在文中筆者利用C4.5算法對(duì)籃球比賽賽后技術(shù)統(tǒng)計(jì)數(shù)據(jù)進(jìn)行挖掘分析,并給出分析結(jié)果。1決策樹的生成及其相關(guān)算法1.1基于決策樹的分類算法決策樹對(duì)雜亂的數(shù)據(jù)進(jìn)行決策挖掘時(shí),決策樹分類方法采用自頂向下的遞歸方式,把一組無序的數(shù)據(jù)整理成類似于流程圖的樹結(jié)構(gòu)。其中每個(gè)內(nèi)部結(jié)點(diǎn)表示在一個(gè)屬性上的測試,每個(gè)分支代表一個(gè)測試輸出,每個(gè)樹葉結(jié)點(diǎn)代表類或類分布。所以,從決策樹的根到葉結(jié)點(diǎn)的一條路徑對(duì)應(yīng)著一條合取規(guī)則?；跊Q策樹的分類算法的一個(gè)最大的優(yōu)點(diǎn)就是它在學(xué)習(xí)過程中不需要使用者了解很多背景知識(shí)。要構(gòu)造決策樹模型,首先將數(shù)據(jù)集劃分為訓(xùn)練集和測試集。在訓(xùn)練集中,根據(jù)每個(gè)屬性的信息增益率,構(gòu)造出最初的決策樹模型。決策樹建立好后,為消除決策樹對(duì)測試數(shù)據(jù)分類時(shí)產(chǎn)生的“過度擬合”問題,將其進(jìn)行剪枝,得到?jīng)Q策樹決策規(guī)則。利用決策樹方法進(jìn)行數(shù)據(jù)挖掘,一般的步驟為:數(shù)據(jù)預(yù)處理、數(shù)據(jù)挖掘操作、剪枝和應(yīng)用。1.2集料數(shù)量的估計(jì)在數(shù)據(jù)進(jìn)行預(yù)處理后,進(jìn)行歸納決策樹。假設(shè)集合S為訓(xùn)練樣本,其熵的計(jì)算公式如下:Info(S)=?Σi=1L((freq(Ci,S)/|S|?log2(freq(Ci,S)/|S|))(S)=-Σi=1L((freq(Ci,S)/|S|*log2(freq(Ci,S)/|S|))式中:freq(Ci,S)代表集合S中屬于類Ci(k個(gè)可能類中的一個(gè))的樣本數(shù)量,|S|表示集合S中的樣本數(shù)量。上面的公式僅僅給出了一個(gè)子集的熵的計(jì)算。若按照非類別屬性X的值將T分成集合T1,T2,…,Tn,需要對(duì)這些子集進(jìn)行熵的加權(quán)和的計(jì)算,公式如下所示:Infox(T)=Σi=1n|Ti|/|T|?InfoΙnfox(Τ)=Σi=1n|Τi|/|Τ|*Ιnfo(Ti)式中:T——按照屬性x進(jìn)行分區(qū)的集合。為了更加明顯地比較不同集合的熵的大小,計(jì)算分區(qū)前的集合的熵和分區(qū)后的熵的差(增益),增益大的就是要選取的節(jié)點(diǎn)。公式如下:Gain(X,T)=Info(T)-Infox(T)信息增益在可能產(chǎn)生多分枝的測試中,往往會(huì)產(chǎn)生比較大的函數(shù)值,導(dǎo)致決策樹分枝多,最終預(yù)測效果可能不會(huì)很理想。信息增益率可以彌補(bǔ)這個(gè)缺陷,信息增益率考慮了每一次劃分所產(chǎn)生的子結(jié)點(diǎn)的個(gè)數(shù)和每個(gè)子結(jié)點(diǎn)的大小,逐個(gè)對(duì)所需要考慮的對(duì)象進(jìn)行劃分,而不再考慮分類所蘊(yùn)涵的信息量,屬性的信息增益率定義為:GainRatio(X,T)=Gain(X,T)SplitInfo(X,T)GainRatio(X,Τ)=Gain(X,Τ)SplitΙnfo(X,Τ)由于T以屬性的值為基準(zhǔn)進(jìn)行分割,故SplitInfo(X,T)是信息量。于是SplitInfo(X,T)是,|Ti|/|T|對(duì)應(yīng)于freq(Ci,S)/|S|,其中{T1,T2,…,Tm}是由以X的取值分割T產(chǎn)生的子集。1.3創(chuàng)建結(jié)論決策樹生成算法的輸入是一組帶有類別標(biāo)記的例子,構(gòu)造的結(jié)果是一棵二叉或多叉的樹。下述算法為構(gòu)造決策樹的主要算法,該方法采用自上而下的遞歸構(gòu)造:輸入:訓(xùn)練樣本samples,候選屬性的集合為attribute_lists輸出:由訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹(1)對(duì)訓(xùn)練樣本samples各項(xiàng)屬性數(shù)據(jù)進(jìn)行預(yù)處理;(2)創(chuàng)建根結(jié)點(diǎn)root,并確定attribute_lists葉結(jié)點(diǎn)屬性;(3)計(jì)算候選屬性attribute_lists中每個(gè)屬性,選取GainRatio(X)最大且同時(shí)獲取的信息增益Gain(X)屬性又不低于所有屬性平均值的屬性作為測試屬性;(4)將當(dāng)前選中的屬性賦值給當(dāng)前結(jié)點(diǎn),將該屬性的屬性值作為該屬性的分叉結(jié)點(diǎn),并且將這些分叉結(jié)點(diǎn)插入隊(duì)列中;(5)從后選屬性attribute_lists中將當(dāng)前使用屬性刪除;(6)從隊(duì)列中取出一個(gè)節(jié)點(diǎn),遞歸進(jìn)行(3)到(5)步驟,直到候選屬性attribute_lists為空;(7)為每個(gè)葉子節(jié)點(diǎn)分配類別屬性,對(duì)相同的類別屬性進(jìn)行合并,將其進(jìn)行約減。基于以上決策算法得到的決策樹數(shù)據(jù)模型,在該模型中之所以選取信息增益率大而信息增益不低于平均值的屬性,是因?yàn)楦咝畔⒃鲆媛时ＷC了高分枝屬性不會(huì)被選取,從而決策樹的樹形不會(huì)因某節(jié)點(diǎn)分枝太多而過于松散。過多的分枝會(huì)使得決策樹過分地依賴某一屬性,而信息增益不低于平均值保證了該屬性的信息量,使得有利于分類的屬性更早地出現(xiàn)。1.4傳統(tǒng)剪枝修剪當(dāng)?shù)玫搅送耆L的決策樹后,為了消除噪聲數(shù)據(jù)和孤立結(jié)點(diǎn)引起的分枝異常,對(duì)決策樹采取剪枝策略。決策樹的剪枝是針對(duì)訓(xùn)練數(shù)據(jù)過分適應(yīng)問題而提出來的,其修剪方法通常利用統(tǒng)計(jì)方法刪去最不可靠的分支(樹枝),以提高分類識(shí)別的速度和數(shù)據(jù)準(zhǔn)確分類的能力。其實(shí)質(zhì)是消除訓(xùn)練集中的孤立點(diǎn)和噪聲。通常采用兩種方法進(jìn)行樹枝的剪枝,分別是:前修剪方法和后剪枝方法(1)停止分區(qū)該方法通過提前停止樹的構(gòu)造,即通過在給定的節(jié)點(diǎn)上就判斷是否需要繼續(xù)劃分或分裂訓(xùn)練樣本的子集來實(shí)現(xiàn)。一旦停止分支,當(dāng)前節(jié)點(diǎn)就成為一個(gè)葉節(jié)點(diǎn)。在建造一個(gè)決策樹時(shí),可以利用統(tǒng)計(jì)上的重要性檢測或信息增益等來對(duì)分支生成情況進(jìn)行評(píng)估。如果在一個(gè)節(jié)點(diǎn)上劃分樣本將導(dǎo)致低于節(jié)點(diǎn)中樣本低于預(yù)定義的閾值,則要停止繼續(xù)分解樣本集合。選取一個(gè)合理的閾值通常比較困難,閾值過大會(huì)導(dǎo)致決策樹過于簡單化,而閾值過小又會(huì)導(dǎo)致多余樹枝無法剪枝。(2)受修剪節(jié)點(diǎn)的分類評(píng)估該方法是人們普遍關(guān)注的決策樹剪枝策略。后剪枝算法輸入為一個(gè)未剪枝的樹T,輸出為剪枝后的決策樹T1,T1是修剪了T中一個(gè)或多個(gè)子樹后獲得的樹?；诖鷥r(jià)復(fù)雜性剪枝算法是一種事后修剪方法,最下面未被修剪的節(jié)點(diǎn)就成為樹葉,并將其標(biāo)記為它所包含樣本中類別個(gè)數(shù)最多的類別。而對(duì)于樹中每個(gè)非葉節(jié)點(diǎn),計(jì)算出該節(jié)點(diǎn)被修剪后所發(fā)生的期望錯(cuò)誤率,根據(jù)每個(gè)分枝的錯(cuò)誤率,以及每個(gè)分枝的權(quán)重,計(jì)算該節(jié)點(diǎn)不被修剪時(shí)的期望分類錯(cuò)誤率;如果修剪導(dǎo)致期望分類錯(cuò)誤率變大,則放棄修剪,保留相應(yīng)節(jié)點(diǎn)的各個(gè)分支,否則就將相應(yīng)節(jié)點(diǎn)分支修剪刪去。在產(chǎn)生一系列經(jīng)過剪枝的決策樹候選之后,利用一個(gè)獨(dú)立的測試數(shù)據(jù)集,對(duì)這些經(jīng)過修剪的決策樹的分類準(zhǔn)確性進(jìn)行評(píng)價(jià),保留下預(yù)期分類錯(cuò)誤率最小的決策樹。除了利用預(yù)期分類錯(cuò)誤率進(jìn)行決策樹修剪之外,還可以利用決策樹的編碼長度來進(jìn)行決策樹的修剪。1.5分類規(guī)則的定義剪枝后生成的決策樹,可以直接從決策樹中提取相應(yīng)的決策規(guī)則。決策樹具有直觀性、易理解等特點(diǎn)。分類規(guī)則是用IF-THEN形式表示,每條規(guī)則都是一條從根到葉節(jié)點(diǎn)的路徑。葉結(jié)點(diǎn)表示具體的結(jié)論,而葉結(jié)點(diǎn)以上的結(jié)點(diǎn)及其邊表示相應(yīng)條件的條件取值。從決策樹到?jīng)Q策規(guī)則見圖1所示。2決策樹c4.5算法的應(yīng)用2.1對(duì)整體參與的單次博弈屬性的課程內(nèi)容設(shè)計(jì)在算法中,采用的數(shù)據(jù)來自NBA某球隊(duì)近三年在常規(guī)賽中與其它隊(duì)伍的比賽。該數(shù)據(jù)中60%數(shù)據(jù)作為訓(xùn)練模型,其余40%的數(shù)據(jù)作為測試數(shù)據(jù)集用來測試模型的準(zhǔn)確度。在這些比賽的數(shù)據(jù)中選擇出12個(gè)屬性作為決策屬性,選出的屬性為:“投籃”、“三分球”、“主客場”、“二分球”、“罰球”、“進(jìn)攻”、“籃板”、“助攻”、“失誤”、“搶斷”、“蓋帽”、“犯規(guī)”。把勝負(fù)作為類別標(biāo)識(shí)。這些屬性的數(shù)據(jù)都是獨(dú)立存在的,不適合直接挖掘,需要對(duì)數(shù)據(jù)進(jìn)行預(yù)處理。(1)主客場對(duì)第四人所得群數(shù)的刪除/刪除將大量不同取值且無概化操作符的屬性或者可用其它屬性代替的屬性刪除。在此例中,主客場對(duì)比賽的影響已經(jīng)體現(xiàn)在球隊(duì)技術(shù)數(shù)據(jù)中,所以應(yīng)將其刪除。如表1所示。(2)控制引力分析在籃球比賽中球隊(duì)的投籃總數(shù)和投籃命中個(gè)數(shù)通常轉(zhuǎn)換為投籃命中率進(jìn)行技術(shù)分析,所以,將其轉(zhuǎn)換為投籃命中率之差。對(duì)于“二分球”、“罰球”、“進(jìn)攻”、“籃板”、“助攻”、“失誤”、“搶斷”、“蓋帽”、“犯規(guī)”轉(zhuǎn)換為對(duì)方的數(shù)據(jù)之差。(3)數(shù)據(jù)的離散化在籃球比賽中眾多數(shù)據(jù)為連續(xù)數(shù)據(jù),由于構(gòu)建決策樹時(shí),用離散型的數(shù)據(jù)進(jìn)行處理速度比較快。因此將連續(xù)數(shù)據(jù)進(jìn)行離散化。根據(jù)籃球比賽的常規(guī)概念和該球隊(duì)的能力,將投籃命中率分為4組:A1<-0.10;-0.10≤A2<0;0≤A3<0.08;A4≥0.08,三分球之差轉(zhuǎn)換為:B1<0;0≤B2≤4;B3≥5,對(duì)于其它數(shù)據(jù)進(jìn)行類型的處理。2.2o投影的決策樹屬性通過對(duì)總比賽場次的60%場的數(shù)據(jù)進(jìn)行計(jì)算,得到該11項(xiàng)屬性的信息增益和信息增益率。經(jīng)過統(tǒng)計(jì),各個(gè)屬性的信息增益和信息增益率如表2所示。從表2可知,屬性Ratio(投籃)=0.0626具有最大的信息增益率值,故選擇該屬性作為決策樹的第一個(gè)分節(jié)點(diǎn)進(jìn)行測試。在決策樹中以勝負(fù)為目標(biāo)屬性,根據(jù)決策樹算法和表2,得到?jīng)Q策樹,由于決策樹太大,考慮到“進(jìn)攻”、“失誤”等7個(gè)屬性比較小,則將7個(gè)屬性刪除,留下的4個(gè)指標(biāo)作為評(píng)價(jià)指標(biāo)。生成決策樹后,對(duì)該決策樹進(jìn)行修剪。修剪后的決策樹的屬性如如圖2所示。決策樹圖2中,通過訓(xùn)練集得到的決策樹分類模型對(duì)新數(shù)據(jù)進(jìn)行分類,可以比較容易地對(duì)比賽勝負(fù)進(jìn)行判斷,從圖2中可以看出,在比賽中投籃命中率是球隊(duì)取勝的關(guān)鍵。2.3高爾夫球場職業(yè)技術(shù)規(guī)范的生成基于修剪后的決策樹,對(duì)其從根到樹葉的每條路徑創(chuàng)建一個(gè)規(guī)則,以IF-THEN形式的分類規(guī)則表示。該分類規(guī)則沿著給定路徑上的每個(gè)屬性和屬性像關(guān)聯(lián)值形成規(guī)則前件(“if”)的一個(gè)合取項(xiàng),則葉結(jié)點(diǎn)包含類預(yù)測,形成后件(“then”)部分,得出最后結(jié)論。從圖2中可提取對(duì)應(yīng)規(guī)則:規(guī)則1:if命中率之差<=-0.10then勝負(fù)=負(fù)[8/88.89%]若一旦該支球隊(duì)的投籃命中率比其他球隊(duì)低0.10時(shí),那么球隊(duì)輸球的場次為8場,占總場次的88.89%,另外一場的勝利是因?yàn)槠渫痘@的次數(shù)比對(duì)手很多,導(dǎo)致其投籃命中的個(gè)數(shù)與對(duì)手的個(gè)數(shù)相近,其才有勝利的可能性。根據(jù)圖2,還可以根據(jù)決策樹的圖的路徑生成其它規(guī)則,將部分規(guī)則列舉如下:規(guī)則2:if命中率之差>-0.10and命中率之差<0and三分球之差>=0and三分球之差<=4and二分球之差<=-5and二分球之差<=0and罰球>=0then勝負(fù)=勝[13/62.5%]若該支球隊(duì)的投籃的命中率屬于(-0.10,0)、三分球之差屬于、二分球之差小于等于0、罰球之差大于等于0時(shí),那么該支球隊(duì)贏球的概率為62.5%,在該階段,則該球隊(duì)則需要提高三分球和二分球的數(shù)量,尤其分?jǐn)?shù)僵持不下時(shí),罰球的質(zhì)量直接影響到球隊(duì)的勝利。規(guī)則3:if命中率之差>0and命中率之差<0.08and三分球之差>=5then勝負(fù)=勝[14/93.33%]若該支球隊(duì)的三分球之差大于等于5的時(shí),球隊(duì)的比賽場次全勝利,此顯示出該支球隊(duì)的三分球在球隊(duì)中是一項(xiàng)很重要的得分點(diǎn)。……規(guī)則中形如ifAthenB[x/y%]表示在條件A下B發(fā)生的情況有x,占該種情況的y%。2.4模型的驗(yàn)證和檢驗(yàn)在實(shí)驗(yàn)中,采用逐一數(shù)據(jù)驗(yàn)證決策樹模型的準(zhǔn)確率。對(duì)剩余的40%的比賽進(jìn)行驗(yàn)證,錯(cuò)誤率為20.63%,準(zhǔn)確率為79.37%。一般認(rèn)為準(zhǔn)確率在60%以上的模型都具有一定準(zhǔn)確度的。因此通過該模型得到的規(guī)則信息能在一定程度上對(duì)球隊(duì)勝負(fù)關(guān)系做出最大可能的正確決策。3基于數(shù)據(jù)挖掘的分類數(shù)據(jù)庫的研究決策樹是數(shù)據(jù)挖掘中的一個(gè)常用的算