數(shù)據(jù)挖掘報告

1、浙江工業(yè)大學計算機學院數(shù)據(jù)挖掘?qū)嶒瀳蟾?分類算法:決策樹、貝葉斯 實驗名稱： 分類算法 班 級： 姓 名： 學 號： 指導教師： 實驗日期： 2016/6/14 目錄一、實驗內(nèi)容51.1決策樹分類實驗51.2貝葉斯分類實驗5二、設計思路52.1決策樹分類設計思路52.2樸素貝葉斯分類設計6三、數(shù)據(jù)結(jié)構設計63.1決策樹數(shù)據(jù)結(jié)構63.1.1初始數(shù)據(jù)（data）存儲結(jié)構63.1.2屬性數(shù)據(jù)（attribute）存儲結(jié)構63.1.3決策樹計算節(jié)點（node）結(jié)構設計73.1.4計數(shù)/分配映射容器（counteri）結(jié)構83.1.5其他數(shù)據(jù)結(jié)構83.2貝葉斯分類器數(shù)據(jù)結(jié)構設計83.2.1初始數(shù)據(jù)（da

2、ta）存儲結(jié)構83.2.2totalYes/totalNo計數(shù)容器93.2.3yes/no計數(shù)容器93.2.4其他數(shù)據(jù)結(jié)構9四、流程圖104.1決策樹分類流程圖104.2貝葉斯分類流程圖12五、偽代碼135.1決策樹偽代碼實現(xiàn)135.2貝葉斯偽代碼實現(xiàn)13六、實驗結(jié)果146.1決策樹測試數(shù)據(jù)146.2決策樹參數(shù)設置146.3決策樹運行結(jié)果156.3.1.剪枝前156.3.2.剪枝后156.3.3IF-THEN規(guī)則176.4貝葉斯樣本數(shù)據(jù)176.5貝葉斯測試數(shù)據(jù)186.6貝葉斯運行結(jié)果18七、問題與解決方案197.1決策樹編寫及調(diào)試問題197.2貝葉斯編寫及調(diào)試問題20八、心得體會20九、學習大

3、綱219.1關聯(lián)規(guī)則219.1.1Apriori算法219.1.2FP-growth算法219.2分類算法219.2.1決策樹分類器219.2.2貝葉斯分類器219.3聚類算法219.3.1k均值算法219.3.2k中心點算法219.3.3PAM算法2121一、實驗內(nèi)容1.1決策樹分類實驗決策樹是當下非常流行的一種分類器，因為，其構造不需要任何領域知識或參數(shù)設置，適合于探測式知識發(fā)現(xiàn)，且其具有很高的準確率。決策樹歸納是從有類標號的訓練元組中學習決策樹。決策樹是一種類似流程圖的樹結(jié)構，每個內(nèi)部節(jié)點表示在一個屬性上的測試，每個分支代表該測試的一個輸出，每個葉子節(jié)點存放著類標號，即最終該分支的類屬性

4、預測。本次實驗采用的是決策樹實現(xiàn)中的C4.5算法，采用信息增益率作為屬性選擇的標準。對連續(xù)屬性方面做了改進，并不是尋找分裂點，而是選擇將連續(xù)值離散化，與離散值共同處理，簡化了實驗流程，提高了運算效率。1.2貝葉斯分類實驗貝葉斯分類基于貝葉斯定理。樸素的貝葉斯分類法中的簡單貝葉斯分類法可與決策樹和經(jīng)過挑選的神經(jīng)網(wǎng)絡分類器相媲美。用于大型數(shù)據(jù)庫，也可體現(xiàn)較高的準確率和速度。樸素貝葉斯是基于貝葉斯定理進行計算的，前提是各項條件間具有良好的獨立性。此外，對于零概率值，本實驗還采用了拉普拉斯校準的方法進行調(diào)整。二、設計思路2.1決策樹分類設計思路決策樹C4.5算法是通過訓練集數(shù)據(jù)的各項屬性，計算當前剩余

5、各項屬性的信息增益率，作為當前節(jié)點的屬性選擇度量，隨后按照該屬性的不同值，將該節(jié)點上的數(shù)據(jù)進行劃分，繼續(xù)遞歸。若當前節(jié)點已無剩余可劃分屬性，則選擇當前節(jié)點的多數(shù)類作為類標號，并停止遞歸；若當前節(jié)點已為純類，則停止遞歸。本實驗就原有的C4.5算法做了改變，并未設計連續(xù)值處理方案，而是在數(shù)據(jù)預處理部分，將連續(xù)值離散化為離散值，便于統(tǒng)一處理，并取得了較好的實驗結(jié)果。同時，本次實驗采取較為輕量級的先剪枝策略，即若某節(jié)點的數(shù)據(jù)數(shù)量達到設定閾值下限，則取該節(jié)點上的多數(shù)類作為該分支的類標號，或某節(jié)點的遞歸深度達到設定深度，同樣取該節(jié)點上的多數(shù)類作為該分支的類標號并返回。實驗數(shù)據(jù)分為檢驗集和訓練集，每次實驗分

