機器學(xué)習(xí)算法總結(jié)_決策樹

1、第三章 決策樹決策樹(Decision Tree）是在已知各種情況發(fā)生概率的基礎(chǔ)上，通過構(gòu)成決策樹來求取凈現(xiàn)值的期望值大于等于零的概率，評價項目風(fēng)險，判斷其可行性的決策分析方法，是直觀運用概率分析的一種圖解法。由于這種決策分支畫成圖形很像一棵樹的枝干，故稱決策樹。在機器學(xué)習(xí)中，決策樹是一個預(yù)測模型，他代表的是對象屬性與對象值之間的一種映射關(guān)系。Entropy = 系統(tǒng)的凌亂程度，使用算法ID3, C4.5和C5.0生成樹算法使用熵。這一度量是基于信息學(xué)理論中熵的概念。2.1 決策樹模型與學(xué)習(xí)2.1.1 決策樹模型定義2.1（決策樹） 分類決策樹模型是一種描述對實例進行分類的樹形結(jié)構(gòu)。決策樹由結(jié)

2、點（node）和有向邊（directed edge）組成。決策點，是對幾種可能方案的選擇，即最后選擇的最佳方案。如果決策屬于多級決策，則決策樹的中間可以有多個決策點，以決策樹根部的決策點為最終決策方案為最終決策方案。狀態(tài)節(jié)點，代表備選方案的經(jīng)濟效果（期望值），通過各狀態(tài)節(jié)點的經(jīng)濟效果的對比，按照一定的決策標準就可以選出最佳方案。由狀態(tài)節(jié)點引出的分支稱為概率枝，概率枝的數(shù)目表示可能出現(xiàn)的自然狀態(tài)數(shù)目每個分枝上要注明該狀態(tài)出現(xiàn)的概率。結(jié)果節(jié)點，將每個方案在各種自然狀態(tài)下取得的損益值標注于結(jié)果節(jié)點的右端。2.1.2 決策樹學(xué)習(xí)決策樹是以實例為基礎(chǔ)的歸納學(xué)習(xí)算法。 它從一組無次序、無規(guī)則的元組中推理出

3、決策樹表示形式的分類規(guī)則。它采用自頂向下的遞歸方式，在決策樹的內(nèi)部結(jié)點進行屬性值的比較，并根據(jù)不同的屬性值從該結(jié)點向下分支，葉結(jié)點是要學(xué)習(xí)劃分的類。從根到葉結(jié)點的一條路徑就對應(yīng)著一條合取規(guī)則，整個決策樹就對應(yīng)著一組析取表達式規(guī)則。1986年Quinlan提出了著名的ID3算法。在ID3算法的基礎(chǔ)上，1993年Quinlan又提出了C4.5算法。為了適應(yīng)處理大規(guī)模數(shù)據(jù)集的需要，后來又提出了若干改進的算法，其中SLIQ(super-vised learning in quest)和SPRINT (scalable parallelizableinduction of decision trees)

4、是比較有代表性的兩個算法。2.1.3 決策樹分析法決策樹分析法是常用的風(fēng)險分析決策方法。該方法是一種用樹形圖來描述各方案在未來收益的計算。比較以及選擇的方法，其決策是以期望值為標準的。它利用了概率論的原理，并且利用一種樹形圖作為分析工具。它利用了概率論的原理，并且利用一種樹形圖作為分析工具。其基本原理是用決策點代表決策問題，用方案分枝代表可供選擇的方案，用概率分枝代表方案可能出現(xiàn)的各種結(jié)果，經(jīng)過對各種方案在各種結(jié)果條件下?lián)p益值的計算比較，為決策者提供決策依據(jù)。決策樹分析法是常用的風(fēng)險分析決策方法。該方法是一種用樹形圖來描述各方案在未來收益的計算。比較以及選擇的方法，其決策是以期望值為標準的。人

5、們對未來可能會遇到好幾種不同的情況。每種情況均有出現(xiàn)的可能，人們目前無法確知，但是可以根據(jù)以前的資料來推斷各種自然狀態(tài)出現(xiàn)的概率。在這樣的條件下，人們計算的各種方案在未來的經(jīng)濟效果只能是考慮到各種自然狀態(tài)出現(xiàn)的概率的期望值，與未來的實際收益不會完全相等。如果一個決策樹只在樹的根部有一決策點，則稱為單級決策；若一個決策不僅在樹的根部有決策點，而且在樹的中間也有決策點，則稱為多級決策?？茖W(xué)的決策是現(xiàn)代管理者的一項重要職責(zé)。我們在企業(yè)管理實踐中，常遇到的情景是：若干個可行性方案制訂出來了，分析一下企業(yè)內(nèi)、外部環(huán)境，大部分條件是己知的，但還存在一定的不確定因素。每個方案的執(zhí)行都可能出現(xiàn)幾種結(jié)果，各種結(jié)

