決策樹(shù)在成績(jī)分析中的應(yīng)用

1、學(xué)年論文決策樹(shù)在成績(jī)分析中的應(yīng)用學(xué)院：計(jì)算機(jī)科學(xué)與工程學(xué)院班級(jí):*姓名:*導(dǎo)師：*摘要1Abstract2第一章緒論3數(shù)據(jù)挖掘的歷史、發(fā)展4數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析4數(shù)據(jù)挖掘研究的發(fā)展趨勢(shì)4第二章數(shù)據(jù)挖掘的基本知識(shí)5數(shù)據(jù)挖掘的定義5數(shù)據(jù)挖掘的分類(lèi)5數(shù)據(jù)挖掘按挖掘任務(wù)類(lèi)型5按挖掘?qū)ο?按挖掘方法6按數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識(shí)7數(shù)據(jù)挖掘技術(shù)的主要方法7關(guān)聯(lián)規(guī)則方法7決策樹(shù)方法7神經(jīng)網(wǎng)絡(luò)方法7遺傳算法8數(shù)據(jù)挖掘的實(shí)現(xiàn)過(guò)程8數(shù)據(jù)準(zhǔn)備8數(shù)據(jù)才掘8模式的評(píng)估解釋8知識(shí)運(yùn)用8第三章決策樹(shù)技術(shù)8決策樹(shù)技術(shù)9算法描述9ID3算法9改進(jìn)算法10ID3算法計(jì)算學(xué)生的成績(jī)信息11改進(jìn)算法計(jì)算學(xué)生的信息18第四章總結(jié)25

2、參考文獻(xiàn)：25決策樹(shù)在成績(jī)分析中的應(yīng)用摘要數(shù)據(jù)挖掘的提出是在20世紀(jì)80年代，它是一個(gè)新興的、面向商業(yè)應(yīng)用的AI研究領(lǐng)域，20世紀(jì)末，隨著Internet的普及，全球信息量以驚人的速度急劇增長(zhǎng)，據(jù)估計(jì)每二十個(gè)月增加一倍。目前的數(shù)據(jù)庫(kù)系統(tǒng)雖然可以高效的實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢(xún)、和統(tǒng)計(jì)等功能，但卻無(wú)法發(fā)現(xiàn)海量數(shù)據(jù)中隱藏的知識(shí)和規(guī)律；人們面臨的主要問(wèn)題不再是缺乏足夠的信息可以使用，而是面對(duì)浩瀚的數(shù)據(jù)海洋如何有效的利用這些數(shù)據(jù)。如何將這些海量的數(shù)據(jù)從數(shù)據(jù)庫(kù)中提取出來(lái)，并轉(zhuǎn)為有用的信息；面對(duì)這一挑戰(zhàn)，數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)技術(shù)應(yīng)運(yùn)而生，并顯示強(qiáng)大的生命力。數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)使數(shù)據(jù)處理技術(shù)進(jìn)入一個(gè)更高級(jí)的階段。它

3、不僅能對(duì)過(guò)去的數(shù)據(jù)進(jìn)行查詢(xún)，而且能夠找出過(guò)去數(shù)據(jù)進(jìn)行查詢(xún)，而且能夠找出過(guò)去數(shù)據(jù)之間潛在的聯(lián)系，進(jìn)行更高層次的分析，以便更好的解決決策、預(yù)測(cè)等問(wèn)題。數(shù)據(jù)挖掘，從技術(shù)角度而言，數(shù)據(jù)挖掘是從大量的，不完全的，有噪聲的、模糊的、隨機(jī)的實(shí)際數(shù)據(jù)中，提取隱含在其中人們事先不知道但有潛在有用的信息和知識(shí)的過(guò)程。從商業(yè)角度，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要的特點(diǎn)是對(duì)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型換處理，從中提取輔助商業(yè)決策的關(guān)鍵性信息和知識(shí)。本論文主要論述的是利用決策樹(shù)技術(shù)對(duì)于大量的學(xué)生數(shù)據(jù)進(jìn)行分析，在其中挖掘有用的信息，目的是提高教學(xué)質(zhì)量。決策樹(shù)技術(shù)，用于分類(lèi)和預(yù)測(cè)的主要的技

4、術(shù)，決策樹(shù)學(xué)習(xí)是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，它著眼于從一組無(wú)次序、無(wú)規(guī)則的實(shí)例中推理出決策樹(shù)表示形式的分類(lèi)規(guī)則，它包括兩個(gè)步驟：一，利用訓(xùn)練樣本集來(lái)建立并精化出一顆決策樹(shù)，建立決策樹(shù)模型。即從數(shù)據(jù)中獲取知識(shí)，進(jìn)行機(jī)器學(xué)習(xí)的過(guò)程。二，利用建好的決策樹(shù)對(duì)新的數(shù)據(jù)進(jìn)行分類(lèi)。關(guān)鍵字：數(shù)據(jù)挖掘，決策樹(shù)技術(shù)，成績(jī)分析ApplicationofdecisiontreeinperformanceanalysisAbstractDataminingisputforwardin1980s,itisanew,twentiethCenturyforthecommercialapplicationofAIresearc

