C4.5算法概述

《C4.5算法概述》由會員分享，可在線閱讀，更多相關《C4.5算法概述（13頁珍藏版）》請在裝配圖網(wǎng)上搜索。

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