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

1、學(xué)年論文決策樹(shù)在成績(jī)分析中的應(yīng)用學(xué)院：計(jì)算機(jī)科學(xué)與工程學(xué)院班級(jí):*學(xué)號(hào):*姓名: 導(dǎo)師：*摘要 1Abstract 2第一章緒論 31.1數(shù)據(jù)挖掘的歷史、發(fā)展 3數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析 3數(shù)據(jù)挖掘研究的發(fā)展趨勢(shì) 3第二章數(shù)據(jù)挖掘的基本知識(shí) 42.1數(shù)據(jù)挖掘的定義 42.2數(shù)據(jù)挖掘的分類 4數(shù)據(jù)挖掘按挖掘任務(wù)類型 42.2.2 按挖掘?qū)ο?42.2.3 按挖掘方法 5按數(shù)據(jù)挖掘所能發(fā)現(xiàn)的知識(shí) 52.3數(shù)據(jù)挖掘技術(shù)的主要方法 52.3.1 關(guān)聯(lián)規(guī)則方法 5決策樹(shù)方法 52.3.3 神經(jīng)網(wǎng)絡(luò)方法 6遺傳算法 62.4數(shù)據(jù)挖掘的實(shí)現(xiàn)過(guò)程 62.4.1 數(shù)據(jù)準(zhǔn)備 6數(shù)據(jù)挖掘 62.4.3 模式的評(píng)估

2、解釋 62.4.4 知識(shí)運(yùn)用 6第三章決策樹(shù)技術(shù) 63.1決策樹(shù)技術(shù) 63.2算法描述 73.2.1 ID3 算法 73.2.2 改進(jìn)算法 83.2.3 ID3 算法計(jì)算學(xué)生的成績(jī)信息 9改進(jìn)算法計(jì)算學(xué)生的信息 13第四章總結(jié) 18參考文獻(xiàn)： 18精選資料，歡迎下載決策樹(shù)在成績(jī)分析中的應(yīng)用摘要數(shù)據(jù)挖掘的提出是在20世紀(jì)80年代，它是一個(gè)新興的、面向商業(yè)應(yīng)用的 AI研究領(lǐng)域，20世紀(jì)末，隨著In ternet的普及，全球信息量以驚人的速度急劇 增長(zhǎng)，據(jù)估計(jì)每二十個(gè)月增加一倍。目前的數(shù)據(jù)庫(kù)系統(tǒng)雖然可以高效的實(shí)現(xiàn)數(shù)據(jù) 的錄入、查詢、和統(tǒng)計(jì)等功能，但卻無(wú)法發(fā)現(xiàn)海量數(shù)據(jù)中隱藏的知識(shí)和規(guī)律；人 們面臨的主

3、要問(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í)的階段。它不僅能對(duì)過(guò)去的數(shù)據(jù)進(jìn)行查詢，而且能夠找出過(guò)去數(shù)據(jù)進(jì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ù)挖掘是

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

5、Applicati on of decisi on tree in performa nee an alysisAbstractData mining is put forward in 1980s, it is a new, twentieth Centuryfor the commercial applicationof AI research field,at the end, with thepopularity of In ternet,the global in formatio n has dramatically in creasedat an alarmi ng rate,

6、is estimated to be doubled every twenty mon ths. Although the curre nt database system can achieve data en try, efficie nt the query and statistical functions, but can not find the kno wledge and rules hidde n in massive data; the main problems that people are facing is not lack of eno ugh in format

7、i on can be used, but the face of the vast ocea n of data and how to use these data effectively. How these massive data extracted from the database, and turn them into useful the in formati on; in the face of this challe nge, data mining and kno wledge discovery tech no logy came into being, and sho

8、w strong vitality. Data mining and kno wledge discovery, data process ing tech no logy into a A more adva need stage. It can not only query on past data, and can ide ntify the past data query, and to find out the pote ntial li nk betwee n past data, higher level of analysis,in order to better solve

9、the decision problem.Data mi ning, predict ion, from a tech ni cal point of view, data mi ning is from a large nu mber of, in complete, no isy, fuzzy and ran dom of the actual data, extract some unknown but pote ntially useful in formati on and kno wledge process. From the bus in ess perspective, th

