PAGE\*roman

iv

目錄

摘要 iii

Abstract iv

第一章緒論 1

1.1 數(shù)據(jù)挖掘技術(shù) 1

1.1.1 數(shù)據(jù)挖掘技術(shù)的應(yīng)用背景 1

1.1.2數(shù)據(jù)挖掘的定義及系統(tǒng)結(jié)構(gòu) 2

1.1.3 數(shù)據(jù)挖掘的方法 4

1.1.4 數(shù)據(jù)挖掘系統(tǒng)的發(fā)展 5

1.1.5 數(shù)據(jù)挖掘的應(yīng)用與面臨的挑戰(zhàn) 6

1.2 決策樹分類算法及其研究現(xiàn)狀 8

1.3數(shù)據(jù)挖掘分類算法的研究意義 10

1.4本文的主要內(nèi)容 11

第二章決策樹分類算法相關(guān)知識 12

2.1決策樹方法介紹 12

2.1.1決策樹的結(jié)構(gòu) 12

2.1.2決策樹的基本原理 13

2.1.3決策樹的剪枝 15

2.1.4決策樹的特性 16

2.1.5決策樹的適用問題 18

2.2ID3 分類算法基本原理 18

2.3其它常見決策樹算法 20

2.4決策樹算法總結(jié)比較 24

2.5實現(xiàn)平臺簡介 25

2.6本章小結(jié) 29

第三章ID3算法的具體分析. 30

3.1ID3 算法分析

30

3.1.1ID3 算法流程

30

3.1.2ID3 算法評價

33

3.2決策樹模型的建立

34

3.2.1 決策樹的生成

34

3.2.2 分類規(guī)則的提取

377

3.2.3模型準(zhǔn)確性評估

388

3.3 本章小結(jié)

39

第四章實驗結(jié)果分析 40

4.1 實驗結(jié)果分析 40

4.1.1生成的決策樹 40

4.1.2 分類規(guī)則的提取 40

4.2 本章小結(jié) 41

第五章總結(jié)與展望 42

參考文獻 44

致謝 45

附錄 46

摘要:信息高速發(fā)展的今天，面對海量數(shù)據(jù)的出現(xiàn)，如何有效利用海量的原始數(shù)據(jù)分析現(xiàn)狀和預(yù)測未來，已經(jīng)成為人類面臨的一大挑戰(zhàn)。由此，數(shù)據(jù)挖掘技術(shù)應(yīng)運而生并得到迅猛發(fā)展。

數(shù)據(jù)挖掘是信息技術(shù)自然演化的結(jié)果，是指從大量數(shù)據(jù)中抽取挖掘出來隱含未知的、有價值的模式或規(guī)律等知識的復(fù)雜過程。

本文主要介紹如何利用決策樹方法對數(shù)據(jù)進行分類挖掘。文中詳細(xì)的闡述了決策樹的基本知識和相關(guān)算法，并對幾種典型的決策樹算法進行了分析比較，如:核心經(jīng)典算法——ID3算法;能夠處理不完整的數(shù)據(jù)、對連續(xù)屬性的數(shù)據(jù)離散化

處理以及克服了ID3算法偏向于選擇取值較多的屬性作為測試屬性的缺點的

C4.5算法;利用GINI系數(shù)判別數(shù)據(jù)集中的分裂屬性并形成二叉樹的 CART算法;使數(shù)據(jù)的分類不受機器主存的限制， 有著良好的伸縮和并行性的SLIQ和SPRNIT算法。ID3算法是最核心的技術(shù)，所以本文主要對它進行了研究和設(shè)計實現(xiàn)。

第四章在JAVA編譯器上實現(xiàn)ID3算法，并對結(jié)果進行分析，決策樹生成，分類規(guī)則的提取，以便于以后直接使用這一規(guī)則進行數(shù)據(jù)分析。在論文的最后一章介紹了目前數(shù)據(jù)挖掘技術(shù)的研究前景。

關(guān)鍵詞:數(shù)據(jù)挖掘；決策樹；ID3算法；信息增益；熵值

Abstract:Today,themassageispassedveryquickly.HowtoinvestigatecurrentstatusandforecastthefuturewithgooduseoftremendousoriginalDatahasbeenbecomingthebigchallengetohumanbeingswhenfacingtheemergenceofmassDataininformationera.Consequently,Dataminingtechnologyemergeandboomquickly.

Datamining,istheproductoftheevolutionofinformationtechnology,whichis

acomplexprocessexcactingtheimplicatedandvaluablepattens,knowledgeandrulesfromalargescaleofdataset.

Thispapermainlyintroducesthedecisiontreealgorithmforclassification.Firstly,thebasicknowledgeaboutdecisiontreeandsomerepresentativealgorithmsforinducingdecisiontreearediscussed,includingID3,whichisclassical;C4.5,whichcandealwithcontinuousattributesandsomeemptyattribute,atthesametime,itcanovercometheID3’weakneswshichisapttoselectsomeattributewithmorevalue;CART,whichusesGINIcoefficientaboutattributeselectionandinducesabinarytree;SLIQand SPRINT,whicharescalableandcanbeeasilyparallelized,moreovertheydon’thaveanylimitationofmainmemory.BecauseID3algorithmswhichisclassical,

sointhepaperImainintroduceit.

Thefirthchapter,ID3algorithmisdevelopedonthejavaplatformbyjava，andcarriesontheanalysistotheresult,thedecisiontreeproduction,the classifiedruleextraction,itwillbeadvantageousforus tousethisruletocarryonthedataanalysis

directlyinthefuture.Iintroducedataminingtechnologyresearchprospectinthepaperlastchapter.

Keywords:Datamining;Decisiontree;ID3algorithm;Informationgain;Entropyvalue

第

PAGE

2

頁,共52頁

第一章緒論

數(shù)據(jù)挖掘技術(shù)

數(shù)據(jù)挖掘技術(shù)的應(yīng)用背景

最近幾十年以來，隨著互聯(lián)網(wǎng)的發(fā)展和企業(yè)信息化程度的日益提高， 科研政府部門普遍使用電子事物處理技術(shù)，商品條形碼被廣泛使用，以及電子商務(wù)和科學(xué)數(shù)據(jù)庫的急劇增長為我們帶來了海量的數(shù)據(jù)。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M行更高層次的分析，以便更好地利用這些數(shù)據(jù)。而目前的數(shù)據(jù)庫系統(tǒng)可以高效地實現(xiàn)數(shù)據(jù)的錄入、 查詢、統(tǒng)計等功能，但無法發(fā)現(xiàn)數(shù)據(jù)中存在的關(guān)系和規(guī)則，無法根據(jù)現(xiàn)有的數(shù)據(jù)預(yù)測未來的發(fā)展趨勢，缺乏挖掘數(shù)據(jù)背后隱藏的知識的手段，從而導(dǎo)致了“數(shù)據(jù)爆炸但知識貧乏”的現(xiàn)象。

大量信息在給人們帶來方便的同時也帶來了一大堆問題：第一是信息過量，難以消化；第二是信息真假難以辨識；第三是信息安全難以保證；第四是信息形式不一致，難以統(tǒng)一處理。人們開始考慮：“如何才能不被信息淹沒，而是從中及時發(fā)現(xiàn)有用的知識、提高信息利用率？”這就引發(fā)了一門新興的自動信息提取技術(shù)：數(shù)據(jù)中的知識發(fā)現(xiàn)，簡稱KDD[1](KnowledgeDiscoveryinDataBase) 。其內(nèi)容主要涉及人工智能領(lǐng)域中的機器學(xué)習(xí)，模式識別、統(tǒng)計學(xué)、智能數(shù)據(jù)庫、知識獲取、專家系統(tǒng)、數(shù)據(jù)庫可視化、數(shù)據(jù)庫領(lǐng)域

的數(shù)據(jù)倉庫聯(lián)機分析處理(OLAP)，多維數(shù)據(jù)庫等方面。KDD已經(jīng)是解決目前信息

系統(tǒng)中普遍面臨的“數(shù)據(jù)爆炸”而“信息缺乏”狀況的最有效的手段之一，并且它的研究領(lǐng)域具有較大的研究意義和較多的研究方向一度成為數(shù)據(jù)庫研究界最

熱的研究方向，擁有人數(shù)眾多的研究群體，受到學(xué)術(shù)界和企業(yè)界的極大關(guān)注。多學(xué)科的相互交融和相互促進，使得這一學(xué)科得以蓬勃發(fā)展，而且已初具規(guī)模。并行計算、計算機網(wǎng)絡(luò)和信息工程等其他領(lǐng)域的國際學(xué)會、 學(xué)刊也把數(shù)據(jù)挖掘和知識發(fā)現(xiàn)列為專題和專刊討論，甚至到了膾炙人口的程度。數(shù)據(jù)挖掘是目前研究的熱點，它可以說是數(shù)據(jù)庫研究中的一個非常有應(yīng)用價值的新領(lǐng)域， 它融合了數(shù)據(jù)庫、人工智能、機器學(xué)習(xí)、數(shù)理統(tǒng)計學(xué)、模糊數(shù)學(xué)等多個領(lǐng)域的理論和技術(shù)。

