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

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

2、;　　1.1.1 數(shù)據(jù)挖掘技術的應用背景1</p><p>　　1.1.2數(shù)據(jù)挖掘的定義及系統(tǒng)結構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ù)挖掘的應用與面臨的挑戰(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>　　第二章 決策樹分類算法相關知識12</p><p>　　2.1決策樹方法介紹12</p><p>　　2.1.1決策樹的結構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決策樹算法總結比較24</p><p>　　2.5實現(xiàn)平臺簡介25</p><p>　　2.6本章小結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算法評價33</p><p>　　3.2決策樹模型的建立34</p><p>　　3.2.1 決策樹的生成34</p><p>　　3.2.2 分類規(guī)則的提取37</p><p>　　3.2.3模型準確性評估38</p><p>　　3.3 本章小結39&l

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

101、t;<p>　　設屬性A具有v個不同的值。可以用屬性A(a1, a2,。。。av)，將S劃分為v個子集{S1, S2,。。。Sv };其中，Sj包含S中這樣的一些樣本，它們在A上具有值aj，。假設選取A作為本次分類的屬性，則這些子集對應于由包含集合S的節(jié)點生長出來的分枝。設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的值而導致的熵的期望壓縮。為了使下一步所需的信息量最小，要求每一次都選擇其信息增益最大的屬性作為決策樹的新結點，并對屬性的每個值創(chuàng)建分枝，依據(jù)此思想劃分訓練數(shù)。</p><p>　　ID3是一個典型的決策樹學習系統(tǒng)，它檢驗數(shù)據(jù)集的所有特征，它以信息增益作為分離目標評價函數(shù)，采用自頂向下，分而治之不可返回的策略，選取決策樹的分裂點，對每

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

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

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