畢業(yè)設(shè)計(jì)論文--數(shù)據(jù)挖掘技術(shù)

1、<p><b>　　目 錄</b></p><p><b>　　摘要iii</b></p><p>　　Abstractiv</p><p><b>　　第一章 緒論1</b></p><p>　　1.1 數(shù)據(jù)挖掘技術(shù)1</p><p>

2、;　　1.1.1 數(shù)據(jù)挖掘技術(shù)的應(yīng)用背景1</p><p>　　1.1.2數(shù)據(jù)挖掘的定義及系統(tǒng)結(jié)構(gòu)2</p><p>　　1.1.3 數(shù)據(jù)挖掘的方法4</p><p>　　1.1.4 數(shù)據(jù)挖掘系統(tǒng)的發(fā)展5</p><p>　　1.1.5 數(shù)據(jù)挖掘的應(yīng)用與面臨的挑戰(zhàn)6</p><p>　　1.2 決策樹(shù)分類(lèi)算法

3、及其研究現(xiàn)狀8</p><p>　　1.3數(shù)據(jù)挖掘分類(lèi)算法的研究意義10</p><p>　　1.4本文的主要內(nèi)容11</p><p>　　第二章 決策樹(shù)分類(lèi)算法相關(guān)知識(shí)12</p><p>　　2.1決策樹(shù)方法介紹12</p><p>　　2.1.1決策樹(shù)的結(jié)構(gòu)12</p><p>

4、;　　2.1.2決策樹(shù)的基本原理13</p><p>　　2.1.3決策樹(shù)的剪枝15</p><p>　　2.1.4決策樹(shù)的特性16</p><p>　　2.1.5決策樹(shù)的適用問(wèn)題18</p><p>　　2.2 ID3分類(lèi)算法基本原理18</p><p>　　2.3其它常見(jiàn)決策樹(shù)算法20</p>

5、;<p>　　2.4決策樹(shù)算法總結(jié)比較24</p><p>　　2.5實(shí)現(xiàn)平臺(tái)簡(jiǎn)介25</p><p>　　2.6本章小結(jié)29</p><p>　　第三章 ID3算法的具體分析30</p><p>　　3.1 ID3算法分析30</p><p>　　3.1.1 ID3算法流程30</p&

6、gt;<p>　　3.1.2 ID3算法評(píng)價(jià)33</p><p>　　3.2決策樹(shù)模型的建立34</p><p>　　3.2.1 決策樹(shù)的生成34</p><p>　　3.2.2 分類(lèi)規(guī)則的提取37</p><p>　　3.2.3模型準(zhǔn)確性評(píng)估38</p><p>　　3.3 本章小結(jié)39&l

7、t;/p><p>　　第四章 實(shí)驗(yàn)結(jié)果分析40</p><p>　　4.1 實(shí)驗(yàn)結(jié)果分析40</p><p>　　4.1.1生成的決策樹(shù)40</p><p>　　4.1.2 分類(lèi)規(guī)則的提取40</p><p>　　4.2 本章小結(jié)41</p><p>　　第五章 總結(jié)與展望42</

8、p><p><b>　　參考文獻(xiàn)44</b></p><p><b>　　致謝45</b></p><p><b>　　附錄46</b></p><p>　　摘要:信息高速發(fā)展的今天，面對(duì)海量數(shù)據(jù)的出現(xiàn)，如何有效利用海量的原始數(shù)據(jù)分析現(xiàn)狀和預(yù)測(cè)未來(lái)，已經(jīng)成為人類(lèi)面臨的一大挑戰(zhàn)

9、。由此，數(shù)據(jù)挖掘技術(shù)</p><p>　　應(yīng)運(yùn)而生并得到迅猛發(fā)展。</p><p>　　數(shù)據(jù)挖掘是信息技術(shù)自然演化的結(jié)果，是指從大量數(shù)據(jù)中抽取挖掘出來(lái)隱含未知的、有價(jià)值的模式或規(guī)律等知識(shí)的復(fù)雜過(guò)程。</p><p>　　本文主要介紹如何利用決策樹(shù)方法對(duì)數(shù)據(jù)進(jìn)行分類(lèi)挖掘。文中詳細(xì)的闡述了決策樹(shù)的基本知識(shí)和相關(guān)算法，并對(duì)幾種典型的決策樹(shù)算法進(jìn)行了分析比較，如:核心經(jīng)典算

10、法——ID3算法;能夠處理不完整的數(shù)據(jù)、對(duì)連續(xù)屬性的數(shù)據(jù)離散化處理以及克服了ID3算法偏向于選擇取值較多的屬性作為測(cè)試屬性的缺點(diǎn)的C4.5算法;利用GINI系數(shù)判別數(shù)據(jù)集中的分裂屬性并形成二叉樹(shù)的CART算法;使數(shù)據(jù)的分類(lèi)不受機(jī)器主存的限制，有著良好的伸縮和并行性的SLIQ和SPRNIT算法。ID3算法是最核心的技術(shù)，所以本文主要對(duì)它進(jìn)行了研究和設(shè)計(jì)實(shí)現(xiàn)。</p><p>　　第四章在JAVA編譯器上實(shí)現(xiàn)ID3算

11、法，并對(duì)結(jié)果進(jìn)行分析，決策樹(shù)生成，分類(lèi)規(guī)則的提取，以便于以后直接使用這一規(guī)則進(jìn)行數(shù)據(jù)分析。在論文的最后一章介紹了目前數(shù)據(jù)挖掘技術(shù)的研究前景。</p><p>　　關(guān)鍵詞:數(shù)據(jù)挖掘；決策樹(shù)；ID3算法；信息增益；熵值</p><p>　　Abstract: Today, the massage is passed very quickly. How to investigate curren

12、t status and forecast the future with good use of tremendous original Data has been becoming the big challenge to human beings when facing the emergence of mass Data in information era. Consequently, Data mining technolo

13、gy emerge and boom quickly.</p><p>　　Data mining, is the product of the evolution of information technology, which is a complex process excacting the implicated and valuable pattens, knowledge and rules from

14、 a large scale of dataset.</p><p>　　This paper mainly introduces the decision tree algorithm for classification. Firstly, the basic knowledge about decision tree and some representative algorithms for induci

15、ng decision tree are discussed, including ID3,which is classical;C4.5,which can deal with continuous attributes and some empty attribute ,at the same time, it can overcome the ID3’weakness which is apt to select some att

16、ribute with more value; CART, which uses GINI coefficient about attribute selection and induces a binary tree</p><p>　　The firth chapter,ID3 algorithm is developed on the java platform by java， and carries o

17、n the analysis to the result, the decision tree production, the classified rule extraction, it will be advantageous for us to use this rule to carry on the data analysis directly in the future. I introduce data mining t

18、echnology research prospect in the paper last chapter. </p><p>　　Key words: Data mining; Decision tree; ID3 algorithm ;Information gain; Entropy value</p><p><b>　　第一章 緒論</b></p>

19、;<p>　　1.1 數(shù)據(jù)挖掘技術(shù)</p><p>　　1.1.1 數(shù)據(jù)挖掘技術(shù)的應(yīng)用背景</p><p>　　最近幾十年以來(lái)，隨著互聯(lián)網(wǎng)的發(fā)展和企業(yè)信息化程度的日益提高，科研政府部門(mén)普遍使用電子事物處理技術(shù)，商品條形碼被廣泛使用，以及電子商務(wù)和科學(xué)數(shù)據(jù)庫(kù)的急劇增長(zhǎng)為我們帶來(lái)了海量的數(shù)據(jù)。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這

20、些數(shù)據(jù)。而目前的數(shù)據(jù)庫(kù)系統(tǒng)可以高效地實(shí)現(xiàn)數(shù)據(jù)的錄入、查詢(xún)、統(tǒng)計(jì)等功能，但無(wú)法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無(wú)法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測(cè)未來(lái)的發(fā)展趨勢(shì)，缺乏挖掘數(shù)據(jù)背后隱藏的知識(shí)的手段，從而導(dǎo)致了“數(shù)據(jù)爆炸但知識(shí)貧乏”的現(xiàn)象。</p><p>　　大量信息在給人們帶來(lái)方便的同時(shí)也帶來(lái)了一大堆問(wèn)題：第一是信息過(guò)量，難以消化；第二是信息真假難以辨識(shí)；第三是信息安全難以保證；第四是信息形式不一致，難以統(tǒng)一處理。人們開(kāi)始考慮：“如

21、何才能不被信息淹沒(méi)，而是從中及時(shí)發(fā)現(xiàn)有用的知識(shí)、提高信息利用率？”這就引 發(fā) 了 一 門(mén) 新 興 的 自 動(dòng) 信 息 提 取 技 術(shù) ： 數(shù) 據(jù) 中 的 知 識(shí) 發(fā) 現(xiàn) ， 簡(jiǎn) 稱(chēng)KDD[1] (Knowledge Discovery in Data Base)。其內(nèi)容主要涉及人工智能領(lǐng)域中的機(jī)器學(xué)習(xí)，模式識(shí)別、統(tǒng)計(jì)學(xué)、智能數(shù)據(jù)庫(kù)、知識(shí)獲取、專(zhuān)家系統(tǒng)、數(shù)據(jù)庫(kù)可視化、數(shù)據(jù)庫(kù)領(lǐng)域的數(shù)據(jù)倉(cāng)庫(kù)聯(lián)機(jī)分析處理(OLAP)，多維數(shù)據(jù)庫(kù)等方面。KDD

