C45算法生成決策樹的研究

1、c4.5算法生成決策樹1、基礎(chǔ)知識當(dāng)我們需要對一個隨機(jī)事件的概率分布逬行預(yù)測時我們的預(yù)測應(yīng)當(dāng)滿足全部已知的條 件，而對未知的情況不要做但可主觀假設(shè)。在這種情況下，概率分布最均勻，預(yù)測的風(fēng)險最 小。因?yàn)檫@時概率分布的信息嬌最大，所以稱之為大嬌法”最大爛法在數(shù)學(xué)形式上很漂亮, 但是實(shí)現(xiàn)起來比較復(fù)雜，但把它運(yùn)用于金融領(lǐng)域的誘惑也比較大，比如說決定股票漲落的因 素可能有幾十甚至上百種,而最大嬌方法涪恰能找到一個同時滿足成千上萬種不同條件的模 型。目前，針對分類問題已有了若干不同領(lǐng)域方法的算法，例如統(tǒng)計學(xué)、機(jī)器學(xué)習(xí)、神經(jīng)網(wǎng) 絡(luò)和粗糙集理論等。其中從機(jī)器學(xué)習(xí)中引岀的決策樹方法是一種較為通用并被深入硏究的分

2、 類方法，由于決策樹分類算法是一種直觀快速的分類方法，它的分類過程不需要背景知識、 并且清晰、易于理解，因此有很大的實(shí)用價值。目前已經(jīng)形成了多種決策樹算法。如cls、 id3、chaid、cart、fact、c4.5、gini、sees. sliq、sprint 等。在決策樹分類算法中，最常用的、最經(jīng)典的是c4.5算法,它繼承了 id3算法的優(yōu)點(diǎn)并 對id3算法進(jìn)行了改進(jìn)和補(bǔ)充。c4.5算法采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn)，克服 了 id3算法中信息增益選擇屬性時偏向選擇取值多的屬性的不足，并能夠完成對連續(xù)屬性 離散化的處理,還能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。根據(jù)分割方法的不同，目前決策的算法可

3、以 分為兩類：基于信息論(information theory )的方法和最小gini指標(biāo)(lowest gini index)方法。對應(yīng)前者的算法有id3、c4.5 ,后者的有cart、sliq和sprint。c4.5算法是以信息論為基礎(chǔ)，以信息爛和信息增益度為衡量標(biāo)準(zhǔn),從而實(shí)現(xiàn)對數(shù)據(jù)的歸納分類。2、算法以下圖數(shù)據(jù)為例，介紹用c4.5建立決策樹的算法。表1室外溫度室內(nèi)溫度室外濕度風(fēng)力 大小機(jī)房樓 層機(jī)房朝向（0： 陰，1：陽）機(jī)房開啟設(shè)備總 額定功率（千瓦）2317654105002417622214502718603-103002419583203002518522114502618505

4、-115003019452214502818433104502718483-10500291840410500id3算法最初假定屬性都是離散值，但在實(shí)際應(yīng)用中，很多屬性值都是連續(xù)的。c4.5對id3不能處理連續(xù)型屬性的缺點(diǎn)進(jìn)行了改進(jìn)。如果存在連續(xù)型的描述性屬性，首先將連 續(xù)型屬性的值分成不同的區(qū)間，即"離散化。對上表中將實(shí)際耗電量分為10個區(qū)間（09 ）（300-320,320-340,340-360,360-380,380-400,400420,420440,440460,460480,480500 ）因?yàn)樽罱K是要得到實(shí)際的耗電量區(qū)間，因此"實(shí)際耗電量屬于"類別

5、屬性"?！笆彝鉁?度"、室內(nèi)溫度"、”室外濕度"、風(fēng)力大小"、“機(jī)房樓層"、“機(jī)房朝向"、機(jī)房開啟設(shè)備總額定功率"屬于非類別屬性"。表2室外溫 度室內(nèi)溫 度室外 濕度風(fēng)力大 小機(jī)房 樓層機(jī)房朝向 （0 ：陰，1：陽）機(jī)房開啟設(shè) 備總額定功 率（千瓦）實(shí)際耗電 量（區(qū)間）231765410500524176222145072718603-103000241958320300025185221145052618505-115004301945221450928184331045062718483-105005