數(shù)據(jù)挖掘DM[2](DataMining) 是KDD的一個最關(guān)鍵步驟，因此實際應(yīng)用中把DM和KDD不作區(qū)分。數(shù)據(jù)挖掘是目前研究的熱點，它可以說是數(shù)據(jù)庫研究中的一個非常有應(yīng)用價值的新領(lǐng)域，它融合了數(shù)據(jù)庫、人工智能、機器學(xué)習(xí)、數(shù)理統(tǒng)計學(xué)、模糊數(shù)學(xué)等多個領(lǐng)域的理論和技術(shù)。 從數(shù)據(jù)分析的觀點來看，數(shù)據(jù)挖掘分為兩類:描述性數(shù)據(jù)挖掘和預(yù)測性數(shù)據(jù)挖掘。描述性數(shù)據(jù)挖掘以概要方式描

述數(shù)據(jù)，提供數(shù)據(jù)所具有的一般性質(zhì);預(yù)測性數(shù)據(jù)挖掘分析數(shù)據(jù)，建立一個或一組模型，產(chǎn)生關(guān)于數(shù)據(jù)的預(yù)測。包括分類和回歸。分類可用于提取描述重要數(shù)據(jù)的模型或預(yù)測未來的數(shù)據(jù)趨勢。1995年，在美國計算機年會(ACM)上，提出了數(shù)據(jù)挖掘的概念。即通過從數(shù)據(jù)庫中抽取隱含的，未知的，具有潛在使用價值信息的過程。數(shù)據(jù)挖掘應(yīng)用的普遍性及帶來的巨大的經(jīng)濟和社會效益， 吸引了許多專家和研究機構(gòu)從事該領(lǐng)域的研究，許多公司推出了自己的數(shù)據(jù)庫挖掘系統(tǒng)。從1989年舉行的第十一屆國際聯(lián)合人工智能學(xué)術(shù)會議上 KDD被提出，到現(xiàn)在不過十多年的時間，但在GartnerGroup 的一次高級技術(shù)調(diào)查中將數(shù)據(jù)挖掘和人工智能列為“未來5 年內(nèi)將對工業(yè)產(chǎn)生深遠影響的五大關(guān)鍵技術(shù)”之首，并且還將數(shù)據(jù)挖掘列為未來五年內(nèi)十大新興技術(shù)投資焦點的第二位。 根據(jù)最近Gartner的HPC研究表明，“隨著數(shù)據(jù)捕獲、傳輸和存儲技術(shù)的快速發(fā)展，大型系統(tǒng)用戶將更多地需要采用新技術(shù)來挖掘市場以外的價值，采用更為廣闊的并行處理系統(tǒng)來創(chuàng)建新的商業(yè)增長點?！?/p>

數(shù)據(jù)挖掘的定義及系統(tǒng)結(jié)構(gòu)

數(shù)據(jù)挖掘也稱為數(shù)據(jù)庫中的知識發(fā)現(xiàn) KDD(KnowledgeDiscoveryinDataBase)。指的是從存放在數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫中的大量數(shù)據(jù)中挖掘出

人們感興趣的知識，這些知識是隱含的、事先未知的潛在有用信息。目的是幫助

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

第

PAGE

3

頁,共52頁

行。

從廣義角度講數(shù)據(jù)、信息是知識的表現(xiàn)形式，但在數(shù)據(jù)挖掘中更多把概念、

規(guī)則、模式、規(guī)律和約束等看作知識。原始數(shù)據(jù)可以是結(jié)構(gòu)化的，如關(guān)系型數(shù)據(jù)庫中的數(shù)據(jù)，也可以是半結(jié)構(gòu)化的，如文本、圖形、圖像數(shù)據(jù)、甚至是分布在網(wǎng)

絡(luò)上的異構(gòu)型數(shù)據(jù)。發(fā)現(xiàn)知識的方法可以是數(shù)學(xué)的或非數(shù)學(xué)的、演繹的或歸納的。

發(fā)現(xiàn)的知識可以被用于信息管理、查詢優(yōu)化、決策支持、過程控制等?？傊?，數(shù)據(jù)挖掘是一門廣義的交叉學(xué)科，它的發(fā)展和應(yīng)用涉及到不同的領(lǐng)域尤其是數(shù)據(jù)

庫、人工智能、數(shù)理統(tǒng)計、可視化、并行計算等。因此，概括起來從廣義上來說，數(shù)據(jù)挖掘是從大型數(shù)據(jù)集（可能是不完全的，有噪聲的，不確定的，各種存儲形

式的）中，挖掘隱含在其中的，人們事先不知道的，對決策有用的知識的過程[3]。從狹義上來說，數(shù)據(jù)挖掘是從特定形式的數(shù)據(jù)集中提煉知識的過程。

數(shù)據(jù)挖掘的系統(tǒng)結(jié)構(gòu)可以用以下的圖來說明：

圖1.1 數(shù)據(jù)挖掘系統(tǒng)結(jié)構(gòu)圖

·數(shù)據(jù)庫、數(shù)據(jù)倉庫或其他信息庫:這是一個或一組數(shù)據(jù)庫、數(shù)據(jù)倉庫、電子表格或其他類型的信息庫?？梢栽跀?shù)據(jù)上進行數(shù)據(jù)清理和集成。

·數(shù)據(jù)庫或數(shù)據(jù)倉庫服務(wù)器:根據(jù)用戶的數(shù)據(jù)挖掘請求負(fù)責(zé)提取相關(guān)數(shù)據(jù)。

·知識庫:這是領(lǐng)域知識，用于指導(dǎo)、搜索或評估結(jié)果模式的興趣度。

·數(shù)據(jù)挖掘引擎:這是數(shù)據(jù)挖掘系統(tǒng)的基本部分。由一組功能模塊組成，用

第

PAGE

12

頁,共52頁

于特征化、關(guān)聯(lián)、分類、聚類分析以及演變和偏差分析。

·模式評估模塊:通常，此模塊使用興趣度度量，并與數(shù)據(jù)挖掘模塊交互，以便將搜索聚焦在有趣的模式上。

·圖形用戶界面:本模塊在用戶和數(shù)據(jù)挖掘系統(tǒng)之間通信，允許用戶與系統(tǒng)交互，指定數(shù)據(jù)挖掘查詢或任務(wù)，提供信息，幫助搜索聚焦，根據(jù)數(shù)據(jù)挖掘的中間結(jié)果進行探索式數(shù)據(jù)挖掘。此外，此模塊還允許用戶瀏覽數(shù)據(jù)庫和數(shù)據(jù)倉庫模式或數(shù)據(jù)結(jié)構(gòu)，評估挖掘的模式，以不同的形式對模式可視化。

數(shù)據(jù)挖掘的方法

數(shù)據(jù)挖掘的功能用于指定數(shù)據(jù)挖掘任務(wù)中要找的模式類型，其任務(wù)一般可分為兩類:描述和預(yù)測。描述性挖掘任務(wù)刻畫數(shù)據(jù)庫中數(shù)據(jù)的一般特性，預(yù)測性挖掘任務(wù)在當(dāng)前數(shù)據(jù)上進行推斷，以進行預(yù)測。在實際應(yīng)用中，往往根據(jù)模式的實際應(yīng)用細(xì)分為以下6 種[4]:

分類模式

回歸模式

時間序列模式

聚類模式

關(guān)聯(lián)模式

序列模式

本文主要介紹分類算法，所以下面主要介紹分類分析方法，分類分析要分析數(shù)據(jù)庫中的一組對象，找出其共同屬性，構(gòu)造分類模型，然后利用分類模型對其它的數(shù)據(jù)對象進行分類。要構(gòu)造分類模型，需要一個訓(xùn)練樣本數(shù)據(jù)集作為輸入，訓(xùn)練集由一組數(shù)據(jù)庫記錄或元組組成，每個元組包含一些字段值，又稱“屬性”或“特征”，這些字段和測試集中記錄的字段相同，另外，每個訓(xùn)練樣本記錄有

一個類別標(biāo)識。分類目標(biāo)是分析訓(xùn)練集中的數(shù)據(jù)， 利用數(shù)據(jù)中能得到的特征，為每一類建立一個恰當(dāng)?shù)拿枋龌蚰Ｐ?，然后根?jù)這些分類描述對測試數(shù)據(jù)進行分類或產(chǎn)生更恰當(dāng)?shù)拿枋?。我們可以舉一個簡單的例子，信用卡公司的數(shù)據(jù)庫中保存著各持卡人的記錄，公司根據(jù)信譽程度將持卡人記錄分成三類 :良好、一般、較差，并且類別標(biāo)記己賦給了各個記錄。分類分析就是分析該數(shù)據(jù)庫的記錄數(shù)據(jù)，

對每個信譽等級做出準(zhǔn)確描述，如“信譽良好的客戶是指那些年收入在 5萬元以

上，年齡在40-50歲之間的人士”，然后根據(jù)這些描述對其它具有相同屬性的數(shù)據(jù)庫記錄進行分類。

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

在解決實際問題時，經(jīng)常要同時使用多種模式。分類模式和回歸模式是使用

最普遍的模式。分類模式、回歸模式、時間序列模式也被認(rèn)為是受監(jiān)督知識，因為在建立模式前數(shù)據(jù)的結(jié)果是已知的， 可以直接用來檢測模式的準(zhǔn)確性，模式的產(chǎn)生是在受監(jiān)督的情況下進行的。一般在建立這些模式時，使用一部分?jǐn)?shù)據(jù)作為樣本，用另一部分?jǐn)?shù)據(jù)來檢驗、校正模式。