10、e data mining is a new bus in ess in formatio n process ing tech no logy,its mai n characteristicis to a large nu mber of bus in ess data in the database the extracti on, tran sformatio n, an alysis and other models for process ing, extracti on bus in ess decisi ons from the key in formati on and kn

11、o wledge.This paper mainly discusses the use of decisi on tree tech no logy for the an alysis of a large nu mber of stude nt data, in which mining useful in formatio n, the purpose is to improve the quality of teach ing.Decisi on tree for classificati onand predict ionof the main tech no logyand dec

12、ision tree learning is instanee based inductive learning algorithm, it looks from a group of out of order, irregular in sta nee reas oning decision tree representationof classificationrules, which includes twosteps: a using training sets to establish and refi ne the decisi on tree, decisi on tree mo

13、del is built. From the data access to kno wledge, carry on the machi ne lear ning process. Second, using the built decisi on tree to classify new data.Keywords: data mining, decisi on tree tech no logy,performa nee an alysis第一章緒論1.1數(shù)據(jù)挖掘的歷史、發(fā)展數(shù)據(jù)挖掘技術(shù)的商業(yè)需求分析由于大型數(shù)據(jù)系統(tǒng)的廣泛使用和把數(shù)據(jù)轉(zhuǎn)換成有用知識(shí)的迫切的需要，數(shù)據(jù)挖掘引起了各行業(yè)的關(guān)注。

14、20世紀(jì)60年代，為了適應(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ù)的研究和開(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)題

15、，并不是每個(gè)人都能夠從過(guò)去的銷售情況預(yù)測(cè)將來(lái)的發(fā) 展趨勢(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ù)的快速訪問(wèn)、集成和抽取等問(wèn)題上有了突 破，數(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ù)內(nèi)容的選擇性輸出，因此它和人們期望的分析預(yù)測(cè)、決策支持等高級(jí)應(yīng)用人有很大 的距離。近年來(lái)，由于數(shù)據(jù)采集技術(shù)的更新，決

16、策所面對(duì)的數(shù)據(jù)量在不斷的增長(zhǎng)， 隨著數(shù)據(jù)的急劇增長(zhǎng)，現(xiàn)有信息管理系統(tǒng)中的數(shù)據(jù)分析工具已無(wú)法適應(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ǔ)類型的適應(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ù)

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

18、既定業(yè)務(wù)目標(biāo)， 對(duì)大量的企業(yè)數(shù)據(jù)進(jìn)行探 索和分析，揭示隱藏的、未知的或驗(yàn)證已知的規(guī)律性，并進(jìn)一步將其模型化的有 效方法。2.2數(shù)據(jù)挖掘的分類數(shù)據(jù)挖掘按挖掘任務(wù)類型1. 分類或預(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)等按挖掘?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ù)挖掘223按挖掘方法1. 機(jī)器學(xué)習(xí)方法2. 統(tǒng)計(jì)方法3. 聚類分析方法4. 神經(jīng)

19、網(wǎng)絡(luò)方法5. 遺傳算法方法6. 數(shù)據(jù)庫(kù)方法7. 近似推理和不確定性推理方法8. 給予證據(jù)理論和元模式的方法9. 現(xiàn)代數(shù)學(xué)分析方法10. 粗糙集或模糊集方法11. 集成方法等按數(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)的屬性 - 值元組。例如：x->y說(shuō)吧表達(dá)的含義是滿足 X遠(yuǎn)足有可能滿足Y。關(guān)聯(lián)分析在 交易數(shù)據(jù)分析、支持定向、商品目錄設(shè)計(jì)和其他業(yè)務(wù)決策等方面有著廣泛的應(yīng)用。決策樹(shù)方法ID3算

20、法是最典型的決策樹(shù)分類算法，決策樹(shù)是從機(jī)器學(xué)習(xí)角度研究和發(fā)展 起來(lái)的，對(duì)于大訓(xùn)練樣本集很難適應(yīng)。決策樹(shù)是通過(guò)一系列規(guī)則對(duì)數(shù)據(jù)進(jìn)行分類 的過(guò)程。以樹(shù)的形式來(lái)表達(dá)模型，主要是對(duì)屬性值進(jìn)行歸納分類，它采用自頂向 下的遞歸方式，在決策樹(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é)果容易理解，精度較高。233神經(jīng)網(wǎng)絡(luò)方法是人們?cè)谀M人腦處理問(wèn)題的過(guò)程中發(fā)展起來(lái)的新型智能信息處理理論。它通過(guò)大量的稱為神經(jīng)元的簡(jiǎn)單處理單元構(gòu)成非線性動(dòng)力學(xué)系統(tǒng)，對(duì)人腦的形象思維、聯(lián)想記憶等進(jìn)行模擬和抽象，

