決策樹算法研究報(bào)告

1、-. z.摘 要隨著信息科技的高速開展，人們對于積累的海量數(shù)據(jù)量的處理工作也日益增重，需創(chuàng)造之母，數(shù)據(jù)挖掘技術(shù)就是為了順應(yīng)這種需求而開展起來的一種數(shù)據(jù)處理技術(shù)。數(shù)據(jù)挖掘技術(shù)又稱數(shù)據(jù)庫中的知識(shí)發(fā)現(xiàn)，是從一個(gè)大規(guī)模的數(shù)據(jù)庫的數(shù)據(jù)中有效地、隱含的、以前未知的、有潛在使用價(jià)值的信息的過程。決策樹算法是數(shù)據(jù)挖掘中重要的分類方法，基于決策樹的各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性、分類預(yù)測的準(zhǔn)確性等方面各有千秋，在各個(gè)領(lǐng)域廣泛應(yīng)用且已經(jīng)有了許多成熟的系統(tǒng)，如語音識(shí)別、模式識(shí)別和專家系統(tǒng)等。本文著重研究和比擬了幾種典型的決策樹算法，并對決策樹算法的應(yīng)用進(jìn)展舉例。關(guān)鍵詞：數(shù)據(jù)挖掘；決策樹；比擬Abs

2、tractWiththerapiddevelopmentofInformationTechnology,peoplearefacingmuchmoreworkloadindealingwiththeaccumulatedmassdata.Dataminingtechnologyisalsocalledtheknowledgediscoveryindatabase,datafromalargedatabaseofeffectively,implicit,previouslyunknownandpotentiallyusevalueofinformationprocess. Algorithm o

3、f decision tree in data mining is an important method of classification based on decision tree algorithms, in e*ecution speed, scalability, output result prehensibility, classification accuracy, each has its own merits., e*tensive application in various fields and have many mature system, such as sp

4、eech recognition, pattern recognition and e*pert system and so on. This paper studies and pares several kinds of typical decision tree algorithm, and the algorithm of decision tree application e*amples.Keywords:Data mining; decision tree；pare目錄TOC o 1-3 h z uHYPERLINK l _Toc440569408第一章 緒論 PAGEREF _

5、Toc440569408 h HYPERLINK l _Toc440569409第二章 文獻(xiàn)綜述 PAGEREF _Toc440569409 h HYPERLINK l _Toc4405694102.1 數(shù)據(jù)挖掘簡述 PAGEREF _Toc440569410 h HYPERLINK l _Toc4405694112.2 決策樹算法背景知識(shí)及研究現(xiàn)狀PAGEREF _Toc440569411 h HYPERLINK l _Toc4405694122.2.1 決策樹算法描述 PAGEREF _Toc440569412 h HYPERLINK l _Toc4405694132.2.2關(guān)聯(lián)分析決策樹

6、算法研究現(xiàn)狀 PAGEREF _Toc440569413 h HYPERLINK l _Toc440569414第三章 決策樹算法 PAGEREF _Toc440569414 h HYPERLINK l _Toc4405694153.1 CLS算法 PAGEREF _Toc440569415 h HYPERLINK l _Toc4405694163.2 ID3算法 PAGEREF _Toc440569416 h HYPERLINK l _Toc4405694173.2.1 信息量大小的度量 PAGEREF _Toc440569417 h HYPERLINK l _Toc4405694183.2

7、.2 ID3決策樹應(yīng)用舉例 PAGEREF _Toc440569418 h HYPERLINK l _Toc4405694193.3 C4.5算法 PAGEREF _Toc440569419 h HYPERLINK l _Toc4405694203.3.1 用信息增益率選擇屬性 PAGEREF _Toc440569420 h HYPERLINK l _Toc4405694213.3.2 處理連續(xù)屬性值 PAGEREF _Toc440569421 h HYPERLINK l _Toc4405694223.3 樹剪枝 PAGEREF _Toc440569422 h HYPERLINK l _Toc