數(shù)據(jù)挖掘系統(tǒng)的發(fā)展

根據(jù)R.Grossman的觀點，數(shù)據(jù)挖掘的發(fā)展過程可分為如下所介紹的一到四代[5]:

第一代:第一代的數(shù)據(jù)挖掘系統(tǒng)僅支持一個或少數(shù)幾個數(shù)據(jù)挖掘算法，這些算法只能夠挖掘向量數(shù)據(jù)。如果數(shù)據(jù)足夠大，并且頻繁的變化，這就需要利用數(shù)據(jù)庫或者數(shù)據(jù)倉庫技術(shù)進行管理，第一代系統(tǒng)顯然不能滿足需求。

第二代:第二代系統(tǒng)的主要特點是支持與數(shù)據(jù)庫和數(shù)據(jù)倉庫的高性能接口，

并有高的可測量性和功能性。第二代系統(tǒng)提供了數(shù)據(jù)挖掘模式和數(shù)據(jù)挖掘查詢語言，從而具有更高的靈活性。然而第二代系統(tǒng)只注重模型的生成，如何和預(yù)言模型系統(tǒng)集成的問題導(dǎo)致了第三代數(shù)據(jù)挖掘系統(tǒng)的開發(fā)。

第三代:第三代數(shù)據(jù)挖掘系統(tǒng)可挖掘intranets 和extranets 上的分布的和高度異質(zhì)的數(shù)據(jù)，并能有效的和操作系統(tǒng)結(jié)合。這一代數(shù)據(jù)挖掘系統(tǒng)的關(guān)鍵技術(shù)之一是提高對建立在異質(zhì)系統(tǒng)上的多個預(yù)言模型以及管理這些預(yù)言模型的元

數(shù)據(jù)提供第一級別的支持。

第四代:第四代數(shù)據(jù)挖掘系統(tǒng)可以挖掘嵌入式、移動式以及一般性的計算設(shè)備所產(chǎn)生的各種數(shù)據(jù)。

數(shù)據(jù)挖掘的應(yīng)用與面臨的挑戰(zhàn)

盡管數(shù)據(jù)挖掘是一個新興的研究領(lǐng)域， 但是卻得到了穩(wěn)定的發(fā)展，每年市場上都會出現(xiàn)新的數(shù)據(jù)挖掘系統(tǒng)，各大數(shù)據(jù)庫軟件公司也分別推出了自己的數(shù)據(jù)挖掘產(chǎn)品。數(shù)據(jù)挖掘廣泛應(yīng)用于科學(xué)研究、商業(yè)應(yīng)用、以及 Web挖掘等很多領(lǐng)域。

科學(xué)研究

數(shù)據(jù)挖掘在天文學(xué)上有一個著名的應(yīng)用系統(tǒng):SKICAT[27](Sky ImageCatalogingandAnalysisTool) 。它是加州理工學(xué)院噴氣推進實驗室與天文學(xué)家合作開發(fā)的用于幫助天文學(xué)家發(fā)現(xiàn)遙遠的類星體的一個工具。 SKICAT的任務(wù)是構(gòu)造星體分類器對星體進行分類，使用了決策樹方法構(gòu)造分類器，結(jié)果使得能分辨的星體較以前的方法在亮度上要低一個數(shù)量級之多， 而且新的方法比以往的方法要在效率上要高40倍以上。數(shù)據(jù)挖掘在生物學(xué)上的應(yīng)用主要集中于分子生物學(xué)特別是基因工程的研究上。進幾年，通過用計算生物分子系統(tǒng)分析法，尤其是基因數(shù)據(jù)庫搜索技術(shù)以在基因研究上做出了很多重大發(fā)現(xiàn)， 數(shù)據(jù)挖掘在分子生物學(xué)上的工作可分為兩種:一是從各種生物體的 DNA序列中定位出具有某種功能的基因串;二是在基因數(shù)據(jù)庫中搜索與某種具有高階結(jié)構(gòu) (不是簡單的線形結(jié)構(gòu))或功能的蛋白質(zhì)相似的高階結(jié)構(gòu)序列。

商業(yè)應(yīng)用

數(shù)據(jù)挖掘技術(shù)以及應(yīng)用此技術(shù)所獲得知識和信息可以被廣泛的應(yīng)用于信息管理、商務(wù)管理、過程控制、市場分析、工程設(shè)計和科學(xué)研究等眾多領(lǐng)域，這些

領(lǐng)域的管理決策層可以通過對歷史數(shù)據(jù)的分析， 發(fā)現(xiàn)諸如市場供需規(guī)律、商品價

格走勢、家庭收入與消費特點、購買商品的習(xí)慣等規(guī)律，以支持企業(yè)的生產(chǎn)、經(jīng)營和銷售決策。

web挖掘(WebMining)

隨著網(wǎng)絡(luò)的迅速發(fā)展，今天它己經(jīng)成為人們交流思想，獲取信息的便利手段。但這些信息缺乏結(jié)構(gòu)化、組織的規(guī)律性、隨意的散布在網(wǎng)絡(luò)的各個角落，這已經(jīng)成為這座世界性圖書館的一大缺憾。數(shù)據(jù)挖掘在因特網(wǎng)上的應(yīng)用主要包括三種:在搜索引擎上(SearchEngine)對文檔進行自動分類、幫助用戶尋找感興趣的新

聞以及利用數(shù)據(jù)挖掘設(shè)計一個電子新聞過濾系統(tǒng)。它利用文本學(xué)習(xí)建立起該用戶的趣向模型，當(dāng)用戶進入一份電子報紙的網(wǎng)頁時，該系統(tǒng)就會根據(jù)學(xué)習(xí)所得的模型對其中的每一篇文章按與用戶的興趣的接近程度進行打分排序， 以便使用戶看到他最感興趣的新聞。

這些實踐將數(shù)據(jù)挖掘和各特定領(lǐng)域知識結(jié)合起來，滿足了特定任務(wù)的需要，也取得了一些很大的成績。數(shù)據(jù)挖掘任務(wù)和方法的多樣性給數(shù)據(jù)挖掘提出了許多挑戰(zhàn)性的課題。在未來的課題研究中，數(shù)據(jù)挖掘研究人員、系統(tǒng)和應(yīng)用開發(fā)人員所面臨的主要問題[6]有:

挖掘算法的效率和可擴展性

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

待挖掘數(shù)據(jù)的時序性

在應(yīng)用領(lǐng)域的數(shù)據(jù)庫中，數(shù)據(jù)大多是隨時間變化的，這可能使得原先發(fā)現(xiàn)的知識失去效用，也為開發(fā)強有力的知識發(fā)現(xiàn)系統(tǒng)提供了潛在的舞臺， 因為重新訓(xùn)練一個系統(tǒng)畢竟要比重新訓(xùn)練一個人(改變他的思維、觀點等)容易得多。我們可以來用隨時間逐步修正所發(fā)現(xiàn)的模式來指導(dǎo)新的發(fā)現(xiàn)過程。 互聯(lián)網(wǎng)絡(luò)上的知識發(fā)現(xiàn)正日益普及，在這信息的海洋中可以發(fā)現(xiàn)大量的新知識。己有一些資源發(fā)現(xiàn)工具可用來發(fā)現(xiàn)含有關(guān)鍵字的文本。目前的問題是，如何從復(fù)雜的數(shù)據(jù)例如多媒體結(jié)構(gòu)化的數(shù)據(jù)中提取有用的信息，對多層次數(shù)據(jù)庫的維護，以及如何處理數(shù)據(jù)的異類性和自主性等等。

和其它系統(tǒng)的集成

一個方法、功能單一的發(fā)現(xiàn)系統(tǒng)，其適用范圍必然受到限制。要在更廣闊的領(lǐng)域發(fā)現(xiàn)知識，知識發(fā)現(xiàn)系統(tǒng)就應(yīng)該是數(shù)據(jù)庫、知識庫、專家系統(tǒng)、決策支持系統(tǒng)、可觀化工具、網(wǎng)絡(luò)等多項技術(shù)集成的系統(tǒng)。

遺漏的噪聲數(shù)掘

這個問題在商業(yè)數(shù)據(jù)庫中尤其突出，據(jù)報告，美國人口調(diào)查數(shù)據(jù)的錯誤率上升到20%。如果不經(jīng)認(rèn)真考慮就來設(shè)計待挖掘數(shù)據(jù)庫，重要的屬性可能會被遺漏掉。用更復(fù)雜的統(tǒng)計策略識別隱藏的變量和相關(guān)性成為必然。

挖掘結(jié)果的可理解性

這是評估挖掘系統(tǒng)的一個重要環(huán)節(jié)。我們應(yīng)該盡可能采用圖形表示、有向非循環(huán)圖結(jié)構(gòu)的規(guī)則、自然語言生成以及數(shù)據(jù)和知識的可視化等技術(shù)，提高挖掘結(jié)果的可理解性。

私有數(shù)據(jù)的保護與數(shù)據(jù)安全性

當(dāng)我們可以在不同的角度和不同的層次看到數(shù)據(jù)庫中的數(shù)據(jù)時， 這與我們保護數(shù)據(jù)的安全性和保護私人數(shù)據(jù)的目標(biāo)相抵觸。因此對在什么情況下數(shù)據(jù)挖掘?qū)?dǎo)致對私有數(shù)據(jù)造成侵犯和采用何種措施來防止敏感信息泄露的研究變得非