5、hfield,attheend,withthepopularityofInternet,theglobalinformationhasdramaticallyincreasedatanalarmingrate,isestimatedtobedoubledeverytwentymonths.Althoughthecurrentdatabasesystemcanachievedataentry,efficientthequeryandstatisticalfunctions,butcannotfindtheknowledgeandruleshiddeninmassivedata;themainpr

6、oblemsthatpeoplearefacingisnotlackofenoughinformationcanbeused,butthefaceofthevastoceanofdataandhowtousethesedataeffectively.Howthesemassivedataextractedfromthedatabase,andturnthemintousefultheinformation;inthefaceofthischallenge,dataminingandknowledgediscoverytechnologycameintobeing,andshowstrongvi

7、tality.Dataminingandknowledgediscovery,dataprocessingtechnologyintoaAmoreadvancedstage.Itcannotonlyqueryonpastdata,andcanidentifythepastdataquery,andtofindoutthepotentiallinkbetweenpastdata,higherlevelofanalysis,inordertobettersolvethedecisionproblem.Datamining,prediction,fromatechnicalpointofview,d

8、ataminingisfromalargenumberof,incomplete,noisy,fuzzyandrandomoftheactualdata,extractsomeunknownbutpotentiallyusefulinformationandknowledgeprocess.Fromthebusinessperspective,thedataminingisanewbusinessinformationprocessingtechnology,itsmaincharacteristicistoalargenumberofbusinessdatainthedatabasethee

9、xtraction,transformation,analysisandothermodelsforprocessing,extractionbusinessdecisionsfromthekeyinformationandknowledge.Thispapermainlydiscussestheuseofdecisiontreetechnologyfortheanalysisofalargenumberofstudentdata,inwhichminingusefulinformation,thepurposeistoimprovethequalityofteaching.Decisiont

10、reeforclassificationandpredictionofthemaintechnologyanddecisiontreelearningisinstancebasedinductivelearningalgorithm,itlooksfromagroupofoutoforder,irregularinstancereasoningdecisiontreerepresentationofclassificationrules,whichincludestwosteps:ausingtrainingsetstoestablishandrefinethedecisiontree,dec

11、isiontreemodelisbuilt.Fromthedataaccesstoknowledge,carryonthemachinelearningprocess.Second,usingthebuiltdecisiontreetoclassifynewdata.Keywords:datamining,decisiontreetechnology,performanceanalysis第一章緒論數(shù)據(jù)挖掘的歷史、發(fā)展數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析由于大型數(shù)據(jù)系統(tǒng)的廣泛使用和把數(shù)據(jù)轉(zhuǎn)換成有用知識(shí)的迫切的需要，數(shù)據(jù)挖掘引起了各行業(yè)的關(guān)注。20世紀(jì)60年代，為了適應(yīng)信息的電子話(huà)需求，信息技術(shù)一直從簡(jiǎn)單

12、的文件處理系統(tǒng)向有效的數(shù)據(jù)庫(kù)系統(tǒng)變革。20世紀(jì)70年代，數(shù)據(jù)庫(kù)系統(tǒng)的三個(gè)主要的模式：層次，網(wǎng)絡(luò)，關(guān)系型數(shù)據(jù)庫(kù)的研究和開(kāi)發(fā)取得了重要的進(jìn)展。20世紀(jì)80年代，關(guān)系型數(shù)據(jù)庫(kù)及其相關(guān)的數(shù)據(jù)模型相關(guān)工具，數(shù)據(jù)索引技術(shù)局組織被廣泛采用，并且成為了整個(gè)數(shù)據(jù)庫(kù)市場(chǎng)的主導(dǎo)。20世紀(jì)80年代中期開(kāi)始，關(guān)系型數(shù)據(jù)庫(kù)技術(shù)和新型技術(shù)的結(jié)合成為數(shù)據(jù)庫(kù)研究和發(fā)展的重要標(biāo)志。從數(shù)據(jù)的分布角度看，分布式數(shù)據(jù)庫(kù)及其透明性、并發(fā)控制、并行處理等成為必須面對(duì)的課題。許多的商業(yè)活動(dòng)中，由于數(shù)據(jù)庫(kù)的普及，人工去整理和理解如此大的數(shù)據(jù)源已經(jīng)存在效率、準(zhǔn)確性等問(wèn)題，并不是每個(gè)人都能夠從過(guò)去的銷(xiāo)售情況預(yù)測(cè)將來(lái)的發(fā)展趨勢(shì)或做出正確的決策。20

