數(shù)據(jù)庫-決策樹

《分布式數(shù)據(jù)庫》課程報告分類算法功能及應用簡介1.1分類技術的方法和意義數(shù)據(jù)挖掘(DataMinig,DM)來源于數(shù)據(jù)庫中的知識發(fā)現(xiàn)，它可以說是數(shù)據(jù)庫研究中的一個非常有應用價值的新領域，它融合了數(shù)據(jù)庫、人工智能、機器學習、數(shù)理統(tǒng)計學、模糊數(shù)學等多個領域的理論和技術。從數(shù)據(jù)分析的觀點來看，數(shù)據(jù)挖掘分為兩類：描述性數(shù)據(jù)挖掘和預測性數(shù)據(jù)挖掘。描述性數(shù)據(jù)挖掘以概要方式描述數(shù)據(jù)，提供數(shù)據(jù)所具有的一般性質；預測性數(shù)據(jù)挖掘分析數(shù)據(jù)，建立一個或一組模型，產(chǎn)生關于數(shù)據(jù)的預測，包括分類和回歸。分類可用于提取描述重要數(shù)據(jù)的模型或預測未來的數(shù)據(jù)趨勢。分類技術是數(shù)據(jù)挖掘的重要分支，它能夠對各個行業(yè)提供良好的決策支持，對整個社會的發(fā)展產(chǎn)生重要而深遠的影響。分類的目的是構造一個分類函數(shù)或分類模型（分類器），該模型能把數(shù)據(jù)庫中的數(shù)據(jù)映射到給定類別中的某一個。分類研究在國外發(fā)展很快，已有很多的算法和模型。因此，研究數(shù)據(jù)分類對數(shù)據(jù)挖掘技術有很大的意義。用于分類挖掘技術的方法有很多，如決策樹方法、遺傳算法、貝葉斯網(wǎng)絡、粗糙集、k-最臨近方法、關聯(lián)規(guī)則方法等等。其中，決策樹方法以其算法容易被人理解、易轉換成IF-THEN分類規(guī)則、效率較高等優(yōu)點被廣泛研究與應用。目前決策樹方法中比較流行的算法有ID3、C4.5、CART、SLIQ和SPRINT等。這些算法都是對訓練數(shù)據(jù)樣本集建立一棵決策樹，利用建好的決策樹，對數(shù)據(jù)進行預測。決策樹的建立可以看成是分類規(guī)則的生成過程，因此可以認為，決策樹實現(xiàn)了數(shù)據(jù)分類規(guī)則的可視化，其輸出結果也容易理解。1.2分類挖掘的應用價值 目前，分類挖掘在實際應用中有著很重要的應用價值，在很多行業(yè)領域都取得了一定的成功。比如，在股票市場上對每只股票的歷史數(shù)據(jù)進行分析，通過相應的技術進行預測，從而做出相對比較準確的判斷；彩票的購買也可以利用數(shù)據(jù)挖掘的分類或預測技術進行分析；在金融領域中將貸款對象分為低貸款風險與高貸款風險兩類。通過決策樹，可以很容易地確定貸款申請者是屬于高風險的還是低風險的。由于決策樹方法在分類挖掘技術中有著獨特的優(yōu)勢，因此對決策樹分類算法的研究有著多層次的研究價值和很高的應用價值。