21、實(shí)現(xiàn)與人腦相似的學(xué)習(xí)、識(shí)別、記憶等信息處 理能力。遺傳算法是模擬自然界生化進(jìn)化過(guò)程的隨機(jī)化搜索算法，它以很強(qiáng)的解決問(wèn)題能力和廣泛的適應(yīng)性滲透到研究與工程的各個(gè)領(lǐng)域。遺傳算法是一種高效的全局并行搜索優(yōu)化算法。2.4數(shù)據(jù)挖掘的實(shí)現(xiàn)過(guò)程數(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ò)上述步驟得到的模式，有

22、可能是沒(méi)有意義或沒(méi)有實(shí)用價(jià)值的， 因此需要 評(píng)估，確定哪些是有效的、有用的模式。此外，大部分模式是數(shù)學(xué)表達(dá)式，需要 將其解釋成可理解的方式呈現(xiàn)給用戶。知識(shí)運(yùn)用運(yùn)用只是主要有兩種途徑。一、只許看知識(shí)本身描述的關(guān)系或結(jié)果，就可以 對(duì)決策提供支持；二、要求對(duì)新的數(shù)據(jù)運(yùn)用知識(shí)，由此可能產(chǎn)生新的問(wèn)題，并需 要對(duì)知識(shí)做進(jìn)一步優(yōu)化。第三章決策樹(shù)技術(shù)3.1決策樹(shù)技術(shù)決策樹(shù)是分類預(yù)測(cè)的主要方法，采用基于實(shí)例的歸納學(xué)習(xí)算法，旨在從一組 無(wú)次序、無(wú)規(guī)則的實(shí)例中推理出決策樹(shù)形式的分類規(guī)則，采用自頂向下的遞歸方式，在決策樹(shù)的內(nèi)部節(jié)點(diǎn)進(jìn)行屬性值的比較并根據(jù)不同屬性判斷從該節(jié)點(diǎn)向下的分枝，在決策樹(shù)的葉節(jié)點(diǎn)得到結(jié)論，所以從根

23、到葉節(jié)點(diǎn)對(duì)應(yīng)一條合取規(guī)則， 整顆 樹(shù)對(duì)應(yīng)一組析取規(guī)則。決策樹(shù)分類是利用屬性值對(duì)各子集逐級(jí)劃分，直到一個(gè)結(jié)點(diǎn)僅含有同一類 樣本為止。3.2算法描述算法基本思路是首先在數(shù)據(jù)集中采用信息增益作為屬性選擇的標(biāo)準(zhǔn)，找出最有影響力的屬性，將數(shù)據(jù)集分成多個(gè)子集，每個(gè)子集又選擇最具影響力的屬性進(jìn)行劃 分，一直進(jìn)行到所有自己僅包含同一類型的樣本為止，最后得到一顆決策樹(shù)。決策樹(shù)的構(gòu)造采用自上而下，分而治之的遞歸方式。初始時(shí)根節(jié)點(diǎn)包含數(shù)據(jù)集的所 有的樣本。若一個(gè)結(jié)點(diǎn)包含的樣本均為同一個(gè)類別，則該結(jié)點(diǎn)成為葉結(jié)點(diǎn)并標(biāo)記 為該類別；否則采用信息增益的度量選擇合適的分類屬性，將數(shù)據(jù)集劃分為若干個(gè)子集。該屬性成為相應(yīng)結(jié)點(diǎn)的測(cè)