6、果的出現(xiàn)有一定的概率，企業(yè)決策存在著一定的勝算，也存在著一定的風(fēng)險。這時，決策的標準只能是期望值。即，各種狀態(tài)下的加權(quán)平均值。針對上述問題，用決策樹法來解決不失為一種好的選擇。決策樹法作為一種決策技術(shù)，已被廣泛地應(yīng)用于企業(yè)的投資決策之中，它是隨機決策模型中最常見、最普及的一種規(guī)策模式和方法此方法，有效地控制了決策帶來的風(fēng)險。所謂決策樹法，就是運用樹狀圖表示各決策的期望值，通過計算，最終優(yōu)選出效益最大、成本最小的決策方法。決策樹法屬于風(fēng)險型決策方法，不同于確定型決策方法，二者適用的條件也不同。應(yīng)用決策樹決策方法必須具備以下條件：1有決策者期望達到的明確目標；2存在決策者可以選擇的兩個以上的可行備

7、選方案；3存在著決策者無法控制的兩種以上的自然狀態(tài)(如氣候變化、市場行情、經(jīng)濟發(fā)展動向等)；4不同行動方案在不同自然狀態(tài)下的收益值或損失值(簡稱損益值)可以計算出來；5決策者能估計出不同的自然狀態(tài)發(fā)生概率。2.2 特征選擇2.2.1 特征選擇問題1、為什么要做特征選擇在有限的樣本數(shù)目下，用大量的特征來設(shè)計分類器計算開銷太大而且分類性能差。2、特征選擇的確切含義將高維空間的樣本通過映射或者是變換的方式轉(zhuǎn)換到低維空間，達到降維的目的，然后通過特征選取刪選掉冗余和不相關(guān)的特征來進一步降維。3、特征選取的原則獲取盡可能小的特征子集，不顯著降低分類精度、不影響類分布以及特征子集應(yīng)具有穩(wěn)定適應(yīng)性強等特點4

8、、特征選擇需要考慮的問題a、確定選擇算法，在允許的時間內(nèi)以最小的代價找出最小的、最能描述類別的特征組合，b、確定評價標準，衡量特征組合是否是最優(yōu)，得到特征獲取操作的停止條件。5、特征獲取方法a、按照特征子集的形成方式可以分為三種，窮舉法（exhaustion）、啟發(fā)法（heuristic）和隨機法（random）。窮舉法需要遍歷特征空間中所有的特征組合，所以方法復(fù)雜度最大，實用性不強；啟發(fā)法通過采用期望的人工機器調(diào)度規(guī)則，重復(fù)迭代產(chǎn)生遞增的特征子集，復(fù)雜度略低于窮舉法，但是只能獲取近似最優(yōu)解；隨即方法分為完全隨機方法和概率隨機方法兩種，對參數(shù)設(shè)置的依賴性較強。b、按照特征評價標準來分，根據(jù)評價

9、函數(shù)與分類器的關(guān)心，可以分為篩選器和封裝器兩種，篩選器的評價函數(shù)與分類器無關(guān)，封裝器采用分類器的錯誤概率作為評價函數(shù)。篩選器的評價函數(shù)可以細分為距離測度、信息測度、相關(guān)性測度和一致性測度。距離測度用距離來衡量樣本之間的相似度，信息測度用利用最小不確定性特征來分類。6、特征獲取方法的選取原則a、處理的數(shù)據(jù)類型b、處理的問題規(guī)模c、問題需要分類的數(shù)量d、對噪聲的容忍能力e、無噪聲環(huán)境下，產(chǎn)生穩(wěn)定性好、最優(yōu)特征子集的能力。 特征選擇的一般過程可用圖1表示。首先從特征全集中產(chǎn)生出一個特征子集，然后用評價函數(shù)對該特征子集進行評價，評價的結(jié)果與停止準則進行比較，若評價結(jié)果比停止準則好就停止，否則就繼續(xù)產(chǎn)生

