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

1、-. z.學(xué)年論文決策樹在成績(jī)分析中的應(yīng)用學(xué)院：計(jì)算機(jī)科學(xué)與工程學(xué)院班級(jí)：*: * : * 導(dǎo)師： * TOC o 1-3 h u HYPERLINK l _Toc6171 摘要 PAGEREF _Toc6171 1 HYPERLINK l _Toc1297 Abstract PAGEREF _Toc1297 1 HYPERLINK l _Toc9424 第一章緒論 PAGEREF _Toc9424 1 HYPERLINK l _Toc1885 1.1數(shù)據(jù)挖掘的歷史、開展 PAGEREF _Toc1885 1 HYPERLINK l _Toc31047 數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析 PAGERE

2、F _Toc31047 1 HYPERLINK l _Toc31242 數(shù)據(jù)挖掘研究的開展趨勢(shì) PAGEREF _Toc31242 1 HYPERLINK l _Toc19113 第二章數(shù)據(jù)挖掘的根本知識(shí) PAGEREF _Toc19113 1 HYPERLINK l _Toc7366 2.1 數(shù)據(jù)挖掘的定義 PAGEREF _Toc7366 1 HYPERLINK l _Toc25713 2.2數(shù)據(jù)挖掘的分類 PAGEREF _Toc25713 1 HYPERLINK l _Toc30103 數(shù)據(jù)挖掘按挖掘任務(wù)類型 PAGEREF _Toc30103 1 HYPERLINK l _Toc25

3、375 2.2.2 按挖掘?qū)ο?PAGEREF _Toc25375 1 HYPERLINK l _Toc27468 2.2.3 按挖掘方法 PAGEREF _Toc27468 1 HYPERLINK l _Toc1385 2.2.4 按數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識(shí) PAGEREF _Toc1385 1 HYPERLINK l _Toc28761 2.3數(shù)據(jù)挖掘技術(shù)的主要方法 PAGEREF _Toc28761 1 HYPERLINK l _Toc20513 關(guān)聯(lián)規(guī)則方法 PAGEREF _Toc20513 1 HYPERLINK l _Toc10675 決策樹方法 PAGEREF _Toc10675

4、 1 HYPERLINK l _Toc25131 2.3.3 神經(jīng)網(wǎng)絡(luò)方法 PAGEREF _Toc25131 1 HYPERLINK l _Toc6504 遺傳算法 PAGEREF _Toc6504 1 HYPERLINK l _Toc308 2.4數(shù)據(jù)挖掘的實(shí)現(xiàn)過程 PAGEREF _Toc308 1 HYPERLINK l _Toc21245 2.4.1 數(shù)據(jù)準(zhǔn)備 PAGEREF _Toc21245 1 HYPERLINK l _Toc27910 數(shù)據(jù)挖掘 PAGEREF _Toc27910 1 HYPERLINK l _Toc12265 2.4.3 模式的評(píng)估解釋 PAGEREF _T

5、oc12265 1 HYPERLINK l _Toc14007 2.4.4 知識(shí)運(yùn)用 PAGEREF _Toc14007 1 HYPERLINK l _Toc27801 第三章決策樹技術(shù) PAGEREF _Toc27801 1 HYPERLINK l _Toc510 3.1決策樹技術(shù) PAGEREF _Toc510 1 HYPERLINK l _Toc6883 3.2算法描述 PAGEREF _Toc6883 1 HYPERLINK l _Toc2668 3.2.1 ID3算法 PAGEREF _Toc2668 1 HYPERLINK l _Toc31960 3.2.2 改良算法 PAGERE

6、F _Toc31960 1 HYPERLINK l _Toc21358 3.2.3 ID3算法計(jì)算學(xué)生的成績(jī)信息 PAGEREF _Toc21358 1 HYPERLINK l _Toc13134 3.2.4 改良算法計(jì)算學(xué)生的信息 PAGEREF _Toc13134 1 HYPERLINK l _Toc24884 第四章總結(jié) PAGEREF _Toc24884 1 HYPERLINK l _Toc17824 參考文獻(xiàn)： PAGEREF _Toc17824 1-. z.決策樹在成績(jī)分析中的應(yīng)用摘要數(shù)據(jù)挖掘的提出是在20世紀(jì)80年代，它是一個(gè)新興的、面向商業(yè)應(yīng)用的AI研究領(lǐng)域，20世紀(jì)末，隨著I

