C45算法-文檔資料

1、1C4.5C4.5算法介紹算法介紹人工智能2一、C4.5算法的概述二、C4.5算法的具體實現(xiàn)三、C4.5算法應(yīng)用舉例C4.5算法介紹算法介紹3一、C4.5算法的概述 C4.5C4.5算法是由算法是由QuinlanQuinlan于于19931993年在年在ID3ID3算法算法的基礎(chǔ)上進一步改進形成的。的基礎(chǔ)上進一步改進形成的。 C4.5 C4.5算法也是機器學(xué)習(xí)算法中的一種分類算法也是機器學(xué)習(xí)算法中的一種分類決策樹算法決策樹算法, , 此算法用此算法用信息增益率信息增益率來選擇決策來選擇決策屬性，其核心算法是屬性，其核心算法是ID3ID3算法。它繼承了算法。它繼承了ID3ID3算算法的全部優(yōu)點，

2、并在法的全部優(yōu)點，并在ID3ID3的基礎(chǔ)上增加了對連續(xù)的基礎(chǔ)上增加了對連續(xù)屬性的屬性的離散化離散化、對未知屬性的處理和產(chǎn)生規(guī)則、對未知屬性的處理和產(chǎn)生規(guī)則等功能，克服了等功能，克服了ID3ID3算法的不足。算法的不足。4C4.5具體在以下幾個方面做出了改進: (1)(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性; ; (2)(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理, ,這是這是一個很關(guān)鍵的改進一個很關(guān)鍵的改進; ; (3)(3)在決策樹構(gòu)造過程中或者構(gòu)造完成之后在決策樹構(gòu)造過程中或者構(gòu)造完成之后, ,進行剪枝進行剪枝; ; (4)(4)能夠

3、對不完整數(shù)據(jù)進行處理能夠?qū)Σ煌暾麛?shù)據(jù)進行處理, ,如未知的屬如未知的屬性值性值; ;(5) C4.5(5) C4.5可以用決策樹形式形成產(chǎn)生式規(guī)則?？梢杂脹Q策樹形式形成產(chǎn)生式規(guī)則。一、C4.5算法的概述5二、C4.5算法的具體實現(xiàn)(1)(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性; ; (2)(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理, ,這是這是一個很關(guān)鍵的改進一個很關(guān)鍵的改進; ; (3)(3)在決策樹構(gòu)造過程中或者構(gòu)造完成之后在決策樹構(gòu)造過程中或者構(gòu)造完成之后, ,進行剪枝進行剪枝; ; (4)(4)能夠?qū)Σ煌暾麛?shù)據(jù)進行處理能夠?qū)Σ煌?/p>

4、整數(shù)據(jù)進行處理, ,如未知的屬如未知的屬性值性值; ;(5) C4.5(5) C4.5可以用決策樹形式形成產(chǎn)生式規(guī)則。可以用決策樹形式形成產(chǎn)生式規(guī)則。6 設(shè)設(shè)T T 為訓(xùn)練數(shù)據(jù)集為訓(xùn)練數(shù)據(jù)集, ,共有共有k k 個類別個類別, ,集合表示為集合表示為 C C1 1 ,C,C2 2 , , ,Ck ,Ck , | | Cj Cj | |為為Cj Cj 類的例子數(shù)類的例子數(shù), , | | T T | |為數(shù)據(jù)集為數(shù)據(jù)集T T 的例子數(shù)。的例子數(shù)。 選擇一個屬性選擇一個屬性V, V, 設(shè)它有設(shè)它有n n個互不重合的取值個互不重合的取值va va ( ( 11a an) ,n) ,則則T T 被分為被