10、下一組特征子集，繼續(xù)進行特征選擇。選出來的特征子集一般還要驗證其有效性。 綜上所述，特征選擇過程一般包括產(chǎn)生過程，評價函數(shù)，停止準則，驗證過程，這4個部分。 (1) 產(chǎn)生過程( Generation Procedure )產(chǎn)生過程是搜索特征子集的過程，負責(zé)為評價函數(shù)提供特征子集。搜索特征子集的過程有多種，將在2.2小節(jié)展開介紹。 (2) 評價函數(shù)( Evaluation Function )評價函數(shù)是評價一個特征子集好壞程度的一個準則。(3) 停止準則( Stopping Criterion )停止準則是與評價函數(shù)相關(guān)的，一般是一個閾值，當(dāng)評價函數(shù)值達到這個閾值后就可停止搜索。(4) 驗證過程

11、( Validation Procedure )在驗證數(shù)據(jù)集上驗證選出來的特征子集的有效性。2.2.2 信息增益信息增益（KullbackLeibler divergence）又稱information divergence，information gain，relative entropy 或者KLIC。在概率論和信息論中，信息增益是非對稱的，用以度量兩種概率分布P和Q的差異。信息增益描述了當(dāng)使用Q進行編碼時，再使用P進行編碼的差異。通常P代表樣本或觀察值的分布，也有可能是精確計算的理論分布。Q代表一種理論，模型，描述或者對P的近似。盡管信息增益通常被直觀地作為是一種度量或距離，但事實上信息

12、增益并不是。就比如信息增益不是對稱的，從P到Q的信息增益通常不等于從Q到P的信息增益。信息增益是f增益（f-divergences）的一種特殊情況。在1951年由Solomon Kullback 和Richard Leibler首先提出作為兩個分布的直接增益（directed divergence）。它與微積分中的增益不同，但可以從Bregman增益（Bregman divergence）推導(dǎo)得到。在信息增益中，重要性的衡量標準就是看特征能夠為分類系統(tǒng)帶來多少信息，帶來的信息越多，該特征越重要。因此先回憶一下信息論中有關(guān)信息量（就是“熵”）的定義。說有這么一個變量X，它可能的取值有n多種，分別

13、是，每一種取到的概率分別是，那么X的熵就定義為：意思就是一個變量可能的變化越多（反而跟變量具體的取值沒有任何關(guān)系，只和值的種類多少以及發(fā)生概率有關(guān)），它攜帶的信息量就越大（因此我一直覺得我們的政策法規(guī)信息量非常大，因為它變化很多，基本朝令夕改，笑）。對分類系統(tǒng)來說，類別C是變量，它可能的取值是，而每一個類別出現(xiàn)的概率是，因此n就是類別的總數(shù)。此時分類系統(tǒng)的熵就可以表示為：信息增益是針對一個一個的特征而言的，就是看一個特征t，系統(tǒng)有它和沒它的時候信息量各是多少，兩者的差值就是這個特征給系統(tǒng)帶來的信息量，即增益。系統(tǒng)含有特征t的時候信息量很好計算，就是剛才的式子，它表示的是包含所有特征時系統(tǒng)的信息

14、量。問題是當(dāng)系統(tǒng)不包含t時，信息量如何計算？我們換個角度想問題，把系統(tǒng)要做的事情想象成這樣：說教室里有很多座位，學(xué)生們每次上課進來的時候可以隨便坐，因而變化是很大的（無數(shù)種可能的座次情況）；但是現(xiàn)在有一個座位，看黑板很清楚，聽老師講也很清楚，于是校長的小舅子的姐姐的女兒托關(guān)系（真輾轉(zhuǎn)?。堰@個座位定下來了，每次只能給她坐，別人不行，此時情況怎樣？對于座次的可能情況來說，我們很容易看出以下兩種情況是等價的：（1）教室里沒有這個座位；（2）教室里雖然有這個座位，但其他人不能坐（因為反正它也不能參與到變化中來，它是不變的）。對應(yīng)到我們的系統(tǒng)中，就是下面的等價：（1）系統(tǒng)不包含特征t；（2）系統(tǒng)雖然

