畢業(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 決策樹分類算法

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

4、;　　2.1.2決策樹的基本原理13</p><p>　　2.1.3決策樹的剪枝15</p><p>　　2.1.4決策樹的特性16</p><p>　　2.1.5決策樹的適用問題18</p><p>　　2.2 ID3分類算法基本原理18</p><p>　　2.3其它常見決策樹算法20</p>

5、;<p>　　2.4決策樹算法總結(jié)比較24</p><p>　　2.5實(shí)現(xiàn)平臺(tái)簡介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決策樹模型的建立34</p><p>　　3.2.1 決策樹的生成34</p><p>　　3.2.2 分類規(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生成的決策樹40</p><p>　　4.1.2 分類規(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ā)展的今天，面對海量數(shù)據(jù)的出現(xiàn)，如何有效利用海量的原始數(shù)據(jù)分析現(xiàn)狀和預(yù)測未來，已經(jīng)成為人類面臨的一大挑戰(zhàn)

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

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

11、法，并對結(jié)果進(jìn)行分析，決策樹生成，分類規(guī)則的提取，以便于以后直接使用這一規(guī)則進(jìn)行數(shù)據(jù)分析。在論文的最后一章介紹了目前數(shù)據(jù)挖掘技術(shù)的研究前景。</p><p>　　關(guān)鍵詞:數(shù)據(jù)挖掘；決策樹；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>　　最近幾十年以來，隨著互聯(lián)網(wǎng)的發(fā)展和企業(yè)信息化程度的日益提高，科研政府部門普遍使用電子事物處理技術(shù)，商品條形碼被廣泛使用，以及電子商務(wù)和科學(xué)數(shù)據(jù)庫的急劇增長為我們帶來了海量的數(shù)據(jù)。激增的數(shù)據(jù)背后隱藏著許多重要的信息，人們希望能夠?qū)ζ溥M(jìn)行更高層次的分析，以便更好地利用這

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

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

22、已經(jīng)是解決目前信息系統(tǒng)中普遍面臨的“數(shù)據(jù)爆炸”而“信息缺乏”狀況的最有效的手段之一，并且它的研究領(lǐng)域具有較大的研究意義和較多的研究方向一度成為數(shù)據(jù)庫研究界最熱的研究方向，擁有人數(shù)眾多的研究群體，受到學(xué)術(shù)界和企業(yè)界的極大關(guān)注。多學(xué)科的相互交融和相互促進(jìn)，使得這一學(xué)科得以蓬勃發(fā)展，而且已初具規(guī)模。并行計(jì)算、計(jì)算機(jī)網(wǎng)絡(luò)和信息工程等其他領(lǐng)域的國際學(xué)會(huì)、學(xué)刊也把數(shù)據(jù)挖掘和知識(shí)發(fā)現(xià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)，它可以說是數(shù)據(jù)庫研究中的一個(gè)非常有應(yīng)用價(jià)值的新領(lǐng)域，它融合了數(shù)據(jù)庫、人工智能、機(jī)器學(xué)習(xí)、數(shù)理統(tǒng)計(jì)學(xué)、模糊數(shù)學(xué)等多個(gè)領(lǐng)域的理論和技術(shù)。從數(shù)據(jù)分析的觀點(diǎn)來看，數(shù)據(jù)挖掘分為兩類:描述性數(shù)據(jù)挖掘和預(yù)測性數(shù)據(jù)挖掘。描述性數(shù)據(jù)挖掘以概要方式描述數(shù)據(jù)，提供數(shù)據(jù)所具有的一般性質(zhì);預(yù)測性數(shù)據(jù)挖掘分析數(shù)據(jù)，建立一個(gè)或一組

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

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

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

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

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

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

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

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

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

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

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

36、造方法有統(tǒng)計(jì)方法、神經(jīng)網(wǎng)絡(luò)方法及機(jī)器學(xué)習(xí)方法等。統(tǒng)計(jì)方法包括貝葉斯法和非參數(shù)法(近鄰學(xué)習(xí)或基于事例的學(xué)習(xí))，對應(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ì)是一種非線性的判別函數(shù)。機(jī)器學(xué)習(xí)方法包括決策樹法和規(guī)則歸納法，前者對應(yīng)的表示是決策樹或判別樹，后者則一般為產(chǎn)生式規(guī)則。另外，近年來又出現(xiàn)了一種稱

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

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

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

40、的數(shù)據(jù)，并能有效的和操作系統(tǒng)結(jié)合。這一代數(shù)據(jù)挖掘系統(tǒng)的關(guān)鍵技術(shù)之一是提高對建立在異質(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ā)展，每年市場上都會(huì)出現(xiàn)新的數(shù)據(jù)挖掘系統(tǒng)，各大數(shù)據(jù)庫軟件公司也分別推出了自己的數(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é)家合作開發(fā)的用于幫助天文學(xué)家發(fā)現(xiàn)遙遠(yuǎn)的類星體的一個(gè)工具。SKICAT的任務(wù)是構(gòu)造星體分類器對星體進(jìn)行分類，使用了決策樹方法構(gòu)造分類器，結(jié)果使得能分辨的星體較以前的方法在亮度上要低一個(gè)數(shù)量級(jí)之多，而且新的方法比以往的方法要在效率上要高40倍以上。數(shù)據(jù)挖掘在生物學(xué)上的應(yīng)用主要集中于分子生物學(xué)特別是基因工程的研究上。進(jìn)幾年，通過用計(jì)算生物分子系統(tǒng)分析法，尤其是基因數(shù)據(jù)庫搜索技術(shù)

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

44、、商務(wù)管理、過程控制、市場分析、工程設(shè)計(jì)和科學(xué)研究等眾多領(lǐng)域，這些領(lǐng)域的管理決策層可以通過對歷史數(shù)據(jù)的分析，發(fā)現(xiàn)諸如市場供需規(guī)律、商品價(jià)格走勢、家庭收入與消費(fèi)特點(diǎn)、購買商品的習(xí)慣等規(guī)律，以支持企業(yè)的生產(chǎn)、經(jīng)營和銷售決策。</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ù)據(jù)挖掘在因特網(wǎng)上的應(yīng)用主要包括三種:在搜索引擎上(Search Engine)對文檔進(jìn)行自動(dòng)分類、幫助用戶尋找感興趣的新聞以及利用數(shù)據(jù)挖掘設(shè)計(jì)一個(gè)電子新聞過濾系統(tǒng)。它利用文本學(xué)習(xí)建立起該用戶的趣向模型，當(dāng)用戶進(jìn)入一份電子報(bào)紙的網(wǎng)頁時(shí)，該系統(tǒng)就會(huì)根據(jù)學(xué)習(xí)所得的模型對其中的每一篇文章按與用戶的興趣的接近程度進(jìn)行打分排序，以便使用戶看到他最感興趣的新聞。<

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

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

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