13、世紀(jì)80年代，產(chǎn)生了數(shù)據(jù)技術(shù)并得到了廣泛的應(yīng)用。高性能的關(guān)系數(shù)據(jù)庫(kù)引擎以及相關(guān)的分布式查詢(xún)、并發(fā)控制等技術(shù)的應(yīng)用，已經(jīng)提升了數(shù)據(jù)庫(kù)的應(yīng)用能力。在數(shù)據(jù)的快速訪(fǎng)問(wèn)、集成和抽取等問(wèn)題上有了突破，數(shù)據(jù)倉(cāng)庫(kù)作為一種新型的數(shù)據(jù)存儲(chǔ)和處理手段，被數(shù)據(jù)庫(kù)廠(chǎng)商廣泛的應(yīng)用。20世紀(jì)80年代后期，產(chǎn)生了數(shù)據(jù)挖局等思想。90年代，分布式數(shù)據(jù)庫(kù)理論上趨于成熟，然而本質(zhì)上查詢(xún)是對(duì)數(shù)據(jù)庫(kù)的被動(dòng)的使用。由于簡(jiǎn)單查詢(xún)只是數(shù)據(jù)庫(kù)內(nèi)容的選擇性輸出，因此它和人們期望的分析預(yù)測(cè)、決策支持等高級(jí)應(yīng)用人有很大的距離。近年來(lái)，由于數(shù)據(jù)采集技術(shù)的更新，決策所面對(duì)的數(shù)據(jù)量在不斷的增長(zhǎng)，隨著數(shù)據(jù)的急劇增長(zhǎng)，現(xiàn)有信息管理系統(tǒng)中的數(shù)據(jù)分析工具已無(wú)法適

14、應(yīng)新的需求。人們希望能夠提供更高層次的數(shù)據(jù)分析功能，自動(dòng)和智能地將待處理的數(shù)據(jù)轉(zhuǎn)化為有用的信息和知識(shí)。數(shù)據(jù)挖掘研究的發(fā)展趨勢(shì)數(shù)據(jù)挖掘必須經(jīng)過(guò)概念的提出、概念的接受、廣泛研究和探索、逐步應(yīng)用和大量應(yīng)用等階段。目前，大部分的學(xué)者認(rèn)為數(shù)據(jù)挖掘仍然處于廣泛研究和探索階段。數(shù)據(jù)挖掘應(yīng)在如下方面進(jìn)行開(kāi)展：1 .數(shù)據(jù)挖掘技術(shù)與商業(yè)邏輯的平滑集成問(wèn)題2 .數(shù)據(jù)挖掘技術(shù)與特定的數(shù)據(jù)存儲(chǔ)類(lèi)型的適應(yīng)問(wèn)題3 .大型數(shù)據(jù)的選擇與規(guī)格化問(wèn)題4 .數(shù)據(jù)挖掘系統(tǒng)的構(gòu)架與交互式挖掘技術(shù)5 .數(shù)據(jù)挖掘語(yǔ)言與系統(tǒng)的可視化問(wèn)題6 .數(shù)據(jù)挖掘理論與算法研究第二章數(shù)據(jù)挖掘的基本知識(shí)數(shù)據(jù)挖掘的定義從技術(shù)角度而言，數(shù)據(jù)挖掘是從大量的、不完全

15、的、有噪聲的、模糊的、隨機(jī)的實(shí)際數(shù)據(jù)中，提取隱含在其中人們事先不知道但又潛在有用的信息和知識(shí)的過(guò)程。這一定義包括多層含義、及數(shù)據(jù)源必須是真實(shí)的、海量的、發(fā)現(xiàn)的知識(shí)應(yīng)是用戶(hù)感興趣的，并且是可接受的、可理解的和可應(yīng)用的，可以?xún)H支持特定的問(wèn)題。從商業(yè)角度而言，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要的特點(diǎn)數(shù)對(duì)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)行抽取、轉(zhuǎn)換、分析和其他模型化處理，從中提取輔助商業(yè)決策的關(guān)鍵性信息和知識(shí)。數(shù)據(jù)挖掘的本質(zhì)是一種深層次的數(shù)據(jù)分析方法。因此數(shù)據(jù)挖掘可以描述為按企業(yè)既定業(yè)務(wù)目標(biāo)，對(duì)大量的企業(yè)數(shù)據(jù)進(jìn)行探索和分析，揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性，并進(jìn)一步將其模型化的有效方法。數(shù)據(jù)挖掘的