15、包含特征t，但是t已經(jīng)固定了，不能變化。我們計算分類系統(tǒng)不包含特征t的時候，就使用情況（2）來代替，就是計算當(dāng)一個特征t不能變化時，系統(tǒng)的信息量是多少。這個信息量其實也有專門的名稱，就叫做“條件熵”，條件嘛，自然就是指“t已經(jīng)固定“這個條件。但是問題接踵而至，例如一個特征X，它可能的取值有n多種，當(dāng)計算條件熵而需要把它固定的時候，要把它固定在哪一個值上呢？答案是每一種可能都要固定一下，計算n個值，然后取均值才是條件熵。而取均值也不是簡單的加一加然后除以n，而是要用每個值出現(xiàn)的概率來算平均（簡單理解，就是一個值出現(xiàn)的可能性比較大，固定在它上面時算出來的信息量占的比重就要多一些）。因此有這樣兩個條

16、件熵的表達式：這是指特征X被固定為值xi時的條件熵，這是指特征X被固定時的條件熵，注意與上式在意義上的區(qū)別。從剛才計算均值的討論可以看出來，第二個式子與第一個式子的關(guān)系就是：2.2.3 熵在信息論中，要對符號進行編碼，一個符號的熵就是要表示這個符號所需要的最少二進制數(shù)位數(shù)；這是一個極限；這也是信息壓縮的基礎(chǔ)；條件熵，當(dāng)兩個符號之間存在某種關(guān)系，或者兩個隨機變量不互相獨立的時候，對于A，B兩個隨機事件，非獨立，知道A的情況，B的不確定性減少。舉例來說，假設(shè)S是一個關(guān)于布爾概念的有14個樣例的集合，它包括9個正例和5個反例（我們采用記號9+，5-來概括這樣的數(shù)據(jù)樣例），那么S相對于這個布爾樣例的熵