常重要。

決策樹分類算法及其研究現(xiàn)狀

分類技術(shù)是數(shù)據(jù)挖掘的重要分支，它能夠?qū)Ω鱾€行業(yè)提供良好的決策支持，對整個社會的發(fā)展產(chǎn)生重要而深遠的影響。 數(shù)據(jù)挖掘的分類模式是一種有指導(dǎo)性的學(xué)習(xí)，即是以實例為基礎(chǔ)的歸納學(xué)習(xí)算法，通過分析由屬性描述的訓(xùn)練數(shù)據(jù)集來構(gòu)造模型由此來預(yù)測新元組的分類標(biāo)記。數(shù)據(jù)分類存在很多方法，如判定樹歸納、貝葉斯分類、神經(jīng)網(wǎng)絡(luò)以及 K-最臨近分類、遺傳算法和粗糙集等。其中決策樹歸納以其易于提取顯式規(guī)則、計算量相對較小、可以顯示重要的決策屬性和較高的分類準(zhǔn)確率等優(yōu)點而得到廣泛的應(yīng)用。據(jù)統(tǒng)計，目前決策樹算法是利用最廣泛的數(shù)據(jù)挖掘算法之一，利用率高達19%。應(yīng)用領(lǐng)域已由醫(yī)療到博弈論和商務(wù)等領(lǐng)域，是一些商業(yè)規(guī)則歸納系統(tǒng)的基礎(chǔ)。在計算機科學(xué)中采用樹形結(jié)構(gòu)描述數(shù)據(jù)集已有不短的時間了，但它一直是一個不受重視的知識發(fā)現(xiàn)過程。隨著數(shù)據(jù)挖掘技術(shù)的產(chǎn)生，決策樹得到了很快的發(fā)展。

決策樹的算法己有很多。1986年J.Ross Quinlan 引入了ID3 算法后，引起了很大的反響[7]。在此基礎(chǔ)上，他又于1993 年，在其“ProgramForMachineLearning”一書中，對ID3 算法進行了補充和改進，提出了后來非常流行的C4.5算法。在大數(shù)據(jù)量情況下的效率和生成規(guī)則的數(shù)量與正確性方面有了顯著的提

高。此外，CHAID算法也有相當(dāng)廣泛的應(yīng)用。1996年又提出了SLIQ和SPRINT算法,RAINFOREST框架結(jié)構(gòu)，它們強調(diào)算法的可伸縮性。由于數(shù)據(jù)挖掘的對象是規(guī)模龐大的數(shù)據(jù)，已有的分類算法在數(shù)據(jù)量小時能夠準(zhǔn)確、高效的分類，效果很好。但當(dāng)用于處理大量數(shù)據(jù)時，已有的算法都會不同程度的出現(xiàn)各種問題， 分類效果不理想。因此，研究數(shù)據(jù)挖掘中準(zhǔn)確、有效的分類算法，雖然是一個傳統(tǒng)的

問題，但仍具有挑戰(zhàn)性。目前，在知識發(fā)現(xiàn)和數(shù)據(jù)挖掘的研究和開發(fā)中已經(jīng)取得了一些令人矚目的成績，對關(guān)聯(lián)規(guī)則、聚類等基本算法的研究已經(jīng)基本日趨成熟，人們的研究重點逐漸轉(zhuǎn)移到數(shù)據(jù)挖掘技術(shù)在新的數(shù)據(jù)類型、 應(yīng)用環(huán)境中使用時所出現(xiàn)的新問題的解決上。例如：

決策樹技術(shù)和神經(jīng)網(wǎng)絡(luò)技術(shù)相結(jié)合。決策樹也具有產(chǎn)生 n維空間下任意復(fù)雜的決策邊界的功能。因此, 可以將決策樹重新構(gòu)造成一個多層的神經(jīng)網(wǎng)絡(luò)。這類方法解決了由神經(jīng)網(wǎng)絡(luò)得到的知識難于被人們理解的缺點。

決策樹技術(shù)和模糊集合原理的結(jié)合。決策樹技術(shù)雖然有許多優(yōu)點,但也存在著不穩(wěn)定的缺點,即決策樹帶來了較大的變動。模糊集合的融通性使人們利用模糊邏輯來解決決策樹的這一缺點并取得了不錯的效果。

決策樹技術(shù)和進化算法,遺傳算法及遺傳編程的結(jié)合。基于進化算法的決策樹系統(tǒng)具有較好的抗噪聲能力 , 同時進化算法很容易在并行計算機上運行 ,因此可以期待基于進化算法的決策樹的運算能力有較大的提高。

決策樹技術(shù)和多智能體的結(jié)合。多智能體系統(tǒng)的復(fù)雜性，而機器學(xué)習(xí)有潛力提供一個魯棒性較強的機制來有效協(xié)調(diào)各智能體間的行為， 因此對多智能體結(jié)合機器學(xué)習(xí)是一個很有前途的方向。

尋找新的構(gòu)造決策樹的方法。自從 Quinlan提出ID3和C4.5方法后，有不少專家提出了其他構(gòu)造決策樹的方法， M.Amherst 等提出了基于多維可視化下的交互式的決策樹構(gòu)造，此方法在決策樹構(gòu)造階段加入了專家知識，這樣便于用戶更深地理解產(chǎn)生決策樹的數(shù)據(jù)及最終產(chǎn)生的決策樹， 同時也顯著地減小了決策樹的大小。

尋找更好的簡化決策樹的方法。尋找更好的簡化決策樹的方法 , 這一直

是決策樹技術(shù)研究的一個熱點。D.Fournier 等提出的一種新的修剪決策樹的方法2DI修剪法。此方法針對數(shù)據(jù)不確定的情況, 利用特性索（Quality Index) 來

權(quán)衡處理決策樹深度和節(jié)點雜質(zhì)。2DI修剪法將保持那些雖不能減小錯誤率但能指出一些特殊性質(zhì)的群體的子樹。

研究產(chǎn)生決策樹的訓(xùn)練和檢驗數(shù)據(jù)的大小及特性與決策樹特性之間的關(guān)

系。實際上, 這就是經(jīng)常提起的數(shù)據(jù)預(yù)處理技術(shù)(Datareprocessing), 與決策樹修剪技術(shù)(Pruning) [7] 相對應(yīng), 也稱它為數(shù)據(jù)減少技術(shù) (DataReductionTechniques) 。

決策樹技術(shù)的軟件實現(xiàn)。將決策樹技術(shù)軟件化一直是決策樹技術(shù)的方向

之一。目前市場上的大多數(shù)據(jù)挖掘軟件如 SAS等都包含有決策樹技術(shù)部分。

以上這些決策樹的研究并不是孤立的, 它們經(jīng)常相互聯(lián)系、相互結(jié)合。決策樹技術(shù)早已被證明是利用計算機模仿人類決策的有效方法。 由于20世紀(jì)末人工智能陷于低潮, 此技術(shù)曾不被重視。值得慶幸的是, 由于數(shù)據(jù)挖掘技術(shù)的興起,作為模仿人類決策主要方法之一 , 近年來決策樹又重新引起了人們的興趣 , 并得到更廣泛的應(yīng)用。將決策樹技術(shù)與其他新興的技術(shù)相結(jié)合 ,決策樹技術(shù)將煥發(fā)出新的生命力。

數(shù)據(jù)挖掘分類算法的研究意義

目前分類挖掘在實際應(yīng)用中有著很重要的應(yīng)用價值， 在很多行業(yè)領(lǐng)域都取得一定的成功。比如:在股票市場上對每只股票的歷史數(shù)據(jù)進行分析，通過相應(yīng)的技術(shù)進行預(yù)測，從而做出相對比較準(zhǔn)確的判斷 ;彩票的購買也可以利用數(shù)據(jù)挖掘的分類或預(yù)測技術(shù)進行分析;在金融領(lǐng)域中將貸款對象分為低貸款風(fēng)險與高貸款風(fēng)險兩類。通過決策樹，我們可以很容易地確定貸款申請者是屬于高風(fēng)險的還是低風(fēng)險的。對于一個計算機銷售的系統(tǒng)，原有的數(shù)據(jù)庫信息已定，假定新的顧客添加到數(shù)據(jù)庫中，你想將新計算機的銷售信息通知顧客。 將促銷材料分發(fā)給數(shù)據(jù)庫所有的顧客的費用可能很高，這時你就可以通過建立分類模型，把資料只寄給那些可能購買新計算機的用戶，從而節(jié)省時間和費用，為你帶來更大的經(jīng)濟效益。由于決策樹方法在分類挖掘技術(shù)中有著獨特的優(yōu)勢， 而分類技術(shù)的應(yīng)用對整個市場的控制、公司的運營和個人的投資都有著很好的控制作用。 數(shù)據(jù)挖掘是一種決策支持過程，是深層次的數(shù)據(jù)信息分析方法，將數(shù)據(jù)挖掘技術(shù)應(yīng)用于成績評估方面是非常有益的，它可以全面地分析考試成績與各種因素之間隱藏的內(nèi)在聯(lián)系，比如，經(jīng)過對學(xué)生相關(guān)數(shù)據(jù)進行分析，數(shù)據(jù)挖掘工具可以回答諸如“哪些因素對

學(xué)生成績可能有影響”等類似的問題，這是傳統(tǒng)評價方法無法具備的。因此對基于決策樹的分類算法的研究有著多層次的研究價值和很高的應(yīng)用價值。