22、已經(jīng)是解決目前信息系統(tǒng)中普遍面臨的“數(shù)據(jù)爆炸”而“信息缺乏”狀況的最有效的手段之一，并且它的研究領(lǐng)域具有較大的研究意義和較多的研究方向一度成為數(shù)據(jù)庫(kù)研究界最熱的研究方向，擁有人數(shù)眾多的研究群體，受到學(xué)術(shù)界和企業(yè)界的極大關(guān)注。多學(xué)科的相互交融和相互促進(jìn)，使得這一學(xué)科得以蓬勃發(fā)展，而且已初具規(guī)模。并行計(jì)算、計(jì)算機(jī)網(wǎng)絡(luò)和信息工程等其他領(lǐng)域的國(guó)際學(xué)會(huì)、學(xué)刊也把數(shù)據(jù)挖掘和知識(shí)發(fā)現(xiàn)列為專(zhuān)題和</p><p>　　數(shù)據(jù)挖掘 D

23、M[2] (Data Mining)是 KDD 的一個(gè)最關(guān)鍵步驟，因此實(shí)際應(yīng)用中把 DM 和 KDD 不作區(qū)分。數(shù)據(jù)挖掘是目前研究的熱點(diǎn)，它可以說(shuō)是數(shù)據(jù)庫(kù)研究中的一個(gè)非常有應(yīng)用價(jià)值的新領(lǐng)域，它融合了數(shù)據(jù)庫(kù)、人工智能、機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計(jì)學(xué)、模糊數(shù)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)。從數(shù)據(jù)分析的觀點(diǎn)來(lái)看，數(shù)據(jù)挖掘分為兩類(lèi):描述性數(shù)據(jù)挖掘和預(yù)測(cè)性數(shù)據(jù)挖掘。描述性數(shù)據(jù)挖掘以概要方式描述數(shù)據(jù)，提供數(shù)據(jù)所具有的一般性質(zhì);預(yù)測(cè)性數(shù)據(jù)挖掘分析數(shù)據(jù)，建立一個(gè)或一組

24、模型，產(chǎn)生關(guān)于數(shù)據(jù)的預(yù)測(cè)。包括分類(lèi)和回歸。分類(lèi)可用于提取描述重要數(shù)據(jù)的模型或預(yù)測(cè)未來(lái)的數(shù)據(jù)趨勢(shì)。1995 年，在美國(guó)計(jì)算機(jī)年會(huì)(ACM)上，提出了數(shù)據(jù)挖掘的概念。即通過(guò)從數(shù)據(jù)庫(kù)中抽取隱含的，未知的，具有潛在使用價(jià)值信息的過(guò)程。數(shù)據(jù)挖掘應(yīng)用的普遍性及帶來(lái)的巨大的經(jīng)濟(jì)和社會(huì)效益，吸引了許多專(zhuān)家和研究機(jī)構(gòu)從事該領(lǐng)域的研究，許多公司推出了自己的數(shù)據(jù)庫(kù)挖掘系統(tǒng)。從 1989 年舉行的第十一屆國(guó)際聯(lián)合人工智能學(xué)術(shù)會(huì)議上 KDD被提出，到現(xiàn)在不過(guò)十多

25、年的時(shí)間，但在 Gartner Group 的一次高級(jí)技術(shù)調(diào)查中將數(shù)據(jù)挖掘和人工智能列為“未來(lái) 5 年內(nèi)將對(duì)</p><p>　　1.1.2數(shù)據(jù)挖掘的定義及系統(tǒng)結(jié)構(gòu)</p><p>　　數(shù)據(jù)挖掘也稱(chēng)為數(shù)據(jù)庫(kù)中的知識(shí)發(fā)現(xiàn)KDD(Knowledge Discovery in Data Base)。指的是從存放在數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù)中的大量數(shù)據(jù)中挖掘出人們感興趣的知識(shí)，這些知識(shí)是隱含的、

26、事先未知的潛在有用信息。目的是幫助決策者尋找數(shù)據(jù)間潛在的關(guān)聯(lián)，發(fā)現(xiàn)被忽略的要素，而這些信息對(duì)預(yù)測(cè)趨勢(shì)和決策行為也許是十分有用的。數(shù)據(jù)挖掘技術(shù)能從DW中自動(dòng)分析數(shù)據(jù)，進(jìn)行歸納性推理，從中發(fā)掘出潛在的模式，或產(chǎn)生聯(lián)想，建立新的業(yè)務(wù)模型，這是一個(gè)高級(jí)的處理過(guò)程。高級(jí)的處理過(guò)程是指一個(gè)多步驟的處理過(guò)程，多步驟之間相互影響、反復(fù)調(diào)整，形成一種螺旋式上升過(guò)程。這個(gè)過(guò)程與人類(lèi)問(wèn)題求解的過(guò)程是存在巨大相似性的。決策樹(shù)分類(lèi)算法的研究與改進(jìn)挖掘過(guò)程可能需要

27、多次的循環(huán)反復(fù)，每一個(gè)步驟一旦與預(yù)期目標(biāo)不符，都要回到前面的步驟，重新調(diào)整，重新執(zhí)行。</p><p>　　從廣義角度講數(shù)據(jù)、信息是知識(shí)的表現(xiàn)形式，但在數(shù)據(jù)挖掘中更多把概念、規(guī)則、模式、規(guī)律和約束等看作知識(shí)。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系型數(shù)據(jù)庫(kù)中的數(shù)據(jù)，也可以是半結(jié)構(gòu)化的，如文本、圖形、圖像數(shù)據(jù)、甚至是分布在網(wǎng)絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識(shí)的方法可以是數(shù)學(xué)的或非數(shù)學(xué)的、演繹的或歸納的。發(fā)現(xiàn)的知識(shí)可以被用于信息管理、

28、查詢(xún)優(yōu)化、決策支持、過(guò)程控制等。總之，數(shù)據(jù)挖掘是一門(mén)廣義的交叉學(xué)科，它的發(fā)展和應(yīng)用涉及到不同的領(lǐng)域尤其是數(shù)據(jù)庫(kù)、人工智能、數(shù)理統(tǒng)計(jì)、可視化、并行計(jì)算等。因此，概括起來(lái)從廣義上來(lái)說(shuō)，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的，有噪聲的，不確定的，各種存儲(chǔ)形式的）中，挖掘隱含在其中的，人們事先不知道的，對(duì)決策有用的知識(shí)的過(guò)程[3]。從狹義上來(lái)說(shuō)，數(shù)據(jù)挖掘是從特定形式的數(shù)據(jù)集中提煉知識(shí)的過(guò)程。</p><p>　　數(shù)據(jù)挖掘

29、的系統(tǒng)結(jié)構(gòu)可以用以下的圖來(lái)說(shuō)明：</p><p>　　圖1.1 數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)圖</p><p>　　·數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)或其他信息庫(kù):這是一個(gè)或一組數(shù)據(jù)庫(kù)、數(shù)據(jù)倉(cāng)庫(kù)、電子表格或其他類(lèi)型的信息庫(kù)?？梢栽跀?shù)據(jù)上進(jìn)行數(shù)據(jù)清理和集成。</p><p>　　·數(shù)據(jù)庫(kù)或數(shù)據(jù)倉(cāng)庫(kù)服務(wù)器:根據(jù)用戶(hù)的數(shù)據(jù)挖掘請(qǐng)求負(fù)責(zé)提取相關(guān)數(shù)據(jù)。</p><

30、p>　　·知識(shí)庫(kù):這是領(lǐng)域知識(shí)，用于指導(dǎo)、搜索或評(píng)估結(jié)果模式的興趣度。</p><p>　　·數(shù)據(jù)挖掘引擎:這是數(shù)據(jù)挖掘系統(tǒng)的基本部分。由一組功能模塊組成，用于特征化、關(guān)聯(lián)、分類(lèi)、聚類(lèi)分析以及演變和偏差分析。</p><p>　　·模式評(píng)估模塊:通常，此模塊使用興趣度度量，并與數(shù)據(jù)挖掘模塊交互，以便將搜索聚焦在有趣的模式上。</p><

31、;p>　　·圖形用戶(hù)界面:本模塊在用戶(hù)和數(shù)據(jù)挖掘系統(tǒng)之間通信，允許用戶(hù)與系統(tǒng)交互，指定數(shù)據(jù)挖掘查詢(xún)或任務(wù)，提供信息，幫助搜索聚焦，根據(jù)數(shù)據(jù)挖掘的中間結(jié)果進(jìn)行探索式數(shù)據(jù)挖掘。此外，此模塊還允許用戶(hù)瀏覽數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)模式或數(shù)據(jù)結(jié)構(gòu)，評(píng)估挖掘的模式，以不同的形式對(duì)模式可視化。</p><p>　　1.1.3 數(shù)據(jù)挖掘的方法</p><p>　　數(shù)據(jù)挖掘的功能用于指定數(shù)據(jù)挖掘任務(wù)

32、中要找的模式類(lèi)型，其任務(wù)一般可分為兩類(lèi):描述和預(yù)測(cè)。描述性挖掘任務(wù)刻畫(huà)數(shù)據(jù)庫(kù)中數(shù)據(jù)的一般特性，預(yù)測(cè)性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進(jìn)行推斷，以進(jìn)行預(yù)測(cè)。在實(shí)際應(yīng)用中，往往根據(jù)模式的實(shí)際應(yīng)用細(xì)分為以下 6 種[4]:</p><p><b>　　1.分類(lèi)模式</b></p><p><b>　　2.回歸模式</b></p><p>&

33、lt;b>　　3.時(shí)間序列模式</b></p><p><b>　　4.聚類(lèi)模式</b></p><p><b>　　5.關(guān)聯(lián)模式</b></p><p><b>　　6.序列模式</b></p><p>　　本文主要介紹分類(lèi)算法，所以下面主要介紹分類(lèi)分析方法

