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ù)可能缺少某些屬性的值。假如- 配套講稿:
如PPT文件的首頁顯示word圖標,表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制:
部分文檔作品中含有的國旗、國徽等圖片,僅作為作品整體效果示例展示,禁止商用。設計者僅對作品中獨創(chuàng)性部分享有著作權。
- 關 鍵 詞:
- C4
裝配圖網(wǎng)所有資源均是用戶自行上傳分享,僅供網(wǎng)友學習交流,未經(jīng)上傳用戶書面授權,請勿作他用。
鏈接地址:http://m.kudomayuko.com/p-13144352.html