6、2918404105007非類別屬性類別屬性通過表2知，實(shí)際耗電量區(qū)間的個數(shù)為：表3序號區(qū)間值個數(shù)102241353461572691總計10定義若存在n個相同概率的消息(massage),則每個消息的概率p是1/n, 個消息傳 遞的信息量為-log2(p) = log2(«)o若有16個事件，則-log2(16) = 4,則需4個比特來 代表一個消息。例如：表3中，區(qū)間為0的信息量為：iog2(2/10)= log2(10)=3.322定義2：若給定的概率分布 (“,)，則由該分布傳遞的信息量稱為p的爛。即() = -(pixlog2(pj) + p2xlog2(p2) + . +

7、 pnxlog2(pn)注意：概率分布越均勻，其信息量越人)。定義3：若f 記錄的集合1根據(jù)類別屬性的值被分成互相獨(dú)立的類g，c2，.q,則識別t的一個元素所屬哪個類所需要的信息量是info(t)= i(p)f其中卩是(c19c2,.ca)的概 率分布，即p = (icii/iti,ic2i/iti,.icj/iti,)例如：表3中，得到實(shí)際耗電量區(qū)間的信息量為(以下單位為比特，下同)：info(t) = i(p)= -<2/10xlog2(2/10) + l/10xlog2(l/10) + 3/10xlog2(3/10)+ j/10xlog2(l/10) + 2/10xlog2(2/1

8、0) + l/10xlog2(l/10) '定義4：若我們先根據(jù)非類別屬性x的值將t分成集合片,丁2,則確定1中一個元素類的信息量可通過確定7；的加權(quán)平均值來得到，即lnfo（7；）的加權(quán)平均值為：bifo(x.t)= £| 7；丨 / 丨卩丨 xinfog1=1例如:屬性“室內(nèi)溫度”的值有“17、18、19”，分類見下表:表4序號室內(nèi)溫度個數(shù)所屬的區(qū)間（個數(shù)11725(1)7(1)21860(1)4(1)5(2)6(1)7(1)31920(1)9(1)總計10p (17) = (1/2, 1/2)p (18) = (1/6,1/6, 2/6, 1/6, 1/6)p (19)