34、，分類(lèi)分析要分析數(shù)據(jù)庫(kù)中的一組對(duì)象，找出其共同屬性，構(gòu)造分類(lèi)模型，然后利用分類(lèi)模型對(duì)其它的數(shù)據(jù)對(duì)象進(jìn)行分類(lèi)。要構(gòu)造分類(lèi)模型，需要一個(gè)訓(xùn)練樣本數(shù)據(jù)集作為輸入，訓(xùn)練集由一組數(shù)據(jù)庫(kù)記錄或元組組成，每個(gè)元組包含一些字段值，又稱(chēng)“屬性”或“特征”，這些字段和測(cè)試集中記錄的字段相同，另外，每個(gè)訓(xùn)練樣本記錄有一個(gè)類(lèi)別標(biāo)識(shí)。分類(lèi)目標(biāo)是分析訓(xùn)練集中的數(shù)據(jù)，利用數(shù)據(jù)中能得到的特征，為每一類(lèi)建立一個(gè)恰當(dāng)?shù)拿枋龌蚰Ｐ?，然后根?jù)這些分類(lèi)描述對(duì)測(cè)試數(shù)據(jù)進(jìn)行分類(lèi)或產(chǎn)

35、生更恰當(dāng)?shù)拿枋?。我們可以舉一個(gè)簡(jiǎn)單的例子，信用卡公司的數(shù)據(jù)庫(kù)中保存著各持卡人的記錄，公司根據(jù)信譽(yù)程度將持卡人記錄分成三類(lèi):良好、一般、較差，并且類(lèi)別標(biāo)記己賦給了各個(gè)記錄。分類(lèi)分析就是分析該數(shù)據(jù)庫(kù)的記錄數(shù)據(jù)，對(duì)每個(gè)信譽(yù)等級(jí)做出準(zhǔn)確描述，如“信譽(yù)良好的客戶(hù)是指那些年收入在5萬(wàn)元以上，年齡在40-50歲之間的人士”，然后根據(jù)這些描述對(duì)其它具有相同屬性的數(shù)據(jù)庫(kù)記錄進(jìn)行分類(lèi)。</p><p>　　在分類(lèi)分析中，分類(lèi)模型的構(gòu)

36、造方法有統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)方法及機(jī)器學(xué)習(xí)方法等。統(tǒng)計(jì)方法包括貝葉斯法和非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí))，對(duì)應(yīng)的知識(shí)表示為判別函數(shù)和原型事例。神經(jīng)網(wǎng)絡(luò)方法主要是多層前向神經(jīng)網(wǎng)絡(luò)的誤差反向傳播(error back propagation，BP)算法，用模型表示是前向反饋神經(jīng)網(wǎng)絡(luò)模型，該算法實(shí)質(zhì)是一種非線(xiàn)性的判別函數(shù)。機(jī)器學(xué)習(xí)方法包括決策樹(shù)法和規(guī)則歸納法，前者對(duì)應(yīng)的表示是決策樹(shù)或判別樹(shù)，后者則一般為產(chǎn)生式規(guī)則。另外，近年來(lái)又出現(xiàn)了一種稱(chēng)

37、為粗糙集(Rough set)新的理論方法，它將知識(shí)表示為產(chǎn)生式規(guī)則。</p><p>　　在解決實(shí)際問(wèn)題時(shí)，經(jīng)常要同時(shí)使用多種模式。分類(lèi)模式和回歸模式是使用最普遍的模式。分類(lèi)模式、回歸模式、時(shí)間序列模式也被認(rèn)為是受監(jiān)督知識(shí)，因?yàn)樵诮⒛Ｊ角皵?shù)據(jù)的結(jié)果是已知的，可以直接用來(lái)檢測(cè)模式的準(zhǔn)確性，模式的產(chǎn)生是在受監(jiān)督的情況下進(jìn)行的。一般在建立這些模式時(shí)，使用一部分?jǐn)?shù)據(jù)作為樣本，用另一部分?jǐn)?shù)據(jù)來(lái)檢驗(yàn)、校正模式。</

38、p><p>　　1.1.4 數(shù)據(jù)挖掘系統(tǒng)的發(fā)展</p><p>　　根據(jù) R.Grossman 的觀點(diǎn)，數(shù)據(jù)挖掘的發(fā)展過(guò)程可分為如下所介紹的一到四代[5]:</p><p>　　第一代:第一代的數(shù)據(jù)挖掘系統(tǒng)僅支持一個(gè)或少數(shù)幾個(gè)數(shù)據(jù)挖掘算法，這些算法只能夠挖掘向量數(shù)據(jù)。如果數(shù)據(jù)足夠大，并且頻繁的變化，這就需要利用數(shù)據(jù)庫(kù)或者數(shù)據(jù)倉(cāng)庫(kù)技術(shù)進(jìn)行管理，第一代系統(tǒng)顯然不能滿(mǎn)足需求。

39、</p><p>　　第二代:第二代系統(tǒng)的主要特點(diǎn)是支持與數(shù)據(jù)庫(kù)和數(shù)據(jù)倉(cāng)庫(kù)的高性能接口，并有高的可測(cè)量性和功能性。第二代系統(tǒng)提供了數(shù)據(jù)挖掘模式和數(shù)據(jù)挖掘查詢(xún)語(yǔ)言，從而具有更高的靈活性。然而第二代系統(tǒng)只注重模型的生成，如何和預(yù)言模型系統(tǒng)集成的問(wèn)題導(dǎo)致了第三代數(shù)據(jù)挖掘系統(tǒng)的開(kāi)發(fā)。</p><p>　　第三代:第三代數(shù)據(jù)挖掘系統(tǒng)可挖掘 intranets和 extranets上的分布的和高度異質(zhì)

40、的數(shù)據(jù)，并能有效的和操作系統(tǒng)結(jié)合。這一代數(shù)據(jù)挖掘系統(tǒng)的關(guān)鍵技術(shù)之一是提高對(duì)建立在異質(zhì)系統(tǒng)上的多個(gè)預(yù)言模型以及管理這些預(yù)言模型的元數(shù)據(jù)提供第一級(jí)別的支持。</p><p>　　第四代:第四代數(shù)據(jù)挖掘系統(tǒng)可以挖掘嵌入式、移動(dòng)式以及一般性的計(jì)算設(shè)備所產(chǎn)生的各種數(shù)據(jù)。</p><p>　　1.1.5 數(shù)據(jù)挖掘的應(yīng)用與面臨的挑戰(zhàn)</p><p>　　盡管數(shù)據(jù)挖掘是一個(gè)新興的研

41、究領(lǐng)域，但是卻得到了穩(wěn)定的發(fā)展，每年市場(chǎng)上都會(huì)出現(xiàn)新的數(shù)據(jù)挖掘系統(tǒng)，各大數(shù)據(jù)庫(kù)軟件公司也分別推出了自己的數(shù)據(jù)挖掘產(chǎn)品。數(shù)據(jù)挖掘廣泛應(yīng)用于科學(xué)研究、商業(yè)應(yīng)用、以及Web挖掘等很多領(lǐng)域。</p><p><b>　?。?）科學(xué)研究</b></p><p>　　數(shù)據(jù)挖掘在天文學(xué)上有一個(gè)著名的應(yīng)用系統(tǒng):SKICAT[27](Sky Image Cataloging and A

42、nalysis Tool)。它是加州理工學(xué)院噴氣推進(jìn)實(shí)驗(yàn)室與天文學(xué)家合作開(kāi)發(fā)的用于幫助天文學(xué)家發(fā)現(xiàn)遙遠(yuǎn)的類(lèi)星體的一個(gè)工具。SKICAT的任務(wù)是構(gòu)造星體分類(lèi)器對(duì)星體進(jìn)行分類(lèi)，使用了決策樹(shù)方法構(gòu)造分類(lèi)器，結(jié)果使得能分辨的星體較以前的方法在亮度上要低一個(gè)數(shù)量級(jí)之多，而且新的方法比以往的方法要在效率上要高40倍以上。數(shù)據(jù)挖掘在生物學(xué)上的應(yīng)用主要集中于分子生物學(xué)特別是基因工程的研究上。進(jìn)幾年，通過(guò)用計(jì)算生物分子系統(tǒng)分析法，尤其是基因數(shù)據(jù)庫(kù)搜索技術(shù)

43、以在基因研究上做出了很多重大發(fā)現(xiàn)，數(shù)據(jù)挖掘在分子生物學(xué)上的工作可分為兩種:一是從各種生物體的DNA序列中定位出具有某種功能的基因串;二是在基因數(shù)據(jù)庫(kù)中搜索與某種具有高階結(jié)構(gòu)(不是簡(jiǎn)單的線(xiàn)形結(jié)構(gòu))或功能的蛋白質(zhì)相似的高階結(jié)構(gòu)序列。</p><p><b>　　（2）商業(yè)應(yīng)用</b></p><p>　　數(shù)據(jù)挖掘技術(shù)以及應(yīng)用此技術(shù)所獲得知識(shí)和信息可以被廣泛的應(yīng)用于信息管理

44、、商務(wù)管理、過(guò)程控制、市場(chǎng)分析、工程設(shè)計(jì)和科學(xué)研究等眾多領(lǐng)域，這些領(lǐng)域的管理決策層可以通過(guò)對(duì)歷史數(shù)據(jù)的分析，發(fā)現(xiàn)諸如市場(chǎng)供需規(guī)律、商品價(jià)格走勢(shì)、家庭收入與消費(fèi)特點(diǎn)、購(gòu)買(mǎi)商品的習(xí)慣等規(guī)律，以支持企業(yè)的生產(chǎn)、經(jīng)營(yíng)和銷(xiāo)售決策。</p><p>　?。?）web挖掘(Web Mining)</p><p>　　隨著網(wǎng)絡(luò)的迅速發(fā)展，今天它己經(jīng)成為人們交流思想，獲取信息的便利手段。但這些信息缺乏結(jié)構(gòu)化