7、nternet的普及，全球信息量以驚人的速度急劇增長(zhǎng)，據(jù)估計(jì)每二十個(gè)月增加一倍。目前的數(shù)據(jù)庫(kù)系統(tǒng)雖然可以高效的實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢、和統(tǒng)計(jì)等功能，但卻無法發(fā)現(xiàn)海量數(shù)據(jù)中隱藏的知識(shí)和規(guī)律；人們面臨的主要問題不再是缺乏足夠的信息可以使用，而是面對(duì)浩瀚的數(shù)據(jù)海洋如何有效的利用這些數(shù)據(jù)。如何將這些海量的數(shù)據(jù)從數(shù)據(jù)庫(kù)中提取出來，并轉(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í)的階段。它不僅能對(duì)過去的數(shù)據(jù)進(jìn)展查詢，而且能夠找出過去數(shù)據(jù)進(jìn)展查詢，而且能夠找出過去數(shù)據(jù)之間潛在的聯(lián)系，進(jìn)展更高層次的分析，以便更好的解決決策、預(yù)測(cè)等

8、問題。數(shù)據(jù)挖掘，從技術(shù)角度而言，數(shù)據(jù)挖掘是從大量的，不完全的，有噪聲的、模糊的、隨機(jī)的實(shí)際數(shù)據(jù)中，提取隱含在其中人們事先不知道但有潛在有用的信息和知識(shí)的過程。從商業(yè)角度，數(shù)據(jù)挖掘是一種新的商業(yè)信息處理技術(shù)，其主要的特點(diǎn)是對(duì)數(shù)據(jù)庫(kù)中的大量業(yè)務(wù)數(shù)據(jù)進(jìn)展抽取、轉(zhuǎn)換、分析和其他模型換處理，從中提取輔助商業(yè)決策的關(guān)鍵性信息和知識(shí)。本論文主要論述的是利用決策樹技術(shù)對(duì)于大量的學(xué)生數(shù)據(jù)進(jìn)展分析，在其中挖掘有用的信息，目的是提高教學(xué)質(zhì)量。決策樹技術(shù)，用于分類和預(yù)測(cè)的主要的技術(shù)，決策樹學(xué)習(xí)是以實(shí)例為根底的歸納學(xué)習(xí)算法，它著眼于從一組無次序、無規(guī)則的實(shí)例中推理出決策樹表示形式的分類規(guī)則，它包括兩個(gè)步驟：一，利用訓(xùn)練

9、樣本集來建立并精化出一顆決策樹，建立決策樹模型。即從數(shù)據(jù)中獲取知識(shí)，進(jìn)展機(jī)器學(xué)習(xí)的過程。二，利用建好的決策樹對(duì)新的數(shù)據(jù)進(jìn)展分類。關(guān)鍵字：數(shù)據(jù)挖掘，決策樹技術(shù)，成績(jī)分析Application of decision tree in performance analysisAbstract Data mining is put forward in 1980s，it is a new, twentieth Century for the mercial application of AI research field,at the end, with the popularity of Inter

10、net, the global information has dramatically increased at an alarming rate, is estimated to be doubled every twenty months. Although the current database system can achieve data entry, efficient the query and statistical functions, but can not find the knowledge and rules hidden in massive data; the

11、 main problems that people are facing is not lack of enough information can be used, but the face of the vast ocean of data and how to use these data effectively. How these massive data e*tracted from the database, and turn them into useful the information; in the face of this challenge, data mining

12、 and knowledge discovery technology came into being, and show strong vitality. Data mining and knowledge discovery, data processing technology into a A more advanced stage. It can not only query on past data, and can identify the past data query, and to find out the potential link between past data,

13、 higher level of analysis, in order to better solve the decision problem. Data mining, prediction, from a technical point of view, data mining is from a large number of, inplete, noisy, fuzzy and random of the actual data, e*tract some unknown but potentially useful information and knowledge process

14、. From the business perspective, the data mining is a new business information processing technology, its main characteristic is to a large number of business data in the database the e*traction, transformation, analysis and other models for processing, e*traction business decisions from the key inf

15、ormation and knowledge. This paper mainly discusses the use of decision tree technology for the analysis of a large number of student data, in which mining useful information, the purpose is to improve the quality of teaching. Decision tree for classification and prediction of the main technology an

16、d decision tree learning is instance based inductive learning algorithm, it looks from a group of out of order, irregular instance reasoning decision tree representation of classification rules, which includes two steps: a using training sets to establish and refine the decision tree, decision tree