5、分為n n個子集個子集 T T1 1,T,T2 2 ,Tn , ,Tn , 這里這里Ti Ti 中的所有實例的取值均為中的所有實例的取值均為vivi。| |TiTi| |為為V V = =vi vi 的例子數(shù)的例子數(shù), , | |CjvCjv| |是是V V = =vi vi 的例子中的例子中, ,具有具有Cj Cj 類別的類別的例子數(shù)。則有：例子數(shù)。則有： (1)類別類別Cj Cj 的發(fā)生概率的發(fā)生概率: p (Cj) : p (Cj) = |= |CjCj| |/ /| |T T| |; ; ( (2 2) )屬性屬性V V = = vi vi 的發(fā)生概率的發(fā)生概率:p (vi) :p (

6、vi) =|=|TiTi| |/ /| |T T| |; ; ( (3 3) )屬性屬性V V = = vi vi 例子中例子中, ,具有類別具有類別Cj Cj 的條件概率的條件概率: : p(Cj p(Cj | | vi ) vi ) = |= |Cjv Cjv | | / / | | Ti Ti | |。 類別的類別的信息熵：信息熵：(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性;kjjjkjjjToTCTCCpCpC1212)(inf|log|)(log)()(H7按照屬性按照屬性V V 把集合把集合T T分割分割, ,分割后的分割后的類別條件熵類別條件熵為：

7、為：)(inf)(inf|)|(log)|()()|(H1112ToToTTvCpvCpvpVCvivniinikjijiji(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性;8信息增益信息增益( (Gain)Gain) ：)(inf)(inf)|()()(GToToVCHCHVainv屬性屬性V V的信息熵：的信息熵：)(inf_|log|) )(log)()(H1212VosplitTTTTvpvpVniiiniii(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性;9信息增益率：信息增益率：)()(_GVHVGainratioainC4.

8、5 C4.5 采用了信息增益率作為對選擇分枝屬性的分枝采用了信息增益率作為對選擇分枝屬性的分枝準(zhǔn)則。信息增益率表示了由分枝產(chǎn)生的有用信息的準(zhǔn)則。信息增益率表示了由分枝產(chǎn)生的有用信息的比率。因此比率。因此, ,這個值越大這個值越大, , 分枝包含的有用信息越多。分枝包含的有用信息越多。(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性;10與與ID3ID3算法相比，算法相比，ID3ID3算法選擇信息增益最大即熵下降最算法選擇信息增益最大即熵下降最大的屬性進行分支的。當(dāng)有大量不同的屬性值和采用標(biāo)大的屬性進行分支的。當(dāng)有大量不同的屬性值和采用標(biāo)準(zhǔn)化的處理程序時準(zhǔn)化的處理程序時

9、, , 這種啟發(fā)式方法很有效。而這種啟發(fā)式方法很有效。而C4.5C4.5算算法是選擇信息增益率最大的屬性進行分支的。從局部看，法是選擇信息增益率最大的屬性進行分支的。從局部看，ID3ID3算法每一步都選擇最優(yōu)分支屬性，但是從整體上看，算法每一步都選擇最優(yōu)分支屬性，但是從整體上看，有可能使得整個決策樹復(fù)雜。而有可能使得整個決策樹復(fù)雜。而C4.5C4.5算法從局部看不一算法從局部看不一定的選擇信息增益最大的屬性，但是從整體看，分支更定的選擇信息增益最大的屬性，但是從整體看，分支更明確，獲得的有用信息更多。明確，獲得的有用信息更多。(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選

10、擇屬性;11(1)(1)用信息增益率代替信息增益來選擇屬性用信息增益率代替信息增益來選擇屬性; ; (2)(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理; ;(3)(3)在決策樹構(gòu)造過程中或者構(gòu)造完成之后在決策樹構(gòu)造過程中或者構(gòu)造完成之后, ,進行剪枝進行剪枝; ; (4)(4)能夠?qū)Σ煌暾麛?shù)據(jù)進行處理能夠?qū)Σ煌暾麛?shù)據(jù)進行處理, ,如未知的屬如未知的屬性值性值; ;(5) C4.5(5) C4.5可以用決策樹形式形成產(chǎn)生式規(guī)則。可以用決策樹形式形成產(chǎn)生式規(guī)則。二、C4.5算法的具體實現(xiàn)12 C4 C45 5算法將分類范圍從分類的屬性擴展到數(shù)字屬性。算法將分類范圍從分類的屬性

11、擴展到數(shù)字屬性。如果數(shù)據(jù)集中存在連續(xù)型的描述性屬性如果數(shù)據(jù)集中存在連續(xù)型的描述性屬性( (數(shù)字屬性數(shù)字屬性) )，C4C45 5算法首先將這些連續(xù)型屬性的值分成不同的區(qū)間，算法首先將這些連續(xù)型屬性的值分成不同的區(qū)間，即即“離散化離散化”。通常將連續(xù)型屬性值。通常將連續(xù)型屬性值“離散化離散化”的方法為：的方法為：尋找該連續(xù)型屬性的最小值，并將它賦值給尋找該連續(xù)型屬性的最小值，并將它賦值給minmin，尋找，尋找該連續(xù)型屬性的最大值，并將它賦值給該連續(xù)型屬性的最大值，并將它賦值給maxmax；設(shè)置區(qū)間設(shè)置區(qū)間minmin，maxmax中的中的N N個等分?jǐn)帱c個等分?jǐn)帱cAiAi，其中，其中，i=1,