本文的主要內(nèi)容

第一章首先闡述了論文課題的研究背景、國內(nèi)外在數(shù)據(jù)挖掘領(lǐng)域的研究現(xiàn)狀以及論文的組織結(jié)構(gòu)。

第二章是本文的重點之一，詳細(xì)的闡述了決策樹分類模型的基本原理、工作的過程，并講述了它的核心算法——ID3算法的基本思想。在本章的最后介紹了ID3算法演變和改進來的其他幾種算法，并對它們進行了比較，做出概況性描述。

第三章也是本文的研究重點之一，因為ID3算法是經(jīng)典的數(shù)據(jù)處理算法，本

文主要研究ID3算法，給出了ID3算法的詳細(xì)描述和它的評價。分析用 ID3實現(xiàn)的決策樹，以及分類規(guī)則的提取。

第四章，用程序?qū)崿F(xiàn)ID3算法、對它的結(jié)果進行分析，實驗結(jié)果證明， ID3

算法是一種經(jīng)典的數(shù)據(jù)處理算法，運用它能夠解決生活中很多數(shù)據(jù)問題。

第五章對全文進行總結(jié)，提出了進一步的研究方向。 ID3算法還有一定的需要改進的地方，在以后的研究中將進行進一步的改進。

第二章決策樹分類算法相關(guān)知識

決策樹方法是目前應(yīng)用最廣泛的歸納推理算法之一， 是一種逼近離散值的方法，也可以把它看作是一個布爾函數(shù)。它是以實例為基礎(chǔ)的歸納學(xué)習(xí)，通常用來形成分類器和預(yù)測模型，著眼于從一組無次序、無規(guī)則的事例理出決策樹表示形成的分類規(guī)則。到目前為止決策樹有很多實現(xiàn)算法。

決策樹方法介紹

在解決分類問題的各種方法中，決策樹[8](DecisionTree，DT)是比較常用的一種方法，它是一種用于分類、聚類和預(yù)測的預(yù)測型建模方法，采用“分而治之”的方法將問題的搜索空間分為若干子集。應(yīng)用這種方法需要構(gòu)建一棵樹對分類過程進行建模。一旦建好了樹，就可以將其應(yīng)用于數(shù)據(jù)集中的元組并得到分類結(jié)果。在決策樹方法中，有兩個基本步驟:構(gòu)建樹和將樹應(yīng)用于數(shù)據(jù)集，一般都集中在如何有效的構(gòu)建樹的研究上。

決策樹的結(jié)構(gòu)

一棵決策樹是這樣一棵樹，該樹的每個非終端點均表示被考察數(shù)據(jù)項目的一個測試或決策。根據(jù)測試結(jié)果，選擇某個分支。為了分類一個特定數(shù)據(jù)項目，我們從根結(jié)點開始，一直向下判定，直到到達一個終端結(jié)點 (或葉子)為止。當(dāng)?shù)竭_一個終端結(jié)點時，一個決策樹便形成了。

決策樹是運用于分類的一種類似于流程圖的樹結(jié)構(gòu) [9]。其中的每個內(nèi)部節(jié)點(internalnode)代表對某個屬性的一次測試，一條邊代表一個測試結(jié)果，葉子(leaf)代表某個類(class)或者類的分布(classdistribution)。最上面的節(jié)點是根結(jié)點。下圖

給出一個商業(yè)上運用決策樹算法得到的一棵決策樹，如圖 2.1所示：

第

PAGE

13

頁,共52頁

圖2.1 DecisionTreedemo

這棵決策樹對“買計算機’，的銷售記錄進行分類。它表示了一個關(guān)心電子產(chǎn)品的用戶是否會購買PC機的知識，用它可以預(yù)測某條記錄(某個人)的購買意向。每個內(nèi)部節(jié)點(方形框)代表對某個屬性的一次檢測。每片葉子 (橢圓框)代表一個類(buys-computers=yes或者buys--computers=no)。這個例子中，樣本向量如

下:(age，student，credit--rating:buys-computers)，被決策數(shù)據(jù)的格式為(age，student，credit--rating)。輸入新的被決策的記錄，可以預(yù)測該記錄隸屬于哪個類。

決策樹的基本原理

決策樹的實現(xiàn)是以信息論原理為基礎(chǔ)的。信息論是香農(nóng)(C.E.Shannon)在1948

年建立的解決信息傳遞的不確定性的一系列理論，以數(shù)學(xué)的方法度量并研究信息。通過通信后對信源中各種符號出現(xiàn)的不確定程度的消除來度量信息量的大小，在這些理論中他提出了一系列概念：

自信息量。設(shè)X1，X2，,，Xn，為信源發(fā)出的信號，在收到Xi之前，收信者對信源發(fā)出信號的不確定性定義為信息符號的自信息量 I(Xi)，即

(2.1)

其中P(Xi)表示信源發(fā)出Xi的概率。

信息熵。自信息量只能反映符號的不確定性，而信息熵可以用來度量整個信源X整體的不確定性，定義如下:

(2.2)

其中i為信源X所有可能的符號數(shù)，即用信源每發(fā)一個符號所提供的平均自信息

第

PAGE

14

頁,共52頁

量來定義信息熵(平均信息量)。

條件熵。如果信源X與隨機變量Y不是相互獨立的，收信者收到信息Y，那么用條件熵 H(X/Y)來度量收信者在收到隨機變量 Y之后，對隨機變量 x仍然存在的不確定性。設(shè)X對應(yīng)信源符號Xi，Y對應(yīng)信源符號Yj，P(Xi/Yj)為當(dāng)Y為Yj時,X為Xi的概率，則有:

(2.3)

平均互信息量。用它來表示信號Y所能提供的關(guān)于X的信息量的大小，可用下式表示:

I(X，Y)=H(X)-H(X/Y) (2.4)

n

在信息論中是用熵(系統(tǒng)信息量的加權(quán)平均)（Entropy)來度量信息的不確定性。不確定性是一組消息的描述如M={m1，m2，,mn}。所有消息的產(chǎn)生是相互獨立的，消息集合中每個消息mi被接受的概率為P(mi)，它包含著一定的信息量，定義為I(mi)=-㏒2(mi)。例如:某個信息源總是發(fā)送同樣的信息，那么接收者就不需要更多的信息，此時信息源的熵就為 0，也就是沒有任何不確定性。相反，如果某個信息發(fā)送了n個不同的信息并且每個信息是相互獨立的， 此時熵的值就是

㏒2（熵是以二進制位的個數(shù)來編碼長度的，故用以 2為底的對數(shù)，后面描述的對數(shù)都是以2為底)。熵用在決策樹中是作為訓(xùn)練集純度的標(biāo)準(zhǔn)。在決策樹形成過程中，最重要的部分是對分裂屬性的選擇。

比較常用的一種方法是計算信息增益[10](InformationGain)。信息增益的原理

來自信息論，它是使某個屬性用來分割訓(xùn)練集而導(dǎo)致的期望熵降低。 因此，信息增益越大的屬性分裂數(shù)據(jù)集的可能性越大。 決策樹的形成就是遞歸的對數(shù)據(jù)集中的每個節(jié)點進行分裂，直到節(jié)點的所有類別都屬于同一類或沒有多余的屬性來劃分訓(xùn)練樣本集。

按照信息論的定義，設(shè)S是s個數(shù)據(jù)樣本的集合，類標(biāo)號屬性有n類樣本的訓(xùn)練數(shù)據(jù)集，每類有Si個實例，則把它們分類所需要的信息量 I用如下公式2.5表示為:

(2.5)

第

PAGE

15

頁,共52頁

Pi是任意樣本屬于類Ci的概率，用Si/S估計。

設(shè)屬性A具有v個不同的值{a1,a2,。。av}?？梢杂脤傩訟將S劃分為v個子集{S1,S2,。。Sv}:其中，Sj包含S中這樣的一些樣本，它們在A上具有值aj。假設(shè)選取A作為本次分類的屬性，則這些子集對應(yīng)于由包含集合 S的節(jié)點生長出來的分枝。設(shè)sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵(entropy)由公式得出:

(2.6)

其中項 為第j個子集的權(quán)值，并等于子集（即 A為aj)中的樣本個數(shù)除以S中的樣本總數(shù)。由信息論定義知 :熵值越小，子集劃分的純度越高。因此對應(yīng)給定的子集Sj有：

(2.7)

其中： 是Sj中的樣本屬于Ci的概率。

在A上的分支將獲得的編碼信息即節(jié)點的信息增益為：

(2.8)

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

決策樹的剪枝

當(dāng)決策樹創(chuàng)建時，由于數(shù)據(jù)中的噪聲和孤立點，許多分支反映的是訓(xùn)練數(shù)據(jù)

[11]

中的異常。剪枝 方法處理這種過分適應(yīng)數(shù)據(jù)問題。通常使用統(tǒng)計度量，剪去

最不可靠的分支，這將導(dǎo)致較快的分類，提高樹獨立于測試數(shù)據(jù)正確分類的能力。主要有兩類剪枝方法:

同步修剪(pre-pruning):

在建樹的過程中，當(dāng)滿足一定條件，例如 InformationGain 或者某些有效

第

PAGE

18

頁,共52頁