49、問題是，如何從復(fù)雜的數(shù)據(jù)例如多媒體結(jié)構(gòu)化的數(shù)據(jù)中提取有用的信息，對多層次數(shù)據(jù)庫的維護(hù)，以及如何處理數(shù)據(jù)的異類性和自主性等等。</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ù)庫、知識(shí)庫、專家系統(tǒng)、決策支持系統(tǒng)、可觀化工具、網(wǎng)絡(luò)等多項(xiàng)技術(shù)集成的系統(tǒng)。</p>

50、<p>　?。?）遺漏的噪聲數(shù)掘</p><p>　　這個(gè)問題在商業(yè)數(shù)據(jù)庫中尤其突出，據(jù)報(bào)告，美國人口調(diào)查數(shù)據(jù)的錯(cuò)誤率上升到20%。如果不經(jīng)認(rèn)真考慮就來設(shè)計(jì)待挖掘數(shù)據(jù)庫，重要的屬性可能會(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ī)則、自然語言生成以及數(shù)據(jù)和知識(shí)的可視化等技術(shù)，提高挖掘結(jié)果的可理解性。</p><p>　　（6）私有數(shù)據(jù)的保護(hù)與數(shù)據(jù)安全性</p><p>　　當(dāng)我們可以在不同的角度和不同的層次看到數(shù)據(jù)庫中的數(shù)據(jù)時(shí)，這與我們保護(hù)數(shù)據(jù)的安全性和保護(hù)私人數(shù)據(jù)的目標(biāo)相抵觸。因此對在什么情況下數(shù)據(jù)挖掘?qū)?huì)導(dǎo)致對私有數(shù)據(jù)造成侵犯和采用何種措施來防止敏感信息泄露的研究變得非常重要

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

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