24、試屬性。對(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)包含的所有樣本均為同一類別或沒(méi)有樣本滿足測(cè)試屬性值，則算法終止。屬性信息增益選擇測(cè)試屬性的方法如下：設(shè)數(shù)據(jù)集S有s個(gè)樣本，類別屬性有m個(gè)不同的取值。定義m個(gè)不同的類 Ci，i 1,2,3.m。設(shè)si為類別Ci的樣本個(gè)數(shù)，則對(duì)一個(gè)數(shù)據(jù)集分類所需的期望信息為：mI （Sij,s 2j smj）=- pij log 2pij）（3.1）i 1其中Pi是任意一個(gè)樣本，類別屬性有 m個(gè)不同的取值，定義 m

25、個(gè)不同的類Ci的概率，可以按sS計(jì)算。因?yàn)椴捎枚M(jìn)制編碼，所以對(duì)數(shù)函數(shù)以2為底。設(shè)屬性A可取v個(gè)不同的值a 1,a 2 ,a 3 av.可以用屬性A將S劃分為v個(gè)子集S1，S2,.S v,其中Sj包含S中屬性A中取值aj為1的樣 本。若屬性A為測(cè)試屬性，設(shè)sj為子集Sj中屬于G類別的樣本數(shù)。則利用屬性 A劃分當(dāng)前集合所需要的期望信息計(jì)算如下：s1 j s2 j s3 j smjE （ A）=I （ s 1j ,s 2j ,s 3j s mj）i 1SS2jS3j如成為第j個(gè)子集的權(quán)值。E（ A）值越小，表示子集劃分結(jié)果越好。而對(duì)于一個(gè)給定子集Sj，其期望信息如式(3.1 )，其中Pij= Lj

26、j |Sj|為子集Sj中任意一個(gè)樣本屬于類別G的概率。由此利用屬性A對(duì)當(dāng)前分支結(jié)點(diǎn)進(jìn)行劃分所獲得的信息增益是：Gain(A)=l(s 門,s 2j,smj)-E(A)Gain(A)是根據(jù)屬性A進(jìn)行集合劃分所獲得的信息熵的減少量。改進(jìn)算法C4.5算法是由ID3算法演變而來(lái)，除了具有ID3算法的功能外，C4.5算法 引入了新的方法和增加了新的功能。(1) 信息增益比例的概念信息增益比例是在信息增益概念基礎(chǔ)上發(fā)展來(lái)的，表示為：Ga in Ratio ( A)=Gai n ( A)/Splitl( A)其中SplitIv(A) =-Pj log2 Pjj 1可以用屬性A將S劃分為V設(shè)屬性A具有V個(gè)不同

27、的值a1,a2,av, 個(gè)子集s1,s2,.sv, 其中Sj包含S中這樣一些樣本：它們?cè)贏上具有值aj.(2) 合并具有連續(xù)值的屬性ID3算法最初假定屬性離散值，但在實(shí)際環(huán)境中，很多屬性值是連續(xù)的對(duì)于連續(xù)屬性值，C4.5其處理過(guò)程如下：*根據(jù)屬性的值，對(duì)數(shù)據(jù)集排序；*用不同的閾值將數(shù)據(jù)集動(dòng)態(tài)地進(jìn)行劃分；*當(dāng)輸出改變時(shí)確定一個(gè)閾值；*取兩個(gè)實(shí)際值中的中點(diǎn)作為一個(gè)閾值；*取兩個(gè)劃分，所有的樣本都在這兩個(gè)劃分中；*得到所有可能的閾值、增益、及增益比；*在每一個(gè)屬性會(huì)變?yōu)閮蓚€(gè)取值，即小于閾值或大于閾值；(3) 處理含有未知屬性值的訓(xùn)練樣本C4.5 處理樣本中可以含有未知的屬性值，其處理方法是用最常用的