2ID3分類算法及其設計實現(xiàn)2.1ID3算法簡介2.1.1ID3算法基本思想決策樹是通過一系列規(guī)則對數(shù)據(jù)進行分類的過程。它提供一種在什么條件下會得到什么值的類似規(guī)則的方法。決策樹分為分類樹和回歸樹兩種，分類樹對離散變量做決策樹，回歸樹對連續(xù)變量做決策樹?；舅惴ǎ?.選擇一個屬性放置在根節(jié)點，為每個可能的屬性值產(chǎn)生一個分支。2.將樣本劃分成多個子集，一個子集對應于一個分支。3.在每個分支上遞歸地重復這個過程，僅使用真正到達這個分支的樣本。4.如果在一個節(jié)點上的所有樣本擁有相同的類別，即停止該部分樹的擴展。ID3算法思想：(1)初始化決策樹T為只含一個樹根(X,Q)，其中X是全體樣本集，Q為全體屬性集。(2)if(T中所有葉節(jié)點(X’,Q’)都滿足X屬于同一類或Q’為空)then算法停止；(3)else{任取一個不具有(2)中所述狀態(tài)的葉節(jié)點(X’,Q’)；(4)foreachQ’中的屬性Ado計算信息增益gain(A,X’)；(5)選擇具有最高信息增益的屬性B作為節(jié)點(X’,Q’)的測試屬性；(6)foreachB的取值bido{從該節(jié)點(X’,Q’)伸出分支，代表測試輸出B=bi；求得X中B值等于bi的子集Xi，并生成相應的葉節(jié)點(Xi’,Q’-{B})；}(7)轉(2)；}ID3算法偽代碼。尋找根節(jié)點尋找根節(jié)點將根節(jié)點壓入棧中將根節(jié)點壓入棧中更新根節(jié)點更新根節(jié)點清空候選表清空候選表找一個除測試點的找一個除測試點的屬性作為候選屬性計算熵值并更新計算熵值并更新包含所有屬性包含所有屬性否是在候選列表中查找最大信息增益的屬性作為根節(jié)點是在候選列表中查找最大信息增益的屬性作為根節(jié)點計算當前增益最大值計算當前增益最大值將節(jié)點插入結果表將節(jié)點插入結果表StackStack是否為空否結束是結束2.1.2ID3算法的基本概念信息熵熵是無序性（或不確定性）的度量指標，是用來度量一個屬性的信息量。假如事件A的全概率劃分是（A1,A2,...,An），每部分發(fā)生的概率是(p1,p2,...,pn)，那信息熵定義為：通常以2為底數(shù)，所以信息熵的單位是bit。補充兩個對數(shù)去處公式：構造樹的基本想法是隨著樹深度的增加，節(jié)點的熵迅速地降低。熵降低的速度越快越好，這樣我們有望得到一棵高度最矮的決策樹。2.1.3ID3實例詳解先看看下面的數(shù)據(jù)表格：Table1我們統(tǒng)計了14天的氣象數(shù)據(jù)(指標包括outlook，temperature，humidity，windy)，并已知這些天氣是否打球(play)。如果給出新一天的氣象指標數(shù)據(jù)：sunny,cool,high,TRUE，判斷一下會不會去打球。在沒有給定任何天氣信息時，根據(jù)歷史數(shù)據(jù)，我們只知道新的一天打球的概率是9/14，不打的概率是5/14。此時的熵為：屬性有4個：outlook，temperature，humidity，windy。我們首先要決定哪個屬性作樹的根節(jié)點。對每項指標分別統(tǒng)計：在不同的取值下打球和不打球的次數(shù)。Table2下面我們計算當已知變量outlook的值時，信息熵為多少。outlook=sunny時，2/5的概率打球，3/5的概率不打球。entropy=0.971outlook=overcast時，entropy=0outlook=rainy時，entropy=0.971而根據(jù)歷史統(tǒng)計數(shù)據(jù)，outlook取值為sunny、overcast、rainy的概率分別是5/14、4/14、5/14，所以當已知變量outlook的值時，信息熵為：5/14×0.971+4/14×0+5/14×0.971=0.693這樣的話系統(tǒng)熵就從0.940下降到了0.693，信息增溢gain(outlook)為0.940-0.693=0.247同樣可以計算出gain(temperature)=0.029，gain(humidity)=0.152，gain(windy)=0.048。gain(outlook)最大（即outlook在第一步使系統(tǒng)的信息熵下降得最快），所以決策樹的根節(jié)點就取outlook。接下來要確定N1取temperature、humidity還是windy?在已知outlook=sunny的情況，根據(jù)歷史數(shù)據(jù)，我們作出類似table2的一張表，分別計算gain(temperature)、gain(humidity)和gain(windy)，選最大者為N1。依此類推，構造決策樹。當系統(tǒng)的信息熵降為0時，就沒有必要再往下構造決策樹了，此時葉子節(jié)點都是純的--這是理想情況。最壞的情況下，決策樹的高度為屬性（決策變量）的個數(shù)，葉子節(jié)點不純（這意味著我們要以一定的概率來作出決策）。用圖形可以形象的表示成：2.2ID3算法仿真程序設計圖2-2ID3仿真程序設計流程圖Fig.2-2ID3simulationprogramdesignflowfigureID3算法程序分為三個存儲過程，包括三部分：存儲過程1構建決策樹，存儲過程2計算熵值，存儲過程3產(chǎn)生輸出結果。（1）存儲過程1BuildTree(table_nameVARCHAR,classVARCHAR,res_nameVARCHARDEFAULT'BTRES,min_gainREALDEFAULT0,root_viewVARCHARDEFAULT'BTROOT',delBOOLEANDEFAULTTRUE)包含六個輸入?yún)?shù)：table_name為創(chuàng)建的訓練集表名，class為你要預測的屬性名，res_name是結果集存放的表的表名，min_gain表示的是最小信息增益，root_view是結果集的視圖，del為刪除中間表。（2）存儲過程2表的作用是計算熵值存儲過程2Entropy(view_nameINVARCHAR,entOUTREAL,totpopOUTINTEGER)包含三個輸入?yún)?shù)，view_name視圖標的名稱，ent為熵值，totpop是關聯(lián)度。（3）存儲過程3表的作用是產(chǎn)生輸入輸出結果。存儲過程3產(chǎn)生輸出結果。Result(numINTEGER,parentVARCHAR,ruleVARCHAR,view_nameVARCHAR)，本程序共有2處result調用分別的作用是：1.輸出rule為空的時候時主屬性的值。2.輸出rule不為空的時候所有的結果。2.3ID3算法仿真程序實驗結果1．創(chuàng)建BTCandidate表，并且定義了CNode、CNod