45、、組織的規(guī)律性、隨意的散布在網(wǎng)絡(luò)的各個(gè)角落，這已經(jīng)成為這座世界性圖書(shū)館的一大缺憾。數(shù)據(jù)挖掘在因特網(wǎng)上的應(yīng)用主要包括三種:在搜索引擎上(Search Engine)對(duì)文檔進(jìn)行自動(dòng)分類(lèi)、幫助用戶(hù)尋找感興趣的新聞以及利用數(shù)據(jù)挖掘設(shè)計(jì)一個(gè)電子新聞過(guò)濾系統(tǒng)。它利用文本學(xué)習(xí)建立起該用戶(hù)的趣向模型，當(dāng)用戶(hù)進(jìn)入一份電子報(bào)紙的網(wǎng)頁(yè)時(shí)，該系統(tǒng)就會(huì)根據(jù)學(xué)習(xí)所得的模型對(duì)其中的每一篇文章按與用戶(hù)的興趣的接近程度進(jìn)行打分排序，以便使用戶(hù)看到他最感興趣的新聞。<

46、;/p><p>　　這些實(shí)踐將數(shù)據(jù)挖掘和各特定領(lǐng)域知識(shí)結(jié)合起來(lái)，滿(mǎn)足了特定任務(wù)的需要，也取得了一些很大的成績(jī)。數(shù)據(jù)挖掘任務(wù)和方法的多樣性給數(shù)據(jù)挖掘提出了許多挑戰(zhàn)性的課題。在未來(lái)的課題研究中，數(shù)據(jù)挖掘研究人員、系統(tǒng)和應(yīng)用開(kāi)發(fā)人員所面臨的主要問(wèn)題[6]有:</p><p>　　（1）挖掘算法的效率和可擴(kuò)展性</p><p>　　目前，GB數(shù)量級(jí)的數(shù)據(jù)庫(kù)已經(jīng)不鮮見(jiàn)，TB數(shù)量級(jí)

47、的數(shù)據(jù)庫(kù)也開(kāi)始出現(xiàn)。海量數(shù)據(jù)庫(kù)中存有成百個(gè)屬性和表，成百萬(wàn)個(gè)元組，問(wèn)題的維數(shù)很大，這不但增大了知識(shí)發(fā)現(xiàn)算法的搜索空間，也增加了盲目發(fā)現(xiàn)的可能性。因此，必須通過(guò)增加知識(shí)發(fā)現(xiàn)過(guò)程中系統(tǒng)和用戶(hù)的交互，既充分利用領(lǐng)域知識(shí)除去無(wú)關(guān)數(shù)據(jù)，降低問(wèn)題維數(shù)，對(duì)待挖掘數(shù)據(jù)進(jìn)行有效的預(yù)處理，又要利用領(lǐng)域知識(shí)進(jìn)一步精練所發(fā)現(xiàn)的模式，濾除因搜索空間過(guò)大可能獲得的無(wú)用信息，從而設(shè)計(jì)出更理想的知識(shí)發(fā)現(xiàn)算法。</p><p>　?。?）待挖掘數(shù)

48、據(jù)的時(shí)序性</p><p>　　在應(yīng)用領(lǐng)域的數(shù)據(jù)庫(kù)中，數(shù)據(jù)大多是隨時(shí)間變化的，這可能使得原先發(fā)現(xiàn)的知識(shí)失去效用，也為開(kāi)發(fā)強(qiáng)有力的知識(shí)發(fā)現(xiàn)系統(tǒng)提供了潛在的舞臺(tái)，因?yàn)橹匦掠?xùn)練一個(gè)系統(tǒng)畢竟要比重新訓(xùn)練一個(gè)人(改變他的思維、觀點(diǎn)等)容易得多。我們可以來(lái)用隨時(shí)間逐步修正所發(fā)現(xiàn)的模式來(lái)指導(dǎo)新的發(fā)現(xiàn)過(guò)程?；ヂ?lián)網(wǎng)絡(luò)上的知識(shí)發(fā)現(xiàn)正日益普及，在這信息的海洋中可以發(fā)現(xiàn)大量的新知識(shí)。己有一些資源發(fā)現(xiàn)工具可用來(lái)發(fā)現(xiàn)含有關(guān)鍵字的文本。目前的

49、問(wèn)題是，如何從復(fù)雜的數(shù)據(jù)例如多媒體結(jié)構(gòu)化的數(shù)據(jù)中提取有用的信息，對(duì)多層次數(shù)據(jù)庫(kù)的維護(hù)，以及如何處理數(shù)據(jù)的異類(lèi)性和自主性等等。</p><p>　?。?）和其它系統(tǒng)的集成</p><p>　　一個(gè)方法、功能單一的發(fā)現(xiàn)系統(tǒng)，其適用范圍必然受到限制。要在更廣闊的領(lǐng)域發(fā)現(xiàn)知識(shí)，知識(shí)發(fā)現(xiàn)系統(tǒng)就應(yīng)該是數(shù)據(jù)庫(kù)、知識(shí)庫(kù)、專(zhuān)家系統(tǒng)、決策支持系統(tǒng)、可觀化工具、網(wǎng)絡(luò)等多項(xiàng)技術(shù)集成的系統(tǒng)。</p>

50、<p>　?。?）遺漏的噪聲數(shù)掘</p><p>　　這個(gè)問(wèn)題在商業(yè)數(shù)據(jù)庫(kù)中尤其突出，據(jù)報(bào)告，美國(guó)人口調(diào)查數(shù)據(jù)的錯(cuò)誤率上升到20%。如果不經(jīng)認(rèn)真考慮就來(lái)設(shè)計(jì)待挖掘數(shù)據(jù)庫(kù)，重要的屬性可能會(huì)被遺漏掉。用更復(fù)雜的統(tǒng)計(jì)策略識(shí)別隱藏的變量和相關(guān)性成為必然。</p><p>　?。?）挖掘結(jié)果的可理解性</p><p>　　這是評(píng)估挖掘系統(tǒng)的一個(gè)重要環(huán)節(jié)。我們應(yīng)該盡可

51、能采用圖形表示、有向非循環(huán)圖結(jié)構(gòu)的規(guī)則、自然語(yǔ)言生成以及數(shù)據(jù)和知識(shí)的可視化等技術(shù)，提高挖掘結(jié)果的可理解性。</p><p>　　（6）私有數(shù)據(jù)的保護(hù)與數(shù)據(jù)安全性</p><p>　　當(dāng)我們可以在不同的角度和不同的層次看到數(shù)據(jù)庫(kù)中的數(shù)據(jù)時(shí)，這與我們保護(hù)數(shù)據(jù)的安全性和保護(hù)私人數(shù)據(jù)的目標(biāo)相抵觸。因此對(duì)在什么情況下數(shù)據(jù)挖掘?qū)?huì)導(dǎo)致對(duì)私有數(shù)據(jù)造成侵犯和采用何種措施來(lái)防止敏感信息泄露的研究變得非常重要

52、。</p><p>　　1.2 決策樹(shù)分類(lèi)算法及其研究現(xiàn)狀</p><p>　　分類(lèi)技術(shù)是數(shù)據(jù)挖掘的重要分支，它能夠?qū)Ω鱾€(gè)行業(yè)提供良好的決策支持，對(duì)整個(gè)社會(huì)的發(fā)展產(chǎn)生重要而深遠(yuǎn)的影響。數(shù)據(jù)挖掘的分類(lèi)模式是一種有指導(dǎo)性的學(xué)習(xí)，即是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)算法，通過(guò)分析由屬性描述的訓(xùn)練數(shù)據(jù)集來(lái)構(gòu)造模型由此來(lái)預(yù)測(cè)新元組的分類(lèi)標(biāo)記。數(shù)據(jù)分類(lèi)存在很多方法，如判定樹(shù)歸納、貝葉斯分類(lèi)、神經(jīng)網(wǎng)絡(luò)以及 K-最

53、臨近分類(lèi)、遺傳算法和粗糙集等。其中決策樹(shù)歸納以其易于提取顯式規(guī)則、計(jì)算量相對(duì)較小、可以顯示重要的決策屬性和較高的分類(lèi)準(zhǔn)確率等優(yōu)點(diǎn)而得到廣泛的應(yīng)用。據(jù)統(tǒng)計(jì)，目前決策樹(shù)算法是利用最廣泛的數(shù)據(jù)挖掘算法之一，利用率高達(dá) 19%。應(yīng)用領(lǐng)域已由醫(yī)療到博弈論和商務(wù)等領(lǐng)域，是一些商業(yè)規(guī)則歸納系統(tǒng)的基礎(chǔ)。在計(jì)算機(jī)科學(xué)中采用樹(shù)形結(jié)構(gòu)描述數(shù)據(jù)集已有不短的時(shí)間了，但它一直是一個(gè)不受重視的知識(shí)發(fā)現(xiàn)過(guò)程。隨著數(shù)據(jù)挖掘技術(shù)的產(chǎn)生，決策樹(shù)得到了很快的發(fā)展。</p

54、><p>　　決策樹(shù)的算法己有很多。1986 年 J.Ross Quinlan 引入了 ID3 算法后，引起了很大的反響[7]。在此基礎(chǔ)上，他又于 1993 年，在其“Program For Machine Learning”一書(shū)中，對(duì) ID3 算法進(jìn)行了補(bǔ)充和改進(jìn)，提出了后來(lái)非常流行的 C4.5算法。在大數(shù)據(jù)量情況下的效率和生成規(guī)則的數(shù)量與正確性方面有了顯著的提高。此外，CHAID 算法也有相當(dāng)廣泛的應(yīng)用。1996