8、4405694233.4 weka平臺(tái)的簡述 PAGEREF _Toc440569423 h HYPERLINK l _Toc440569424第四章 決策樹在學(xué)生成績中的應(yīng)用 PAGEREF _Toc440569424 h HYPERLINK l _Toc4405694254.1數(shù)據(jù)的預(yù)處理 PAGEREF _Toc440569425 h HYPERLINK l _Toc4405694264.2數(shù)據(jù)的訓(xùn)練集處理 PAGEREF _Toc440569426 h HYPERLINK l _Toc4405694274.3數(shù)據(jù)的校驗(yàn)和成績分析 PAGEREF _Toc440569427 h HYPE

9、RLINK l _Toc440569428第五章 結(jié)論 PAGEREF _Toc440569428 h HYPERLINK l _Toc440569429參 考 文 獻(xiàn) PAGEREF _Toc440569429 h I-. z.第一章 緒論無論在企業(yè)應(yīng)用領(lǐng)域，還是在科學(xué)領(lǐng)域，數(shù)據(jù)挖掘技術(shù)有著廣泛的應(yīng)用價(jià)值。 在企業(yè)應(yīng)用領(lǐng)域，用于制定好的市場策略以及企業(yè)的關(guān)鍵性決策。在商業(yè)面，數(shù)據(jù)挖掘技術(shù)可以增強(qiáng)企業(yè)的競爭優(yōu)勢，縮短銷售周期，降低生產(chǎn)本錢，有助制定市場方案和銷售策略，并已經(jīng)成為電子商務(wù)中的關(guān)鍵技術(shù)。近年來，隨著我國高等教育的飛速開展，高校的教學(xué)管理信息不斷增多。教學(xué)工作信息化有了很大的進(jìn)步，好

10、多高校在管理學(xué)生和教師信息方面有了很好的方式。比方我校的教務(wù)系統(tǒng)，這些系統(tǒng)為教師和學(xué)生提供了很好的幫助。這些系統(tǒng)中積累了大量的數(shù)據(jù)。目前的這些數(shù)據(jù)庫系統(tǒng)雖然根本上都可以實(shí)現(xiàn)數(shù)據(jù)的錄入、修改、統(tǒng)計(jì)、查詢等功能，但是這些數(shù)據(jù)所隱藏的價(jià)值并沒有被充分的挖掘和利用，信息資源的浪費(fèi)還是比擬嚴(yán)重的。為了提高教學(xué)質(zhì)量，將數(shù)據(jù)挖掘技術(shù)引入到高校學(xué)生成績分析中，對這些數(shù)據(jù)進(jìn)展深入的挖掘和合理的分析，從而挖掘出傳統(tǒng)的分析方法所無法得出的結(jié)論。進(jìn)而利用分析結(jié)果引導(dǎo)教學(xué)的開展，從而有利于提高教學(xué)質(zhì)量。第二章文獻(xiàn)綜述數(shù)據(jù)挖掘作為一個(gè)新興的多學(xué)科穿插應(yīng)用領(lǐng)域，正在各行各業(yè)的決策支持活動(dòng)扮演著越來越重要的角色。2.1數(shù)據(jù)挖

11、掘簡述數(shù)據(jù)挖掘英語：Data mining，又譯為資料探勘、數(shù)據(jù)采礦。它是數(shù)據(jù)庫知識(shí)發(fā)現(xiàn)英語：Knowledge-Discovery in Databases，簡稱：KDD)中的一個(gè)步驟。數(shù)據(jù)挖掘一般是指從大量的數(shù)據(jù)中自動(dòng)搜索隱藏于其中的有著特殊關(guān)系性屬于Association rule learning的信息的過程。數(shù)據(jù)挖掘通常與計(jì)算機(jī)科學(xué)有關(guān)，并通過統(tǒng)計(jì)、在線分析處理、情報(bào)檢索、機(jī)器學(xué)習(xí)、專家系統(tǒng)依靠過去的經(jīng)歷法則和模式識(shí)別等諸多方法來實(shí)現(xiàn)上述目標(biāo)。數(shù)據(jù)挖掘是通過分析每個(gè)數(shù)據(jù)，從大量數(shù)據(jù)中尋找其規(guī)律的技術(shù)，主要有數(shù)據(jù)準(zhǔn)備、規(guī)律尋找和規(guī)律表示3個(gè)步驟。數(shù)據(jù)準(zhǔn)備是從相關(guān)的數(shù)據(jù)源中選取所需的數(shù)據(jù)