28、值分在 同一類中。具體采用概率的方法，依據(jù)屬性已知的值，對(duì)屬性和每一個(gè)值賦予一個(gè)概率，取得這些概率依賴于該屬性已知的值。(4) 規(guī)則的產(chǎn)生一旦樹(shù)被建立。就可以把樹(shù)轉(zhuǎn)換成if-the n 的規(guī)則，規(guī)則存儲(chǔ)于一個(gè)二 維的數(shù)組中，每一行代表樹(shù)中的一個(gè)規(guī)則，即從根到葉之間 的一個(gè)路徑。表中 的每列存放著樹(shù)中的結(jié)點(diǎn)。323 ID3 算法計(jì)算學(xué)生的成績(jī)信息學(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一般01

29、0男一般>=3良好011女一般1-2一般012男好<=1良好013男一般>=3良好014男一般<=1一般理工科學(xué)生成績(jī)分析表如下:從表中選取14個(gè)樣本，其中良好的人數(shù)有 6個(gè)，一般的人數(shù)有7個(gè)，不及 格一個(gè)人；選擇是否良好為類別屬性。其中良好用 yes表示，一般用 no表示，Yes有6人，no有7人；即 I (6,7)二6/13log 26/13-7/13log27/13=0.9957依次計(jì)算各個(gè)屬性，1性別屬性A性別='男，yes有4個(gè)，no有4個(gè)I （ 4,4）=1b.性別='女，yes有2個(gè)，no有3個(gè)I ( 2,3)=0.9710E (性別)=8

30、/13+5/13*0.9710=0.9888Gai n(性別)=0.9957-0.9888=0.00692. 基礎(chǔ)程度屬性A. 基礎(chǔ)程度=良好，yes有2個(gè)，no有0個(gè)1(2 , 0)=0B 基礎(chǔ)程度='好，yes有2個(gè)，no有3個(gè)I (2,3 ) =0.9710C.基礎(chǔ)程度=一般，yes有2個(gè)，no有4個(gè)I (2,4 ) =0.9180E (基礎(chǔ)程度)=5/13*0.9710+6/13*0.9180=0.7972Gain(基礎(chǔ)程度)=0.9957-0.7972=0.19853. 上機(jī)時(shí)間屬性a. 上機(jī)時(shí)間=1,yes有3個(gè)，no有3個(gè)I (3,3, ) =1b. 上機(jī)時(shí)間=1-2，y

31、es有0個(gè)，no有4個(gè)I (0,4 ) =0c. 上機(jī)時(shí)間=3, yes有3個(gè)，no有0個(gè)I(3,0 ) =0E(上機(jī)時(shí)間)=6/13=0.4615Gain(上機(jī)時(shí)間)=0.9957-0.4615=0.5342由此可知，上機(jī)時(shí)間的信息增益值最大，因此選做根節(jié)點(diǎn)。上機(jī)時(shí)間=1學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)004男一般一般006女好一般007男好良好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 (性別)=1Gai

32、n (性別)=02.基礎(chǔ)程度屬性A. 基礎(chǔ)程度=一般，yes有0個(gè)，no有2個(gè)I (0,2 ) =0B. 基礎(chǔ)程度='好，yes有2個(gè)，no有1個(gè)I (2,1 ) =0.9180C. 基礎(chǔ)程度=良好，yes有1個(gè)，no有0個(gè)I (1,0 ) =0E (基礎(chǔ)程度)=3/6*0.9180=0.4590Gain(基礎(chǔ)程度)=1-0.4590=0.5410因此，以基礎(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 ) =0