55、 年又提出了 SLIQ和SPRINT算法,RAINFOREST 框架結(jié)構(gòu)，它們強(qiáng)調(diào)算法的可伸縮性。由于數(shù)據(jù)挖掘的對(duì)象是規(guī)模龐大的數(shù)據(jù)，已有的分類(lèi)算法在數(shù)據(jù)量小時(shí)能夠準(zhǔn)確、高效的分類(lèi)，效果很好。但當(dāng)用于處理大量數(shù)據(jù)時(shí)，已有的算法都會(huì)不同程度的出現(xiàn)各種問(wèn)題，分類(lèi)效果不理想。因此，研究數(shù)據(jù)挖掘中準(zhǔn)確、有效的分類(lèi)算法，雖然是一個(gè)傳統(tǒng)的問(wèn)題，但仍具有挑戰(zhàn)性。目前，在知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘的研究和開(kāi)發(fā)中已經(jīng)取得了一些令人矚目的成績(jī)，對(duì)關(guān)聯(lián)規(guī)則、聚類(lèi)等基

56、本算法的研究已經(jīng)基本日趨成熟， 人們的研究重點(diǎn)逐漸轉(zhuǎn)移到數(shù)據(jù)挖掘技術(shù)在新的數(shù)據(jù)類(lèi)型、應(yīng)用環(huán)境中使用時(shí)所出現(xiàn)的新問(wèn)題的解決上。例如：</p><p>　　1．決策樹(shù)技術(shù)和神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合。決策樹(shù)也具有產(chǎn)生n 維空間下任意復(fù)雜的決策邊界的功能。因此, 可以將決策樹(shù)重新構(gòu)造成一個(gè)多層的神經(jīng)網(wǎng)絡(luò)。這類(lèi)方法解決了由神經(jīng)網(wǎng)絡(luò)得到的知識(shí)難于被人們理解的缺點(diǎn)。</p><p>　　2．決策樹(shù)技術(shù)和模糊集

57、合原理的結(jié)合。決策樹(shù)技術(shù)雖然有許多優(yōu)點(diǎn),但也存在著不穩(wěn)定的缺點(diǎn),即決策樹(shù)帶來(lái)了較大的變動(dòng)。模糊集合的融通性使人們利用模糊邏輯來(lái)解決決策樹(shù)的這一缺點(diǎn)并取得了不錯(cuò)的效果。</p><p>　　3．決策樹(shù)技術(shù)和進(jìn)化算法,遺傳算法及遺傳編程的結(jié)合。基于進(jìn)化算法的決策樹(shù)系統(tǒng)具有較好的抗噪聲能力, 同時(shí)進(jìn)化算法很容易在并行計(jì)算機(jī)上運(yùn)行, 因此可以期待基于進(jìn)化算法的決策樹(shù)的運(yùn)算能力有較大的提高。</p><

58、p>　　4．決策樹(shù)技術(shù)和多智能體的結(jié)合。多智能體系統(tǒng)的復(fù)雜性，而機(jī)器學(xué)習(xí)有潛力提供一個(gè)魯棒性較強(qiáng)的機(jī)制來(lái)有效協(xié)調(diào)各智能體間的行為，因此對(duì)多智能體結(jié)合機(jī)器學(xué)習(xí)是一個(gè)很有前途的方向。</p><p>　　5．尋找新的構(gòu)造決策樹(shù)的方法。自從Quinlan提出ID3 和C4.5方法后，有不少專(zhuān)家提出了其他構(gòu)造決策樹(shù)的方法，M. Amherst 等提出了基于多維可視化下的交互式的決策樹(shù)構(gòu)造，此方法在決策樹(shù)構(gòu)造階段加入

59、了專(zhuān)家知識(shí)，這樣便于用戶(hù)更深地理解產(chǎn)生決策樹(shù)的數(shù)據(jù)及最終產(chǎn)生的決策樹(shù)，同時(shí)也顯著地減小了決策樹(shù)的大小。</p><p>　　6．尋找更好的簡(jiǎn)化決策樹(shù)的方法。尋找更好的簡(jiǎn)化決策樹(shù)的方法, 這一直是決策樹(shù)技術(shù)研究的一個(gè)熱點(diǎn)。D. Fournier 等提出的一種新的修剪決策樹(shù)的方法2DI 修剪法。此方法針對(duì)數(shù)據(jù)不確定的情況, 利用特性索（Quality Index) 來(lái)權(quán)衡處理決策樹(shù)深度和節(jié)點(diǎn)雜質(zhì)。2DI修剪法將保持那

60、些雖不能減小錯(cuò)誤率但能指出一些特殊性質(zhì)的群體的子樹(shù)。</p><p>　　7．研究產(chǎn)生決策樹(shù)的訓(xùn)練和檢驗(yàn)數(shù)據(jù)的大小及特性與決策樹(shù)特性之間的關(guān)系。實(shí)際上, 這就是經(jīng)常提起的數(shù)據(jù)預(yù)處理技術(shù)(Data reprocessing) ,與決策樹(shù)修剪技術(shù)(Pruning) [7] 相對(duì)應(yīng), 也稱(chēng)它為數(shù)據(jù)減少技術(shù)(Data Reduction Techniques) 。</p><p>　　8．決策樹(shù)技

61、術(shù)的軟件實(shí)現(xiàn)。將決策樹(shù)技術(shù)軟件化一直是決策樹(shù)技術(shù)的方向之一。目前市場(chǎng)上的大多數(shù)據(jù)挖掘軟件如SAS 等都包含有決策樹(shù)技術(shù)部分。</p><p>　　以上這些決策樹(shù)的研究并不是孤立的, 它們經(jīng)常相互聯(lián)系、相互結(jié)合。決策樹(shù)技術(shù)早已被證明是利用計(jì)算機(jī)模仿人類(lèi)決策的有效方法。由于20 世紀(jì)末人工智能陷于低潮, 此技術(shù)曾不被重視。值得慶幸的是, 由于數(shù)據(jù)挖掘技術(shù)的興起, 作為模仿人類(lèi)決策主要方法之一, 近年來(lái)決策樹(shù)又重新引起

62、了人們的興趣, 并得到更廣泛的應(yīng)用。將決策樹(shù)技術(shù)與其他新興的技術(shù)相結(jié)合,決策樹(shù)技術(shù)將煥發(fā)出新的生命力。</p><p>　　1.3數(shù)據(jù)挖掘分類(lèi)算法的研究意義</p><p>　　目前分類(lèi)挖掘在實(shí)際應(yīng)用中有著很重要的應(yīng)用價(jià)值，在很多行業(yè)領(lǐng)域都取得一定的成功。比如:在股票市場(chǎng)上對(duì)每只股票的歷史數(shù)據(jù)進(jìn)行分析，通過(guò)相應(yīng)的技術(shù)進(jìn)行預(yù)測(cè)，從而做出相對(duì)比較準(zhǔn)確的判斷;彩票的購(gòu)買(mǎi)也可以利用數(shù)據(jù)挖掘的分類(lèi)或

63、預(yù)測(cè)技術(shù)進(jìn)行分析;在金融領(lǐng)域中將貸款對(duì)象分為低貸款風(fēng)險(xiǎn)與高貸款風(fēng)險(xiǎn)兩類(lèi)。通過(guò)決策樹(shù)，我們可以很容易地確定貸款申請(qǐng)者是屬于高風(fēng)險(xiǎn)的還是低風(fēng)險(xiǎn)的。對(duì)于一個(gè)計(jì)算機(jī)銷(xiāo)售的系統(tǒng)，原有的數(shù)據(jù)庫(kù)信息已定，假定新的顧客添加到數(shù)據(jù)庫(kù)中，你想將新計(jì)算機(jī)的銷(xiāo)售信息通知顧客。將促銷(xiāo)材料分發(fā)給數(shù)據(jù)庫(kù)所有的顧客的費(fèi)用可能很高，這時(shí)你就可以通過(guò)建立分類(lèi)模型，把資料只寄給那些可能購(gòu)買(mǎi)新計(jì)算機(jī)的用戶(hù)，從而節(jié)省時(shí)間和費(fèi)用，為你帶來(lái)更大的經(jīng)濟(jì)效益。由于決策樹(shù)方法在分類(lèi)挖掘技

64、術(shù)中有著獨(dú)特的優(yōu)勢(shì)，而分類(lèi)技術(shù)的應(yīng)用對(duì)整個(gè)市場(chǎng)的控制、公司的運(yùn)營(yíng)和個(gè)人的投資都有著很好的控制作用。數(shù)據(jù)挖掘是一種決策支持過(guò)程，是深層次的數(shù)據(jù)信息分析方法，將數(shù)據(jù)挖掘技術(shù)應(yīng)用于成績(jī)?cè)u(píng)估方面是非常有益的，它可以全面地分析考試成績(jī)與各種因素之間隱藏的內(nèi)在聯(lián)系，比如，經(jīng)過(guò)對(duì)學(xué)生相關(guān)數(shù)據(jù)進(jìn)行分析，數(shù)據(jù)挖掘工具可以回答諸如“哪些因素對(duì)學(xué)生成績(jī)可能有影響”等</p><p>　　1.4本文的主要內(nèi)容</p>&l