16、分類(lèi)數(shù)據(jù)挖掘按挖掘任務(wù)類(lèi)型1 .分類(lèi)或預(yù)測(cè)模型發(fā)現(xiàn)2 .數(shù)據(jù)總結(jié)與聚類(lèi)發(fā)現(xiàn)3 .關(guān)聯(lián)規(guī)則發(fā)現(xiàn)4 .序列模式發(fā)現(xiàn)6 .混沌模式發(fā)現(xiàn)7 .依賴(lài)關(guān)系或依賴(lài)模型發(fā)現(xiàn)異常和趨勢(shì)發(fā)現(xiàn)等按挖掘?qū)ο? .關(guān)系型數(shù)據(jù)庫(kù)挖掘2 .面向?qū)ο髷?shù)據(jù)挖掘3 .空間數(shù)據(jù)庫(kù)挖掘4 .時(shí)態(tài)數(shù)據(jù)庫(kù)挖掘5 .文本數(shù)據(jù)源挖掘6 .多媒體數(shù)據(jù)庫(kù)挖掘7 .異質(zhì)數(shù)據(jù)庫(kù)挖掘8 .遺產(chǎn)數(shù)據(jù)庫(kù)挖掘數(shù)據(jù)庫(kù)挖掘按挖掘方法1 .機(jī)器學(xué)習(xí)方法2 .統(tǒng)計(jì)方法3 .聚類(lèi)分析方法4 .神經(jīng)網(wǎng)絡(luò)方法5 .遺傳算法方法6 .數(shù)據(jù)庫(kù)方法7 .近似推理和不確定性推理方法8 .給予證據(jù)理論和元模式的方法9 .現(xiàn)代數(shù)學(xué)分析方法10 .粗糙集或模糊集方法按數(shù)據(jù)挖掘所能發(fā)現(xiàn)

17、的知識(shí)1 .挖掘廣義型知識(shí)2 .挖掘差異型知識(shí)3 .挖掘關(guān)聯(lián)型知識(shí)4 .挖掘預(yù)測(cè)性知識(shí)5 .挖掘偏離型知識(shí)6 .挖掘不確定性知識(shí)數(shù)據(jù)挖掘技術(shù)的主要方法關(guān)聯(lián)規(guī)則方法從數(shù)據(jù)集中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則，該規(guī)則顯示給定數(shù)據(jù)集中經(jīng)常一起出現(xiàn)的屬性-值元組。例如：x->y說(shuō)吧表達(dá)的含義是滿(mǎn)足X遠(yuǎn)足有可能滿(mǎn)足Y。關(guān)聯(lián)分析在交易數(shù)據(jù)分析、支持定向、商品目錄設(shè)計(jì)和其他業(yè)務(wù)決策等方面有著廣泛的應(yīng)用。決策樹(shù)方法ID3算法是最典型的決策樹(shù)分類(lèi)算法，決策樹(shù)是從機(jī)器學(xué)習(xí)角度研究和發(fā)展起來(lái)的，對(duì)于大訓(xùn)練樣本集很難適應(yīng)。決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類(lèi)的過(guò)程。以樹(shù)的形式來(lái)表達(dá)模型，主要是對(duì)屬性值進(jìn)行歸納分類(lèi)，它采用自頂向下的

18、遞歸方式，在決策樹(shù)內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較，并根據(jù)不同的屬性值來(lái)判斷從該節(jié)點(diǎn)向下的分支，在決策樹(shù)的葉節(jié)點(diǎn)得到結(jié)論。采用決策樹(shù)可以將數(shù)據(jù)規(guī)則可視化，不需要更長(zhǎng)時(shí)間的構(gòu)造過(guò)程，輸出結(jié)果容易理解，精度較高。神經(jīng)網(wǎng)絡(luò)方法是人們?cè)谀M人腦處理問(wèn)題的過(guò)程中發(fā)展起來(lái)的新型智能信息處理理論。它通過(guò)大量的稱(chēng)為神經(jīng)元的簡(jiǎn)單處理單元構(gòu)成非線(xiàn)性動(dòng)力學(xué)系統(tǒng)，對(duì)人腦的形象思維、聯(lián)想記憶等進(jìn)行模擬和抽象，實(shí)現(xiàn)與人腦相似的學(xué)習(xí)、識(shí)別、記憶等信息處理能力。遺傳算法是模擬自然界生化進(jìn)化過(guò)程的隨機(jī)化搜索算法，它以很強(qiáng)的解決問(wèn)題能力和廣泛的適應(yīng)性滲透到研究與工程的各個(gè)領(lǐng)域。遺傳算法是一種高效的全局并行搜索優(yōu)化算法。數(shù)據(jù)挖掘的實(shí)現(xiàn)過(guò)程