6、別輪流取第i個數(shù)據(jù)塊為檢驗集，其余k-1個數(shù)據(jù)塊為訓練集，通過訓練集得出的IF-THEN規(guī)則在檢驗集上進行檢驗，統(tǒng)計正確數(shù)量，并計算準確率。2.2樸素貝葉斯分類設計樸素貝葉斯分類算法基于貝葉斯定理，計算P(Ci|X)=(P(X|Ci)*P(Ci)/P(X)，最大化P(Ci|X)，其中P(Ci|X)最大的類Ci稱為最大后驗假設。即Ci為X條件下的情況預測。根據(jù)式子特點，P(X)對于所有類為常數(shù)，只需要最大化P(X|Ci)P(Ci)即可。同時，為了降低計算開銷，可以做類獨立條件的樸素假定，則有P(X|Ci)=P(x1|Ci)*P(x2|Ci)*P(xn|Ci)最后計算P(X|Ci)*P(Ci),選

7、出其中最大的值，其所對應的Ci類即作為預測結(jié)果。三、數(shù)據(jù)結(jié)構設計3.1決策樹數(shù)據(jù)結(jié)構3.1.1初始數(shù)據(jù)（data）存儲結(jié)構struct datavector <int> val; /該條記錄的數(shù)據(jù)列表 int res;DataListmaxDataAmount;1.vector <int> valval用于存儲某一條數(shù)據(jù)的各項屬性的值。2.int resres表示該條數(shù)據(jù)的結(jié)果。3.data DataListmaxDataAmountDataList數(shù)組則用于存儲data類型的多條數(shù)據(jù),maxDataAmount是宏定義的數(shù)據(jù)量最大值，可隨具體情況改動。3.1.2屬性數(shù)

8、據(jù)（attribute）存儲結(jié)構struct attribute /屬性集合 bool consecutive; /該屬性連續(xù)1或離散0 string attributeName; /該屬性名稱 AttributeListmaxAttributeAmount;1. bool consecutivebool類型的consecutive屬性用于標明該條屬性是否屬于連續(xù)值，是值為1，不是值為0，在本次實驗中，皆為0。2. string attributeName string類型的attributeName屬性則用于存儲該屬性對應名稱。3. attribute AttributeListmaxAtt

9、ributeAmountAttributeList數(shù)組用于存儲attribute類型的屬性數(shù)據(jù)。maxAttributeAmount是宏定義的屬性數(shù)據(jù)量最大值。3.1.3決策樹計算節(jié)點（node）結(jié)構設計struct node/決策樹計算中間節(jié)點 vector <int> attributeList; /剩余屬性列表，存屬性下標 vector <int> dataList; /該節(jié)點的數(shù)據(jù)條數(shù)，存數(shù)據(jù)下標 vector <int> subnodeList; /該節(jié)點的子節(jié)點存儲下標 int res, selected_type, selected_val;/

10、最后的結(jié)果,選擇的分類屬性，分類值 int cur_selected_type; /當前節(jié)點選擇的分類屬性 bool is_tail; /是否是尾部節(jié)點 NodeListmaxNodeAmount;1. vector <int> attributeListattributeList存儲的是，當前節(jié)點可在接下來遞歸過程中用于劃分的剩余屬性在AttributeList中對應的下標ID。2.vector <int> dataListdataList存儲的是，被劃分到當前節(jié)點的數(shù)據(jù)在DataList中對應的存儲下標。3. vector <int> subnodeLi

11、stsubnodeList存儲的是當前節(jié)點的劃分出來的子樹節(jié)點在NodeList中的存儲下標。4.node NodeListmaxNodeAmountNodeList存儲的是在決策樹遞歸過程中產(chǎn)生的中間節(jié)點。初始節(jié)點下標為0，該節(jié)點上有全部的屬性以及全部的數(shù)據(jù)。5.others 其余屬性中，cur_selected_type和selected_type是極易混淆的，selected_type 是當前節(jié)點被什么屬性劃分到當前分支，而cur_selected_type是當前節(jié)點按照什么屬性進行劃分。3.1.4計數(shù)/分配映射容器（counteri）結(jié)構1.map <int,int> co

12、unter1統(tǒng)計某離散值屬性的對應各類值的臨時計數(shù)器。2.map <int,int> counter2統(tǒng)計某離散值屬性的對應各類值結(jié)果為真值的臨時計數(shù)器，結(jié)合counter1在計算信息增益率使用。3.map <int,int> counter3在node節(jié)點按屬性劃分數(shù)據(jù)時，為子節(jié)點分配nodeID的映射計數(shù)器。3.1.5其他數(shù)據(jù)結(jié)構1. int correct_num50Correct_num數(shù)組用于統(tǒng)計每次驗證的正確數(shù)量。2. int selected_val50, selected_type50selected_type為節(jié)點選擇的劃分屬性，selected_va

13、l為節(jié)點選擇的劃分值，兩者用于后續(xù)輔助輸出IF-THEN規(guī)則。3.2貝葉斯分類器數(shù)據(jù)結(jié)構設計3.2.1初始數(shù)據(jù)（data）存儲結(jié)構struct datavector <int> v;int res;dataArraydataSize;1.vector <int> vv向量用于儲存該條數(shù)據(jù)各項屬性的值。2.int resres用于存儲該條數(shù)據(jù)的結(jié)果3. data dataArraydataSizedataArraydataSize數(shù)組用于存儲數(shù)據(jù)列表，dataSize是最大數(shù)據(jù)量。3.2.2totalYes/totalNo計數(shù)容器vector <map <in

14、t,int> > totalYes/totalNo1.totalYes/totalNo用于存儲整個數(shù)據(jù)集中各項屬性的數(shù)量情況，配合yes/no數(shù)組可以計算出訓練集的各項屬性值為真或假的數(shù)量。3.2.3yes/no計數(shù)容器vector <map <int,int> > yeskSize/nokSize1.yeskSize用于統(tǒng)計各項屬性中最后結(jié)果為真的各項屬性的數(shù)量。2.nokSize用于統(tǒng)計各項屬性中最后結(jié)果為假的各項屬性的數(shù)量。3.2.4其他數(shù)據(jù)結(jié)構1.int checkArraykSize輸入的檢查屬性對應的存儲下標。2.int checkValkSiz

15、e 輸入的各項屬性對應的取值。四、流程圖4.1決策樹分類流程圖4.2貝葉斯分類流程圖五、偽代碼5.1決策樹偽代碼實現(xiàn)(1)數(shù)據(jù)輸入(2)設置分區(qū)偏移量為0(3)創(chuàng)建初始節(jié)點N(4)調(diào)用C45開始決策樹運算(5)if cut_branch為真then(6) if滿足遞歸結(jié)束條件then(7) 標記該節(jié)點多數(shù)類，返回(8)if attributeList為空 then(9) 標記該節(jié)點多數(shù)類，返回(10)if dataList中所有數(shù)據(jù)的結(jié)果為純類 then(11) 標記純類，并返回(12)計算當前節(jié)點剩余屬性信息增益率(13)選取信息增益率最大者作為繼續(xù)劃分標準，繼續(xù)遞歸(14)遞歸完成，分區(qū)偏

16、移量+1(15)if k則檢驗尚未完成 then(16) 跳轉(zhuǎn)到(3)(17)計算平均預測準確率(18)程序結(jié)束5.2貝葉斯偽代碼實現(xiàn)(1)數(shù)據(jù)輸入(2)確定k則驗證中的k值(3)利用vector <map <int,int> > yeskSize統(tǒng)計各子集結(jié)果為真情況下，對應各屬性數(shù)量(4)利用vector <map <int,int> > nokSize統(tǒng)計各子集結(jié)果為假情況下，對應各屬性數(shù)量(5)利用vector <map <int,int> > totalYes統(tǒng)計全集結(jié)果為真情況下，對應各屬性數(shù)量(6)利用vec

17、tor <map <int,int> > totalNo統(tǒng)計全集結(jié)果為假情況下，對應各屬性數(shù)量(7)進行拉普拉斯校正(8)利用總集的屬性計數(shù)減去子集的屬性計數(shù)，獲取訓練集各屬性對應數(shù)量(9)利用貝葉斯定理計算，確定預測結(jié)果(10)計算檢驗集正確率(11)程序結(jié)束六、實驗結(jié)果6.1決策樹測試數(shù)據(jù)1.LIMIT_BAL: Amount of the given credit (NT dollar): it includes both the individual consumer credit and his/her family (supplementary) credi

18、t.2.SEX: Gender (1 = male; 2 = female).3.EDUCATION: Education (1 = graduate school; 2 = university; 3 = high school; 4 = others).4.MARRIGE: Marital status (1 = married; 2 = single; 3 = others).5.AGE: Age.6.PAY_I History of past payment.7.default_payment_next_month YES=1,NO=06.2決策樹參數(shù)設置 屬性數(shù)量 數(shù)據(jù)條數(shù) k則驗證

19、 是否剪枝6.3決策樹運行結(jié)果 6.3.1.剪枝前 1.剪枝前準確率大致為76.55%。 2.剪枝前耗時8622ms。3.內(nèi)存占用為39.2MB。4.外存占用為12016KB。6.3.2.剪枝后 1.剪枝后準確率為79.22%，準確率提高了2-3個百分點。2.剪枝后耗時3391ms，較剪枝前有大的改進。3.內(nèi)存使用為39.8MB，受后臺其他進程影響，但與前者無顯著差異。4.外存使用為17KB，IF-THEN規(guī)則變得更加簡潔。6.3.3IF-THEN規(guī)則LIMIT_BAL是在原始數(shù)據(jù)/50000后得到的。6.4貝葉斯樣本數(shù)據(jù)1.LIMIT_BAL: Amount of the given cre

20、dit (NT dollar): it includes both the individual consumer credit and his/her family (supplementary) credit.2.SEX: Gender (1 = male; 2 = female).3.EDUCATION: Education (1 = graduate school; 2 = university; 3 = high school; 4 = others).4.MARRIGE: Marital status (1 = married; 2 = single; 3 = others).5.

21、AGE: Age.6.PAY_I History of past payment.7.default_payment_next_month YES=1,NO=06.5貝葉斯測試數(shù)據(jù)【數(shù)據(jù)說明】：第一行為測試樣例數(shù)，隨后每一行第一個整數(shù)，代表該組測試樣例有幾個屬性，隨后每兩個整數(shù)，分別代表屬性存儲的下標，和該屬性的值。6.6貝葉斯運行結(jié)果1.準確率/運行時間 準確率波動較大，最高可達84%，最低只能達到63%。理論上而說，貝葉斯預測準確率應該較高，此次實驗準確率不是特別高，受限于條件之間關聯(lián)性較大，沒有良好的獨立性。運行時間明顯較決策樹有大幅度提升，數(shù)量級減小，為406ms。2.顯示每次驗證準確

22、率及結(jié)果3.內(nèi)/外存使用情況內(nèi)存使用為34.9MB，與決策樹相差不大。外存使用情況為空。七、問題與解決方案7.1決策樹編寫及調(diào)試問題1.【問題描述】決策樹在構建子樹過程中，發(fā)現(xiàn)子樹上的屬性數(shù)量大于父節(jié)點屬性數(shù)量。 【問題分析】子樹的屬性列表是由父節(jié)點的屬性列表構造得到，理應小于父節(jié)點屬性數(shù)量。但實際調(diào)試卻發(fā)現(xiàn)子樹的屬性列表中屬性數(shù)量大于父節(jié)點屬性數(shù)量。 【問題解決】仔細檢查，調(diào)試后發(fā)現(xiàn)是子樹尚未全部構造完成，便開始遞歸，造成節(jié)點ID起始位置出錯，隨后調(diào)整遞歸位置，便解決了此問題。2.【問題描述】屬性選擇過程中出現(xiàn)了未選中任何屬性的情況。 【問題分析】1.因為計算某些屬性增益率的過程中，出現(xiàn)了極

23、值，造成最后計算均值的時候，均值也變成了極值，故而無法選中任何屬性。2.因為精度問題，造成與均值比較時，無法精確判斷大小關系。 【問題解決】1.選取測試的信息增益必須較大，至少與所有測試的平均增益一樣大。2.加上了10-6次方的eps精度修正。7.2貝葉斯編寫及調(diào)試問題1.【問題描述】 出現(xiàn)程序崩潰的情況。【問題分析】此實驗，實驗代碼結(jié)構較為簡單，并未特殊結(jié)構，程序崩潰可能是由于訪問非法空間造成?！締栴}解決】 經(jīng)逐步調(diào)試后，發(fā)現(xiàn)造成程序崩潰的根本原因是忘記為總計數(shù)器分配空間，分配后，問題迎刃而解。八、心得體會通過這門課程的學習，對數(shù)據(jù)挖掘?qū)W科的基本概念有了簡單的了解。但只有真正通過實驗的實踐，才能切實體會到關聯(lián)規(guī)則、分類、聚類等挖掘算法的真正思想。尤其是分類算法，通過實驗，明了了訓練集和檢驗集的區(qū)別及作用。通過對訓練集的挖掘，并在檢驗集上進行檢驗，得到正確率，從而進一步進行修正和學習，提高預測準確性。幾種方法的核心思想都不是特別復雜，但分類的決策樹算法的實現(xiàn)較為復雜，調(diào)試占據(jù)了不少的時間，導致錯誤的，往往都是一些小細節(jié)。從而更加驗證了，只有自己從頭到尾操作過了，才能更好地，更加全面地理解算法。本次實驗在代碼調(diào)試能力上得到了檢驗，同時，更多的是，對于數(shù)據(jù)挖掘的理解，及其功能和應用，為之后的研究興趣和方向提供了參考。九、學習大綱9.