33、.9810因?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-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ù)如下所示:324改進(jìn)算法計(jì)算學(xué)生的信息學(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良好0

34、08女良好<=1良好009男好1-2一般010男一般>=3良好011女一般1-2一般012男好<=1良好013男一般>=3良好014男一般<=1一般理工科學(xué)生成績(jī)分析表如下:按成績(jī)是否良好進(jìn)行劃分，yes表示良好，no表示一般計(jì)算學(xué)習(xí)成績(jī)屬性分類的期望信息得到：I （s1,s2）=l（6,7 ）二6/13log 26/13-7/13log2 7/13=0.99571. 計(jì)算性別的Splitl的值得到：Splitl（性別）二5/13LOG25/13-8/13LOG 2 8/13=0.9612對(duì)于決策學(xué)習(xí)成績(jī)來(lái)說(shuō)，計(jì)算性別屬性每個(gè)分布的期望信息得到：1. 對(duì)于性別=&

35、#39;男，s1仁4, s21=4,l（4,4）=12. 對(duì)于性別='女，s12= 2 , s22=3 ,1（2,3）=0.9710因此，得到性別屬性的熵為：E （性別）=8/13+5/13*0.9710= 0.7580對(duì)應(yīng)的信息增益：Gain （性別）=1 （S1,S2）-E（性別）=0.2377信息增益比例為：Gai nRatio （性別）=0.2377/0.9612=0.24732. 計(jì)算基礎(chǔ)程度屬性的SplitI值得到：SplitI（ 基礎(chǔ)程度）=-2/13LOG22/13-5/13LOG 25/13-6/13LOG2 6/13=1.4605對(duì)于決策學(xué)習(xí)成績(jī)屬性來(lái)說(shuō)，計(jì)算基礎(chǔ)程

36、度的每個(gè)分布的期望信息得到：1. 對(duì)于基礎(chǔ)程度=一般，S11= 2， S21= 4，I （2,4）=0.91802. 對(duì)于基礎(chǔ)程度='好，S12=2,S22=3 , I（2，3）=0.97103. 對(duì)于基礎(chǔ)程度=良好，S13= 2，S33= 0 ，I （2,0）=0因此得到基礎(chǔ)程度屬性的熵為：E （基礎(chǔ)程度）=6/13*0.9180+5/13*0.9710=0.7972對(duì)應(yīng)的信息增益：Gain（基礎(chǔ)程度）=0.9957- 0.7972=0.1985信息增益比例：GainRatio（基礎(chǔ)程度）=0.1985/1.4605=0.13593. 計(jì)算上機(jī)時(shí)間屬性的SplitI的值：Split

37、I（上機(jī)時(shí)間）=3/13log 23/13-4/13log 24/13-6/13log 26/13=1.5262對(duì)于決策學(xué)習(xí)成績(jī)屬性來(lái)說(shuō)，計(jì)算上機(jī)時(shí)間的每個(gè)分布的期望信息得到：1. 對(duì)于上機(jī)時(shí)間>=3,S1仁3, s2仁0, 1(3,0)=02. 上機(jī)時(shí)間=1-2，s21=4, s22=0, I(4,0)=03. 上機(jī)時(shí)間 <=1, s3仁3,s33=3 I(3,3)=1因此得到上機(jī)時(shí)間的熵為：E (上機(jī)時(shí)間)=6/13=0.4615對(duì)應(yīng)的信息增益：Gain(上機(jī)時(shí)間)=0.9957-0.4615=0.5342信息增益比例：GainRatio(上機(jī)時(shí)間)=0.5342/1.5262

38、=0.35004. 選取最大的 GainRatio(上機(jī)時(shí)間)=0.5342/1.5262=0.3500，根據(jù)上機(jī)時(shí)間的取值，可以得到三個(gè)分支，同時(shí)數(shù)據(jù)集被劃分為三個(gè)子集，如圖所示:上機(jī)時(shí)間=1*1-21>=3_學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)學(xué)號(hào)性別基礎(chǔ)程度學(xué)習(xí)成績(jī)001女良好良好004男一般一般002女一般一般010男一般良好006女好一般003男好一般013男一般良好007男好良好009男好一般008女良好良好011女一般一般012男好良好014男一般一般計(jì)算每個(gè)子樹(shù)的生成過(guò)程：對(duì)于第一個(gè)子樹(shù)，yes有3個(gè)，no有3個(gè)，1(3,3)=11. 計(jì)算性別屬性的 Spli

39、tI值得到：Splitl（ 性別）=4/6log 24/6 - 2/6log 22/6=0.9183對(duì)于決策學(xué)習(xí)成績(jī)，計(jì)算性別的兩個(gè)屬性的分布的期望信息得到：1性別=男，S1仁2, s2仁2, l（2,2）=12性別='女，S12=1， s22=1, I（1,1）=1因此得性別屬性的熵為：E （性別）=1對(duì)應(yīng)的信息增益為：Gai n （性別）=1-1=0信息增益比例：GainRatio（性別）=02. 計(jì)算基礎(chǔ)程度屬性的 SplitI值得到：SplitI（基礎(chǔ)程度） 二2/6log 22/6 - 3/6log23/6-1/6log 21/6=1.4591對(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, 1（2,1）=0.91803.基礎(chǔ)程度='良好，s13=1,s33=0 , I（1,0）=0因此得基礎(chǔ)程度屬性的熵為：E （基礎(chǔ)程度）=4/6*0.9180=0.6120對(duì)應(yīng)的信息增益為：Gain （基礎(chǔ)程度）=1-0.612=0.3880信息增益比例GainRatio（基礎(chǔ)程度）=0.3880