C4.5算法概述

《C4.5算法概述》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《C4.5算法概述（13頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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