17、為：注意，如果S的所有成員屬于同一類，例如，如果所有的成員是正的，那么p-就是0，于是； 另外S的正反樣例數(shù)量相等，；S的正反樣例數(shù)量不等，熵介于0，1之間，如下圖所示：/根據(jù)具體屬性和值來計算熵 double ComputeEntropy(vector <vector <string> > remain_state, string attribute, string value,bool ifparent) vector<int> count (2,0); unsigned int i,j; bool done_flag = false;/哨兵值 for(

18、j = 1; j < MAXLEN; j+) if(done_flag) break; if(!attribute_pare(attribute)for(i=1;i<remain_state.size();i+)if(!ifparent&&!remain_pare(value) | ifparent)/ifparen記錄是否算父節(jié)點 if(!remain_stateiMAXLEN - 1.compare(yes) count0+; else count1+; done_flag = true; if(count0 = 0 | c

19、ount1 = 0 ) return 0;/全部是正實例或者負實例 /具體計算熵 根據(jù)+count0,-count1,log2為底通過換底公式換成自然數(shù)底數(shù) double sum = count0 + count1; doubleentropy=-count0/sum*log(count0/sum)/log(2.0) - count1/sum*log(count1/sum)/log(2.0); return entropy; 舉個例子：A事件是：季節(jié)春，夏，秋，冬，B事件是：天氣下雨，下雪，晴天，多云；那就可以畫出一個二維表格，最直觀的是 夏天&下雪的概率<冬天&下雪的概

20、率；當(dāng)我知道天氣是下雪的時候，我就有很大的概率認為季節(jié)是冬天；這說明：我知道了B事件的情況，對A的不確定性減少了；如果A，B是獨立的，比如，A事件是季節(jié)春，夏，秋，冬，B事件是交通的情況堵，不堵，我知道B的情況，對A的不確定性并沒影響。上面說的是概念性的理解，如果用數(shù)學(xué)公式對應(yīng)起來理解，為什么會出現(xiàn)這樣的情況？已知B的情況，A的概率有沒有變化？當(dāng)A，B獨立，說明 沒有變化，當(dāng)AB不獨立的時候，即兩者存在某種相關(guān)性質(zhì)，換句話說就是B確定的前提下，A的概率分布與在總體上看不一樣。信息論中有熵，用來表示時間的不確定性，這個跟這個事件的可能值數(shù)目，還有取每個值的概率，比如有A事件1,2,3,4每個取值

21、等概，那么熵為2；如果A1,2每個取值等概率，熵為1；當(dāng)取值數(shù)目一樣的時候A1,2,3,4，那么這個熵小于2；這是為什么？因為在數(shù)據(jù)壓縮方面，對于小概率事件就要用長的編碼，大概率事件用短編碼，這樣最后平均每個事件的編碼就比較小！而對于等概率事件，這種策略就沒法使用，就沒法實現(xiàn)數(shù)據(jù)的壓縮；熵說的就是這種下界。反過來，當(dāng)我們說一個事件熵很大，就意味著1這個事件的取值范圍很多2（或者）這個事件中每個取值的概率比較均勻以上兩者都代表著這個事件的不確定性很大，所以我們又說熵是一種不確定性的度量那么什么是條件熵呢，為什么小于等于呢？上面說了，知道了B，1：首先A的取值范圍會縮小，為什么？拿上面一個例子來說

22、，我知道了天氣是下雪，那么幾乎可以說A的取值只能從春天，冬天里選擇；2：A中每個取值的概率分布會發(fā)生變化與的概率分布不同；數(shù)學(xué)證明；即已知B的結(jié)果，A的不確定性減少；要表述A這個事件的編碼數(shù)更少； 在決策樹中，我們關(guān)心的是H（結(jié)果|屬性）的關(guān)系，即已知某屬性，結(jié)果的不確定性還有多少；我們需要知道，哪個屬性能使得結(jié)果的不確定性減少最多。2.3 決策樹的生成2.3.1 ID3算法如果學(xué)習(xí)的任務(wù)是對一個大的例子集作分類概念的歸納定義，而這些例子又都是用一些無結(jié)構(gòu)的屬性值對來表示，則可以采用示例學(xué)習(xí)方法的一個變種決策樹學(xué)習(xí)，其代表性的算法是昆蘭（J.R.Quinlan，1986）提出的ID3。ID3算

23、法是由Quinlan首先提出的。該算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。以下是一些信息論的基本概念：定義2.2：若存在n個相同概率的消息，則每個消息的概率p是1/n，一個消息傳遞的信息量為定義2.3：若有n個消息，其給定概率分布為，則由該分布傳遞的信息量稱為P的熵，記為。定義2.4：若一個記錄集合T根據(jù)類別屬性的值被分成互相獨立的類C1C2.Ck，則識別T的一個元素所屬哪個類所需要的信息量為Info(T)=I(p)，其中P為C1C2Ck的概率分布，即。定義2.5：若我們先根據(jù)非類別屬性X的值將T分成集合T1,T2Tn，則確定T中一個元素類的信息量可通過

24、確定Ti的加權(quán)平均值來得到，即Info(Ti)的加權(quán)平均值為：定義2.6：信息增益度是兩個信息量之間的差值，其中一個信息量是需確定T的一個元素的信息量，另一個信息量是在已得到的屬性X的值后需確定的T一個元素的信息量，信息增益度公式為：ID3算法計算每個屬性的信息增益，并選取具有最高增益的屬性作為給定集合的測試屬性。對被選取的測試屬性創(chuàng)建一個節(jié)點，并以該節(jié)點的屬性標記，對該屬性的每個值創(chuàng)建一個分支據(jù)此劃分樣本。ID3的輸入是描述各種已知類別實例的列表。例子由預(yù)先定義的屬性值對來表示。歸納推理產(chǎn)生的結(jié)果不是以往討論的那種合取表達式，而是一棵決策樹（也稱判別樹，并可轉(zhuǎn)而表示為決策規(guī)則的一個集合），用

25、它可正確地區(qū)分所有給定例子的類屬。樹中的每一非葉節(jié)點對應(yīng)一個需測試的屬性，每個分叉就是該屬性可能的取值；樹的葉節(jié)點則指示一個例子事物的類別。ID3的顯著優(yōu)點是歸納學(xué)習(xí)花費的時間和所給任務(wù)的困難度（取決于例子個數(shù)，用來描述對象的屬性數(shù)，所學(xué)習(xí)概念的復(fù)雜度即決策樹的節(jié)點數(shù)等）僅成線性增長關(guān)系。當(dāng)然，ID3只能處理用屬性-值對表示的例子。在ID3中, 每一個例子用相同的一組屬性來表示，每一個屬性又有自身的屬性值集，如"顏色"屬性可取值是紅、綠、蘭等。構(gòu)造決策樹的目的是為了對事物作出正確的分類。決策樹形式的分類規(guī)則適用于任何的對象集。如是空的，那么它無需分類，對應(yīng)的決策樹也為空；如

26、中的對象是同一類的，那么決策樹就一個葉節(jié)點，即該類名；如果集中的對象屬于二個不同的類別，那未我們可以選取一個對象的屬性，隨后按其可能值把劃分成一些不相交的子集C1，C2，Cn，其中Ci是含有所選屬性的第個值的那些對象集。對每一個這樣的子集又可以用同樣的策略處理，最后的結(jié)果是一棵樹。ID3（Examples,Target-attrlbute,Attrlbutes）創(chuàng)建樹的root節(jié)點如果Examples都為正，返回label=+的單節(jié)點輸root如果Examples都為反，返回label=-的單節(jié)點輸root如果Attrlbutes為空，那么返回單節(jié)點輸root，label=Examples中最

27、普遍的Target-attributes值否則開始A Attributes中分類examples能力最好的屬性Root的決策屬性A對于A的每個可能值vi 在root下加一個新的分支對應(yīng)測試A=vi 令Examples為Examples中滿足A屬性值為vi的子集 如果Examples為空 在這個新分支下加一個葉子結(jié)點，節(jié)點的label=Examples中最普遍的Target-attributes值 否則在新分支下加一個子樹ID3 （Examples Target-attribute，Attributes-A）結(jié)束返回root下面給出一個關(guān)于人分類的例子（對象）集，并預(yù)先定義了指定的一組屬性及其可

28、取值：高度高，矮，發(fā)色黑色, 紅色，金色和眼睛蘭色，棕色。這里，將人分為兩類，分別以、來指示。 高度 發(fā)色 眼睛 類別矮黑色蘭色高黑色蘭色矮金色蘭色高金色棕色高黑色棕色矮金色棕色高金色蘭色高紅色蘭色如我們首先選取"發(fā)色"為樹的根節(jié)點，即可獲得圖6.11所示的決策樹。相應(yīng)于"黑色"，"紅色"和"金色"三值都有一個對象子集。隨后我們再測試"金色"這一分支，又按屬性"眼睛"把其所含的對象集劃分成蘭色和棕色二類。至此，所有葉結(jié)點相應(yīng)的對象子集只含同一類的對象，我們就可以用相應(yīng)的類別名

29、（本例中的+ 和 -）來取代各子集，得到一決策樹。一個對象所屬類的判別從決策樹的根開始，首先依據(jù)根節(jié)點指示的屬性（發(fā)色），選擇與該對象屬性值相應(yīng)的分支；然后，以同樣的方式進行下去, 一直到達葉節(jié)點。有時判別一個對象的類別，由于從根到葉節(jié)點的路徑較短，只要測試少量的屬性。如上例中，若"發(fā)色"的值是"黑色"或"紅色"，則對象就可以直接歸屬相應(yīng)的類別，而不必再去判定其它屬性的取值；若為"金色"，則再測試一次"眼睛"的值（而不必考慮"高度"）就可以進行判別。若不存在這樣的二個對象:它

30、們在每個屬性上都具有相同的值，卻屬于不同的類別，那么這種生成決策樹的過程是可行的。產(chǎn)生這種歸納學(xué)習(xí)方法的關(guān)鍵在于如何選擇一系列有用的屬性來測試一個對象集，以使生成的決策樹是最小的。ID3采用了香農(nóng)（Shannon）信息論中的方法以使分類時期望（平均）的測試次數(shù)最小。一個決策樹可看成一個信息源，即給定一個對象，可從決策樹產(chǎn)生一個該對象所屬類別的消息(比如類別"+"或"-")。決策樹的復(fù)雜程度與借助這個消息所傳遞的信息量密切相關(guān)。若決策樹傳遞的不同類別消息的概率用P+ (對應(yīng)于"+"類)和P-表示(對應(yīng)于"-"類)，那

31、么這個消息的期望信息量為:對給定的物體集C，我們可以把這概率近似地表示為相對頻率, 此時P+和P-分別等于C中類別為"+"和"-"的對象所占的比例。從C集對應(yīng)的決策樹中得到消息的期望信息量記為M(C)，并定義M()=0。對于上述例子，C集有八個例子，三個為"+"，五為"-"，則 這是一個局部決策樹，A為構(gòu)造決策樹時下一個可能選取的屬性，Ai為屬性A的值且是互斥的。屬性A將集合C劃分為若干個子集合C1，C2，.，Cn。設(shè)M(Ci)是值為Ai的子集Ci所對應(yīng)決策樹的期望信息量，則確定以屬性A作為樹根的決策樹的期望信息量

32、B(C, A)可通過權(quán)值平均而得到: B(C, A)(A值為Ai的概率) * M(Ci)同樣我們把Ai的概率用相對比例來代替，即在所有對象中具有Ai值所占的相對比例。我們希望待選的測試屬性能使決策樹獲得最大的信息增益即M(C)-B(C, A)為最大值。因為M(C)為判別一個對象的類屬所要求的總的期望信息量，B(C,A)為按屬性A構(gòu)造局部決策樹后還需要的期望信息量。二者的差越大，說明測試這個屬性所能傳遞的信息量越大,則判別的速度也就越快。例如，我們選取的屬性為"高度"，對高度值為"高"的分支的所需期望信息量為：同樣對值為"矮"的分支為:

33、則以屬性"高度"作劃分后進一步判別所需的期望信息量為：B(C,"高度") = 5/8 * 0.971 + 3/8 * 0.918 = 0.951則測試這屬性傳遞的信息為: M(C)-B(C,"高度") = 0.954 - 0.951 = 0.003 bits。如果我們不是選擇"高度"而選用屬性"頭發(fā)",則有:B(C,"頭發(fā)") = 3/8 * 0 + 1/8 * 0 + 4/8 * 1 = 0.5 bits則測試屬性"頭發(fā)"獲取的信息為M(C)-B(C,&

34、quot;頭發(fā)") = 0.945 - 0.5 = 0.45 bits。同樣對屬性"眼睛"測試，獲得信息為0.347bits。根據(jù)最大信息量原理,ID3就選取"頭發(fā)"為決策樹的根節(jié)點屬性。ID3通過不斷的循環(huán)處理，逐步求精決策樹，直到形成一棵完整的決策樹，即樹的葉節(jié)點所對應(yīng)的對象（例子）均屬于同一類。2.3.2 C4.5的生成算法C4.5算法繼承了ID3算法的優(yōu)點，并在以下幾方面對ID3算法進行了改進： 1) 用信息增益率來選擇屬性，克服了用信息增益選擇屬性時偏向選擇取值多的屬性的不足； 2) 在樹構(gòu)造過程中進行剪枝； 3) 能夠完成對連續(xù)屬性

35、的離散化處理； 4) 能夠?qū)Σ煌暾麛?shù)據(jù)進行處理。C4.5算法與其它分類算法如統(tǒng)計方法、神經(jīng)網(wǎng)絡(luò)等比較起來有如下優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。其缺點是：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。C4.5算法是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標準，從而實現(xiàn)對數(shù)據(jù)的歸納分類。1用信息增益率來選擇屬性克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。信息增益率定義為： 其中Gain(S,A)與ID3算法中的信息增益相同，而分裂信息SplitInfo(S,A

36、)代表了按照屬性A分裂樣本集S的廣度和均勻性。其中，S1到Sc是c個不同值的屬性A分割S而形成的c個樣本子集。如按照屬性A把S集（含30個用例）分成了10個用例和20個用例兩個集合則2可以處理連續(xù)數(shù)值型屬性C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點上的分枝屬性時，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個數(shù)進行計算；對于某個連續(xù)性描述屬性Ac，假設(shè)在某個結(jié)點上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5將作以下處理。(1)將該結(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述屬性的具體數(shù)值，由小到大進行排序，得到屬性值的取值序列A1c，A2c，Atot

37、alc。(2)在取值序列中生成total-1個分割點。第i（0<i<total）個分割點的取值設(shè)置為Vi=（Aic+A（i+1）c）/2,它可以將該節(jié)點上的數(shù)據(jù)集劃分為兩個子集。(3)從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分數(shù)據(jù)集的方式，C4.5計算它的信息增益比，并且從中選擇信息增益比最大的分割點來劃分數(shù)據(jù)集。3采用了一種后剪枝方法避免樹的高度無節(jié)制的增長，避免過度擬合數(shù)據(jù)，該方法使用訓(xùn)練樣本集本身來估計剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下： 其中N是實例的數(shù)量，f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數(shù)），q為真實的

38、誤差率，c為置信度（C4.5算法的一個輸入?yún)?shù)，默認值為0.25），z為對應(yīng)于置信度c的標準差，其值可根據(jù)c的設(shè)定值通過查正態(tài)分布表得到。通過該公式即可計算出真實誤差率q的一個置信度上限，用此上限為該節(jié)點誤差率e做一個悲觀的估計： 通過判斷剪枝前后e的大小，從而決定是否需要剪枝。4對于缺失值的處理在某些情況下，可供使用的數(shù)據(jù)可能缺少某些屬性的值。假如x，c(x)是樣本集S中的一個訓(xùn)練實例，但是其屬性A的值A(chǔ)(x)未知。處理缺少屬性值的一種策略是賦給它結(jié)點n所對應(yīng)的訓(xùn)練實例中該屬性的最常見值；另外一種更復(fù)雜的策略是為A的每個可能值賦予一個概率。例如，給定一個布爾屬性A，如果結(jié)點n包含6個已知A=