54、><p>　　決策樹的算法己有很多。1986 年 J.Ross Quinlan 引入了 ID3 算法后，引起了很大的反響[7]。在此基礎(chǔ)上，他又于 1993 年，在其“Program For Machine Learning”一書中，對 ID3 算法進(jìn)行了補(bǔ)充和改進(jìn)，提出了后來非常流行的 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ù)挖掘的對象是規(guī)模龐大的數(shù)據(jù)，已有的分類算法在數(shù)據(jù)量小時(shí)能夠準(zhǔn)確、高效的分類，效果很好。但當(dāng)用于處理大量數(shù)據(jù)時(shí)，已有的算法都會(huì)不同程度的出現(xiàn)各種問題，分類效果不理想。因此，研究數(shù)據(jù)挖掘中準(zhǔn)確、有效的分類算法，雖然是一個(gè)傳統(tǒng)的問題，但仍具有挑戰(zhàn)性。目前，在知識(shí)發(fā)現(xiàn)和數(shù)據(jù)挖掘的研究和開發(fā)中已經(jīng)取得了一些令人矚目的成績，對關(guān)聯(lián)規(guī)則、聚類等基

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

76、息量。用它來表示信號(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)來度量信息的不確定性。不確定性是一組消息的描述如M={m1，m2，…mn}。所有消息的產(chǎn)生是相互獨(dú)立的，消息集合中每個(gè)

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

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

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

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

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

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

83、噪聲和孤立點(diǎn)，許多分支反映的是訓(xùn)練數(shù)據(jù)中的異常。剪枝[11]方法處理這種過分適應(yīng)數(shù)據(jù)問題。通常使用統(tǒng)計(jì)度量，剪去最不可靠的分支，這將導(dǎo)致較快的分類，提高樹獨(dú)立于測試數(shù)據(jù)正確分類的能力。主要有兩類剪枝方法:</p><p>　　1．同步修剪 (pre-pruning):</p><p>　　在建樹的過程中，當(dāng)滿足一定條件，例如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)取子集中頻率最大的類作為自己的標(biāo)識(shí)，或者可能僅僅存儲(chǔ)這些實(shí)例的概率分布函數(shù)。然而，選取一個(gè)適當(dāng)?shù)拈撝凳抢щy的，因?yàn)檩^高的閾值可能導(dǎo)致過分簡化的數(shù)，而較低的閾值可能使得樹的化簡太少。</p><p>　　2．遲滯修剪(pos-pruning):</p><p>　　與建樹時(shí)的訓(xùn)練集獨(dú)立的訓(xùn)練數(shù)據(jù)進(jìn)入決策樹并到達(dá)葉節(jié)點(diǎn)時(shí)，訓(xùn)練數(shù)據(jù)的

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

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

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

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

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

90、所要測試的屬性的復(fù)雜度不大于O(logn)。在有許多相關(guān)屬性的情形下，這是理想的結(jié)果。</p><p><b>　　2．復(fù)制</b></p><p>　　子樹的復(fù)制指的是在不同的分枝復(fù)制相同的屬性測試。由于屬性間存在相關(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í)，生成的決策樹會(huì)有子樹復(fù)制問題。復(fù)制現(xiàn)象導(dǎo)致決策樹理解，同時(shí)還導(dǎo)致分塊問題:當(dāng)樹很大時(shí)，會(huì)造成數(shù)據(jù)集的劃分越來越小，從而性能越差。</p><p><b>　　3．缺值</b></p><p>　　決策樹是一種層次測試方法，如果某個(gè)屬性值未知的話，就會(huì)難以決定下一步分枝，因此必須使用特殊的機(jī)制來處理缺值的問題。&l

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

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

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

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

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

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

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

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

100、法信息增益求值[15]的算法:</p><p>　　設(shè)S是s個(gè)樣本的集合。假定類別屬性具有m個(gè)不同值，定義m個(gè)不同類Ci(i=l，……，m)。設(shè)si 是Ci中的樣本數(shù)。對一個(gè)給定的樣本集，它總的信息熵I值由公式2.9給出：</p><p>　　(2.9) </p><p>　　Pi是任意樣本屬于類別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中這樣的一些樣本，它們在A上具有值aj，。假設(shè)選取A作為本次分類的屬性，則這些子集對應(yīng)于由包含集合S的節(jié)點(diǎn)生長出來的分枝。設(shè)sij是子集Sj中類Ci的樣本數(shù)。根據(jù)由A劃分成子集的熵(entropy)由公式2.10得出:</p><p><b>

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

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

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

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

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