19、數(shù)據(jù)準(zhǔn)備數(shù)據(jù)挖掘的處理對(duì)象是海量的數(shù)據(jù)，是長(zhǎng)期積累的結(jié)果。這些數(shù)據(jù)不適合直接進(jìn)行挖掘，需要進(jìn)行預(yù)處理。數(shù)據(jù)預(yù)處理包括數(shù)據(jù)的選擇、清潔（消除噪聲、冗余數(shù)據(jù)）、推測(cè)（推算缺失數(shù)據(jù)）、轉(zhuǎn)換（離散型數(shù)據(jù)與連續(xù)型數(shù)據(jù)之間的轉(zhuǎn)換）、數(shù)據(jù)縮減（減少數(shù)據(jù)量）。數(shù)據(jù)挖掘根據(jù)挖掘的目標(biāo)，選取相應(yīng)算法的參數(shù)，分析數(shù)據(jù)，得到可能形成知識(shí)的模型模式的評(píng)估解釋通過(guò)上述步驟得到的模式，有可能是沒(méi)有意義或沒(méi)有實(shí)用價(jià)值的，因此需要評(píng)估，確定哪些是有效的、有用的模式。止匕外，大部分模式是數(shù)學(xué)表達(dá)式，需要將其解釋成可理解的方式呈現(xiàn)給用戶(hù)。知識(shí)運(yùn)用運(yùn)用只是主要有兩種途徑。一、只許看知識(shí)本身描述的關(guān)系或結(jié)果，就可以對(duì)決策提供支持；二、

20、要求對(duì)新的數(shù)據(jù)運(yùn)用知識(shí)，由此可能產(chǎn)生新的問(wèn)題，并需要對(duì)知識(shí)做進(jìn)一步優(yōu)化。第三章決策樹(shù)技術(shù)決策樹(shù)技術(shù)決策樹(shù)是分類(lèi)預(yù)測(cè)的主要方法，采用基于實(shí)例的歸納學(xué)習(xí)算法，旨在從一組無(wú)次序、無(wú)規(guī)則的實(shí)例中推理出決策樹(shù)形式的分類(lèi)規(guī)則，采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同屬性判斷從該節(jié)點(diǎn)向下的分枝，在決策樹(shù)的葉節(jié)點(diǎn)得到結(jié)論，所以從根到葉節(jié)點(diǎn)對(duì)應(yīng)一條合取規(guī)則，整顆樹(shù)對(duì)應(yīng)一組析取規(guī)則。決策樹(shù)分類(lèi)是利用屬性值對(duì)各子集逐級(jí)劃分，直到一個(gè)結(jié)點(diǎn)僅含有同一類(lèi)樣本為止。算法描述ID3算法基本思路是首先在數(shù)據(jù)集中采用信息增益作為屬性選擇的標(biāo)準(zhǔn)，找出最有影響力的屬性，將數(shù)據(jù)集分成多個(gè)子集，每個(gè)子集又選擇

21、最具影響力的屬性進(jìn)行劃分，一直進(jìn)行到所有自己僅包含同一類(lèi)型的樣本為止，最后得到一顆決策樹(shù)。決策樹(shù)的構(gòu)造采用自上而下，分而治之的遞歸方式。初始時(shí)根節(jié)點(diǎn)包含數(shù)據(jù)集的所有的樣本。若一個(gè)結(jié)點(diǎn)包含的樣本均為同一個(gè)類(lèi)別，則該結(jié)點(diǎn)成為葉結(jié)點(diǎn)并標(biāo)記為該類(lèi)別；否則采用信息增益的度量選擇合適的分類(lèi)屬性，將數(shù)據(jù)集劃分為若干個(gè)子集。該屬性成為相應(yīng)結(jié)點(diǎn)的測(cè)試屬性。對(duì)測(cè)試屬性的每個(gè)已知值都創(chuàng)建一個(gè)分支，同時(shí)也包含一個(gè)被劃分的子集。遞歸的對(duì)所獲得的每個(gè)劃分形成一顆決策樹(shù)。一旦一個(gè)屬性出現(xiàn)在某個(gè)結(jié)點(diǎn)上，則不能出現(xiàn)在該結(jié)點(diǎn)之后所產(chǎn)生的子樹(shù)結(jié)點(diǎn)上。當(dāng)一個(gè)結(jié)點(diǎn)包含的所有樣本均為同一類(lèi)別或沒(méi)有樣本滿(mǎn)足測(cè)試屬性值，則算法終止。屬性信息