39、1和4個A=0的實例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺少值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進一步細分。C4.5就是使用這種方法處理缺少的屬性值。5 C4.5算法的優(yōu)缺點優(yōu)點：產(chǎn)生的分類規(guī)則易于理解，準確率較高。缺點：在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進行多次的順序掃描和排序，因而導(dǎo)致算法的低效。此外，C4.5只適合于能夠駐留于內(nèi)存的數(shù)據(jù)集，當(dāng)訓(xùn)練集大得無法在內(nèi)存容納時程序無法運行。2.4 決

40、策樹的剪枝通常在實際應(yīng)用中，直接生成的完全決策樹不能立即用于對未知樣本進行分類。由于完全決策樹對訓(xùn)練樣本的特征描述得“過于精確”，無法實現(xiàn)對新樣本的合理分析，所以此時它不是一棵分析新數(shù)掘的最佳決策樹。一棵完全決策樹能準確地反映訓(xùn)練集中數(shù)據(jù)特征，但因失去了一般代表性而無法用于對新數(shù)據(jù)的分類或預(yù)測，這種現(xiàn)象稱為“過適應(yīng)”。解決過適應(yīng)問題的主要方法是對決策樹進行剪枝。剪枝(Pruning)方法的主要目的是去掉那些噪聲或異常數(shù)據(jù)，使決策樹具有更泛化能力。剪枝常采用統(tǒng)計度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨立于測試數(shù)據(jù)進行證確分類的能力。剪枝按其實施的時間分為兩種方法：事前修剪法和事后修