12、并整合成用于數(shù)據(jù)挖掘的數(shù)據(jù)集；規(guī)律尋找是用*種方法將數(shù)據(jù)集所含的規(guī)律找出來；規(guī)律表示是盡可能以用戶可理解的方式如可視化將找出的規(guī)律表示出來。決策樹是判定給定樣本與*種屬性相關(guān)聯(lián)的決策過程的一種表示方法，從數(shù)據(jù)中生成分類器的一個(gè)特別有效的方法是生成一棵決策樹，該方法廣泛應(yīng)用與數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等領(lǐng)域，用來解釋用分類相關(guān)的問題，決策樹表示法是應(yīng)用最廣泛的邏輯方法之一。目前生成決策樹方法的算法主要有三種：CART算法、ID3算法和C4.5算法。其中C4.5算法具有分類速度快且精度高的特點(diǎn)，是開展比擬完善的一種決策樹算法。2.2決策樹算法背景知識(shí)及研究現(xiàn)狀決策樹算法描述決策樹，顧名思義就是一個(gè)類似于流

13、程圖的樹型構(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ù)不同的答復(fù)轉(zhuǎn)向相應(yīng)的分支，在新到達(dá)的結(jié)點(diǎn)處做同樣的分支判斷，持續(xù)這一過程直到到達(dá)*個(gè)葉結(jié)點(diǎn)。在決策樹中，每個(gè)部結(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 決策樹關(guān)聯(lián)分析決策樹算法研究現(xiàn)狀決策樹算法廣泛應(yīng)用于各個(gè)領(lǐng)域，已經(jīng)

14、有了廣泛的應(yīng)用并且有許多成熟的系統(tǒng)，如語音識(shí)別、醫(yī)療診斷、模式識(shí)別和專家系統(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ù)挖掘方法的主動(dòng)性和快速性顯得日益重要。 (2)適應(yīng)多數(shù)據(jù)類型和容噪性。隨著計(jì)算機(jī)網(wǎng)絡(luò)和信息的社會(huì)化，數(shù)據(jù)挖掘的對象已不單是關(guān)系數(shù)據(jù)庫模型，而是分布、異構(gòu)的多類型數(shù)據(jù)庫，數(shù)據(jù)的非構(gòu)造化程度、噪聲等現(xiàn)象越來越突出，這也是決策樹技術(shù)面臨的困難問題。(3)決策樹方法的遞增性。數(shù)據(jù)挖掘出來的知識(shí)，只是

15、相對于*一時(shí)間的*些數(shù)據(jù)，新的數(shù)據(jù)可能使發(fā)現(xiàn)的新知識(shí)與原來的知識(shí)沖突。因此，設(shè)計(jì)具有遞增性決策樹挖掘方法，也是實(shí)用化的根本要求之一。第三章 決策樹算法3.1 CLS算法CLS算法是早期的決策樹學(xué)習(xí)算法，是許多決策樹學(xué)習(xí)算法的根底。CLS根本思想：從一棵空決策樹開場，選擇*一屬性作為測試屬性。該測試屬性對應(yīng)決策樹中的決策結(jié)點(diǎn)。根據(jù)該屬性的值的不同，可將訓(xùn)練樣本分成相應(yīng)的子集，如果該子集為空，或該子集中的樣本屬于同一個(gè)類，則該子集為葉結(jié)點(diǎn)，否則該子集對應(yīng)于決策樹的部結(jié)點(diǎn)，即測試結(jié)點(diǎn)，需要選擇一個(gè)新的分類屬性對該子集進(jìn)展劃分，直到所有的子集都為空或者屬于同一類。例1：如表3.1所示為人員眼睛、頭發(fā)顏

16、色與所屬人種之間的關(guān)系：人員眼睛顏色頭發(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)色灰色根據(jù)眼睛顏色所劃分的子集中的樣本不屬于同一類，所以選擇新的測試屬性頭發(fā)顏色對各個(gè)子集進(jìn)展劃分，如圖3.2所示，所得的樣本屬于同一類，決策樹構(gòu)建完成。眼睛顏色頭發(fā)顏色頭發(fā)顏色頭發(fā)顏色黑色藍(lán)色灰色白種人4白種人2混血7白種人6黃種人1混血8白種人5白種人3黑色金色金色紅色黑色金色紅色黑色圖3

17、.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，這些類的大小分別標(biāo)記為|C1|，|C2|，|。則任意樣本S屬于類Ci的概率為：。假設(shè)屬性A的所有不同

18、值的集合為*A，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所示，對于任意給定的客人，能否幫助公司將

19、這位客人歸類。表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

20、) 計(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-P2log2

21、P2=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.9

22、048G(信譽(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)造樹構(gòu)造如圖3.3：年齡買/不買買/不買買中青老在年齡屬性為青年時(shí)，分別計(jì)算收入信息增益、學(xué)生信息增益、信譽(yù)信息增益可知，在屬性學(xué)生處信息增益值最大，因此取學(xué)生為分支屬性；同理，當(dāng)年齡屬性為老年時(shí)，同樣的計(jì)算可得分支屬性為信譽(yù)。預(yù)測消費(fèi)者是否會(huì)購置電腦的決策樹分類構(gòu)建完成，如圖3.4所示：年齡學(xué)生信譽(yù)買買不買不買買中青老否是優(yōu)良圖3.4 誰在買

23、計(jì)算機(jī)3.3 C4.5算法C4.5算法是ID3算法的改良，它繼承了ID3算法的優(yōu)點(diǎn)并對ID3算法進(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

24、*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.

25、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ù)

26、集。3.3 樹剪枝剪枝方法的主要目的是去掉那些噪聲或異常數(shù)據(jù)，使決策樹具有更泛化能力。剪枝常采用統(tǒng)計(jì)度量，剪掉最不可靠的分枝，從而帶來較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)進(jìn)展正確分類的能力。剪枝按其實(shí)施的時(shí)間分為兩種方法：事前修剪法和事后修剪法。C4.5算法采用一種后剪枝方法。事后剪枝是由完全生長的樹剪去分枝。通過刪除結(jié)點(diǎn)的分枝，剪掉樹結(jié)點(diǎn)。它在允許決策樹得到最充分生長的根底上，再根據(jù)一定的規(guī)則，剪去決策樹中的那些不具有一般代表性的葉結(jié)點(diǎn)或分枝。修剪后，被修剪的分枝結(jié)點(diǎn)就成為一個(gè)葉結(jié)點(diǎn)，并將其標(biāo)記為它所包含樣本中類別個(gè)數(shù)最多的類別。3.4 決策樹算法比擬分析基于決策樹算法自提出至今種類不下幾十種。各種算法在執(zhí)行速度、可擴(kuò)展性、輸出結(jié)果的可理解性，分類預(yù)測的準(zhǔn)確性等方面各有千秋。最早提出的CLS算法只是給出了生成決策樹系統(tǒng)的框架，卻沒有具體說明算法的容；ID3算法采用信息熵的增益進(jìn)展屬性選擇，但只能處理具有離散型屬性和屬性值齊全的元組，生成形如多叉樹的決策樹。后來出現(xiàn)的C4.5算法經(jīng)過改良，能夠直接處理連續(xù)屬性，也能夠處理屬性值空缺的訓(xùn)練元組，它采用信息增益率進(jìn)展屬性選擇。由于ID3算法與C4.5算法生成決策樹分支多，規(guī)模過于龐大，出現(xiàn)了根據(jù)GINI系數(shù)來選擇測試屬性的決策樹算法，比方CART。對