22、增益選擇測(cè)試屬性的方法如下：設(shè)數(shù)據(jù)集S有s個(gè)樣本，類(lèi)別屬性有m個(gè)不同的取值。定義m個(gè)不同的類(lèi)Ci,i1,2,3.m。設(shè)si為類(lèi)別Ci的樣本個(gè)數(shù)，則對(duì)一個(gè)數(shù)據(jù)集分類(lèi)所需的期望信息為：mI(sij,s2j.smj)=-pijlog2pij)()i1其中Pi是任意一個(gè)樣本，類(lèi)別屬性有m個(gè)不同的取值，定義m個(gè)不同的類(lèi)G的概率，可以按sJS計(jì)算。因?yàn)椴捎枚M(jìn)制編碼，所以對(duì)數(shù)函數(shù)以2為底。設(shè)屬性A可取v個(gè)不同的值a1,a2,a3av.可以用屬性A將S劃分為v個(gè)子集Si,S2,.Sv,其中Sj包含S中屬性A中取值aj為1的樣本。若屬性A為測(cè)試屬性，設(shè)Sj為子集Sj中屬于G類(lèi)別的樣本數(shù)。則利用屬性A劃分當(dāng)前集

23、合所需要的期望信息計(jì)算如下：vsijs2js3jSmjmjE(A)=I(Sij,s2j,s3jsiiS其中.汨S3j.Smj成為第j個(gè)子集的權(quán)值。e(A)值越小，表示子集S劃分結(jié)果越好。而對(duì)于一個(gè)給定子集Sj,其期望信息如式()，其中Pij=工為|Sj|子集Sj中任意一個(gè)樣本屬于類(lèi)別C的概率。由此利用屬性A對(duì)當(dāng)前分支結(jié)點(diǎn)進(jìn)行劃分所獲得的信息增益是：Gain(A)=I(sh，s2j,smj)-E(A)Gain(A)是根據(jù)屬性A進(jìn)行集合劃分所獲得的信息嫡的減少量。改進(jìn)算法算法是由ID3算法演變而來(lái)，除了具有ID3算法的功能外，算法引入了新的方法和增加了新的功能。(1)信息增益比例的概念信息增益比例

24、是在信息增益概念基礎(chǔ)上發(fā)展來(lái)的，表示為:GainRatio(A)=Gain(A)/SplitI(A)其中SplitI(A)=-Pjlog2Pj設(shè)屬性A具有V個(gè)不同的值a1,a2,.av,可以用屬性A將S劃分為V個(gè)子集s1,s2,.sv,其中Sj包含S中這樣一些樣本：它們?cè)贏(yíng)上具有值aj.(2)合并具有連續(xù)值的屬性ID3算法最初假定屬性離散值，但在實(shí)際環(huán)境中，很多屬性值是連續(xù)的.對(duì)于連續(xù)屬性值，其處理過(guò)程如下：* 根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序；* 用不同的閾值將數(shù)據(jù)集動(dòng)態(tài)地進(jìn)行劃分；* 當(dāng)輸出改變時(shí)確定一個(gè)閾值；* 取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值；* 取兩個(gè)劃分，所有的樣本都在這兩個(gè)劃分中；*

25、得到所有可能的閾值、增益、及增益比；* 在每一個(gè)屬性會(huì)變?yōu)閮蓚€(gè)取值，即小于閾值或大于閾值；(3)處理含有未知屬性值的訓(xùn)練樣本處理樣本中可以含有未知的屬性值，其處理方法是用最常用的值分在同一類(lèi)中。具體采用概率的方法，依據(jù)屬性已知的值，對(duì)屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率依賴(lài)于該屬性已知的值。(4)規(guī)則的產(chǎn)生一旦樹(shù)被建立。就可以把樹(shù)轉(zhuǎn)換成if-then的規(guī)則，規(guī)則存儲(chǔ)于一個(gè)二維的數(shù)組中，每一行代表樹(shù)中的一個(gè)規(guī)則，即從根到葉之間的一個(gè)路徑。表中的每列存放著樹(shù)中的結(jié)點(diǎn)。ID3算法計(jì)算學(xué)生的成績(jī)信息理工科學(xué)生成績(jī)分析表如下:學(xué)號(hào)性別基礎(chǔ)程度上機(jī)時(shí)間學(xué)習(xí)成績(jī)001女良好>=3良好002女一般1

26、-2一般003男好1-2一般004男一般<=1一般005男一般0不及格006女好<=1一般007男好<=1良好008女良好<=1良好009男好1-2一般010男一般>=3良好011女一般1-2一般012男好<=1良好013男一般>=3良好014男一般<=1一般從表中選取14個(gè)樣本，其中良好的人數(shù)有6個(gè)，一般的人數(shù)有7個(gè)，不及格一個(gè)人；選擇是否良好為類(lèi)別屬性。其中良好用yes表示，一般用no表示，Yes有6人，no有7人;即I(6,7)=-6/13log26/13-7/13log27/13=依次計(jì)算各個(gè)屬性，1 .性別屬性A性別='男