65、t;p>　　第一章首先闡述了論文課題的研究背景、國(guó)內(nèi)外在數(shù)據(jù)挖掘領(lǐng)域的研究現(xiàn)狀以及論文的組織結(jié)構(gòu)。</p><p>　　第二章是本文的重點(diǎn)之一，詳細(xì)的闡述了決策樹(shù)分類(lèi)模型的基本原理、工作的過(guò)程，并講述了它的核心算法——ID3算法的基本思想。在本章的最后介紹了ID3算法演變和改進(jìn)來(lái)的其他幾種算法，并對(duì)它們進(jìn)行了比較，做出概況性描述。</p><p>　　第三章也是本文的研究重點(diǎn)之一，因

66、為ID3算法是經(jīng)典的數(shù)據(jù)處理算法，本文主要研究ID3算法，給出了ID3算法的詳細(xì)描述和它的評(píng)價(jià)。分析用ID3實(shí)現(xiàn)的決策樹(shù)，以及分類(lèi)規(guī)則的提取。</p><p>　　第四章，用程序?qū)崿F(xiàn)ID3算法、對(duì)它的結(jié)果進(jìn)行分析，實(shí)驗(yàn)結(jié)果證明，ID3算法是一種經(jīng)典的數(shù)據(jù)處理算法，運(yùn)用它能夠解決生活中很多數(shù)據(jù)問(wèn)題。 </p><p>　　第五章對(duì)全文進(jìn)行總結(jié)，提出了進(jìn)一步的研究方向。ID3算法還有一定的需要

67、改進(jìn)的地方，在以后的研究中將進(jìn)行進(jìn)一步的改進(jìn)。</p><p>　　第二章 決策樹(shù)分類(lèi)算法相關(guān)知識(shí)</p><p>　　決策樹(shù)方法是目前應(yīng)用最廣泛的歸納推理算法之一，是一種逼近離散值的方法，也可以把它看作是一個(gè)布爾函數(shù)。它是以實(shí)例為基礎(chǔ)的歸納學(xué)習(xí)，通常用來(lái)形成分類(lèi)器和預(yù)測(cè)模型，著眼于從一組無(wú)次序、無(wú)規(guī)則的事例理出決策樹(shù)表示形成的分類(lèi)規(guī)則。到目前為止決策樹(shù)有很多實(shí)現(xiàn)算法。</p>

68、<p>　　2.1決策樹(shù)方法介紹</p><p>　　在解決分類(lèi)問(wèn)題的各種方法中，決策樹(shù)[8] (Decision Tree，DT)是比較常用的一種方法，它是一種用于分類(lèi)、聚類(lèi)和預(yù)測(cè)的預(yù)測(cè)型建模方法，采用“分而治之”的方法將問(wèn)題的搜索空間分為若干子集。應(yīng)用這種方法需要構(gòu)建一棵樹(shù)對(duì)分類(lèi)過(guò)程進(jìn)行建模。一旦建好了樹(shù)，就可以將其應(yīng)用于數(shù)據(jù)集中的元組并得到分類(lèi)結(jié)果。在決策樹(shù)方法中，有兩個(gè)基本步驟:構(gòu)建樹(shù)和將樹(shù)

69、應(yīng)用于數(shù)據(jù)集，一般都集中在如何有效的構(gòu)建樹(shù)的研究上。</p><p>　　2.1.1決策樹(shù)的結(jié)構(gòu)</p><p>　　一棵決策樹(shù)是這樣一棵樹(shù)，該樹(shù)的每個(gè)非終端點(diǎn)均表示被考察數(shù)據(jù)項(xiàng)目的一個(gè)測(cè)試或決策。根據(jù)測(cè)試結(jié)果，選擇某個(gè)分支。為了分類(lèi)一個(gè)特定數(shù)據(jù)項(xiàng)目，我們從根結(jié)點(diǎn)開(kāi)始，一直向下判定，直到到達(dá)一個(gè)終端結(jié)點(diǎn)(或葉子)為止。當(dāng)?shù)竭_(dá)一個(gè)終端結(jié)點(diǎn)時(shí)，一個(gè)決策樹(shù)便形成了。</p><

70、;p>　　決策樹(shù)是運(yùn)用于分類(lèi)的一種類(lèi)似于流程圖的樹(shù)結(jié)構(gòu)[9]。其中的每個(gè)內(nèi)部節(jié)點(diǎn)(internal node)代表對(duì)某個(gè)屬性的一次測(cè)試，一條邊代表一個(gè)測(cè)試結(jié)果，葉子(leaf)代表某個(gè)類(lèi)(class)或者類(lèi)的分布(class distribution)。最上面的節(jié)點(diǎn)是根結(jié)點(diǎn)。下圖給出一個(gè)商業(yè)上運(yùn)用決策樹(shù)算法得到的一棵決策樹(shù)，如圖2.1所示： </p><p>　　圖2.1 Decisio

71、n Tree demo</p><p>　　這棵決策樹(shù)對(duì)“買(mǎi)計(jì)算機(jī)’，的銷(xiāo)售記錄進(jìn)行分類(lèi)。它表示了一個(gè)關(guān)心電子產(chǎn)品的用戶(hù)是否會(huì)購(gòu)買(mǎi)PC機(jī)的知識(shí)，用它可以預(yù)測(cè)某條記錄(某個(gè)人)的購(gòu)買(mǎi)意向。每個(gè)內(nèi)部節(jié)點(diǎn)(方形框)代表對(duì)某個(gè)屬性的一次檢測(cè)。每片葉子(橢圓框)代表一個(gè)類(lèi)(buys-computers=yes或者buys--computers=no)。這個(gè)例子中，樣本向量如下:(age，student，credit--ra

72、ting: buys-computers)，被決策數(shù)據(jù)的格式為(age，student，credit--rating)。輸入新的被決策的記錄，可以預(yù)測(cè)該記錄隸屬于哪個(gè)類(lèi)。</p><p>　　2.1.2決策樹(shù)的基本原理</p><p>　　決策樹(shù)的實(shí)現(xiàn)是以信息論原理為基礎(chǔ)的。信息論是香農(nóng)(C.E.Shannon)在1948年建立的解決信息傳遞的不確定性的一系列理論，以數(shù)學(xué)的方法度量并研究信

73、息。通過(guò)通信后對(duì)信源中各種符號(hào)出現(xiàn)的不確定程度的消除來(lái)度量信息量的大小，在這些理論中他提出了一系列概念：</p><p>　?。?）自信息量。設(shè)X1，X2，…，Xn，為信源發(fā)出的信號(hào)，在收到Xi之前，收信者對(duì)信源發(fā)出信號(hào)的不確定性定義為信息符號(hào)的自信息量I(Xi)，即 (2.1)</p><p>　　其

74、中P(Xi)表示信源發(fā)出Xi的概率。</p><p>　?。?）信息熵。自信息量只能反映符號(hào)的不確定性，而信息熵可以用來(lái)度量整個(gè)信源X整體的不確定性，定義如下:</p><p><b>　　(2.2)</b></p><p>　　其中i為信源X所有可能的符號(hào)數(shù)，即用信源每發(fā)一個(gè)符號(hào)所提供的平均自信息量來(lái)定義信息熵(平均信息量)。</p&g

75、t;<p>　?。?）條件熵。如果信源X與隨機(jī)變量Y不是相互獨(dú)立的，收信者收到信息Y，那么用條件熵H(X/Y)來(lái)度量收信者在收到隨機(jī)變量Y之后，對(duì)隨機(jī)變量x仍然存在的不確定性。設(shè)X對(duì)應(yīng)信源符號(hào)Xi，Y對(duì)應(yīng)信源符號(hào)Yj，P(Xi/Yj)為當(dāng)Y為Yj時(shí),X為Xi的概率，則有:</p><p><b>　　(2.3)</b></p><p>　　（4）平均互信

76、息量。用它來(lái)表示信號(hào)Y所能提供的關(guān)于X的信息量的大小，可用下式表示:</p><p>　　I(X，Y)=H(X)-H(X/Y) (2.4)</p><p>　　在信息論中是用熵 (系統(tǒng)信息量的加權(quán)平均)（Entropy)來(lái)度量信息的不確定性。不確定性是一組消息的描述如M={m1，m2，…mn}。所有消息的產(chǎn)生是相互獨(dú)立的，消息集合中每個(gè)

77、消息mi被接受的概率為P(mi)，它包含著一定的信息量，定義為I(mi)=-㏒2( mi)。例如:某個(gè)信息源總是發(fā)送同樣的信息，那么接收者就不需要更多的信息，此時(shí)信息源的熵就為0，也就是沒(méi)有任何不確定性。相反，如果某個(gè)信息發(fā)送了n個(gè)不同的信息并且每個(gè)信息是相互獨(dú)立的，此時(shí)熵的值就是㏒2n（熵是以二進(jìn)制位的個(gè)數(shù)來(lái)編碼長(zhǎng)度的，故用以2為底的對(duì)數(shù)，后面描述的對(duì)數(shù)都是以2為底)。熵用在決策樹(shù)中是作為訓(xùn)練集純度的標(biāo)準(zhǔn)。在決策樹(shù)形成過(guò)程中，最重要的

78、部分是對(duì)分裂屬性的選擇。</p><p>　　比較常用的一種方法是計(jì)算信息增益[10] (Information Gain)。信息增益的原理來(lái)自信息論，它是使某個(gè)屬性用來(lái)分割訓(xùn)練集而導(dǎo)致的期望熵降低。因此，信息增益越大的屬性分裂數(shù)據(jù)集的可能性越大。決策樹(shù)的形成就是遞歸的對(duì)數(shù)據(jù)集中的每個(gè)節(jié)點(diǎn)進(jìn)行分裂，直到節(jié)點(diǎn)的所有類(lèi)別都屬于同一類(lèi)或沒(méi)有多余的屬性來(lái)劃分訓(xùn)練樣本集。</p><p>　　按照信

