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

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

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

3、綱219.1關(guān)聯(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中心點(diǎn)算法219.3.3PAM算法2121一、實(shí)驗(yàn)內(nèi)容1.1決策樹分類實(shí)驗(yàn)決策樹是當(dāng)下非常流行的一種分類器，因?yàn)椋錁?gòu)造不需要任何領(lǐng)域知識或參數(shù)設(shè)置，適合于探測式知識發(fā)現(xiàn)，且其具有很高的準(zhǔn)確率。決策樹歸納是從有類標(biāo)號的訓(xùn)練元組中學(xué)習(xí)決策樹。決策樹是一種類似流程圖的樹結(jié)構(gòu)，每個內(nèi)部節(jié)點(diǎn)表示在一個屬性上的測試，每個分支代表該測試的一個輸出，每個葉子節(jié)點(diǎn)存放著類標(biāo)號，即最終該分支的類屬性

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

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

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

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

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

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

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

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

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

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

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

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

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

17、tor <map <int,int> > totalNo統(tǒng)計(jì)全集結(jié)果為假情況下，對應(yīng)各屬性數(shù)量(7)進(jìn)行拉普拉斯校正(8)利用總集的屬性計(jì)數(shù)減去子集的屬性計(jì)數(shù)，獲取訓(xùn)練集各屬性對應(yīng)數(shù)量(9)利用貝葉斯定理計(jì)算，確定預(yù)測結(jié)果(10)計(jì)算檢驗(yàn)集正確率(11)程序結(jié)束六、實(shí)驗(yàn)結(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ù)量 數(shù)據(jù)條數(shù) k則驗(yàn)證

19、 是否剪枝6.3決策樹運(yùn)行結(jié)果 6.3.1.剪枝前 1.剪枝前準(zhǔn)確率大致為76.55%。 2.剪枝前耗時8622ms。3.內(nèi)存占用為39.2MB。4.外存占用為12016KB。6.3.2.剪枝后 1.剪枝后準(zhǔn)確率為79.22%，準(zhǔn)確率提高了2-3個百分點(diǎn)。2.剪枝后耗時3391ms，較剪枝前有大的改進(jìn)。3.內(nèi)存使用為39.8MB，受后臺其他進(jìn)程影響，但與前者無顯著差異。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ù)，分別代表屬性存儲的下標(biāo)，和該屬性的值。6.6貝葉斯運(yùn)行結(jié)果1.準(zhǔn)確率/運(yùn)行時間 準(zhǔn)確率波動較大，最高可達(dá)84%，最低只能達(dá)到63%。理論上而說，貝葉斯預(yù)測準(zhǔn)確率應(yīng)該較高，此次實(shí)驗(yàn)準(zhǔn)確率不是特別高，受限于條件之間關(guān)聯(lián)性較大，沒有良好的獨(dú)立性。運(yùn)行時間明顯較決策樹有大幅度提升，數(shù)量級減小，為406ms。2.顯示每次驗(yàn)證準(zhǔn)確

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

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