統(tǒng)計量達到某個預(yù)先設(shè)定的閾值時，節(jié)點不再繼續(xù)分裂，內(nèi)部節(jié)點成為一個葉子節(jié)點。葉子節(jié)點取子集中頻率最大的類作為自己的標(biāo)識，或者可能僅僅存儲這些實例的概率分布函數(shù)。然而，選取一個適當(dāng)?shù)拈撝凳抢щy的，因為較高的閾值可能導(dǎo)致過分簡化的數(shù)，而較低的閾值可能使得樹的化簡太少。

遲滯修剪(pos-pruning):

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

決策樹的特性

決策樹有很多的優(yōu)點，是實際應(yīng)用和學(xué)術(shù)研究領(lǐng)域最普遍采用的方法之一。主要特點有：

1．靈活性

決策樹不需要對數(shù)據(jù)的分布進行任何假設(shè)，它是非參數(shù)方法。事例空間被分成子空間，每一個子空間適用于不同的模型。一棵決策樹能完全包含一個事例空間，如果有足夠的數(shù)據(jù)，它能近似任意函數(shù)的最優(yōu)貝葉斯錯誤率。

2．健壯性[12]

對單變量經(jīng)過單調(diào)轉(zhuǎn)換后的輸入，單變量樹的輸出是不變的。例如，對 x，log2x,或者作為第j個輸入變量，會產(chǎn)生同樣結(jié)構(gòu)的樹。因此沒有必要考慮輸入變量的轉(zhuǎn)換式。另外由于對內(nèi)部屬性進行了選擇，相對于有不相關(guān)輸入變量的情況，而產(chǎn)生的樹更加具有健壯性。

可解釋性

全面的和復(fù)雜的決策可以通過一系列簡單和局部的決策近似取得。所有的決策都是用來描述該問題的屬性值上的。決策樹具有這兩個特性，具有可理解性和可解釋性，它們是決策樹被廣泛使用的原因。

速度

決策樹算法采用自上而下，分而治之，不需要回溯戰(zhàn)略的一種貪婪算法。時間復(fù)雜是與例子的數(shù)目成線性關(guān)系的。

同樣，決策樹也面對一些問題:

分塊

分塊使得數(shù)據(jù)被分成較小的子集。假定每次分枝數(shù)據(jù)都分成相等大小的數(shù)

目，那決策樹所要測試的屬性的復(fù)雜度不大于 O(logn)。在有許多相關(guān)屬性的情形下，這是理想的結(jié)果。

復(fù)制

子樹的復(fù)制指的是在不同的分枝復(fù)制相同的屬性測試。 由于屬性間存在相關(guān)性項性(一個結(jié)果可由多個條件決定)，例如，布爾函數(shù)f=X1X2+X3X4中屬性X1和X2，或者屬性X3屬性X4間不是相互獨立的，而是存在相關(guān)性;另外該布爾函數(shù)有多個乘積項X1X2和X3X4。出現(xiàn)這種情況時，生成的決策樹會有子樹復(fù)制問題。復(fù)制現(xiàn)象導(dǎo)致決策樹理解，同時還導(dǎo)致分塊問題 :當(dāng)樹很大時，會造成數(shù)據(jù)集的劃分越來越小，從而性能越差。

缺值

決策樹是一種層次測試方法，如果某個屬性值未知的話，就會難以決定下一步分枝，因此必須使用特殊的機制來處理缺值的問題。

連續(xù)屬性

決策樹算法的瓶頸是對連續(xù)屬性的處理。在這種情況下，要在每一個節(jié)點對每一個屬性進行一系列的操作。有學(xué)者認(rèn)為處理許多的連續(xù)屬性的操作占決策樹構(gòu)造過程70%的時間。

不穩(wěn)定性

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

決策樹的適用問題

盡管已經(jīng)開發(fā)的每種決策樹算法有這樣或那樣不太一致的能力和要求， 通常

[13]

決策樹算法最適合具有以下特征的問題 :

實例是由“屬性一值”對表示的:實例是用一系列固定的屬性和它們的值來描述的。在最簡單的決策樹學(xué)習(xí)中，每一個屬性取少數(shù)的離散的值。但擴展的算法允許處理值域為實數(shù)的屬性。

目標(biāo)函數(shù)具有離散的輸出值:(例如最常見的布爾類型的分類:yes 或

no)。決策樹方法很容易擴展到學(xué)習(xí)有兩個以上輸出的函數(shù)。

可能需要析取的描述，決策樹很自然的可以代表析取表達式。

訓(xùn)練數(shù)據(jù)可以包含錯誤:決策樹學(xué)習(xí)對錯誤有很好的健壯性，無論是訓(xùn)練樣例所屬的分類錯誤還是描述這些樣例的屬性值錯誤。

訓(xùn)練數(shù)據(jù)可以包含缺少屬性值的實例:決策樹學(xué)習(xí)甚至可以在有未知屬性值的訓(xùn)練樣例中使用。

己經(jīng)發(fā)現(xiàn)很多實際的問題符合這些特征，所以決策樹學(xué)習(xí)己經(jīng)被應(yīng)用到很多問題中。例如根據(jù)疾病分類患者;根據(jù)起因分類設(shè)備故障;根據(jù)拖欠支付的可能性分類貸款申請。對于這些問題，核心任務(wù)是要把樣例分類到各個可能的離散值對應(yīng)的類別中。

ID3 分類算法基本原理

在本章的開始就已經(jīng)提到了決策樹的生成到目前為止有很多種算法，但它們多數(shù)是圍繞決策樹的核心算法ID3演變而來的。在本文主要是對ID3算法研究和設(shè)計實現(xiàn)，具體的內(nèi)容將在下一章詳細(xì)介紹。

早期著名的決策樹算法是1986年由Quinlan提出的ID3算法[14].給出ID3

算法ID3tree(T.Tattributelist) 的具體描述。其中，假設(shè)用 T代表當(dāng)前樣本集，當(dāng)前的候選屬性集用 T-attributelist 表示，候選屬性集中的所有屬性皆為離散型，連續(xù)值屬性必須事先經(jīng)過預(yù)處理轉(zhuǎn)化為離散型。

ID3算法運用信息熵理論，選擇當(dāng)前樣本集中具有最大信息增益值的屬性作

為測試屬性;樣本集的劃分則依據(jù)測試屬性的取值進行，測試屬性有多少不同取值就將樣本集劃分為多少子樣本集，同時，決策樹上相應(yīng)于該樣本集的節(jié)點長出

第

PAGE

19

頁,共52頁

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

給出ID3算法信息增益求值[15]的算法:

設(shè)S是s個樣本的集合。假定類別屬性具有 m個不同值，定義m個不同類Ci(i=l，,,，m)。設(shè)si 是Ci中的樣本數(shù)。對一個給定的樣本集，它總的信息熵I值由公式2.9給出：

Pi是任意樣本屬于類別Ci的概率，用Si/S估計。

(2.9)

設(shè)屬性A具有v個不同的值?？梢杂脤傩訟(a1,a2,。。av)，將S劃分為v個子集{S1,S2,。。Sv};其中，Sj包含S中這樣的一些樣本，它們在A上具有值aj，。假設(shè)選取A作為本次分類的屬性，則這些子集對應(yīng)于由包含集合S的節(jié)點生長出來的分枝。設(shè)sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵(entropy)由公式2.10得出:

(2.10)

其中， (2.11)

是Sj中類為Ci的樣本的概率，最后，用屬性A劃分樣本集S后所得的信息增益值由公式 2.12給出：

(2.12)

選擇屬性A使Entropy(E/A)最小，則信息增益將增大。也就是說， Gain(A)

是由于知道屬性A的值而導(dǎo)致的熵的期望壓縮。為了使下一步所需的信息量最

第

PAGE

20

頁,共52頁

小，要求每一次都選擇其信息增益最大的屬性作為決策樹的新結(jié)點， 并對屬性的每個值創(chuàng)建分枝，依據(jù)此思想劃分訓(xùn)練數(shù)。

ID3是一個典型的決策樹學(xué)習(xí)系統(tǒng)，它檢驗數(shù)據(jù)集的所有特征，它以信息增益作為分離目標(biāo)評價函數(shù)，采用自頂向下，分而治之不可返回的策略，選取決策樹的分裂點，對每個分支的子集采用遞歸調(diào)用同種方法建立決策樹結(jié)點和分枝，直到某一子集中的數(shù)據(jù)都屬于同一類。

其它常見決策樹算法

經(jīng)典的ID3算法在1986年由Quinlan提出后有許多學(xué)者對此算法進行了大量的研究，先后出現(xiàn)了以C4.5、CART、SLIQ、SPRINT等較新的有關(guān)決策樹分類的算法，下面簡要描述這幾種算法的基本概念和思想。

C4.5算法

C4.5算法是Quinlan在1993年針對ID3存在的一些缺點提出的，它是ID3

算法的后繼，同時也成為后面諸多決策樹算法的基礎(chǔ)。 C4.5是ID3的改進版本

[23]

[16]。它主要在以下幾個方面對 ID3作了改進:缺省值的預(yù)測屬性仍可用,提出了修剪思想,可以進行規(guī)則推導(dǎo)。特別是在應(yīng)用單機的決策樹算法中， C4.5算法不僅分類準(zhǔn)確率高而且速度快。C4.5算法在ID3的基礎(chǔ)上彌補了對連續(xù)型屬性、屬性值空缺情況的處理 ，對樹剪枝也進行了處理。與 ID3不同，C4.5采用基于信息增益率(information gainratio) 的方法選擇測試屬性。信息增益率等于信息增益對分割信息量(split information) 的比值。對樣本集T，假設(shè)J是有S個不同取值的離散屬性，用J分割樣本集所得信息增益的算法同 ID3算法。分割