79、息論的定義，設(shè)S是s個(gè)數(shù)據(jù)樣本的集合，類(lèi)標(biāo)號(hào)屬性有n類(lèi)樣本的訓(xùn)練數(shù)據(jù)集，每類(lèi)有Si個(gè)實(shí)例，則把它們分類(lèi)所需要的信息量I用如下公式2.5表示為:</p><p><b>　　(2.5)</b></p><p>　　Pi是任意樣本屬于類(lèi)Ci的概率，用Si/S估計(jì)。</p><p>　　設(shè)屬性A具有v個(gè)不同的值{ a1, a2,。。。av }。可以用

80、屬性A將S劃分為v個(gè)子集{S1, S2,。。。Sv }:其中，Sj包含S中這樣的一些樣本，它們?cè)贏上具有值aj。假設(shè)選取A作為本次分類(lèi)的屬性，則這些子集對(duì)應(yīng)于由包含集合S的節(jié)點(diǎn)生長(zhǎng)出來(lái)的分枝。設(shè)sij是子集Sj中類(lèi)Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵(entropy)由公式得出:</p><p>　　(2.6) </p><p>　　其中項(xiàng)為第j個(gè)子集的權(quán)值，并等于子集

81、（即A為aj)中的樣本個(gè)數(shù)除以S中的樣本總數(shù)。由信息論定義知:熵值越小，子集劃分的純度越高。因此對(duì)應(yīng)給定的子集Sj有：</p><p>　　(2.7) </p><p>　　其中：是Sj中的樣本屬于Ci的概率。</p><p>　　在A上的分支將獲得的編碼信息即節(jié)點(diǎn)的信息增益為：</p><p>　　(2.8)

82、 </p><p>　　也就是說(shuō)，Gain(A)是由于知道屬性A的值而導(dǎo)致的熵的期望壓縮。為了使下一步所需的信息量最小，要求每一次都選擇其信息增益最大的屬性作為決策樹(shù)的新結(jié)點(diǎn)，并對(duì)屬性的每個(gè)值創(chuàng)建分枝，依據(jù)此思想劃分訓(xùn)練數(shù)據(jù)樣本集。</p><p>　　2.1.3決策樹(shù)的剪枝</p><p>　　當(dāng)決策樹(shù)創(chuàng)建時(shí)，由于數(shù)據(jù)中的

83、噪聲和孤立點(diǎn)，許多分支反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝[11]方法處理這種過(guò)分適應(yīng)數(shù)據(jù)問(wèn)題。通常使用統(tǒng)計(jì)度量，剪去最不可靠的分支，這將導(dǎo)致較快的分類(lèi)，提高樹(shù)獨(dú)立于測(cè)試數(shù)據(jù)正確分類(lèi)的能力。主要有兩類(lèi)剪枝方法:</p><p>　　1．同步修剪 (pre-pruning):</p><p>　　在建樹(shù)的過(guò)程中，當(dāng)滿(mǎn)足一定條件，例如Information Gain或者某些有效統(tǒng)計(jì)量達(dá)到某個(gè)預(yù)先設(shè)定

84、的閾值時(shí)，節(jié)點(diǎn)不再繼續(xù)分裂，內(nèi)部節(jié)點(diǎn)成為一個(gè)葉子節(jié)點(diǎn)。葉子節(jié)點(diǎn)取子集中頻率最大的類(lèi)作為自己的標(biāo)識(shí)，或者可能僅僅存儲(chǔ)這些實(shí)例的概率分布函數(shù)。然而，選取一個(gè)適當(dāng)?shù)拈撝凳抢щy的，因?yàn)檩^高的閾值可能導(dǎo)致過(guò)分簡(jiǎn)化的數(shù)，而較低的閾值可能使得樹(shù)的化簡(jiǎn)太少。</p><p>　　2．遲滯修剪(pos-pruning):</p><p>　　與建樹(shù)時(shí)的訓(xùn)練集獨(dú)立的訓(xùn)練數(shù)據(jù)進(jìn)入決策樹(shù)并到達(dá)葉節(jié)點(diǎn)時(shí)，訓(xùn)練數(shù)據(jù)的

85、class label與葉子節(jié)點(diǎn)的class label不同，這時(shí)稱(chēng)為發(fā)生了分類(lèi)錯(cuò)誤。當(dāng)樹(shù)建好之后，對(duì)每個(gè)內(nèi)部節(jié)點(diǎn)，算法通過(guò)每個(gè)枝條的出錯(cuò)率進(jìn)行加權(quán)平均，計(jì)算如果不剪枝該節(jié)點(diǎn)的錯(cuò)誤率。如果裁減能夠降低錯(cuò)誤率，那么該節(jié)點(diǎn)的所有兒子就被剪掉，而該節(jié)點(diǎn)成為一片葉子。出錯(cuò)率用與訓(xùn)練集數(shù)據(jù)獨(dú)立的測(cè)試數(shù)據(jù)校驗(yàn)。最終形成一棵錯(cuò)誤率盡可能小的決策樹(shù)。在實(shí)際應(yīng)用中可以交叉使用同步修剪和遲滯修剪，形成組合式方法。遲滯修剪所需的計(jì)算比同步修剪多，但通常產(chǎn)生更

86、可靠的樹(shù)。</p><p>　　2.1.4決策樹(shù)的特性</p><p>　　決策樹(shù)有很多的優(yōu)點(diǎn)，是實(shí)際應(yīng)用和學(xué)術(shù)研究領(lǐng)域最普遍采用的方法之一。主要特點(diǎn)有：</p><p><b>　　1．靈活性 </b></p><p>　　決策樹(shù)不需要對(duì)數(shù)據(jù)的分布進(jìn)行任何假設(shè)，它是非參數(shù)方法。事例空間被分成子空間，每一個(gè)子空間適用

87、于不同的模型。一棵決策樹(shù)能完全包含一個(gè)事例空間，如果有足夠的數(shù)據(jù)，它能近似任意函數(shù)的最優(yōu)貝葉斯錯(cuò)誤率。</p><p>　　2．健壯性[12] </p><p>　　對(duì)單變量經(jīng)過(guò)單調(diào)轉(zhuǎn)換后的輸入，單變量樹(shù)的輸出是不變的。例如，對(duì)x，log2x,或者作為第j個(gè)輸入變量，會(huì)產(chǎn)生同樣結(jié)構(gòu)的樹(shù)。因此沒(méi)有必要考慮輸入變量的轉(zhuǎn)換式。另外由于對(duì)內(nèi)部屬性進(jìn)行了選擇，相對(duì)于有不相關(guān)輸入變量的情況，而產(chǎn)生

88、的樹(shù)更加具有健壯性。</p><p><b>　　3．可解釋性 </b></p><p>　　全面的和復(fù)雜的決策可以通過(guò)一系列簡(jiǎn)單和局部的決策近似取得。所有的決策都是用來(lái)描述該問(wèn)題的屬性值上的。決策樹(shù)具有這兩個(gè)特性，具有可理解性和可解釋性，它們是決策樹(shù)被廣泛使用的原因。</p><p><b>　　4．速度 </b>

89、;</p><p>　　決策樹(shù)算法采用自上而下，分而治之，不需要回溯戰(zhàn)略的一種貪婪算法。時(shí)間復(fù)雜是與例子的數(shù)目成線(xiàn)性關(guān)系的。</p><p>　　同樣，決策樹(shù)也面對(duì)一些問(wèn)題:</p><p><b>　　1．分塊 </b></p><p>　　分塊使得數(shù)據(jù)被分成較小的子集。假定每次分枝數(shù)據(jù)都分成相等大小的數(shù)目，那決策樹(shù)

90、所要測(cè)試的屬性的復(fù)雜度不大于O(logn)。在有許多相關(guān)屬性的情形下，這是理想的結(jié)果。</p><p><b>　　2．復(fù)制</b></p><p>　　子樹(shù)的復(fù)制指的是在不同的分枝復(fù)制相同的屬性測(cè)試。由于屬性間存在相關(guān)性項(xiàng)性(一個(gè)結(jié)果可由多個(gè)條件決定)，例如，布爾函數(shù)f=X1X2+X3X4中屬性X1和X2，或者屬性X3屬性X4間不是相互獨(dú)立的，而是存在相關(guān)性;另外該

91、布爾函數(shù)有多個(gè)乘積項(xiàng)X1X2和X3X4。出現(xiàn)這種情況時(shí)，生成的決策樹(shù)會(huì)有子樹(shù)復(fù)制問(wèn)題。復(fù)制現(xiàn)象導(dǎo)致決策樹(shù)理解，同時(shí)還導(dǎo)致分塊問(wèn)題:當(dāng)樹(shù)很大時(shí)，會(huì)造成數(shù)據(jù)集的劃分越來(lái)越小，從而性能越差。</p><p><b>　　3．缺值</b></p><p>　　決策樹(shù)是一種層次測(cè)試方法，如果某個(gè)屬性值未知的話(huà)，就會(huì)難以決定下一步分枝，因此必須使用特殊的機(jī)制來(lái)處理缺值的問(wèn)題。&l

92、t;/p><p><b>　　4．連續(xù)屬性</b></p><p>　　決策樹(shù)算法的瓶頸是對(duì)連續(xù)屬性的處理。在這種情況下，要在每一個(gè)節(jié)點(diǎn)對(duì)每一個(gè)屬性進(jìn)行一系列的操作。有學(xué)者認(rèn)為處理許多的連續(xù)屬性的操作占決策樹(shù)構(gòu)造過(guò)程70%的時(shí)間。</p><p><b>　　5．不穩(wěn)定性</b></p><p>　　訓(xùn)