12、2,i=1,2, ,N,N；分別計算把分別計算把(min(min，Ai)Ai)和和(Ai,max)(i=1,2,3, (Ai,max)(i=1,2,3, ,N),N)作為區(qū)作為區(qū)間值時的信息增益率（間值時的信息增益率（RatioRatio）值，并進行比較；）值，并進行比較；選取選取信息增益率最大的信息增益率最大的A A。作為該連續(xù)型屬性的斷點，將屬性。作為該連續(xù)型屬性的斷點，將屬性值設(shè)置為值設(shè)置為minmin，AA和和(A(A，max)max)兩個區(qū)間值。兩個區(qū)間值。(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理13 離散化處理過程中，離散化處理過程中，C4.5C4.5算法

13、是對節(jié)點上的每個算法是對節(jié)點上的每個屬性都要計算其信息增益率屬性都要計算其信息增益率, ,然后從中選擇信息增益然后從中選擇信息增益率最大的屬性斷點。由于在信息增益率計算過程中涉率最大的屬性斷點。由于在信息增益率計算過程中涉及到對數(shù)函數(shù)的計算及到對數(shù)函數(shù)的計算, ,在計算程序中就得調(diào)用庫函數(shù)在計算程序中就得調(diào)用庫函數(shù), ,同時隨著數(shù)據(jù)量的增大，計算量也隨之增大。這樣就同時隨著數(shù)據(jù)量的增大，計算量也隨之增大。這樣就增加了計算量時間。因此，在改進的增加了計算量時間。因此，在改進的C4.5C4.5算法中采用算法中采用了了“Fayyad Fayyad 邊界點判定定理邊界點判定定理”(2)能夠完成對連續(xù)屬

14、性的離散化處理能夠完成對連續(xù)屬性的離散化處理14 定義定義 : 屬性屬性A 中的一個值中的一個值T 是一邊界點是一邊界點, 當(dāng)且僅當(dāng)在按當(dāng)且僅當(dāng)在按A 的值排序的實例序列中的值排序的實例序列中, 存在兩個實例存在兩個實例e1 , e2 S 具有不同的類具有不同的類, 使得使得A ( e1 ) T A( e2 ) , 且不存在且不存在任何其他的實例任何其他的實例eS , 使得使得A( e1 ) A ( e) A ( e2 ) 。A ( e) 表示實例表示實例e 的的A屬性值。屬性值。S 表示實例的表示實例的集合。集合。 定理定理 : 若若T 使得使得E ( A , T , S ) 最小最小, 則

15、則T 是一個邊界點。是一個邊界點。其中其中, A 為屬性為屬性, S 為實例集合為實例集合, E表示平均類熵表示平均類熵, T 為為某一閾值點。某一閾值點。 定理表明定理表明, 對連續(xù)屬性對連續(xù)屬性A , 使得實例集合的平均類熵達使得實例集合的平均類熵達到最小值的到最小值的T , 總是處于實例序列中兩個相鄰異類實例總是處于實例序列中兩個相鄰異類實例之間。之間。(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理15 由由Fayyad 邊界點判定定理可知邊界點判定定理可知, 無需檢查每一個閾無需檢查每一個閾值點值點, 只要檢查相鄰不同類別的邊界點即可。為了保持與只要檢查相鄰不同類別

16、的邊界點即可。為了保持與C4.5 的一致性的一致性, 這里邊界點選為相鄰不同類別的屬性值這里邊界點選為相鄰不同類別的屬性值中較小的一個。例如中較小的一個。例如, 當(dāng)排序后的實例屬性值為當(dāng)排序后的實例屬性值為 v1 , v2 , , v10 , 其中前其中前3 個屬于類別個屬于類別C1 , 中間中間4 個屬于類別個屬于類別C2 , 最后最后3個屬于類別個屬于類別C3 , 因此只需考察兩個邊界點因此只需考察兩個邊界點v3 與與v7而無需檢查其余而無需檢查其余7 個閾值點個閾值點, 然后選擇然后選擇v3 與與v7 中使得平中使得平均類熵最小的那個作為最優(yōu)閾值。均類熵最小的那個作為最優(yōu)閾值。(2)能夠

17、完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理16 當(dāng)需要離散化的屬性的屬性值越多當(dāng)需要離散化的屬性的屬性值越多, , 而所屬類別而所屬類別越少時越少時, , 性能提高越明顯性能提高越明顯; ; 當(dāng)出現(xiàn)最不理想情況當(dāng)出現(xiàn)最不理想情況, , 即每個屬性值對應(yīng)一個類即每個屬性值對應(yīng)一個類別別, , 改進算法運算次數(shù)與未改進算法相同改進算法運算次數(shù)與未改進算法相同, , 不會降低不會降低算法性能。算法性能。(2)能夠完成對連續(xù)屬性的離散化處理能夠完成對連續(xù)屬性的離散化處理17C4.5分類算法在碩士研究生智育測評中的應(yīng)用分類算法在碩士研究生智育測評中的應(yīng)用采用某高校碩士研究生一年級的采用某高

18、校碩士研究生一年級的20名學(xué)生的期末考試成績作為數(shù)名學(xué)生的期末考試成績作為數(shù)據(jù)集據(jù)集,其中的課程有英語精讀、英語聽說等英語類課程、自然辯其中的課程有英語精讀、英語聽說等英語類課程、自然辯證法、科學(xué)社會主義等政治類課程證法、科學(xué)社會主義等政治類課程,還有數(shù)據(jù)挖掘概論、數(shù)據(jù)庫還有數(shù)據(jù)挖掘概論、數(shù)據(jù)庫原理、并行計算導(dǎo)論等專業(yè)性課程。原理、并行計算導(dǎo)論等專業(yè)性課程。在建立決策樹的過程中在建立決策樹的過程中,我們將按以下方式分類我們將按以下方式分類:政治成績政治成績(包括自包括自然辯證法和科學(xué)社會主義然辯證法和科學(xué)社會主義) ,英語成績英語成績(包括英語精讀、英語聽說包括英語精讀、英語聽說和專業(yè)外語和專

19、業(yè)外語) ,核心專業(yè)課成績核心專業(yè)課成績(與本專業(yè)培養(yǎng)目標(biāo)最緊密的課程與本專業(yè)培養(yǎng)目標(biāo)最緊密的課程) ,一般專業(yè)課成績一般專業(yè)課成績(除核心專業(yè)課外的專業(yè)課除核心專業(yè)課外的專業(yè)課) 。將這四個屬性作為決策屬性將這四個屬性作為決策屬性,定義成績大于等于定義成績大于等于85分為分為“優(yōu)優(yōu)”;大大于等于于等于80,小于小于85分為分為“良良”;大于等于大于等于70,小于小于80為為“中中”。將。將四個屬性的和作為智育成績四個屬性的和作為智育成績,并按智育測評的標(biāo)準(zhǔn)并按智育測評的標(biāo)準(zhǔn),將訓(xùn)練樣本中將訓(xùn)練樣本中智育成績由高到低按比例分類智育成績由高到低按比例分類: 10%為優(yōu)、為優(yōu)、30%為良、為良、4

20、0%為中為中等、剩余為及格四個標(biāo)準(zhǔn)等、剩余為及格四個標(biāo)準(zhǔn),并將這四個標(biāo)準(zhǔn)作為分類屬性并將這四個標(biāo)準(zhǔn)作為分類屬性(如表如表1所示所示) 。三、C4.5算法應(yīng)用舉例18 表表1決策樹訓(xùn)練樣本集決策樹訓(xùn)練樣本集編號 政治 英語 核心專業(yè)課 一般專業(yè)課 智育成績 1 78. 67 83. 33 88. 14 86 336. 14 2 81 83. 67 94. 86 86. 44 345. 97 3 83. 33 91. 33 90. 43 87. 06 352. 15 4 81. 33 82. 5 93. 33 88. 2 345. 36 5 71. 33 78. 17 90. 86 85. 93

21、326. 29 6 83. 33 79. 67 87. 14 80 330. 14 7 79 80. 83 90 87. 32 337. 15 8 82 82. 67 88. 71 82. 28 335. 66 9 72. 67 81. 33 87. 5 83. 13 324. 6310 81. 33 84. 83 81. 29 87. 78 335. 23三、C4.5算法應(yīng)用舉例19 表表1決策樹訓(xùn)練樣本集決策樹訓(xùn)練樣本集編號 政治 英語 核心專業(yè)課 一般專業(yè)課 智育成績11 77. 33 80. 5 85. 14 86. 53 329. 5012 75. 67 86. 5 91. 13 9

22、0. 41 343. 7113 81. 33 84 89. 33 89. 56 344. 2214 84. 33 85. 67 91 81. 53 342. 5315 82 85. 5 88. 17 82. 26 337. 9316 79. 67 85 86. 86 86. 89 338. 4217 79 86. 17 89 88. 75 342. 9218 78. 67 83. 83 78. 29 89. 38 330. 1719 85. 67 86. 67 94. 29 87. 94 354. 5720 79. 33 79. 17 87. 83 80. 72 327. 05三、C4.5算法

23、應(yīng)用舉例20 2. 2建立決策樹建立決策樹 智育成績中達到優(yōu)、良、中等、及格四類標(biāo)準(zhǔn)的子集數(shù)分別為: r1 = 2、r2 = 6、r3 = 8、r4 = 4,首先計算 集合T分類的信息熵: I(r1 、r2 、r3 、r4,)=I(2,6,8,4) = =1. 9464393 然后計算每個決策屬性的期望信息量(即熵值) ,以決策屬性“政治成績”為例,分別計算它為優(yōu)、良、中三個類別時的期望信息量,最終得出它的信息增益率。202log202-2206log206-2208log208-2204log204-2三、C4.5算法應(yīng)用舉例21當(dāng)“ 政治成績 ” 為優(yōu)時, I( u11 , u21 , u

24、31 , u41 ) = I(1, 0, 0, 0) =0.225;(2) 當(dāng)“ 政治成績 ” 為良時 ,I ( u12 , u22 , u32 , u42 ) = I (1, 4, 4, 0)(3) 當(dāng)“ 政治成績 ” 為中時 ,三、C4.5算法應(yīng)用舉例522. 1204log204204log204202log202)4 , 4 , 2 , 0(),( I22243332313 Iuuuu201log201-2204log204-2392 . 1204log204-222所以政治成績的期望信息量為：387.1),(2010),(209),( I201(E433323134232221241

25、312111uuuuIuuuuIuuuu政治成績）三、C4.5算法應(yīng)用舉例政治成績的信息增益為：0.559(),( I(G4321政治成績）政治成績）Errrrain政治成績的信息增益率為：0.4029096E(（政治成績）政治成績）政治成績）GainRatio23三、C4.5算法應(yīng)用舉例 同理同理, ,得出決策屬性得出決策屬性“ 英語成績英語成績 ” 、 “核心核心專業(yè)課成績專業(yè)課成績 ” 、 “一般專業(yè)課成績一般專業(yè)課成績 ” 的信息增的信息增益率分別為益率分別為: :0.144E(（核心專業(yè)）核心專業(yè)）核心專業(yè)）GainRatio0.366E(（英語成績）英語成績）英語成績）GainRa

26、tio0.117E(（一般專業(yè)課）一般專業(yè)課）一般專業(yè)課）GainRatio24 決策屬性決策屬性“政治成績政治成績 ” 的信息增益率最大的信息增益率最大, ,因此因此將此作為決策樹的根節(jié)點將此作為決策樹的根節(jié)點, ,對于每個分支按上述步驟對于每個分支按上述步驟, ,根據(jù)信息增益率由大到小根據(jù)信息增益率由大到小, ,建立從根節(jié)點到葉節(jié)點的建立從根節(jié)點到葉節(jié)點的決策樹。決策樹。三、C4.5算法應(yīng)用舉例2526 2 . 3 結(jié)果分析 由此決策樹可知由此決策樹可知: (1) 英語成績?yōu)閮?yōu)的情況下英語成績?yōu)閮?yōu)的情況下 ,核心專業(yè)課成績?nèi)珵閮?yōu)核心專業(yè)課成績?nèi)珵閮?yōu) ,一般專業(yè)課一般專業(yè)課成績?yōu)閮?yōu)的概率是成