27、9;，yes有4個(gè)，no有4個(gè)I(4,4)=1b.性別='女'，yes有2個(gè)，no有3個(gè)I(2,3)=E(性別)=8/13+5/13*=2 .Gain(性別)=基礎(chǔ)程度屬性A.基礎(chǔ)程度='良好，yes有2個(gè)，no有0個(gè)I(2,0)=0B基礎(chǔ)程度='好，yes有2個(gè)，no有3個(gè)I(2,3)=C.基礎(chǔ)程度='一般，yes有2個(gè)，no有4個(gè)I(2,4)=E(基礎(chǔ)程度)=5/13*+6/13*=3.Gain(基礎(chǔ)程度)=上機(jī)時(shí)間屬性a. 上機(jī)時(shí)間=i,yes有3個(gè)，no有3個(gè)I(3,3,)=1b. 上機(jī)時(shí)間=i-2,yes有0個(gè)，no有4個(gè)I(0,4)=0c.

28、上機(jī)時(shí)間=3,yes有3個(gè)，no有0個(gè)I(3,0)=0E(上機(jī)時(shí)間)=6/13=Gain(上機(jī)時(shí)間)=由此可知，上機(jī)時(shí)間的信息增益值最大，因此選做根節(jié)點(diǎn)。上機(jī)時(shí)間=1學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)004男T006女好T007男好良好008女良好良好012男好良好014男Yes有3個(gè)，no有3個(gè)I(3,3)=11.性別屬性A.性別='男'，yes有2個(gè)，no有2個(gè)I(2,2)=1B.性別='女'，yes有1個(gè)，no有1個(gè)I(1,1)=1E(性別)=1Gain(性別)=02.基礎(chǔ)程度屬性A.基礎(chǔ)程度=一般，yes有0個(gè)，no有2個(gè)I(0,2)=0B.基礎(chǔ)程度='好

29、'，yes有2個(gè)，no有1個(gè)I(2,1)=C.基礎(chǔ)程度='良好，yes有1個(gè)，no有0個(gè)I(1,0)=0E(基礎(chǔ)程度)=3/6*=Gain(基礎(chǔ)程度)=因此，以基礎(chǔ)程度作為根節(jié)點(diǎn)基礎(chǔ)程度='一般'學(xué)號(hào)性別學(xué)習(xí)成績(jī)004男一般014男一般因此，確定一個(gè)葉節(jié)點(diǎn)?；A(chǔ)程度='好'學(xué)號(hào)性別學(xué)習(xí)成績(jī)006女一般007男良好012男良好Yes有2個(gè)，no有1個(gè)I(2,1)=因?yàn)橹挥袑傩孕詣e，所以性別屬性作為根節(jié)點(diǎn)性別='男'學(xué)號(hào)學(xué)習(xí)成績(jī)007良好012良好確定一個(gè)葉節(jié)點(diǎn),性別='女'學(xué)號(hào)學(xué)習(xí)成績(jī)006一般確定葉節(jié)點(diǎn)上機(jī)時(shí)間=1

30、-2學(xué)號(hào)性別基礎(chǔ)程度成績(jī)002女一般一般003男好一般009男好一般011女一般一般確定葉節(jié)點(diǎn)上機(jī)時(shí)間=3學(xué)號(hào)性別基礎(chǔ)程度成績(jī)001女良好良好013男一般良好確定葉節(jié)點(diǎn)得到的決策樹(shù)如下所示:改進(jìn)算法計(jì)算學(xué)生的信息理工科學(xué)生成績(jī)分析表如下:按成績(jī)是否良好進(jìn)行劃分，yes表示良好，no表示一般學(xué)號(hào)性別基礎(chǔ)程度上機(jī)時(shí)間學(xué)習(xí)成績(jī)001女良好>=3良好002女一般1-2一般003男好1-2一般004男一般<=1一般005男一般0不及格006女好<=1一般007男好<=1良好008女良好<=1良好009男好1-2一般010男一般>=3良好011女一般1-2一般012男好