信息量由公式： 給出。其中|T|為數(shù)據(jù)集T的例子數(shù);假設(shè)a是在連續(xù)區(qū)間取值的連續(xù)型屬性，首先將樣本集T按屬性a的取值從小到大排序，一般用快速排序法。假定排好后屬性的取值序列為 v1，v2，,，vm，則對i∈（l，m-1），有值v=(vi+vi+1)/2 和按值V劃分的兩個子樣本集:，這樣劃分所得的信息增益記為Gain。線性地掃描序列v1，v2，,，vm，找出v’，使得Gainv’最大，則v’稱為局部閾值。則按連續(xù)屬性a劃分樣本集T的信息增益為Gain，T被劃分為Tvl’，Tv2’兩個子集，在此劃分上求出的信息增益率為連續(xù)屬性a的最終信息增益率。而在序列v1，v2，,，vm，中找到的最接近但又

第

PAGE

21

頁,共52頁

不超過局部閾值v’的取值v*成為當(dāng)前節(jié)點在屬性a上的分割閾值。按照上述方法求出當(dāng)前候選屬性集中所有屬性的信息增益率，比較它們找出信息增益率最高的屬性，若為離散屬性，則按照該屬性的不同取值分割當(dāng)前樣本集 ;若為連續(xù)屬性，則依據(jù)它的分割閾值，將當(dāng)前樣本集分為兩個子樣本集。對每個子樣本集用同樣的方法繼續(xù)分割直到不可分割或到達停止條件為止。

當(dāng)訓(xùn)練集中含有的一些樣本在某些屬性上的值空缺，該算法為每個樣本設(shè)

立的初始權(quán)值為1.0。當(dāng)從樣本訓(xùn)練集T中選擇了測試屬性A將T劃分S個子樣本集T1，T2，,Tn，對每個子樣本集Ti，它包含的樣本為T中A=ai和A值空缺的樣本。Ti中含空缺值的樣本的權(quán)值成正比于Ti中A值不空缺的樣本數(shù)對T中A值不空缺的樣本數(shù)的比值。

在生成決策樹后，就開始計算每個節(jié)點的分類錯誤進行樹剪枝。對每個葉子節(jié)點，分類錯誤為該節(jié)點中不屬于該節(jié)點所表示類別的樣本的權(quán)值之和 ;對于非葉節(jié)點，分類錯誤為它的各個孩子節(jié)點的分類錯誤之和。如果計算出某節(jié)點 N的分類錯誤超過了將節(jié)點 N所代表的樣本集T中的所有樣本分配為T中出現(xiàn)最多的類別所得的分類錯誤，則將節(jié)點 N的所有子枝剪去，使N成為葉節(jié)點，將T中出現(xiàn)最多的類別分配給它。由于 C4.5采用訓(xùn)練樣本集來估計分類錯誤，因此使得到的決策樹模型融入了訓(xùn)練集中的異常，而這些異常通常在總體樣本中并不出現(xiàn)，從而導(dǎo)致決策樹傾向于過度擬合。這個缺陷可以使用一種悲觀估計來補償，選擇一組獨立于訓(xùn)練樣本集的測試集來優(yōu)化決策樹。

比較ID3算法，C4.5算法在效率上有了很大的提高[24]。不僅可以直接處理連續(xù)型屬性，還可以允許訓(xùn)練樣本集中出現(xiàn)屬性空缺的樣本。 生成的決策樹的分枝也較少。但是，C4.5算法在選擇測試屬性，分割樣本集上所采用的技術(shù)仍然沒有脫離信息熵原理，因此生成的決策樹仍然是多叉樹。如果想生成結(jié)構(gòu)更為簡潔的二叉樹，必須采用新的原理來分割樣本集。

CART算法

CART[17]是(ClassficationAndRegressionTree) 的簡稱，可以處理高度傾斜或多態(tài)的數(shù)值型的數(shù)據(jù)，它與ID3、C4.5算法的最大不同之處是采用的分裂節(jié)點的標(biāo)準(zhǔn)，它采用的是計算GINI系數(shù)[29]，GINI系數(shù)越小劃分越合理，樣本的純度也越高，劃分的效果越好。

第

PAGE

22

頁,共52頁

2

例如，對訓(xùn)練集T，gini(T)=1- ∑pj。其中pj是類別j在T中出現(xiàn)的概率。若 T 被劃分為 T1 ，T2 ，則此次劃分的 GIN1 系數(shù)為

其中，S是T中樣本的個數(shù)，s1，s2分別為T1，T2中的樣本個數(shù)。對候選屬性集中的每一個屬性， CART算法計算該屬性上每種可能劃分的GINI系數(shù)，找到GINI系數(shù)最小的劃分作為該屬性上的最佳劃分，然

后比較所有候選屬性上最佳劃分的 GINI系數(shù)，擁有最小劃分GINI系數(shù)的屬性成

為最終測試屬性。與ID3、C4.5的算法只為葉子節(jié)點分配類別不同，CART算法考慮到每個節(jié)點都有成為葉子節(jié)點的可能， 對每個節(jié)點(包括葉節(jié)點和非葉節(jié)點)都分配類別。分配類別的方法可以用當(dāng)前節(jié)點中出現(xiàn)最多的類別， 也可以參考當(dāng)前節(jié)點的分類錯誤或其它的方法。CART算法在下列條件之一滿足時停止構(gòu)建決策樹:(l) 所有節(jié)點中的樣本數(shù)為1或樣本屬于同一類;(2)決策樹高度到達用戶設(shè)置的閥值。

SLIQ算法

ID3 、C4.5等算法對規(guī)模較小的，可以全部放入主存的訓(xùn)練數(shù)據(jù)集很有效，但當(dāng)訓(xùn)練樣本集大到不能全部放入主存時，這些算法的效率明顯降低。為了提高算法的可伸縮性，使之對大規(guī)模訓(xùn)練數(shù)據(jù)集也能有效地生成分類模型， 需要對傳統(tǒng)的算法進行改進。一種改進方法是:首先將訓(xùn)練樣本集劃分成若干子集，使得每一個子集都能完全放入主存;然后對每個子集分別構(gòu)造一棵決策樹 ;再將這些樹綜合，得到最終的決策樹。這種算法與前面介紹的算法相比，減少了運行時間。但生成的決策樹分類準(zhǔn)確率有所下降。

SLIQ[18](SupervisedLearningInQuest) 算法是IBM研究人員提出的一種快速可伸縮的適合處理較大規(guī)模數(shù)據(jù)的決策樹分類算法。 SLIQ算法首次提出在算法中運用一些特殊數(shù)據(jù)結(jié)構(gòu)如屬性表和類表。 SLIQ算法在執(zhí)行過程中需要隨時修改類表，因此類表常駐內(nèi)存，而類表的大小會隨著訓(xùn)練集增大而增大，因此SLIQ算法受到主存容量的限制。

由于使用了新的數(shù)據(jù)結(jié)構(gòu)，SLIQ算法可并行化。在有多處理器的并行環(huán)境

中，假設(shè)每個處理器都各自擁有獨立的主存和輔存。 SLIQ算法可將屬性表平均分配給各個處理器，使決策樹的生成并行進行。對于類表，可以讓每個處理器都

第

PAGE

28

頁,共52頁

有一份，或?qū)⑺指詈蠓纸o各個處理器。根據(jù)對類表的不同處理，并行 SLIQ算法可分為SLIQ/R和SLIQ/D兩種版本。SLIQ/R為每個處理器都拷貝一份全局的類表。在各個處理器并行掃描屬性表的過程中，對某個處理器中的類表進行的修改都要及時更新到各個處理器的類表中。處理器間要不斷通信，保證每一時刻各個處理器上的類表一樣。SLIQ/D將類表分割后再平均分給各個處理器。它的問題是，在某個處理器中掃描到的屬性項，它對應(yīng)的類表可能在另一個處理器中，

處理器間也要通過通信來更新類表。

SPRINT算法

SPRINT(Scalable Parallelizable Induction ofClassification Tree)

算法的提出其目的是解決主存容量的受限問題，并能處理大規(guī)模的訓(xùn)練樣本集，有效的生成決策樹模型。SLIQ算法要求類表駐留內(nèi)存,當(dāng)訓(xùn)練集增加，導(dǎo)致類表

放不進內(nèi)存時，SLIQ算法就無法進行，這限制了SLIQ處理數(shù)據(jù)的最大規(guī)模[19]。SPRINT算法使用了與SLIQ算法不同的數(shù)據(jù)結(jié)構(gòu)。不使用獨立的類表，而是為每個屬性建立一個屬性表，表項形如(屬性值，類別，樣本序號)連續(xù)屬性的屬性表要按屬性值預(yù)排序;離散屬性表則沒有預(yù)排序過程。屬性表不須常駐內(nèi)存。在建