27、績?yōu)閮?yōu)的概率是 71 . 4%。說明英語水平的提高對計算機專業(yè)課程。說明英語水平的提高對計算機專業(yè)課程的學(xué)習(xí)有很大的幫助的學(xué)習(xí)有很大的幫助 ,對于出色的完成培養(yǎng)目標(biāo)具有至關(guān)重要的作用。對于出色的完成培養(yǎng)目標(biāo)具有至關(guān)重要的作用。 (2) 核心專業(yè)課成績?yōu)閮?yōu)的情況下核心專業(yè)課成績?yōu)閮?yōu)的情況下 ,一般專業(yè)課成績?yōu)閮?yōu)的概率一般專業(yè)課成績?yōu)閮?yōu)的概率是是 66 . 7%。說明核心專業(yè)課成績的提高對一般專業(yè)課成績的提高是。說明核心專業(yè)課成績的提高對一般專業(yè)課成績的提高是正相關(guān)的。正相關(guān)的。 (3) 在智育成績?yōu)樵谥怯煽優(yōu)椤?良良 ” 以上的同學(xué)中以上的同學(xué)中 ,他們的核心專業(yè)課成他們的核心專業(yè)課成績都是績都是“ 優(yōu)優(yōu) ” 。說明這種課程設(shè)置方式。說明這種課程設(shè)置方式 ,使智育成績優(yōu)異的同學(xué)使智育成績優(yōu)異的同學(xué) ,核心專業(yè)課成績也非常優(yōu)秀核心專業(yè)課成績也非常優(yōu)秀 ,這是研究生教育管理者最希望看到的結(jié)這是研究生教育管理者最希望看到的結(jié)果。果。 (4) 政治成績的好壞政治成績的好壞 ,對于英語成績、對于英語成績、 專業(yè)課成績的好壞沒有必專業(yè)課成績