31、<=1良好013男一般>=3良好014男一般<=1一般計(jì)算學(xué)習(xí)成績(jī)屬性分類(lèi)的期望信息得到：I(s1,s2)=I(6,7)=-6/13log26/13-7/13log27/13=1.計(jì)算性別的Splitl的值得到：Splitl(性別)=-5/13LOG25/13-8/13LOG28/13=對(duì)于決策學(xué)習(xí)成績(jī)來(lái)說(shuō)，計(jì)算性別屬性每個(gè)分布的期望信息得到：1 .對(duì)于性別二男，s11=4,s21=4,I(4,4)=12 .對(duì)于性別二女，s12=2,s22=3,I(2,3)=因此，得到性別屬性的嫡為：E(性別)=8/13+5/13*=對(duì)應(yīng)的信息增益：Gain(性別)=I(S1,S2)-E(性

32、別)=信息增益比例為：GainRatio(性別)=3 .計(jì)算基礎(chǔ)程度屬性的SplitI值得到：SplitI(基礎(chǔ)程度)=-2/13LOG22/13-5/13LOG25/13-6/13LOG26/13=對(duì)于決策學(xué)習(xí)成績(jī)屬性來(lái)說(shuō)，計(jì)算基礎(chǔ)程度的每個(gè)分布的期望信息得到：1 .對(duì)于基礎(chǔ)程度='一般'，S11=2,S21=4,I(2,4)=2 .對(duì)于基礎(chǔ)程度='好'，S12=2,S22=3,I(2,3)=3 .對(duì)于基礎(chǔ)程度='良好'，S13=2,S33=0,I(2,0)=0因此得到基礎(chǔ)程度屬性的嫡為：E（基礎(chǔ)程度）=6/13*+5/13*=對(duì)應(yīng)的信息增益：

33、Gain（基礎(chǔ)程度尸=信息增益比例：GainRatio（基礎(chǔ)程度）=3.計(jì)算上機(jī)時(shí)間屬性的Splitl的值：SplitI（上機(jī)時(shí)間）=3/1310g23/13-4/1310g24/13-6/1310g26/13=對(duì)于決策學(xué)習(xí)成績(jī)屬性來(lái)說(shuō)，計(jì)算上機(jī)時(shí)間的每個(gè)分布的期望信息得到:1 .對(duì)于上機(jī)時(shí)間>=3,S11=3,s21=0,I（3,0）=02 .上機(jī)時(shí)間=1-2,s21=4,s22=0,I（4,0）=03 .上機(jī)時(shí)間<=1,s31=3,s33=3I（3,3）=1因此得到上機(jī)時(shí)間的嫡為：E（上機(jī)日間）=6/13=對(duì)應(yīng)的信息增益：Gain（上機(jī)時(shí)間）=信息增益比例：GainRatio（

34、上機(jī)時(shí)間）=4 .選取最大的GainRatio(上機(jī)時(shí)間)=,根據(jù)上機(jī)時(shí)間的取值，可以得到三個(gè)分支，同時(shí)數(shù)據(jù)集被劃分為三個(gè)子集，如圖所示：上機(jī)時(shí)間=112>=3學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)004男006女好007男好良好學(xué)號(hào)T生另基礎(chǔ)程度學(xué)習(xí)成績(jī)002女003男好009男好學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)001女良好良好010男良好013男良好計(jì)算每個(gè)子樹(shù)的生成過(guò)程：對(duì)于第一個(gè)子樹(shù)，yes有3個(gè)，no有3個(gè)，I(3,3)=11.計(jì)算性別屬性的Splitl值得到:SplitI（性別）=4/6log24/6-2/6log22/6=對(duì)于決策學(xué)習(xí)成績(jī)，計(jì)算性別的兩個(gè)屬性的分布的期望信息得到：1 .性別=&#

35、39;男，S11=2,s21=2,I（2,2）=12 .性別='女'S12=1,s22=1,I（1,1）=1因此得性別屬性的嫡為：E（性別）=1對(duì)應(yīng)的信息增益為：Gain（性別）=1-1=0信息增益比例：GainRatio（性別）=02.計(jì)算基礎(chǔ)程度屬性的SplitI值得到：SplitI（基礎(chǔ)程度）=-2/6log22/6-3/6logz3/6-1/6log21/6=對(duì)于決策學(xué)習(xí)成績(jī)屬性來(lái)說(shuō)，計(jì)算基礎(chǔ)程度的每個(gè)分布的信息增益：1 .基礎(chǔ)程度='一般，S11=2,S21=0,I（2,0）=02 .基礎(chǔ)程度='好'，S12=2,s22=1,I（2,1）=3 .基礎(chǔ)程度='良好s13=1,s33=0,I（1,0）=0因此得基礎(chǔ)程度屬性的嫡為：E（基礎(chǔ)程度）=4/6*=對(duì)應(yīng)的信息增益為:Gain（基礎(chǔ)程度）信息增益比例GainRatio（基礎(chǔ)程度）=因此選擇信息增益比例最大的基礎(chǔ)程度作為子根節(jié)點(diǎn)，根據(jù)基礎(chǔ)程度的取值，分為三個(gè)分支,同時(shí)數(shù)據(jù)集被劃分為三個(gè)子集。上機(jī)時(shí)間=1-2,確定為no。上機(jī)時(shí)間=3,