決策樹算法研究.doc

長治學(xué)院學(xué)士學(xué)位論文2012 屆學(xué)士學(xué)位畢業(yè)論文決策樹算法研究 學(xué) 號： 姓 名： 指導(dǎo)教師： 專 業(yè)： 系 別： 完成時(shí)間：2012年5月決策樹算法研究專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù) 姓名： 學(xué)號： 指導(dǎo)教師：摘要 決策樹算法是數(shù)據(jù)挖掘中重要的分類方法，基于決策樹的各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性、分類預(yù)測的準(zhǔn)確性等方面各有千秋，在各個(gè)領(lǐng)域廣泛應(yīng)用且已經(jīng)有了許多成熟的系統(tǒng)，如語音識別、模式識別和專家系統(tǒng)等。本文著重研究和比較了幾種典型的決策樹算法，并對決策樹算法的應(yīng)用進(jìn)行舉例。關(guān)鍵詞 決策樹算法，度量，比較，應(yīng)用1、引言數(shù)據(jù)挖掘是一個(gè)利用分析工具從大量的、不完全的、模糊的數(shù)據(jù)中，提取隱含在其中的有用的信息和知識的過程。分類算法是屬于預(yù)測式數(shù)據(jù)挖掘的一種數(shù)據(jù)分析方法，其目的是根據(jù)重要樣本數(shù)據(jù)集找出能準(zhǔn)確描述并區(qū)分?jǐn)?shù)據(jù)類的模型，以便對未來的測試數(shù)據(jù)進(jìn)行分類。決策樹算法就是一種典型的分類方法，它著眼于從一組無次序、無規(guī)則的事例中推理出決策樹表示形式的分類規(guī)則。決策樹方法的起源是概念學(xué)習(xí)系統(tǒng)CLS，發(fā)展到ID3方法為高潮，最后又演化為能處理連續(xù)屬性的C4.5，其他典型的決策樹方法還有CART，SLIQ和SPRINT等。本文重點(diǎn)介紹了ID3算法以及C4.5算法，分析比較了幾種典型算法的優(yōu)點(diǎn)和不足，并對算法所面臨的問題進(jìn)行簡要闡述，提出今后開展研究的建議。2、決策樹算法背景知識及研究現(xiàn)狀2.1 決策樹算法描述決策樹，顧名思義就是一個(gè)類似于流程圖的樹型結(jié)構(gòu)。個(gè)決策樹由根結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)構(gòu)成。樹的最高層節(jié)點(diǎn)稱為根結(jié)點(diǎn)，是整個(gè)決策樹的開始。與根結(jié)點(diǎn)相連的不同分支，對應(yīng)這個(gè)屬性的不同取值，根據(jù)不同的回答轉(zhuǎn)向相應(yīng)的分支，在新到達(dá)的結(jié)點(diǎn)處做同樣的分支判斷，持續(xù)這一過程直到到達(dá)某個(gè)葉結(jié)點(diǎn)。在決策樹中，每個(gè)內(nèi)部結(jié)點(diǎn)表示一個(gè)測試，該結(jié)點(diǎn)的每個(gè)分支表示該測試的一個(gè)結(jié)果，每個(gè)葉結(jié)點(diǎn)表示一個(gè)類別。例如公司需要預(yù)測某位客人是否要買計(jì)算機(jī)，圖2.1就是為了解決這個(gè)問題而建立的一顆決策樹,從中可以看到?jīng)Q策樹的基本組成部分：根結(jié)點(diǎn)、分支和葉結(jié)點(diǎn)。年齡學(xué)生信譽(yù)買買不買不買買中青老否是優(yōu)良圖2.1 決策樹2.2 決策樹算法研究現(xiàn)狀決策樹算法廣泛應(yīng)用于各個(gè)領(lǐng)域，已經(jīng)有了廣泛的應(yīng)用并且有許多成熟的系統(tǒng)，如語音識別、醫(yī)療診斷、模式識別和專家系統(tǒng)等。目前，決策樹技術(shù)面臨的挑戰(zhàn)表現(xiàn)在以下幾個(gè)方面：(1)可擴(kuò)展性亟待提高。在大型數(shù)據(jù)集中，能從中快速而準(zhǔn)確地發(fā)現(xiàn)隱藏于其中的主要分類規(guī)則，即認(rèn)為算法具有良好的可擴(kuò)展性。數(shù)據(jù)挖掘面臨的數(shù)據(jù)往往是海量的，對實(shí)時(shí)性要求較高的決策場所，數(shù)據(jù)挖掘方法的主動性和快速性顯得日益重要。 (2)適應(yīng)多數(shù)據(jù)類型和容噪性。隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息的社會化，數(shù)據(jù)挖掘的對象已不單是關(guān)系數(shù)據(jù)庫模型，而是分布、異構(gòu)的多類型數(shù)據(jù)庫，數(shù)據(jù)的非結(jié)構(gòu)化程度、噪聲等現(xiàn)象越來越突出，這也是決策樹技術(shù)面臨的困難問題。(3)決策樹方法的遞增性。數(shù)據(jù)挖掘出來的知識，只是相對于某一時(shí)間的某些數(shù)據(jù)，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識與原來的知識沖突。因此，設(shè)計(jì)具有遞增性決策樹挖掘方法，也是實(shí)用化的基本要求之一。3、決策樹算法簡介3.1 CLS算法CLS算法是早期的決策樹學(xué)習(xí)算法，是許多決策樹學(xué)習(xí)算法的基礎(chǔ)。CLS基本思想：從一棵空決策樹開始，選擇某一屬性作為測試屬性。該測試屬性對應(yīng)決策樹中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對應(yīng)于決策樹的內(nèi)部結(jié)點(diǎn)，即測試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對該子集進(jìn)行劃分，直到所有的子集都為空或者屬于同一類。例1：如表3.1所示為人員眼睛、頭發(fā)顏色與所屬人種之間的關(guān)系： 表3.1 人員眼睛、頭發(fā)顏色與所屬人種人員眼睛顏色頭發(fā)顏色所屬人種1黑色黑色黃種人2藍(lán)色金色白種人3灰色金色白種人4藍(lán)色紅色白種人5灰色紅色白種人6黑色金色混血7灰色黑色混血8藍(lán)色黑色混血根據(jù)表3.1所提供的信息，選擇“眼睛顏色”為測試屬性，可將該樣本劃分為相應(yīng)的子集如圖3.1所示。眼睛顏色1,62,4,83,5,7黑色藍(lán)色灰色圖3.1 初步構(gòu)建決策樹根據(jù)“眼睛顏色”所劃分的子集中的樣本不屬于同一類，所以選擇新的測試屬性“頭發(fā)顏色”對各個(gè)子集進(jìn)行劃分，如圖3.2所示，所得的樣本屬于同一類，決策樹構(gòu)建完成。眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色藍(lán)色灰色白種人4白種人2混血7白種人6黃種人1混血8白種人5白種人3黑色金色金色紅色黑色金色紅色黑色圖3.2 決策樹3.2 ID3算法ID3算法是決策樹學(xué)習(xí)算法中最具有影響和最為典型的算法，它的基本思想是，利用信息熵原理，選擇信息增益最大的屬性作為分類屬性。3.2.1 信息量大小的度量Shannon1948年提出的信息論理論。事件ai的信息量I(ai)可如下度量：，其中p(ai)表示事件ai發(fā)生的概率。假設(shè)有n個(gè)互不相容的事件a1,a2,a3,，an，它們中有且僅有一個(gè)發(fā)生，則其平均的信息量可如下度量：= ，在決策樹分類中，假設(shè)S是訓(xùn)練樣本集合，|S|是訓(xùn)練樣本數(shù)，樣本劃分為n個(gè)不同的類C1，C2，Cn，這些類的大小分別標(biāo)記為|C1|，|C2|，|Cn|。則任意樣本S屬于類Ci的概率為：。假設(shè)屬性A的所有不同值的集合為XA，Sv是S中屬性A的值為v的樣本子集，在選擇屬性A后的每一個(gè)分支節(jié)點(diǎn)上，對該節(jié)點(diǎn)的樣本集Sv分類的熵為E(Sv)。選擇A導(dǎo)致的期望熵定義為每個(gè)子集Sv的熵的加權(quán)和，權(quán)值為屬于Sv的樣本占原始樣本S的比例,即期望熵為：,屬性A相對樣本集合S的信息增益Gain(S，A)定義為：，其中Gain(S，A)是指因知道屬性A的值后導(dǎo)致的熵的期望壓縮。Gain(S，A)越大，說明選擇測試屬性A對分類提供的信息越多。ID3算法就是將每個(gè)節(jié)點(diǎn)選擇信息增益Gain(S，A)最大的屬性作為測試屬性。3.2.2 ID3決策樹應(yīng)用舉例例2：公司收集了數(shù)據(jù)如下表3.2所示，對于任意給定的客人，能否幫助公司將這位客人歸類。表3.2 誰在買計(jì)算機(jī)計(jì)數(shù)年齡收入學(xué)生信譽(yù)歸類：買計(jì)算機(jī)？64青高否良不買64青高否優(yōu)不買128中高否良買60老中否良買64老低是良買64老低是優(yōu)不買64中低是優(yōu)買128青中否良不買64青低是良買132老中是良買64青中是優(yōu)買32中中否優(yōu)買32中高是良買63老中否優(yōu)不買1老中否優(yōu)買(1) 計(jì)算決策屬性的熵決策屬性“買計(jì)算機(jī)？”，該屬性分為兩類：買、不買。S1(買)=641 S2(不買)=383 S=S1+S2=1024P1=641/1024=0.6260 P2=383/1024=0.3740I(S1，S2)=I(641,383)=-P1log2P1-P2log2P2=0.9537(2) 計(jì)算條件屬性的熵條件屬性共有4個(gè)，分別是年齡、收入、學(xué)生、信譽(yù)。分別計(jì)算不同屬性的信息增益。計(jì)算年齡的熵：年齡共分三個(gè)組：青年、中年、老年青年買與不買比例為128/256P1=128/384 P2=256/384I(S1，S2)=I(128,256)=-P1log2P1-P2log2P2=0.9183中年買與不買的比例為256/0P1=256/256 P2=0/256I(S1,S2)=I(256,0)=-P1log2P1-P2log2P2=0老年買與不買的比例為257/127P1=257/384 P2=127/384I(S1，S2)=I(257,127)= -P1log2P1-P2log2P2=0.9157所占比例：青年組：384/1024=0.375；中年組：256/1024=0.25；老年組：384/1024=0.375計(jì)算年齡的平均信息期望：E(年齡)=0.375*0.9183+0.25*0+0.375*0.9157=0.6877G(年齡)=0.9537-0.6877=0.266計(jì)算收入的熵：收入共分三個(gè)組：高、中、低E(收入)=0.9361 G(收入) =0.9537-0.9361=0.0176計(jì)算學(xué)生的熵：學(xué)生共分為兩個(gè)組：學(xué)生、非學(xué)生E(學(xué)生)=0.7811G(學(xué)生) =0.9537-0.7811=0.1726計(jì)算信譽(yù)的熵：信譽(yù)分兩個(gè)組：良好，優(yōu)秀E(信譽(yù))=0.9048G(信譽(yù)) =0.9537-0.9048=0.0453(3) 計(jì)算選擇結(jié)點(diǎn)：通過以上計(jì)算可知，年齡信息增益值最大，因此選擇年齡屬性進(jìn)行分支，觀察表3.2，當(dāng)年齡為“中”時(shí)，對應(yīng)的歸類都為買，因此該處形成葉結(jié)點(diǎn)；而年齡取“青”、“老”時(shí)，對應(yīng)的歸類不唯一，因此構(gòu)造樹結(jié)構(gòu)如圖3.3：年齡買/不買買/不買買中青老圖3.3 樹結(jié)構(gòu)在年齡屬性為青年時(shí)，分別計(jì)算收入信息增益、學(xué)生信息增益、信譽(yù)信息增益可知，在屬性學(xué)生處信息增益值最大，因此取學(xué)生為分支屬性；同理，當(dāng)年齡屬性為老年時(shí)，同樣的計(jì)算可得分支屬性為信譽(yù)。預(yù)測消費(fèi)者是否會購買電腦的決策樹分類構(gòu)建完成，如圖3.4所示：年齡學(xué)生信譽(yù)買買不買不買買中青老否是優(yōu)良圖3.4 誰在買計(jì)算機(jī)3.3 C4.5算法C4.5算法是ID3算法的改進(jìn)，它繼承了ID3算法的優(yōu)點(diǎn)并對ID3算法進(jìn)行了改進(jìn)和補(bǔ)充。C4.5算法采用信息增益率作為選擇分支屬性的標(biāo)準(zhǔn)，克服了ID3算法中信息增益選擇屬性時(shí)偏向選擇取值多的屬性的不足，并能夠完成對連續(xù)屬性離散化的處理，還能夠?qū)Σ煌暾麛?shù)據(jù)進(jìn)行處理。3.3.1 用信息增益率選擇屬性信息增益率等于信息增益與分裂信息的比值，定義如下：，上式中SplitInfo(A)表示屬性A的分裂信息，分裂信息用來衡量屬性分裂數(shù)據(jù)的廣度和均勻，其定義如下： 。根據(jù)例2中提供的信息，可計(jì)算：SplitInfo(384,256,384)=-(0.375*log20.375+0.25*log20.25+0.375*log20.375) =2.999GainRatio(年齡)=gain(年齡)/split(384,256,384)=0.266/2.999=0.089其他的三個(gè)屬性可以類似地得出它們的信息增益率，如下表3.3所示：表3.3 屬性對應(yīng)的信息增益率年齡收入Gain0.266Gain0.018SplitInfo2.999SplitInfo1.528GainRatio0.089GainRatio0.012學(xué)生信譽(yù)Gain0.173Gain0.045Splitinfo0.998SplitInfo0.929GainRatio0.173GainRatio0.048利用C4.5算法構(gòu)建決策樹中選取各屬性中信息增益率最大的屬性作為分裂點(diǎn)，以后的做法與ID3的相同，唯一的不同之處是判斷標(biāo)準(zhǔn)由信息增益變成了信息增益率。3.3.2處理連續(xù)屬性值C4.5既可以處理離散型描述屬性，也可以處理連續(xù)性描述屬性。在選擇某結(jié)點(diǎn)上的分枝屬性時(shí)，對于離散型描述屬性，C4.5的處理方法與ID3相同，按照該屬性本身的取值個(gè)數(shù)進(jìn)行計(jì)算；對于某個(gè)連續(xù)性描述屬性， C4.5將作以下處理：(1) 對屬性的取值由小到大進(jìn)行排序。(2) 兩個(gè)屬性取值之間的中點(diǎn)作為可能的分裂點(diǎn)，將該結(jié)點(diǎn)上的數(shù)據(jù)集分成兩部分，計(jì)算每個(gè)可能的分裂點(diǎn)的信息增益。 (3) 計(jì)算每一種分割所對應(yīng)的信息增益率，選擇最大的分割點(diǎn)來劃分?jǐn)?shù)據(jù)集。3.3.3 樹剪枝剪枝方法的主要目的是去掉那些噪聲或異常數(shù)據(jù)，使決策樹具有更泛化能力。剪枝常采用統(tǒng)計(jì)度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)進(jìn)行正確分類的能力。剪枝按其實(shí)施的時(shí)間分為兩種方法：事前修剪法和事后修剪法。C4.5算法采用一種后剪枝方法。事后剪枝是由完全生長的樹剪去分枝。通過刪除結(jié)點(diǎn)的分枝，剪掉樹結(jié)點(diǎn)。它在允許決策樹得到最充分生長的基礎(chǔ)上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉結(jié)點(diǎn)或分枝。修剪后，被修剪的分枝結(jié)點(diǎn)就成為一個(gè)葉結(jié)點(diǎn)，并將其標(biāo)記為它所包含樣本中類別個(gè)數(shù)最多的類別。4、決策樹算法比較分析基于決策樹算法自提出至今種類不下幾十種。各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性，分類預(yù)測的準(zhǔn)確性等方面各有千秋。最早提出的CLS算法只是給出了生成決策樹系統(tǒng)的框架，卻沒有具體說明算法的內(nèi)容；ID3算法采用信息熵的增益進(jìn)行屬性選擇，但只能處理具有離散型屬性和屬性值齊全的元組，生成形如多叉樹的決策樹。后來出現(xiàn)的C4.5算法經(jīng)過改進(jìn)，能夠直接處理連續(xù)屬性，也能夠處理屬性值空缺的訓(xùn)練元組，它采用信息增益率進(jìn)行屬性選擇。由于ID3算法與C4.5算法生成決策樹分支多，規(guī)模過于龐大，出現(xiàn)了根據(jù)GINI系數(shù)來選擇測試屬性的決策樹算法，比如CART。對這幾種算法進(jìn)行一個(gè)概要性的比較如表4.1所示。表4.1 典型決策樹算法比較屬性選擇度量處理連續(xù)屬性剪枝方法是否需要獨(dú)立測試樣本集決策樹結(jié)構(gòu)ID3信息增益離散化分類錯(cuò)誤是多叉樹C4.5信息增益率預(yù)排序分類錯(cuò)誤否多叉樹CARTGINI系數(shù)預(yù)排序MDL否二叉樹5、總結(jié)本文重點(diǎn)闡述了ID3算法與C4.5算法及其應(yīng)用舉例，比較了幾種典型決策樹算法的優(yōu)缺點(diǎn)。對于相當(dāng)大的范圍內(nèi)的應(yīng)用來說，決策樹分類比其他分類技術(shù)能生成更精確的分類結(jié)果，但是對決策樹分類性能的度量和評價(jià)會困難些。即使在樹分類器的每一等級上的分類效果是最優(yōu)的，也不能保證最終的結(jié)果是最優(yōu)的，雖然決策樹算法使用最好的特征進(jìn)行分類，但還是可能存在一些特征對分類很有用，卻沒有用到。如果能把這些特征選擇出來，選擇在每個(gè)子集上能夠有效分類的特征，就能有效地減少樹的層數(shù)，對于分類結(jié)果會有很大的提高。參考文獻(xiàn)1 馮少榮.決策樹算法的研究與改進(jìn)J.廈門大學(xué)學(xué)報(bào).2007,46(4):496497.2 劉小虎,李生.決策樹的優(yōu)化算法J.軟件學(xué)報(bào).1998,9(10):797-800.3 洪家榮,丁明峰.一種新的決策樹歸納學(xué)習(xí)算法J.計(jì)算機(jī)學(xué)報(bào).2011,6:470-474.4 遲慶云.決策樹分類算法及應(yīng)用J.棗莊學(xué)院學(xué)報(bào).2005,22:29-31.5 王曉東.算法設(shè)計(jì)與分析M.北京：清華大學(xué)出版社,2003.75-80.6 王光宏,蔣平.數(shù)據(jù)挖掘綜述J.同濟(jì)大學(xué)學(xué)報(bào).2004,32(2):246-252.7 路紅梅.基于決策樹的經(jīng)典算法綜述J.宿州學(xué)報(bào).2007,22(2):99-95.8 楊明,張載鴻.決策樹學(xué)習(xí)算法ID3的研究J.微機(jī)發(fā)展.2002,12(5):89-94.9 李啟炎.應(yīng)用c4.5算法構(gòu)造客戶分類決策樹的方法J.計(jì)算機(jī)工程.2003,(14):89-91.10 吉根林.決策樹分類計(jì)數(shù)研究.計(jì)算機(jī)工程J.2004,(9):91-94.Re