41、剪法。（1）事前修剪法該方法通過提前停止樹的構(gòu)造而對樹“剪枝”，即通過在當(dāng)前節(jié)點上判斷是否需要繼續(xù)劃分該節(jié)點所含訓(xùn)練樣本集來實現(xiàn)。一旦停止，節(jié)點不再繼續(xù)分裂，當(dāng)前節(jié)點就成為一個葉節(jié)點。該葉節(jié)點中可能包含多個不同類別的訓(xùn)練樣本，由于該修剪是在分枝之前做出的，所以稱之為事前修剪。事前修剪法的優(yōu)點是在樹生成的同時進行了剪枝，因而效率高，但是它可能剪去了某些有用但還沒生成的節(jié)點。常用的方法是設(shè)定決策樹的最大高度(層數(shù))來限制樹的生長。還有一種方法是設(shè)定每個節(jié)點必須包含的最少記錄數(shù)，當(dāng)節(jié)點中記錄的個數(shù)小于這個數(shù)值時就停止分割。然而，選擇一個適當(dāng)?shù)拈撝凳潜容^困難的，較高的閾值可能導(dǎo)致過分簡化的樹，而較低的

42、閾值可能會導(dǎo)致多余樹枝無法修剪。（2）事后修剪法該方法是由完全生長的樹剪去分枝。通過刪除節(jié)點的分枝，剪掉樹節(jié)點。它在允許決策樹得到最充分生長的基礎(chǔ)上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉節(jié)點或分枝。修剪后，被修剪的分枝節(jié)點就成為一個葉節(jié)點，并將其標記為它所包含樣本中類別個數(shù)最多的類別。事后修剪是一邊修剪一邊檢驗的過程，一般規(guī)則是：當(dāng)樹建好之后，對每個內(nèi)部節(jié)點，首先計算該節(jié)點上的子樹被剪枝可能出現(xiàn)的錯誤率，然后，使用每個分枝的錯誤率，結(jié)合沿每個分枝觀察的權(quán)重評估，計算不對該節(jié)點剪枝的期望錯誤率。如果剪掉該節(jié)點能夠降低錯誤率，那么該節(jié)點的所有子節(jié)點就被剪掉，該節(jié)點成為葉節(jié)點。產(chǎn)生一組逐漸被剪枝的樹之后，使用一個獨立的測試集評估每棵樹的準確率，就能得到具有最小期望錯誤率的決策樹。當(dāng)然也可以結(jié)合使用事前修剪