17、model is built. From the data access to knowledge, carry on the machine learning process. Second, using the built decision tree to classify new data.Keywords: data mining, decision tree technology， performance analysis第一章緒論1.1數(shù)據(jù)挖掘的歷史、開展數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析由于大型數(shù)據(jù)系統(tǒng)的廣泛使用和把數(shù)據(jù)轉(zhuǎn)換成有用知識(shí)的迫切的需要，數(shù)據(jù)挖掘引起了各行業(yè)的關(guān)注。20世紀(jì)60

18、年代，為了適應(yīng)信息的電子話需求，信息技術(shù)一直從簡(jiǎn)單的文件處理系統(tǒng)向有效的數(shù)據(jù)庫(kù)系統(tǒng)變革。20世紀(jì)70年代，數(shù)據(jù)庫(kù)系統(tǒng)的三個(gè)主要的模式：層次，網(wǎng)絡(luò)，關(guān)系型數(shù)據(jù)庫(kù)的研究和開發(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年代中期開場(chǎng)，關(guān)系型數(shù)據(jù)庫(kù)技術(shù)和新型技術(shù)的結(jié)合成為數(shù)據(jù)庫(kù)研究和開展的重要標(biāo)志。從數(shù)據(jù)的分布角度看，分布式數(shù)據(jù)庫(kù)及其透明性、并發(fā)控制、并行處理等成為必須面對(duì)的課題。許多的商業(yè)活動(dòng)中，由于數(shù)據(jù)庫(kù)的普及，人工去整理和理解如此大的數(shù)據(jù)源已經(jīng)存在效率、準(zhǔn)確性等問題，并不是每個(gè)人都能夠從過去

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

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

21、數(shù)據(jù)挖掘的定義從技術(shù)角度而言，數(shù)據(jù)挖掘是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的實(shí)際數(shù)據(jù)中，提取隱含在其中人們事先不知道但又潛在有用的信息和知識(shí)的過程。這一定義包括多層含義、及數(shù)據(jù)源必須是真實(shí)的、海量的、發(fā)現(xiàn)的知識(shí)應(yīng)是用戶感興趣的，并且是可承受的、可理解的和可應(yīng)用的，可以僅支持特定的問題。從商業(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)

22、證的規(guī)律性，并進(jìn)一步將其模型化的有效方法。2.2數(shù)據(jù)挖掘的分類數(shù)據(jù)挖掘按挖掘任務(wù)類型分類或預(yù)測(cè)模型發(fā)現(xiàn)2.數(shù)據(jù)總結(jié)與聚類發(fā)現(xiàn)3.關(guān)聯(lián)規(guī)則發(fā)現(xiàn)4.序列模式發(fā)現(xiàn)5.相似模式發(fā)現(xiàn)6.混沌模式發(fā)現(xiàn)7.依賴關(guān)系或依賴模型發(fā)現(xiàn)異常和趨勢(shì)發(fā)現(xiàn)等2.2.2 按挖掘?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ù)挖掘9.web數(shù)據(jù)庫(kù)挖掘 2.2.3 按挖掘方法 1.機(jī)器學(xué)習(xí)方法2.統(tǒng)計(jì)方法 3. 聚類分析方法 4.神經(jīng)網(wǎng)絡(luò)方法 5.遺傳算法方法 6.數(shù)據(jù)庫(kù)方法 7.近似推理和不確定性推理方法 8.給予證據(jù)理論和

23、元模式的方法 9.現(xiàn)代數(shù)學(xué)分析方法 10.粗糙集或模糊集方法 11.集成方法等2.2.4 按數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識(shí)1.挖掘廣義型知識(shí) 2.挖掘差異型知識(shí) 3.挖掘關(guān)聯(lián)型知識(shí) 4.挖掘預(yù)測(cè)性知識(shí) 5.挖掘偏離型知識(shí) 6.挖掘不確定性知識(shí)2.3數(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)的屬性-值元組。例如：*y說吧表達(dá)的含義是滿足*遠(yuǎn)足有可能滿足Y。關(guān)聯(lián)分析在交易數(shù)據(jù)分析、支持定向、商品目錄設(shè)計(jì)和其他業(yè)務(wù)決策等方面有著廣泛的應(yīng)用。決策樹方法ID3算法是最典型的決策樹分類算法，決策樹是從機(jī)器學(xué)習(xí)角度研究和開展起來的，對(duì)于大訓(xùn)練樣本集很難適應(yīng)。決策樹是

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