9、 = (1/2,1/2)則每個溫度的信息量為:皿(17) = /(卩(17) = -(1/2 *呃(1/2)+1/2*呃(1/2歸.000切向(18) = /(18)= -=2.252'1/6* log2(l/6)+l/6*log2(l/6)+2/6*log2(2/6)+>j/6* log2(l/6)+l/6*log2(l/6)丿9)=/(p(l 9) =-(1/2*log2(l/2)+1/2*log2(l 72)=1.000/"b(室內(nèi)溫度,t) = 2/l0x/n/?;(l7) + 6/l0x/n/?xl8) + 2/l0xzn/?xl9)=1.751定義5：將增益

10、gain （x, t）定義為：gc77（- ,t） = injo（t） -1對o（戶用胃增益，就倉旨在應(yīng)用了某一測試之后，其對應(yīng)的可能性豐富程度下降，不確定性減小,這個減小的幅度就是增益，其實(shí)質(zhì)上對 應(yīng)著分類帶來的好處1上式的增益值為：gai叭x,t）= htfo（t）- btfo（室內(nèi)溫,1）=2.446-1.751=0.695以上是id3計算信息增益的方法，c4.5算法對此進(jìn)行了改進(jìn)。c4.5算法采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn)，克服了 id3算法中信息增益選擇屬性時偏向選擇取值多的屬 性的不足。若我們一個屬性d ,據(jù)其取值將t分成集合tl、t2tn ,當(dāng)每一個集合中所有記錄得岀的結(jié)果

11、相同，即同時取值為"是或"否"時，info(d , t)為0匕時增益gain(dj )取最大值。因此用增益比值來代替，即：gainratiodj) = - °刃"(色門splitlnfodj)由于t是以類型屬性d的值為基準(zhǔn)進(jìn)行的分割，故splitinfo ( d , t )是信息量。舉例:根據(jù)表4 ,得到:splitinfo (室內(nèi)溫度,t)= (2/10*10空(2/1() + 6/10*10(6/10) + 2/10*10空(2/1()= 1.371 ,則 gainratiod.t) = 0.695/1.371=0.507可利用函數(shù)gain

12、的定義將屬性進(jìn)行排列，并可構(gòu)造一棵決策樹，其中每一個節(jié)點(diǎn)都是 屬性中具有最大增益的屬性，從而不必考慮來自于根的路徑。3. 選擇連續(xù)變量的閾值(測試條件)到連續(xù)數(shù)據(jù)的分支的閾值點(diǎn)如何確定呢？很簡單，把需要處理的樣本(對應(yīng)根節(jié)點(diǎn))或 樣本子集(對應(yīng)子樹)按照連續(xù)變量的大小從小到大進(jìn)行排序，假設(shè)該屬性對應(yīng)的不同的屬性值一共有n個，那么總共有n-1個可能的候選分割閾值點(diǎn),每個候選的分割閾值點(diǎn)的值 為上述排序后的屬性值鏈表中兩兩前后連續(xù)元素的中點(diǎn)，那么我們的任務(wù)就是從這個n1 個候選分割閾值點(diǎn)中選出一個，使得前面提到的信息論標(biāo)準(zhǔn)最大。在excel中，對室外溫 度(第二步)詳細(xì)介紹了如何分割閾值點(diǎn)并逬行計

13、算。4、樹的終止樹的建立實(shí)際上是一個遞歸過程,那么這個遞歸什么時候到達(dá)終止條件退出遞歸呢？有 兩種方式，第一種方式是如果某一節(jié)點(diǎn)的分支所覆蓋的樣本都屬于同一類的時候，那么遞歸就可以終止，該分支就會產(chǎn)生一個葉子節(jié)點(diǎn)。還有一種方式就是，如果某一分支覆蓋的樣本 的個數(shù)如果小于一個閾值，那么也可產(chǎn)生葉子節(jié)點(diǎn)，從而終止建立樹。我們只考慮二叉分割 的情況,因?yàn)檫@樣生成的樹的準(zhǔn)確度更高。5、樹的修剪樹一旦生成后，便進(jìn)入第二階段一彥剪階段。決策樹為什么要剪枝？原因就是避免決策樹過擬合樣本。前面的算法生成的決策樹非常的詳細(xì)而龐大，每個屬性都被詳細(xì)地 加以考慮，決策樹的樹葉節(jié)點(diǎn)所覆蓋的訓(xùn)練樣本都是”純"

14、的。因此用這個決策樹來對訓(xùn)練 樣本進(jìn)行分類的話，你會發(fā)現(xiàn)對于訓(xùn)練樣本而言,這個樹表現(xiàn)堪稱完美，它可以100%完美 正確得對訓(xùn)練樣本集中的樣本進(jìn)行分類(因?yàn)闆Q策樹本身就是100%完美擬合訓(xùn)練樣本的產(chǎn) 物)，但是，這會帶來一個問題,如果訓(xùn)練樣本中包含了一些錯誤,按照前面的算法,這些 錯誤也會100%點(diǎn)不留得被決策樹學(xué)習(xí)了，這就是"過擬合。c4.5的締造者昆蘭教授很 早就發(fā)現(xiàn)了這個問題,他做過一個試驗(yàn)，在某一個數(shù)據(jù)集中，過擬合的決策樹的錯誤率比一 個經(jīng)過簡化了的決策樹的錯誤率要高。目前決策樹的修剪的策略有三種：基于代價復(fù)雜度的修剪(cost-complexitypruning 悲觀修剪(pessimistic pruning )和 mdl ( minimum description l