樹過程中，SPRINT為每個待分裂節(jié)點設(shè)立一個類直方圖。它記錄了每個不同取值的樣本在各個類別中的個數(shù)。當(dāng)測試條件形成，節(jié)點分裂時，屬性表也分裂到新的葉節(jié)點中。每個待分裂的葉節(jié)點對應(yīng)一張屬性表， SPRINT掃描屬性表尋找最佳分割，計算最佳分割的信息可從相應(yīng)的直方圖獲得，因此計算每次分割至多只需要一張屬性表的直方圖常駐內(nèi)存。由于直方圖的大小不會隨屬性表的增大而增大，SPRINT算法完全擺脫了主存容量的限制。

SPRINT建樹具體步驟如下:

生成根節(jié)點，并為所有屬性建立屬性表，同時預(yù)排序連續(xù)屬性的屬性表。

如果節(jié)點中的樣本可歸成一類，則算法停止 ;否則轉(zhuǎn)3);

利用屬性表尋找擁有最小Gini值的劃分作為最佳劃分方案。算法依次掃描該節(jié)點上的每張屬性表。由于計算 Gini 值需要該節(jié)點上直方圖的信息，因此處理每一張屬性表前均要清空并初始化直方圖。對于連續(xù)屬性 A，要求初始化Cbelow為0。，Cabove為該節(jié)點上的樣本關(guān)于A的總體分布。每掃描A屬性表的一條記錄(設(shè)屬性值為v)，都要更新一次Cbelow和Cabove且計算對應(yīng)于劃分A

≦v的Gini 值。這樣，一遍掃描完A屬性表，就可得到該節(jié)點上關(guān)于 A屬性的最佳劃分，并記錄下來。對于離散屬性，先清空 countmatrix ，在掃描B屬性表的同時更新countmatrix ，掃描完后，根據(jù)構(gòu)造好的countmatrix 求解最佳劃分中的S，并記錄下來。當(dāng)掃描完該節(jié)點的所有屬性表時就可得到該節(jié)點的最佳劃分方案。

根據(jù)劃分方案，生成該節(jié)點的兩個子節(jié)點 N1，N2。

劃分該節(jié)點上的各屬性表，使之關(guān)聯(lián)到 N1或N2上。首先劃分測試屬性的屬性表:依次掃描記錄<屬性值x，類別屬性c，樣本號id>，判斷x屬于哪個孩子，然后將該條記錄移至該孩了節(jié)點的新屬性表中，同時將 id 值寫入Hash表，以保存劃分后樣本所在孩子節(jié)點的信息。然后劃分其余屬性表 :依次掃描記錄，依據(jù)樣本號查找Hash表中該樣本劃分后所在的孩子節(jié)點，然后將該記錄移至該孩子節(jié)點的新屬性表中。

分別轉(zhuǎn)2）考察N1、N2節(jié)點。

通過實踐表明，在SLQI的類表可以存進內(nèi)存的情況下，SPRINT比SLQI執(zhí)行得慢;然而在訓(xùn)練數(shù)據(jù)集規(guī)模超過SLIQ能承受得最大規(guī)模后，SPRINT的效率比SLIQ的要好得多，且數(shù)據(jù)量越大，SPRINT的效率越高。

PUBLIC算法

上述含有剪枝的算法都是分成兩步進行，即先建樹再剪枝。而 Rageev.R等人在1998年提出的PUBLIC算法將建樹、剪枝結(jié)合到一步完成，在建樹階段不生成會被剪枝的子樹，因而大大提高了效率。 PUBLIC的建樹基于SPRINT方法、剪枝基于MDL（最小描述長度法）原則[20]。PUBLIC采用低估策略正過高的代價估算來防止過度剪枝，即對將要擴展的葉節(jié)點計算編碼代價的較低閾值， 而對于另兩類葉節(jié)點(剪枝形成的、不能被擴展的)，估算方法不變。計算較低閾值的方法有多種，但最簡單有效的方法是將它設(shè)置為 1。

決策樹算法總結(jié)比較

以上對各種決策樹作了簡單的介紹，下面我們對決策樹做一下比較和評估，對決策樹方法的比較可采用下面的標(biāo)準(zhǔn)：

在選擇測試屬性技術(shù)方面： ID3算法采用信息增益作為測試屬性，信息最小的熵作為根結(jié)點，C4.5算法采用信息增益率作為測試屬性，而CART算法，

SLIQ算法，SPRINT算法則都采用GINI系數(shù)作為測試屬性。

在連續(xù)屬性的處理技術(shù)方面：ID3算法采用離散化技術(shù)，C4.5算法，

CART算法，SLIQ算法，SPRINT算法則都采用預(yù)排序方法來處理連續(xù)屬性。

在剪枝方法方面：ID3，C4.5算法和CART算法采用分類錯誤方法對決策樹進行修剪，而SLIQ和SPRINT算法則采用MDL方法對決策樹進行修剪。

在測試樣本方面：ID3算法需要獨立的測試樣本，而C4.5算法，CART

算法，SLIQ算法，SPRINT算法都不需要獨立的測試樣本。

在可伸縮性的評估方面：ID3算法，C4.5算法，CART算法的可伸縮性較差，而SPRINT算法的可伸縮性好，而SLIQ算法相比較前幾種算法，可伸縮性就相對較好一些。

在并行性方面：ID3算法，C4.5算法，CART算法的并行性就差一些，

而SPRINT算法的并行性就比前幾個算法好一些，而SLIQ算法的并行性相比前幾個就更好一些。

在結(jié)構(gòu)方面：ID3算法和C4.5算法生成的決策樹是多叉樹，而CART

算法，SLIQ算法，SPRINT算法生成的決策樹則是以二叉樹的形式存在。

ID3算法，C4.5算法，CART算法，SLIQ算法，SPRINT算法中剪枝的算法都是分成兩步進行，即先建樹再剪枝，而 PUBLIC算法的建樹基于SPRINT方法，剪枝基于MDL（最小描述長度法）原則將建樹、剪枝結(jié)合到一步完成，在

建樹階段不生成會被剪枝的子樹，因而大大提高了效率。

實現(xiàn)平臺簡介

本實驗在java_jdk_1_5_0_04平臺上實現(xiàn)，java_jdk_1_5_0_04是在WindowsXP操作系統(tǒng)上的最新版本[41]。1995年Java語言剛一推出，便以其純面向?qū)ο蟆⑵脚_無關(guān)性、多線程、高安全性、良好的可移植性和可擴展性等特性，受到了計

算機界的普遍歡迎，并得到了廣泛的應(yīng)用和發(fā)展。近幾年來，Java的應(yīng)用已經(jīng)擴展到各個應(yīng)用領(lǐng)域，加上各種功能配件的推陳出新，使得Java能夠滿足產(chǎn)品開發(fā)的需求，成為網(wǎng)絡(luò)時代最流行的程序設(shè)計語言。利用Java來開發(fā)軟件，具有跨平臺、易整合、易擴展的優(yōu)點。

（1）Java的產(chǎn)生：

1991年初，美國加州的SunMicrosystem公司(以下簡稱Sun公司)成立了

一個以JamesGosling為首、名為Green的項目研發(fā)小組，其目標(biāo)是開發(fā)一個面向家用電器市場的軟件產(chǎn)品，用軟件實現(xiàn)一個對家用電器進行集成控制的小型控

制裝置。他們首先注意到這個產(chǎn)品必須具有平臺獨立性，即讓該軟件在任何 CPU上都能運行。為達到此目的，Gosling首先從改寫C++語言的編譯器著手。但是，他們很快便意識到這個產(chǎn)品還必須具有高度的簡潔性和安全性， 而C++在這方面顯然無法勝任。因此，Gosling決定自行開發(fā)一種新的語言，并將該語言命名為Oak(橡樹)。Oak是Green項目小組開發(fā)的一個名為“*7”(Star Seven)產(chǎn)品中的一個組成部分。StarSeven 是一個集成了Oak、GreenOS(一種操作系統(tǒng))、用戶接口模塊和硬件模塊四個部分的類似于 PDA(PersonalDigitalAssistant ，個人數(shù)字助理)的設(shè)備。

有趣的是，在這段時間里，WWW的發(fā)展卻如日中天。1993年7月，伊利諾斯

大學(xué)的NCSA推出了一個在Internet 上廣為流行的WWW瀏覽器Mosaic1.0 版。然而，這時的WWW頁面雖然內(nèi)容豐富，可以實現(xiàn)聲、圖、文并茂，但它卻是靜態(tài)的，若想增強WWW的動感，需要通過一種機制來使它具有動態(tài)性。其解決方案顯然是嵌入一種既安全可靠，又非常簡練的語言。 Oak完全滿足這一要求。但是，要將它推向市場，為人們所廣泛接受，還必須采用一種合適的策略。 1994年，Sun公司的創(chuàng)始人之一BillJoy 的介入，使Oak成為Java而得以走紅。

Java的特點：

Sun公司在“Java 白皮書”中對 Java的定義是：“Java:Asimple,object-oriented, distributed, interpreted, robust, secure,architecture-neutral,portable,high-performance,multi-threaded,and

dynamiclanguage.”。按照這個定義，Java是一種具有“簡單、面向?qū)ο蟮?、分布式、解釋型、健壯、安全、與體系結(jié)構(gòu)無關(guān)、可移植、高性能、多線程和動態(tài)執(zhí)行”等特性的語言。下面我們簡要敘述 Java的這些特性。

1）簡單性

Java 語言簡單而高效，基本Java系統(tǒng)(編譯器和解釋器)所占空間不到250KB。Gosling等人在設(shè)計Java之初，是從改寫C++編譯器入手