25、決問題能力和廣泛的適應(yīng)性滲透到研究與工程的各個(gè)領(lǐng)域。遺傳算法是一種高效的全局并行搜索優(yōu)化算法。2.4數(shù)據(jù)挖掘的實(shí)現(xiàn)過程2.4.1 數(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í)的模型2.4.3 模式的評(píng)估解釋通過上述步驟得到的模式，有可能是沒有意義或沒有實(shí)用價(jià)值的，因此需要評(píng)估，確定哪些是有效的、有用的模式。此外，大局部模式是數(shù)學(xué)表達(dá)式，需要將其

26、解釋成可理解的方式呈現(xiàn)給用戶。2.4.4 知識(shí)運(yùn)用運(yùn)用只是主要有兩種途徑。一、只許看知識(shí)本身描述的關(guān)系或結(jié)果，就可以對(duì)決策提供支持；二、要求對(duì)新的數(shù)據(jù)運(yùn)用知識(shí)，由此可能產(chǎn)生新的問題，并需要對(duì)知識(shí)做進(jìn)一步優(yōu)化。第三章決策樹技術(shù)3.1決策樹技術(shù)決策樹是分類預(yù)測(cè)的主要方法，采用基于實(shí)例的歸納學(xué)習(xí)算法，旨在從一組無次序、無規(guī)則的實(shí)例中推理出決策樹形式的分類規(guī)則，采用自頂向下的遞歸方式，在決策樹的部節(jié)點(diǎn)進(jìn)展屬性值的比擬并根據(jù)不同屬性判斷從該節(jié)點(diǎn)向下的分枝，在決策樹的葉節(jié)點(diǎn)得到結(jié)論，所以從根到葉節(jié)點(diǎn)對(duì)應(yīng)一條合取規(guī)則，整顆樹對(duì)應(yīng)一組析取規(guī)則。決策樹分類是利用屬性值對(duì)各子集逐級(jí)劃分，直到一個(gè)結(jié)點(diǎn)僅含有同一類樣

27、本為止。3.2算法描述3.2.1 ID3算法根本思路是首先在數(shù)據(jù)集中采用信息增益作為屬性選擇的標(biāo)準(zhǔn)，找出最有影響力的屬性，將數(shù)據(jù)集分成多個(gè)子集，每個(gè)子集又選擇最具影響力的屬性進(jìn)展劃分，一直進(jìn)展到所有自己僅包含同一類型的樣本為止，最后得到一顆決策樹。決策樹的構(gòu)造采用自上而下，分而治之的遞歸方式。初始時(shí)根節(jié)點(diǎn)包含數(shù)據(jù)集的所有的樣本。假設(shè)一個(gè)結(jié)點(diǎn)包含的樣本均為同一個(gè)類別，則該結(jié)點(diǎn)成為葉結(jié)點(diǎn)并標(biāo)記為該類別；否則采用信息增益的度量選擇適宜的分類屬性，將數(shù)據(jù)集劃分為假設(shè)干個(gè)子集。該屬性成為相應(yīng)結(jié)點(diǎn)的測(cè)試屬性。對(duì)測(cè)試屬性的每個(gè)值都創(chuàng)立一個(gè)分支，同時(shí)也包含一個(gè)被劃分的子集。遞歸的對(duì)所獲得的每個(gè)劃分形成一顆決策

28、樹。一旦一個(gè)屬性出現(xiàn)在*個(gè)結(jié)點(diǎn)上，則不能出現(xiàn)在該結(jié)點(diǎn)之后所產(chǎn)生的子樹結(jié)點(diǎn)上。當(dāng)一個(gè)結(jié)點(diǎn)包含的所有樣本均為同一類別或沒有樣本滿足測(cè)試屬性值，則算法終止。屬性信息增益選擇測(cè)試屬性的方法如下：設(shè)數(shù)據(jù)集S有s個(gè)樣本，類別屬性有m個(gè)不同的取值。定義m個(gè)不同的類Ci，i1,2,3m。設(shè)si為類別Ci的樣本個(gè)數(shù)，則對(duì)一個(gè)數(shù)據(jù)集分類所需的期望信息為：Is,ss)=-log3.1其中p是任意一個(gè)樣本，類別屬性有m個(gè)不同的取值，定義m個(gè)不同的類C的概率，可以按s/S計(jì)算。因?yàn)椴捎枚M(jìn)制編碼，所以對(duì)數(shù)函數(shù)以2為底。設(shè)屬性A可取v個(gè)不同的值a,a,aa.可以用屬性A將S劃分為v個(gè)子集S，S,S,其中Sj包含S中屬性A

