C4.5算法概述

.目錄1 決策樹算法21.1 具體應(yīng)用場景和意義21.2 現(xiàn)狀分析32 C4.5算法對ID3算法的改進(jìn)43 C4.5算法描述73.1 C4.5算法原理73.2 算法框架83.3 C4.5算法偽代碼94 實例分析95 C4.5算法的優(yōu)勢與不足125.1 C4.5算法的優(yōu)勢125.2 C4.5算法的不足：12參考文獻(xiàn)12C4.5算法綜述摘要最早的決策樹算法是由Hunt等人于1966年提出的CLS。當(dāng)前最有影響的決策樹算法是Quinlan于1986年提出的ID3和1993年提出的C4.5。ID3只能處理離散型描述屬性，它選擇信息增益最大的屬性劃分訓(xùn)練樣本，其目的是進(jìn)行分枝時系統(tǒng)的熵最小，從而提高算法的運算速度和精確度。ID3算法的主要缺陷是，用信息增益作為選擇分枝屬性的標(biāo)準(zhǔn)時，偏向于取值較多的屬性，而在某些情況下，這類屬性可能不會提供太多有價值的信息。C4.5是ID3算法的改進(jìn)算法，不僅可以處理離散型描述屬性，還能處理連續(xù)性描述屬性。C4.5采用了信息增益比作為選擇分枝屬性的標(biāo)準(zhǔn)，彌補了ID3算法的不足。C4.5算法在ID3算法的基礎(chǔ)上進(jìn)行了改進(jìn)，對于預(yù)測變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大的改進(jìn)，既適合于分類問題，又適合于回歸問題，是目前應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中收到研究者的廣泛關(guān)注。1 決策樹算法1.1具體應(yīng)用場景和意義決策樹（Decision Tree）是用于分類和預(yù)測的主要技術(shù)，它著眼于從一組無規(guī)則的事例推理出決策樹表示形式的分類規(guī)則，采用自頂向下的遞歸方式，在決策樹的內(nèi)部節(jié)點進(jìn)行屬性值的比較，并根據(jù)不同屬性判斷從該節(jié)點向下分支，在決策樹的葉節(jié)點得到結(jié)論。因此，從根節(jié)點到葉節(jié)點就對應(yīng)著一條合理規(guī)則，整棵樹就對應(yīng)著一組表達(dá)式規(guī)則?；跊Q策樹算法的一個最大的優(yōu)點是它在學(xué)習(xí)過程中不需要使用者了解很多背景知識，只要訓(xùn)練事例能夠用屬性即結(jié)論的方式表達(dá)出來，就能使用該算法進(jìn)行學(xué)習(xí)。決策樹算法在很多方面都有應(yīng)用，如決策樹算法在醫(yī)學(xué)、制造和生產(chǎn)、金融分析、天文學(xué)、遙感影像分類和分子生物學(xué)、機器學(xué)習(xí)和知識發(fā)現(xiàn)等領(lǐng)域得到了廣泛應(yīng)用。決策樹技術(shù)是一種對海量數(shù)據(jù)集進(jìn)行分類的非常有效的方法。通過構(gòu)造決策樹模型，提取有價值的分類規(guī)則，幫助決策者做出準(zhǔn)確的預(yù)測已經(jīng)應(yīng)用在很多領(lǐng)域。決策樹算法是一種逼近離散函數(shù)值的方法。它是一種典型的分類方法，首先對數(shù)據(jù)進(jìn)行處理，利用歸納算法生成可讀的規(guī)則和決策樹，然后對新數(shù)據(jù)進(jìn)行分析。本質(zhì)上決策樹是通過一系列規(guī)則對數(shù)據(jù)進(jìn)行分類的過程。決策樹的典型算法有ID3、C4.5和CART等，基于決策樹的分類模型有如下幾個特點：（1）決策樹方法結(jié)構(gòu)簡單，便于理解；（2）決策樹模型效率高，對訓(xùn)練集較大的情況較為適合；（3）決策樹方法通常不需要接受訓(xùn)練集數(shù)據(jù)外的知識；（4）決策樹方法具有較高的分類精確度。在決策樹算法中，最常用的、最經(jīng)典的是C4.5算法，它在決策樹算法中的主要優(yōu)點是：形象直觀。該算法通過兩個步驟來建立決策樹：樹的生成階段和樹的剪枝階段。該算法主要基于信息論中的熵理論。熵在系統(tǒng)學(xué)上是表示事物的無序度，是系統(tǒng)混亂程度的統(tǒng)計量。C4.5基于生成的決策樹中節(jié)點所含的信息熵最小的原理。它把信息增益率作為屬性選擇的度量標(biāo)準(zhǔn)，可以得出很容易理解的決策規(guī)則。1.2 現(xiàn)狀分析決策樹技術(shù)是迄今為止發(fā)展最為成熟的一種概念學(xué)習(xí)方法。它最早產(chǎn)生于二十世紀(jì)60年代，是由Hunt等人研究人類概念建模時建立的學(xué)習(xí)系統(tǒng)（CLS，Concept Learning System），到70年代末，J Ross Quinlan提出ID3算法，此算法的目的在于減少樹的深度。但是忽略了葉子數(shù)目的研究。1975年和1984年，分別有人提出CHAID（Chi-squared Automatic Interaction Detection）和CART（Classification and Regression Tree，亦稱BFOS）算法。1986年，J.C.Schlimmer提出ID4算法。1988年，P.E.Utgoff提出ID5R算法。1993年，Quinlan本人以ID3算法為基礎(chǔ)研究出C4.5/C5.0算法，C4.5算法在ID3算法的基礎(chǔ)上進(jìn)行了改進(jìn)，對于預(yù)測變量的缺值處理、剪枝技術(shù)、派生規(guī)則等方面作了較大的改進(jìn)，既適合于分類問題，又適合于回歸問題，因而是目前應(yīng)用最為廣泛的歸納推理算法之一，在數(shù)據(jù)挖掘中收到研究者的廣泛關(guān)注。數(shù)據(jù)挖掘需要選擇復(fù)雜度低的算法和并行高效的策略，復(fù)雜度低的算法包括盡量把全局最優(yōu)問題轉(zhuǎn)化成局部最優(yōu)的問題和近似線性或盡量低階的多項式復(fù)雜度算法等，而高效并行的策略包括需要有高超的遞歸改為循環(huán)的技巧和盡量避免使用全局信息等。現(xiàn)在研究者們還在繼續(xù)研究改進(jìn)的決策樹算法，對于C4.5算法研究人員們從不同的角度對其進(jìn)行了相應(yīng)的改進(jìn)，其中有針對C4.5算法處理連續(xù)型屬性比較耗時的改進(jìn)，利用數(shù)學(xué)上的等價無窮小提高信息增益率的計算效率等等方面。本報告時針對C4.5算法本身進(jìn)行的分析和算法實現(xiàn)，同時會考慮進(jìn)一步的深入學(xué)習(xí)。2 C4.5算法對ID3算法的改進(jìn)決策樹構(gòu)造的輸入是一組帶有類別標(biāo)記的例子，構(gòu)造的結(jié)果是一棵二叉樹或多叉樹。二叉樹的內(nèi)部節(jié)點(非葉子節(jié)點)一般表示為一個邏輯判斷，如形式為a=aj的邏輯判斷，其中a是屬性，aj 是該屬性的所有取值：樹的邊是邏輯判斷的分支結(jié)果。多叉樹(ID3)的內(nèi)部結(jié)點是屬性，邊是該屬性的所有取值，有幾個屬性值就有幾條邊。樹的葉子節(jié)點都是類別標(biāo)記。由于數(shù)據(jù)表示不當(dāng)、有噪聲或者由于決策樹生成時產(chǎn)生重復(fù)的子樹等原因，都會造成產(chǎn)生的決策樹過大。因此，簡化決策樹是一個不可缺少的環(huán)節(jié)。尋找一棵最優(yōu)決策樹，主要應(yīng)解決以下3個最優(yōu)化問題：生成最少數(shù)目的葉子節(jié)點；生成的每個葉子節(jié)點的深度最??；生成的決策樹葉子節(jié)點最少且每個葉子節(jié)點的深度最小。ID3算法是一種經(jīng)典的決策樹算法，它從根節(jié)點開始，根節(jié)點被賦予一個最好的屬性。隨后對該屬性的每個取值都生成相應(yīng)的分支，在每個分支上又生成新的節(jié)點。對于最好的屬性的選擇標(biāo)準(zhǔn)，ID3采用基于信息熵定義的信息增益來選擇內(nèi)節(jié)點的測試屬性，熵（Entropy）刻畫了任意樣本集的純度。ID3算法存在的缺點：（1）ID3算法在選擇根節(jié)點和內(nèi)部節(jié)點中的分支屬性時，采用信息增益作為評價標(biāo)準(zhǔn)。信息增益的缺點是傾向于選擇取值較多是屬性，在有些情況下這類屬性可能不會提供太多有價值的信息。（2）ID3算法只能對描述屬性為離散型屬性的數(shù)據(jù)集構(gòu)造決策樹。ID3算法的局限是它的屬性只能取離散值，為了使決策樹能應(yīng)用與連續(xù)屬性值，Quinlan給出了ID3的一個擴展算法，即C4.5算法。C4.5算法是ID3的改進(jìn)，其中屬性的選擇依據(jù)同ID3。它對于實值變量的處理與接下來論述的CART算法一致，采用多重分支。C4.5算法能實現(xiàn)基于規(guī)則的剪枝。因為算法生成的每個葉子都和一條規(guī)則相關(guān)聯(lián)，這個規(guī)則可以從樹的根節(jié)點直到葉子節(jié)點的路徑上以邏輯合取式的形式讀出。決策樹的分類過程就是把訓(xùn)練集劃分為越來越小的子集的過程。理想的結(jié)果是決策樹的葉子節(jié)點的樣本都有同類標(biāo)記。如果是這樣，顯然決策樹的分支應(yīng)該停止了，因為所以的類別已經(jīng)被分開了。C4.5算法之所以是最常用的決策樹算法，是因為它繼承了ID3算法的所有優(yōu)點并對ID3算的進(jìn)行了改進(jìn)和補充。C4.5算法采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn)，克服了ID3算法中信息增益選擇屬性時偏向選擇取值多的屬性的不足，并能夠完成對連續(xù)屬性離散化是處理，還能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。C4.5算法屬于基于信息論（Information Theory）的方法，它是以信息論為基礎(chǔ)，以信息熵和信息增益度為衡量標(biāo)準(zhǔn)，從而實現(xiàn)對數(shù)據(jù)的歸納分類。C4.5算法主要做出了以下方面的改進(jìn)：（1）用信息增益率來選擇屬性克服了用信息增益來選擇屬性時偏向選擇值多的屬性的不足。信息增益率定義為：GainRatio(S, A) = Gain(S,A)SplitInfo(S,A) (1)其中，Grain（S，A）與ID3算法中的信息增益相同，而分裂信息SplitInfo（S， A）代表了按照屬性A分裂樣本集S的廣度和均勻性。SplitInfo(S, A) = -i=1c|Si|S|Log2|Si|S| (2) (2)其中，S1到Sc是c個不同值的屬性A分割S而形成的c個樣本子集。如按照屬性A把S集（含30個用例）分成了10個用例和20個用例兩個集合，則SplitInfo(S，A)=-1/3*log(1/3)-2/3*log(2/3)。（2）可以處理連續(xù)數(shù)值型屬性C4.5算法既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某節(jié)點上的分枝屬性時，對于離散型描述屬性，C4.5算法的處理方法與ID3相同，按照該屬性本身的取值個數(shù)進(jìn)行計算；對于某個連續(xù)性描述屬性Ac，假設(shè)在某個節(jié)點上的數(shù)據(jù)集的樣本數(shù)量為total，C4.5算法將作以下處理：將該節(jié)點上的所有數(shù)據(jù)樣本按照連續(xù)型描述的屬性的具體數(shù)值，由小到大進(jìn)行排序，得到屬性值的取值序列A1c，A2c，Atotalc。在取值序列生成total-1個分割點。第i（0<i<total）個分割點的取值設(shè)置為Vi=（Aic+A（i+1）c）/2，它可以將該節(jié)點上的數(shù)據(jù)集劃分為兩個子集。從total-1個分割點中選擇最佳分割點。對于每一個分割點劃分?jǐn)?shù)據(jù)集的方式，C4.5算法計算它的信息增益比，并且從中選擇信息增益比最大的分割點來劃分?jǐn)?shù)據(jù)集。（3）采用了一種后剪枝方法避免樹的高度無節(jié)制的增長，避免過度擬合數(shù)據(jù)，該方法是用訓(xùn)練樣本本身來估計剪枝前后的誤差，從而決定是否真正剪枝。方法中使用的公式如下：Pr f-qq(1-q)/N>z = c (3)其中N是實例的數(shù)量，f=E/N為觀察到的誤差率（其中E為N個實例中分類錯誤的個數(shù)），q為真實的誤差率，c為置信度（C4.5算法的一個熟人參數(shù)，默認(rèn)值為0.25），z為對應(yīng)于置信度c的標(biāo)準(zhǔn)差，其值可根據(jù)c的設(shè)定值通過查正態(tài)分布表得到。通過該公式即可計算出真實誤差率q的一個置信區(qū)間上限，用此上限為該節(jié)點誤差率e做一個悲觀的估計：e = f+z22N+ZfN-f2N+z24N21+z2N (4) 通過判斷剪枝前后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=1和4個A=0的實例，那么A(x)=1的概率是0.6，而A(x)=0的概率是0.4。于是，實例x的60%被分配到A=1的分支，40%被分配到另一個分支。這些片斷樣例（fractional examples）的目的是計算信息增益，另外，如果有第二個缺失值的屬性必須被測試，這些樣例可以在后繼的樹分支中被進(jìn)一步細(xì)分。C4.5就是使用這種方法處理缺少的屬性值3 C4.5算法描述3.1 C4.5算法原理I(,sm) = i=1mpilog2(Pi) (5)設(shè)S是s個數(shù)據(jù)樣本的集合。假定類標(biāo)號Ci(I = 1,m)具有m個不同的值，設(shè)si是類Ci中的樣本數(shù)。對一個給定的樣本分類所需的期望信息由下式給出：其中，pi是任意樣本屬于ci的概率，并用si/s來估計。設(shè)屬性A具有v個子集s1,sv;其中，sj包含S中這樣一些樣本，它們在A上具有值aj。如果A選作測試屬性，則這些子集對應(yīng)于由包含集合S的節(jié)點生長出來的分枝。設(shè)sij是子集sj中類ci的樣本數(shù)。根據(jù)由A劃分成子集的熵由下式給出：E(A) = i=1vsij+SmjSI(sij,smj) (6) I(S1j,S2j,Smj) = -i=1mpijlog2Pij (7) 其中，項(sij+smj)/s充當(dāng)?shù)趈個子集的權(quán)，并且等于子集（即A值為aj）中的樣本個數(shù)除以s中的樣本總數(shù)。熵值越小，子集劃分的純度越高。對于給定的子集sj有：其中，pij=sij/sj是sj中的樣本屬于類cj的概率。 Gain(A) = I(s1,sm) E(A) (8) 在A上分枝將獲得的編碼信息是：以上和ID3算法的基本原理相同，而C4.5所不同的是在后面使用信息以上和ID3算法的基本原理相同，而C4.5所不同的是在后面使用信息增益比例來取代信息增益。SplitInfo(S, A) = -i=1c|Si|S|Log2|Si|S| (9) (9)其中，s1到sc是c個值的屬性A分割S而形成的c個樣本子集。這時，在屬性A上所得到的信息增益比為： GainRatio(S, A) = Gain(S,A)SplitInfo(S,A) (10) (10)C4.5算法計算每個屬性的信息增益比。具有最高信息增益比的屬性選作給定集合S的測試屬性。創(chuàng)建一個節(jié)點，并以該屬性標(biāo)記，對屬性的每個值創(chuàng)建分枝，并據(jù)此劃分樣本。3.2 算法框架確切的說，C4.5不是單個的算法，而是一套算法，C4.5有許多的功能，每個功能都對應(yīng)著一個算法，這些功能組合起來就形成了一套算法就是C4.5。C4.5分類樹構(gòu)造算法框架如下圖：圖1 算法框架圖該算法的框架表述還是比較清晰的，從根節(jié)點開始不斷得分治，遞歸，生長，直至得到最后的結(jié)果。根節(jié)點代表整個訓(xùn)練樣本集，通過在每個節(jié)點對某個屬性的測試驗證，算法遞歸得將數(shù)據(jù)集分成更小的數(shù)據(jù)集。某一節(jié)點對應(yīng)的子樹對應(yīng)著原數(shù)據(jù)集中滿足某一屬性測試的部分?jǐn)?shù)據(jù)集。這個遞歸過程一直進(jìn)行下去，直到某一節(jié)點對應(yīng)的子樹對應(yīng)的數(shù)據(jù)集都屬于同一個類為止。3.3 C4.5算法偽代碼假設(shè)用S代表當(dāng)前樣本集，當(dāng)前候選屬性集用A表示，則C4.5算法C4.5formtree(S, A)的偽代碼如下。算法：Generate_decision_tree由給定的訓(xùn)練數(shù)據(jù)產(chǎn)生一棵決策樹；輸入：訓(xùn)練樣本samples；候選屬性的集合attributelist；輸出：一棵決策樹；（1）創(chuàng)建根節(jié)點N；（2）IF S都屬于同一類C，則返回N為葉節(jié)點，標(biāo)記為類C；（3）IF attributelist為空 OR S中所剩的樣本數(shù)少于某給定值則返回N為葉節(jié)點，標(biāo)記N為S中出現(xiàn)最多的類；（4）FOR each attributelist中的屬性；計算信息增益率information gain ratio；（5）N的測試屬性test.attribute = attributelist具有最高信息增益率的屬性；（6）IF測試屬性為連續(xù)型則找到該屬性的分割閾值；（7）For each由節(jié)點N一個新的葉子節(jié)點If該葉子節(jié)點對應(yīng)的樣本子集S為空則分裂此葉子節(jié)點生成新葉節(jié)點，將其標(biāo)記為S中出現(xiàn)最多的類Else 在該葉子節(jié)點上執(zhí)行C4.5formtree(S, S.attributelist)，繼續(xù)對它分裂；（8）計算每個節(jié)點的分類錯誤，進(jìn)行剪枝。4 實例分析下面我們通過對畢業(yè)生就業(yè)信息的分析加以理解。在這個分析的結(jié)果能夠幫助教育者尋找到可能影響畢業(yè)生就業(yè)的信息，從而在今后的教學(xué)過程中進(jìn)行改進(jìn)，使得畢業(yè)生在就業(yè)時更具有競爭力。表1的數(shù)據(jù)時經(jīng)過預(yù)處理的數(shù)據(jù)集，從表中我們可以得到類標(biāo)號屬性“就業(yè)情況”有2個不同的值（“已”，“未”），因此有2個不同的類。其中對應(yīng)于類值“已”有14個樣本，類值“未”有8個樣本。根據(jù)公式（5）我們先計算訓(xùn)練集的全部信息量：I(就業(yè)情況) = I(14, 8) = -14/22log2(14/22)-8/22log2(8/22) = 0.04566030接著，需要計算每個屬性的信息增益比。如以屬性“性別”為例：由公式（5）有：I(男) = I(10, 7) = -10/17log2(10/17)-7/17log2(7/17)=0.97741728I(女) = I(4, 1) = -4/5log2(1/5)-1/5log2(1/5)=0.72192809由公式（6）有：E(性別) = 17/22*I(男) + 5/22*I(女)=0.91935197由公式（8）求出這種劃分的信息增益：Gain(性別) = I(就業(yè)情況) E(性別) = 0.02630833再根據(jù)公式（9）求出在該屬性上的分裂信息：SplitInfo(性別) = -17/22log2(17/22)-5/22-log2(55/22)=0.77322667最后再根據(jù)公式（10）求出在該屬性上的增益比：GainRatio(學(xué)生干部) = 0.41171446, GainRatio(綜合成績) = 0.08839108, GainRatio(畢業(yè)成績) = 0.10167158由上述計算結(jié)果可知“學(xué)生干部”在屬性中具有最大的信息增益比，取“學(xué)生干部”為根屬性，引出一個分枝，樣本按此劃分。對引出的每一個分枝再用此分類法進(jìn)行分類，再引出分枝。最后所構(gòu)造出的判定數(shù)如下圖所示：圖2 畢業(yè)生就業(yè)情況判定樹5 C4.5算法的優(yōu)勢與不足5.1 C4.5算法的優(yōu)勢（1）保持了原有決策樹算法的優(yōu)點：決策樹方法結(jié)構(gòu)簡單，便于理解；決策樹模型效率高，對訓(xùn)練集較大的情況較為適合； 決策樹方法通常不需要接受訓(xùn)練集數(shù)據(jù)外的知識；決策樹方法具有較高的分類精確度。（2）對ID3算法進(jìn)行了改進(jìn)：決策使用信息增益作為屬性選擇度量，更傾向于選擇分支更多的屬性；可以處理連續(xù)值；可以處理缺失值；對樹進(jìn)行剪枝，避免過擬合。5.2 C4.5算法的不足：（1）數(shù)據(jù)集增大一點，學(xué)習(xí)時間會迅速地增長：處理連續(xù)屬性比較耗時，計算信息增益率的速度還有待提高；在構(gòu)造樹的過程中，需要對數(shù)據(jù)集進(jìn)行多次的順序掃描和排序，因而導(dǎo)致算法的低效；（2）對訓(xùn)練樣本數(shù)量和質(zhì)量要求較高，對空值的適應(yīng)性較差；（3）算法不夠穩(wěn)定，精度也不是最高，后續(xù)發(fā)展為C5.0算法。參考文獻(xiàn)1喬增偉,孫衛(wèi)祥. C4.5算法的兩點改進(jìn)J. 江蘇工業(yè)學(xué)院報,2008,04:56-59.2李會,胡笑梅. 決策樹中ID3算法與C4.5算法分析與比較J. 水電能源科學(xué),2008,02:129-132+163.3黃愛輝. 決策樹C4.5算法的改進(jìn)及應(yīng)用J. 科學(xué)技術(shù)與程,2009,01:34-36+42.4李瑞,程亞楠. 一種改進(jìn)的C4.5算法J. 科學(xué)技術(shù)與工程,2010,27:6670-6674. 8廖紅文，周德龍.AdaBoost及其改進(jìn)算法綜述J.計算機系統(tǒng)應(yīng)用，2012，05:240-244.5李楠,段隆振,陳萌. 決策樹C4.5算法在數(shù)據(jù)挖掘中的分析及其應(yīng)用J. 計算機與現(xiàn)代化,2008,12:160-163.