決策樹(shù)算法研究.doc

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