93、練集的小的變化能引起最終的樹(shù)發(fā)生很大的變化。在每一個(gè)節(jié)點(diǎn)，分枝度量準(zhǔn)則對(duì)屬性進(jìn)行排列并選擇最好的屬性進(jìn)行排序。如果有兩個(gè)以上的屬性具有相同的排序值，則訓(xùn)練集數(shù)據(jù)的小的變化就能改變排序，該節(jié)點(diǎn)下面的子樹(shù)就會(huì)發(fā)生變化。這種遞歸的分枝戰(zhàn)略表明對(duì)于每個(gè)產(chǎn)生的分枝，數(shù)據(jù)集基于測(cè)試屬性被分割，在進(jìn)行了一些分割后，通常就只有非常少的數(shù)據(jù)進(jìn)行決策，因此靠近葉節(jié)點(diǎn)做出的決策就沒(méi)有在根節(jié)點(diǎn)附近做出的決策可靠。</p><p>　　2

94、.1.5決策樹(shù)的適用問(wèn)題</p><p>　　盡管已經(jīng)開(kāi)發(fā)的每種決策樹(shù)算法有這樣或那樣不太一致的能力和要求，通常決策樹(shù)算法最適合具有以下特征的問(wèn)題[13]:</p><p>　　（1）實(shí)例是由“屬性一值”對(duì)表示的:實(shí)例是用一系列固定的屬性和它們的值來(lái)描述的。在最簡(jiǎn)單的決策樹(shù)學(xué)習(xí)中，每一個(gè)屬性取少數(shù)的離散的值。但擴(kuò)展的算法允許處理值域?yàn)閷?shí)數(shù)的屬性。</p><p>　

95、?。?）目標(biāo)函數(shù)具有離散的輸出值:(例如最常見(jiàn)的布爾類(lèi)型的分類(lèi):yes或no)。決策樹(shù)方法很容易擴(kuò)展到學(xué)習(xí)有兩個(gè)以上輸出的函數(shù)。</p><p>　?。?）可能需要析取的描述，決策樹(shù)很自然的可以代表析取表達(dá)式。</p><p>　　（4）訓(xùn)練數(shù)據(jù)可以包含錯(cuò)誤:決策樹(shù)學(xué)習(xí)對(duì)錯(cuò)誤有很好的健壯性，無(wú)論是訓(xùn)練樣例所屬的分類(lèi)錯(cuò)誤還是描述這些樣例的屬性值錯(cuò)誤。</p><p>

96、　?。?）訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實(shí)例:決策樹(shù)學(xué)習(xí)甚至可以在有未知屬性值的訓(xùn)練樣例中使用。</p><p>　　己經(jīng)發(fā)現(xiàn)很多實(shí)際的問(wèn)題符合這些特征，所以決策樹(shù)學(xué)習(xí)己經(jīng)被應(yīng)用到很多問(wèn)題中。例如根據(jù)疾病分類(lèi)患者;根據(jù)起因分類(lèi)設(shè)備故障;根據(jù)拖欠支付的可能性分類(lèi)貸款申請(qǐng)。對(duì)于這些問(wèn)題，核心任務(wù)是要把樣例分類(lèi)到各個(gè)可能的離散值對(duì)應(yīng)的類(lèi)別中。</p><p>　　2.2 ID3分類(lèi)算法基本原理&l

97、t;/p><p>　　在本章的開(kāi)始就已經(jīng)提到了決策樹(shù)的生成到目前為止有很多種算法，但它們多數(shù)是圍繞決策樹(shù)的核心算法ID3演變而來(lái)的。在本文主要是對(duì)ID3算法研究和設(shè)計(jì)實(shí)現(xiàn)，具體的內(nèi)容將在下一章詳細(xì)介紹。</p><p>　　早期著名的決策樹(shù)算法是1986年由Quinlan提出的ID3算法[14] .給出ID3算法ID3tree(T.T attributelist)的具體描述。其中，假設(shè)用T代表

98、當(dāng)前樣本集，當(dāng)前的候選屬性集用T-attributelist 表示，候選屬性集中的所有屬性皆為離散型，連續(xù)值屬性必須事先經(jīng)過(guò)預(yù)處理轉(zhuǎn)化為離散型。</p><p>　　ID3算法運(yùn)用信息熵理論，選擇當(dāng)前樣本集中具有最大信息增益值的屬性作為測(cè)試屬性;樣本集的劃分則依據(jù)測(cè)試屬性的取值進(jìn)行，測(cè)試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時(shí)，決策樹(shù)上相應(yīng)于該樣本集的節(jié)點(diǎn)長(zhǎng)出新的葉子節(jié)點(diǎn)。由于決策樹(shù)的結(jié)構(gòu)越簡(jiǎn)單越能從

99、本質(zhì)的層次上概括事物的規(guī)律，我們于是期望非葉節(jié)點(diǎn)到達(dá)后代節(jié)點(diǎn)的平均路徑總是最短，即生成的決策樹(shù)的平均深度最小。這就要求在每個(gè)節(jié)點(diǎn)選擇好的劃分。香農(nóng)的信息論表明:系統(tǒng)的不確定性越小，信息的傳遞就越充分。ID3算法根據(jù)信息理論，采用劃分后樣本集的不確定性作為衡量劃分好壞的標(biāo)準(zhǔn)，用信息增益值度量:信息增益值越大，不確定性越小。因此，算法在每個(gè)非葉節(jié)點(diǎn)選擇信息增益最大的屬性作為測(cè)試屬性。</p><p>　　給出ID3算

100、法信息增益求值[15]的算法:</p><p>　　設(shè)S是s個(gè)樣本的集合。假定類(lèi)別屬性具有m個(gè)不同值，定義m個(gè)不同類(lèi)Ci(i=l，……，m)。設(shè)si 是Ci中的樣本數(shù)。對(duì)一個(gè)給定的樣本集，它總的信息熵I值由公式2.9給出：</p><p>　　(2.9) </p><p>　　Pi是任意樣本屬于類(lèi)別Ci的概率，用Si/S估計(jì)。</p&g

101、t;<p>　　設(shè)屬性A具有v個(gè)不同的值。可以用屬性A(a1, a2,。。。av)，將S劃分為v個(gè)子集{S1, S2,。。。Sv };其中，Sj包含S中這樣的一些樣本，它們?cè)贏上具有值aj，。假設(shè)選取A作為本次分類(lèi)的屬性，則這些子集對(duì)應(yīng)于由包含集合S的節(jié)點(diǎn)生長(zhǎng)出來(lái)的分枝。設(shè)sij是子集Sj中類(lèi)Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵(entropy)由公式2.10得出:</p><p><b>

102、;　　(2.10)</b></p><p>　　其中， (2.11)</p><p>　　是Sj中類(lèi)為Ci的樣本的概率，最后，用屬性A劃分樣本集S后所得的信息增益值由公式2.12給出：</p><p><b>　　(2.12)</b></p><p>　　選擇屬性A使Entro

103、py (E/A)最小，則信息增益將增大。也就是說(shuō)，Gain(A)是由于知道屬性A的值而導(dǎo)致的熵的期望壓縮。為了使下一步所需的信息量最小，要求每一次都選擇其信息增益最大的屬性作為決策樹(shù)的新結(jié)點(diǎn)，并對(duì)屬性的每個(gè)值創(chuàng)建分枝，依據(jù)此思想劃分訓(xùn)練數(shù)。</p><p>　　ID3是一個(gè)典型的決策樹(shù)學(xué)習(xí)系統(tǒng)，它檢驗(yàn)數(shù)據(jù)集的所有特征，它以信息增益作為分離目標(biāo)評(píng)價(jià)函數(shù)，采用自頂向下，分而治之不可返回的策略，選取決策樹(shù)的分裂點(diǎn)，對(duì)每

104、個(gè)分支的子集采用遞歸調(diào)用同種方法建立決策樹(shù)結(jié)點(diǎn)和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類(lèi)。</p><p>　　2.3其它常見(jiàn)決策樹(shù)算法</p><p>　　經(jīng)典的ID3算法在1986年由Quinlan提出后有許多學(xué)者對(duì)此算法進(jìn)行了大量的研究，先后出現(xiàn)了以C4.5、CART、SLIQ、SPRINT等較新的有關(guān)決策樹(shù)分類(lèi)的算法，下面簡(jiǎn)要描述這幾種算法的基本概念和思想。</p>&

105、lt;p><b>　?。?）C4.5算法</b></p><p>　　C4.5算法是Quinlan在1993年針對(duì)ID3存在的一些缺點(diǎn)提出的，它是ID3算法的后繼，同時(shí)也成為后面諸多決策樹(shù)算法的基礎(chǔ)。C4. 5是ID3的改進(jìn)版本[16]。它主要在以下幾個(gè)方面對(duì)ID3作了改進(jìn):缺省值的預(yù)測(cè)屬性仍可用,提出了修剪思想,可以進(jìn)行規(guī)則推導(dǎo)。特別是在應(yīng)用單機(jī)的決策樹(shù)算法中，C4.5算法不僅分類(lèi)準(zhǔn)

106、確率高而且速度快。C4.5算法在ID3的基礎(chǔ)上彌補(bǔ)了對(duì)連續(xù)型屬性、屬性值空缺情況的處理[23]，對(duì)樹(shù)剪枝也進(jìn)行了處理。與ID3不同，C4.5采用基于信息增益率(information gain ratio)的方法選擇測(cè)試屬性。信息增益率等于信息增益對(duì)分割信息量(split information)的比值。對(duì)樣本集T，假設(shè)J是有S個(gè)不同取值的離散屬性，用J分割樣本集所得信息增益的算法同ID3算法。分割信息量由公式：給出。其中|T|為數(shù)據(jù)集