29、中取值a為1的樣本。假設(shè)屬性A為測(cè)試屬性，設(shè)s為子集S中屬于C類別的樣本數(shù)。則利用屬性A劃分當(dāng)前集合所需要的期望信息計(jì)算如下：EA=Is,s,ss) 其中成為第j個(gè)子集的權(quán)值。EA)值越小，表示子集劃分結(jié)果越好。而對(duì)于一個(gè)給定子集S，其期望信息如式3.1，其中p=為子集S中任意一個(gè)樣本屬于類別C的概率。由此利用屬性A對(duì)當(dāng)前分支結(jié)點(diǎn)進(jìn)展劃分所獲得的信息增益是： Gain(A)=I(s,s,s)-E(A)Gain(A)是根據(jù)屬性A進(jìn)展集合劃分所獲得的信息熵的減少量。3.2.2 改良算法C4.5算法是由ID3算法演變而來，除了具有ID3算法的功能外，C4.5算法引入了新的方法和增加了新的功能。(1)

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

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

32、12一般004男一般=1一般005男一般0不及格006女好=1一般007男好=1良好008女良好=3良好011女一般1-2一般012男好=3良好014男一般=1一般.從表中選取14個(gè)樣本，其中良好的人數(shù)有6個(gè)，一般的人數(shù)有7個(gè)，不及格一個(gè)人；選擇是否良好為類別屬性。其中良好用yes表示，一般用no表示，Yes有6人，no有7人；即I6,7=-6/13log6/13-7/13log7/13=0.9957依次計(jì)算各個(gè)屬性，性別屬性 A性別=男，yes有4個(gè)，no有4個(gè)I4,4=1B.性別=女，yes有2個(gè)，no有3個(gè)I2,3=0.9710E性別=8/13+5/13*0.9710=0.9888Gai

33、n(性別=0.9957-0.9888=0.0069根底程度屬性A.根底程度=良好，yes有2個(gè)，no有0個(gè)I(2，0)=0 B根底程度=好，yes有2個(gè)，no有3個(gè)I2,3=0.9710 C.根底程度=一般，yes有2個(gè)，no有4個(gè) I2,4=0.9180E根底程度=5/13*0.9710+6/13*0.9180=0.7972 Gain根底程度=0.9957-0.7972=0.1985上機(jī)時(shí)間屬性 A.上機(jī)時(shí)間=3,yes有3個(gè)，no有0個(gè) I3,0=0 E上機(jī)時(shí)間=6/13=0.4615 Gain(上機(jī)時(shí)間=0.9957-0.4615=0.5342由此可知，上機(jī)時(shí)間的信息增益值最大，因此選做

34、根節(jié)點(diǎn)。上機(jī)時(shí)間=3*性別根底程度成績(jī)001女良好良好013男一般良好確定葉節(jié)點(diǎn)得到的決策樹如下所示：3.2.4 改良算法計(jì)算學(xué)生的信息*性別根底程度上機(jī)時(shí)間學(xué)習(xí)成績(jī)001女良好=3良好002女一般1-2一般003男好12一般004男一般=1一般005男一般0不及格006女好=1一般007男好=1良好008女良好=3良好011女一般1-2一般012男好=3良好014男一般=3,S11=3, s21=0, I(3,0)=0 2.上機(jī)時(shí)間=1-2，s21=4, s22=0, I(4,0)=0 3.上機(jī)時(shí)間=3計(jì)算每個(gè)子樹的生成過程：對(duì)于第一個(gè)子樹，yes有3個(gè)，no有3個(gè)，I(3,3)=11.計(jì)算

35、性別屬性的SplitI值得到： SplitI(性別=4/6log4/6 - 2/6log2/6=0.9183對(duì)于決策學(xué)習(xí)成績(jī)，計(jì)算性別的兩個(gè)屬性的分布的期望信息得到：1.性別=男，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(性別=0計(jì)算根底程度屬性的SplitI值得到： SplitI根底程度=-2/6log2/6 - 3/6log3/6-1/6log1/6=1.4591對(duì)于決策學(xué)習(xí)成績(jī)屬性來說，計(jì)算根底程度的每個(gè)分布的信息增益： 1.根底程度=一般，S11=2，S21=0，I2,0=0 2.根底程度= 好，S12=2，s22=1, I(2,1)=0.9180 3.根底程度=良好，s13=1,s33=0 , I(1,0)=0因此得根底程度屬性的熵為： E根底程度=4/6*0.9180=0.6120對(duì)應(yīng)的信息增益為：Gain根底程度=1-0.612=0.3880信息增益比例GainR