增量數(shù)據(jù)挖掘初探

1、增量數(shù)據(jù)挖掘初探趙浩磊 (陜西理工學(xué)院數(shù)學(xué)系信息與計算科學(xué)專業(yè)2003級3班，陜西漢中723001)指導(dǎo)教師 周濤摘 要本文介紹了數(shù)據(jù)挖掘領(lǐng)域中的增量頻繁模式挖掘，在介紹了頻繁項集挖掘與增量頻繁模式挖掘的一搬概念后，文章又相繼介紹了了三種由相關(guān)研究人員提出的增量頻繁模式挖掘算法，并分析了這些算法的優(yōu)點與不足，并且在分析的同時發(fā)現(xiàn)了IUAMAR算法的嚴重缺陷，指出它是不可靠的算法最后，文章根據(jù)火鍋銷售數(shù)據(jù)挖掘的現(xiàn)實情況，結(jié)合其中的兩種算法的優(yōu)點，介紹了銷售數(shù)據(jù)挖掘的實現(xiàn)。關(guān)鍵詞 數(shù)據(jù)挖掘；關(guān)聯(lián)規(guī)則；頻繁項集；增量挖掘算法1 引言1.1 問題的提出近年來，信息技術(shù)的廣泛應(yīng)用提出了對信息處理能力的更

2、高要求，老式的數(shù)據(jù)統(tǒng)計方法面對海量的數(shù)據(jù)以及全新的數(shù)據(jù)處理概念顯得力不從心，在這種背景下,數(shù)據(jù)挖掘技術(shù)應(yīng)運而生，并成為研究的熱點數(shù)據(jù)挖掘就是從大量的、不完全的、有噪聲的、模糊的、原始的數(shù)據(jù)中提取隱含在其中人們事先不知道也不可能直接獲取的，但卻非常有潛在價值的信息，它們包括關(guān)聯(lián)規(guī)則挖掘、特征規(guī)則、分類規(guī)則等其中關(guān)聯(lián)規(guī)則挖掘是發(fā)現(xiàn)大量數(shù)據(jù)中項與項之間有趣的關(guān)聯(lián)或聯(lián)系，它是數(shù)據(jù)挖掘領(lǐng)域中的一個熱鬧課題，得到了業(yè)界廣泛的研究其中:Apriori算法是最早提出的也是最經(jīng)典的算法，后來又出現(xiàn)了另一個高效的算法FP-Growth,它解決了Apriori算法中的一個最大缺陷但它本身的實現(xiàn)卻比較困難之后，廣大學(xué)

3、者就以上述算法為藍本進行改進，使之更加有效，更加容易實現(xiàn)，并將其融入到各種數(shù)據(jù)處理系統(tǒng)中，使之發(fā)揮出自己巨大的作用但是以上的研究都是以假設(shè)數(shù)據(jù)庫為靜態(tài)的前提的事實上，在很多領(lǐng)域數(shù)據(jù)庫都處在不斷地更新（增加、刪除、修改）中，所用的支持度閾值也會不斷改變，并且動態(tài)數(shù)據(jù)庫往往要求對用戶的查尋指令做出快速地反應(yīng)因此，提高動態(tài)數(shù)據(jù)庫中關(guān)聯(lián)規(guī)則發(fā)現(xiàn)的效率便成了一個重要的問題進行增量數(shù)據(jù)挖掘最直接的方法就是對更新后的數(shù)據(jù)庫進行一次關(guān)聯(lián)規(guī)則挖掘，但這樣顯然有很大的開銷，而且隨著時間的增長、數(shù)據(jù)庫規(guī)模的不斷增長，這樣的方法也顯得不現(xiàn)實如何利用原始數(shù)據(jù)庫的挖掘結(jié)果來更新頻繁項集便成了增量頻繁模式挖掘研究的起點雖然

4、目前頻繁模式的增量挖掘領(lǐng)域研究地還不很充分，但是廣大研究人員對它們所做出的改進還是值得肯定的，針對閾值不變的增量頻繁模式挖掘研究總體分為兩大類：第一種的分別挖掘出原始數(shù)據(jù)庫和更新數(shù)據(jù)庫中的頻繁項集，然后使用某種規(guī)則對其進行更新，這種算法的特點是可以最大利用現(xiàn)有的關(guān)聯(lián)規(guī)則挖掘算法，但是頻繁項集的更新規(guī)則很重要，規(guī)則制定或?qū)崿F(xiàn)的時候一但發(fā)生問題，將對結(jié)果的分析產(chǎn)生致命影響第二種的基于散列的方法，這種方法不需要添加復(fù)雜的更新規(guī)則，實現(xiàn)起來也非常容易，結(jié)果可靠性高，但是它將占用較高的系統(tǒng)資源 本文將帶介紹、分析幾種不同類型的算法 ，然后以一銷售數(shù)據(jù)庫為例介紹算法的實際應(yīng)用 1.2 數(shù)據(jù)挖掘的基本概念與

5、定義項（item）是一個文字，在交易數(shù)據(jù)庫中，它可以代表商品；分類時，它可以代表屬性的值設(shè)為項的全集，為事務(wù)數(shù)據(jù)庫，其中每個事務(wù)包含中的一個子集支持度計數(shù)：項集的支持度是指，事務(wù)數(shù)據(jù)庫中，包含的事務(wù)的個數(shù)支持度：項集的支持度計數(shù)等于的支持度計數(shù)除以事務(wù)數(shù)據(jù)庫中事務(wù)的總條數(shù)給定一個支持度閾值minsup，若的支持度minsup，則是頻繁的，若包含有k個項，則稱X為頻繁k-項集1Apriori性質(zhì)1：若一個項集是頻繁的，則它的所有子集也是頻繁的；同樣，如果一個項集有不頻繁的子集，則這個項集就不可能是頻繁的2 融合原始、增量數(shù)據(jù)庫頻繁模式的算法前面已經(jīng)介紹過，基于融合思想的算法需要用基本的數(shù)據(jù)挖掘算

6、法分別挖掘出原始、增量數(shù)據(jù)庫中的頻繁項集，然后對它們進行融合融合的時候需要以下三大結(jié)論的支持：設(shè)K是項集，DB為原始數(shù)據(jù)庫，db為增量數(shù)據(jù)庫，NDB為更新后的數(shù)據(jù)庫1 K在DB中是頻繁的，在db中也是頻繁的，則K在NDB中是頻繁的2 K在DB中是不頻繁的，在db中也是不頻繁的，則K在NDB中是不頻繁的3 K只在DB或db其中之一中頻繁，則K在NDB中是否頻繁是不確定的2其中DB是原始數(shù)據(jù)庫，db是增量數(shù)據(jù)庫，K是頻繁項集，NDB是更新后的數(shù)據(jù)庫以上結(jié)論很容易根據(jù)頻繁項集的定義得到證明有了上面的理論，很多學(xué)者對此思想產(chǎn)生的算法進行了一些研究、改進，比如：只需要挖掘出原始數(shù)據(jù)庫中的頻繁項集，而用其

7、它方法處理增量數(shù)據(jù)庫如：何宏，肖建華，肖偉平提出了IUAMAR算法3，該算法可以處理對挖掘數(shù)據(jù)庫進行追加的情況，利用挖掘知識庫信息即原數(shù)據(jù)庫挖掘出來的高頻項目集和最小非高頻繁項目集來產(chǎn)生新候選項目集，避免了類似Apriori的算法中候選項目集的數(shù)量龐大的問題下面文章將介紹這個算法，并對它的優(yōu)缺點進行分析2.1 算法的相關(guān)概念與定義DB :原始數(shù)據(jù)庫;db:增量數(shù)據(jù)庫;UD：更新后的數(shù)據(jù)庫:原始數(shù)據(jù)庫中挖掘出來的高頻項目集;MNL：最小非高頻繁項目集；|DB| :原始數(shù)據(jù)庫的長度（事務(wù)數(shù)）;|db| :增量數(shù)據(jù)庫的長度（事務(wù)數(shù)）;|UD| :更新后的數(shù)據(jù)庫的長度（事務(wù)數(shù)）;Dx :X 項目集出現(xiàn)

8、在DB庫的次數(shù);dx :X 項目集出現(xiàn)在db庫的次數(shù);CUD:新產(chǎn)生的候選項目集.Cx：候選項集在UD中出現(xiàn)的次數(shù)minsup：用戶定義的支持度閾值定義數(shù)據(jù)結(jié)構(gòu)：struct knowledge int field ;/ 挖 掘 數(shù) 據(jù) 庫的字段代碼struct knowledge*next其中field為項目集的出現(xiàn)次數(shù)用此結(jié)構(gòu)建立三張鏈表：LDB,LMNI,LUD定義 1 這里所謂的最小非高頻繁項目集，為沒有子集或是其子集皆為高頻項目集的非高頻項目集定理 1 設(shè)，則時，項目集在更新后的數(shù)據(jù)庫中仍為高頻項目集.證明：因為Dx,dx分別為X在D和d中的支持度計數(shù)，則為X在UD中的支持度，若它m

9、insup則滿足一個項集在數(shù)據(jù)庫中頻繁的定義，定理1證畢定理設(shè)，則時，X項目集在更后的新數(shù)據(jù)庫中變?yōu)楦咧蓄l繁項目集證明同上2.2 IUAMAR算法的流程步驟 1用Apriori算法挖掘原始數(shù)據(jù)庫DB，產(chǎn)生高頻項目集合及最小非高頻項目集MNL，將結(jié)果分別保存到LDB,LMNI兩個鏈表中，LUB暫時為空步驟 2 遍歷db，更新各鏈表中與MNL元素的出現(xiàn)次數(shù)步驟 3 使用定理和定理檢查各鏈表中的元素，如果不滿足定理，則刪除該項目集 ，并 且 更 新 三張 鏈 表 ,將不滿足的清除出LB和LMNI，并將所有滿足項集的并入LUB步驟 4使用LMNI和LUB產(chǎn)生新的候選項集 步 驟 5 利用上述產(chǎn)生的候選

10、項目集掃描更新后的UD一次，找出所有候選項目集在UD中出現(xiàn)的次數(shù) ， 如果候選項目集X出現(xiàn)的次數(shù)，則這些項目集和更新后的LB、LMNI中的項目集合并一起成為更新數(shù)據(jù)庫中的高頻項目集算法的偽代碼描述:BEGAINApriori(DB,LDB,LMNI,LUB)/算法的第一步IUAMAR(DB,db，minsup)For each Transaction T in db/掃描db中的每項Updating(db,LDB,UMll);/用db中的記錄更新兩鏈表各項目集出現(xiàn)的次數(shù)For eachitem set X in LDBif(Dx+dx)/不滿足定理LDB=LDB-XLUB=For eachit

11、em set Y in LMNIif(Dx+dx)/不滿足定理LMNI=LMNI-XLUB=CUD=gen(LUD,LMNI)/LUD和LMNI通過gen()產(chǎn)生候選項目集CUDFor each itemset X in CUDif(Cx)/不滿足條件CUD=CUD-XLUB=LUBCUDEND2.3 實例說明表2.3.1 事務(wù)數(shù)據(jù)庫編號事務(wù)編號事務(wù)11,2,361,3,4,521,4,573,4,531,3,582,344,5,691,3,4,552,3,6102,6表格 2.3.1設(shè)DB為表2.3.1中第條事務(wù)，db為表2.3.1中第條事務(wù)，minsup=0.4現(xiàn)利用上述算法對其進行增量挖

12、掘首先用Apriori算法挖掘DB得：DB=1(4),3(4),4(3),5(4),13(3),15(3),45(3),LMNI =2(2),6(2),14(2),34(1),35(2)其中小括號中的數(shù)字是該集合在相應(yīng)數(shù)據(jù)庫中出現(xiàn)的總次數(shù)用db更新鏈表后變?yōu)?LDB=1(6),3(7),4(5),5(5),13(4),15(4),45(4)，LMNI=2(4),6(3),14(3),34(3),35(4)經(jīng)過第三步的處理，各鏈表變?yōu)?LDB=1,3,4,5,13,15,45;LMNI=2,35;LUB=1,2,3,4,5,13,15,35,45調(diào)用gen()函數(shù)產(chǎn)生候選項集:CUD=1,2,3

13、,4,5,13,15,45,12,23,24,25,123,125,245,35,135,345，檢查其在UB中的支持度計數(shù)：CUD=1(6),2(4),3(7),4(5),5(5),13(4),15(4),45(5),12(1),23(3),24(0),25(0),123(1),125(0),245(0),35(4),135(3),345(3)最后得到LUB=1,2,3,4,5,13,15,45,35,算法結(jié)束2.4 算法分析優(yōu)點：顯然，該算法通過引入“最小非高頻繁項集”的概念巧妙得處理了經(jīng)典Apriori算法產(chǎn)生候選項集過多的問題，再加上鏈表的應(yīng)用速度明顯提高，內(nèi)存占用也不大，用代碼實現(xiàn)起

14、來也很容易缺點：首先先考慮算法的可靠性問題，這是人們對一個算法所最關(guān)心的文中所述的算法可以說是以原始數(shù)據(jù)庫中的頻繁項集和最小非高頻繁項集為基礎(chǔ)的但是算法對三大定義中的最后一條考慮不周試想，若增量數(shù)據(jù)庫比原始數(shù)據(jù)庫還大，并且在增量數(shù)據(jù)庫中出現(xiàn)了新的，在原始數(shù)據(jù)庫中不曾出現(xiàn)過的新項集，上述算法如何處理？不論是LDB還是LMNI都沒有該項集的出現(xiàn)，顯然根據(jù)上述算法新的頻繁項集丟失了，同樣的問題也出現(xiàn)在對“非最小非高頻繁項集的處理上”下來我們來做個實驗：設(shè)原始數(shù)據(jù)庫仍為表2.3.1中的前條，新的增量數(shù)據(jù)庫ndb如下：表2.3.2 增量數(shù)據(jù)庫ndb編號事務(wù)72,5,6,785,6,795,6,7,810

15、6,7,8115,6,7,9125,6,9首先用Apriori算法挖掘DB得：LDB=1(4),3(4),4(3),5(3),13(3),15(3),45(3),LMNI =2(2),6(2),14(2),34(1),35(2)用db更新鏈表后變?yōu)?LDB=1(4),3(4),4(3),5(8),13(3),15(3),45(3)，LMNI=2(3),6(8),14(2),34(1),35(2)經(jīng)過第三步的處理，各鏈表變?yōu)?LDB=5;LMNI=6;LUB=5,6調(diào)用gen()函數(shù)產(chǎn)生候選項集并檢查其在UB中的支持度計數(shù):CUD=5(8),6(8),56(6)，：最后得到LUB=5,6,56,

16、算法結(jié)束根據(jù)頻繁項集的定義，更新后的數(shù)據(jù)庫中的頻率項集應(yīng)該是5,6,7,56,67，顯然頻繁項集7,67被丟失了雖然udb數(shù)據(jù)庫很特殊，但由此可證明IUAMAR算法失去了一搬性，是不可靠的而如果把minsup設(shè)成0.3或者用個一般的增量數(shù)據(jù)庫，UAMAR算法的缺點就被掩蓋了綜上所述，IUAMAR算法失去了最重要的可靠性，因而是失敗的3 基于事務(wù)樹的增量挖掘算法基于樹的頻繁項集挖掘算法一直就是另一個研究熱點，基于樹的挖掘算法最大的優(yōu)點就是不用產(chǎn)生候選項集，并且對事務(wù)數(shù)據(jù)庫的掃描次數(shù)很少下面，文章將介紹由業(yè)寧，逸生，厚立提出的基于事務(wù)線索樹的算法5，并分析它的優(yōu)缺點3.1 算法所使用的定義與概念定

17、 義 1 設(shè)I=是一組項目集，D是一組事務(wù)集(也稱之為事務(wù)數(shù)據(jù)庫).D中的每個事務(wù)即是一組項目定 義 2 設(shè)序列S=， 將序列分成任意的兩段S1=,S2=，其中,S1,S2非空，則稱SI為S2的前綴,S2為S1的后綴.定義 3 事務(wù)線索樹(transactiont hread tree,簡稱TT-tree)有且具有一個根結(jié)點，當結(jié)點數(shù)量n>1時，其余結(jié)點可以分為m(m>0)個互不相交的有限集,其中每個集合本身又是一棵樹.設(shè)根結(jié)點為第0層，根結(jié)點的全部子結(jié)點組成第1層，子結(jié)點的全部子結(jié)點組成第2層， ，依次類推，直到葉子結(jié)點.當層數(shù)大于1時，每個子結(jié)點都有一個唯一的指針指向其父結(jié)點，

18、稱該指針為線索.定 義 4 葉子結(jié)點所處的層數(shù)稱為路徑長度L定 義 5 結(jié)點索引表是由項目集I中的每一個項目I及支持度計數(shù)以及指向事務(wù)線索樹中I，的結(jié)點鏈指針組成定義TT-tree中的結(jié)點由兩個域構(gòu)成，Item域保存項目集的名稱，suport域保存該項目集當前的支持度計數(shù)3.2 TT -t re e構(gòu) 造 算 法輸入事務(wù)數(shù)據(jù)庫D輸出TT-tree算法步驟:stepl 打開事務(wù)數(shù)據(jù)庫;創(chuàng)建一個root結(jié)點.step2 while(事務(wù)數(shù)據(jù)庫結(jié)束?)step3 讀一條事務(wù)T=step4 將事務(wù)中的項目I排序.step5 for each I in Tstep6 if(Match(TT-tree,I

19、)為真)step7 Update ( TT-tree,Node)step8 elsestep9 Insert( TT-tree,I)stepl0 endifstepll endforstepl2 wend算法 中 的 3個子函數(shù)Match,Updat和Insert,分別定義如下:Match (TT-tree,I)函數(shù)從根結(jié)點開始匹配事務(wù)項目集序列和TT-tree上的一條路徑，如果匹配則返回true，否則返回false.Update(TT-tree,Node)函數(shù)將鏈表中Node的計數(shù)加1，再將結(jié)點索引表的計數(shù)加1.Insert (fatherNode,I)函數(shù)，形參為父結(jié)點fatherNode

20、和項目I它的過程如下：step1創(chuàng)建一個新結(jié)點step2將結(jié)的點的項目集域設(shè)為Istep3將結(jié)點的suport域設(shè)為1step4將結(jié)點的首指針指向fatherNodestep5判斷索引表中是否存在該結(jié)點的記錄，若存在，相當支持度計數(shù)加1,若不存在，則創(chuàng)建它，最后把索引表中的結(jié)點和樹中的相應(yīng)結(jié)點相連接下面舉個例子說明TT-Tree的構(gòu)造算法設(shè)事務(wù)數(shù)據(jù)庫如表3.2.1所示：表3.2.1 事務(wù)數(shù)據(jù)庫TID項集1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3按照上述算法可以得到如圖3.2.1的TT-tree：I1

21、I2I3I4I567622 RootI1:6I2:3I2:4I3:2I3:2I4:1I3:2I4:1I5:1I5:1圖3.2.1：TT-Tree同結(jié)點的線索指針指向父結(jié)點的指針結(jié)點索引表由上圖可知：如果從葉子結(jié)點逆向拆解TT-Tree，可以把圖還原為原來的事務(wù)數(shù)據(jù)庫，由此得到以下性質(zhì)： 性質(zhì)壓縮的TT-tree和事務(wù)數(shù)據(jù)庫是互逆的3.3 由TT-tree到關(guān)聯(lián)規(guī)則的產(chǎn)生定 理 1 最大頻繁集的長度小于等于線索樹中最長路徑的長度L.證 明 ：因為：最大頻繁集事務(wù)集所以：|最 大 頻 繁集的長度|事務(wù)集的長度|而 最長路徑的長度=max|事務(wù)集的長度|證 畢 .引理 1 頻繁集的全部非空子集都是頻

22、繁的.定理 2 設(shè) 路徑為，則一定有，該路徑的支持度計數(shù)為min(m,n,o,.,x)=x證明： 由于構(gòu)造TT-tree時，事務(wù)中的項目I中是按照序號排序的，且從root結(jié)點開始向下構(gòu)造.因此同一條路徑中的上層結(jié)點的數(shù)目一定大于等于下層結(jié)點的數(shù)目.因而 min(m,n,o,.,x)=x成立，證畢定理 3 從葉子結(jié)點開始，具有相同后綴全部路徑的交集A的支持度計數(shù)，等于各個路徑的子集A支持度計數(shù)之和.證明：根據(jù)TT-tree的構(gòu)造算法，若兩條路徑完全相同，在樹中的體現(xiàn)便是被壓縮到同一分枝中如果兩條路徑有不同的前綴，則相同的后綴被壓縮在同一分枝中，而不同的前綴在不同的分枝中因此要求兩條路徑相同后綴部

23、分的支持度計數(shù)，則將兩條路徑的支持度計數(shù)相加證畢定 理 4 通過逆向搜索TT-tree尋找各路徑及其路徑交集的支持度計數(shù)，如果其支持度計數(shù)大于等于頻繁集支持度，則路徑和路徑交集的集合以及所包含的子集皆為頻繁集.證 明 由性質(zhì)1可知，TT-tree是事務(wù)數(shù)據(jù)庫的壓縮存儲，其路徑的支持度計數(shù)反映了相同事務(wù)的個數(shù)，大于等于頻繁集支持度的路徑，其集合即為頻繁集.同理，由定理3可知，路徑交集的支持度計數(shù)大于等于頻繁集支持度，則路徑交集亦為頻繁集.易知頻繁集的子集一定是頻繁集.證畢挖 掘 算 法描述輸入 T T-tree輸 出 一個頻繁集表算 法 步 驟:step1 forEach Node in Ind

24、ex_table_for_Node/從結(jié)點索引表中的最后一個結(jié)點開始step2 if Node.spportminsuport/不滿足條件continue ;step3 elsestep4 將該結(jié)點插入FS1（頻繁1-項集）中根據(jù)結(jié)點索引表指針，尋找TT-Tree中的相同結(jié)點，再根據(jù)線索指針逆向搜索到根結(jié)點.產(chǎn)生以該結(jié)點為后綴的一條或多條路徑.step5 利用定理2計算各條路徑的支持度計數(shù)，利用定理3計算路徑交集的支持度計數(shù).step6 產(chǎn) 生頻繁集step7 end for下面以圖3.2.1為例說明該算法是如何工作的(設(shè)最小支持度計數(shù)為)首先查找結(jié)點索引表中的最后一個元素：I5,滿足條件，將

25、其插入FS1,FS1=I5:2搜索從I5到root的各條路徑：I1,I2,I5,I1,I2,I3,I5路徑長度：L(I1,I2,I5)=3，L(I1,I2,I3,I5)=4，路徑支持度計數(shù)S(I1,I2,I5)=min(I1,I2,I5)=min(6,4,1)=1，S(I1,I2,I3,I5)=min(I1,I2,I3,I5)=min(6,4,2,1)=1，為方便起見，把S(I1,I2,I5)=1簡記為I1,I2,I5:1最大長度為的頻繁項集（簡記為FS4）FS4=再計算路徑的交集I1,I2,I3,I5:1I1,I2,I5:1=I1,I2,I5:2得到FS3=I1,I2,I5:2根據(jù)引理可得F

26、S2=I1,I2:2,I1,I5:2,I2,I5:2再從結(jié)點索引表中的I4開始，F(xiàn)S1=I5:2,I4,2，搜索到root的各路徑：I1,I2,I4:1,I2,I4:1這兩條路徑本身不產(chǎn)生頻繁項集，考慮它們的交集I1,I2,I4:1I2,I4:1=I2,I4:2，更新FS2得FS2=I1,I2:2,I1,I5:2,I2,I4:2,I2,I5:2注意：此處所說的更新是指用最新的支持度計數(shù)代替原來的支持度計數(shù)而并非疊加因為交運算本身就處理了需要疊加的情況然后，從結(jié)點I3開始，F(xiàn)S1=I5:2,I4:2,I3:6，搜索I3到root的各路徑I1,I2,I3:2,I1,I3:2,I2,I3:2三條路徑

27、本身便是頻繁項集，更新相應(yīng)的FS得：FS3=I1,I2,I3:2,I1,I2,I5:2，F(xiàn)S2=I1,I2:2,I1,I3:2,I1,I5:2,I2,I3:2,I2,I5:2計算路徑交集I1,I2,I3:2I1,I3:2I2,I3:2=I3:6，暫不考慮FS1，I1,I2,I3:2I1,I3:2=I1,I3:4，I1,I2,I3:2I2,I3:2=I2,I3:4，I1,I3:2I2,I3:2=I3:4，更新相應(yīng)FS得：FS2=I1,I2:2,I1,I3:4,I1,I5:2,I2,I3:4,I2,I5:2從I2開始, FS1=I5:2,I4:2,I3:6,I2:7,搜索I2到root的路徑I1,

28、I2:4,I2:3 更新相應(yīng)的頻繁項集:FS2=I1,I2:4,I1,I3:4,I1,I5:2,I2,I3:4,I2,I5:2從I1開始, FS1=I5:2,I4:2,I3:6,I2:7,I1:6,搜索I1到root的路徑：I1:6算法結(jié)束最后得到如表3.3.1所示的頻繁項集：表格3.3.1 最終的頻繁項集FS4FS3FS2FS1I1,I2,I3:2I1,I2,I5:2I1,I2:4I1,I3:4I1,I5:2I2,I3:4I2,I5:2I2,I4:2I5:2I4:2I3:6I2:7I1:63.4 算法分析算法優(yōu)點：(1) 該算法支持增量頻繁模式挖掘，算法結(jié)束后，將TT-tree保存，若有新的

29、增量數(shù)據(jù)庫需要添加，可將增量數(shù)據(jù)庫在原TT-tree的基礎(chǔ)上壓縮成樹，即從數(shù)據(jù)庫的更新變成樹的更新，樹更新完畢后重新由樹生成關(guān)聯(lián)規(guī)則(2) 該算法只需要掃描一便原始數(shù)據(jù)庫，相比Apriori算法大大減少了IO開銷(3) 該算法利用樹（鏈表）來壓縮數(shù)據(jù)庫，并產(chǎn)生頻繁項集，不但節(jié)省了存貯空間，而且由于鏈表在內(nèi)存操作中的高速性，節(jié)省了算法實現(xiàn)后程序運行的時間開銷(4) 算法從整個數(shù)據(jù)庫著眼，從最大項集入手，對索引樹中的元素逐個處理，保證了產(chǎn)生頻繁項集的完整性，而支持度的合理更新，也保證了不會出現(xiàn)錯誤的冗余項集算法的缺點：(1) 若有增量數(shù)據(jù)庫加入，需要重新由TT-tree產(chǎn)生頻繁項集，上次挖掘產(chǎn)生的

30、結(jié)果沒有得到充分利用，而且增量數(shù)據(jù)庫越大，增量數(shù)據(jù)庫加入的次數(shù)越多，需要的重復(fù)的交運算越多，這個缺點越明顯(2) 若產(chǎn)生的TT-tree比較復(fù)雜，如各層（尤其是層）結(jié)點的數(shù)目過多，算法就面臨著大量的交運算但要保證算法的可靠性，這個缺點是不可避免的綜上所述，雖然“基于事務(wù)線索樹的一次掃描關(guān)聯(lián)規(guī)則增 量 挖 掘 算 法”具有它的弱點，但相對來說，它還是是一個成功的，高效的改進型算法4 基于散列思想的增量頻繁模式挖掘算法宋中山，成林輝，吳立峰，提出的LIUA算法便是基于散列的，非常簡單，容易實現(xiàn)，下面文章就介紹這個算法4.1LIUA算法簡介LIUA(ListIn crementalU pdating

31、A lgorithm，鏈表增量數(shù)據(jù)挖掘算法)利用鏈表插入、刪除效率高的特性，在數(shù)據(jù)挖掘的過程中充分保存以前已經(jīng)挖掘出來的信息，來提高隨后的增量挖掘的效率.算法主要分為掃描DB和掃描db兩部分.這里DB為更新前的目標數(shù)據(jù)庫，db為數(shù)據(jù)庫中新增加的記錄集.(1) 掃 描 DB.首先根據(jù)用戶輸人的物品的種類n建立n個鏈表Listn,Listi(i=1,2,.,n) 的每個節(jié)點存在兩個域:item域用來存放物品組合的名稱;count域用來存放對應(yīng)物品的支持度.Listi用來存放i-itemset(i-項集)的所有情況.例如:List1 存 放1-項集的所有情況，并根據(jù)count值按降序排列.然后 掃

32、描 DB中的第一條事務(wù)，得出這條事務(wù)的所有非空子集(非空子集代表這條事務(wù)中所有物品的組合情況)，根據(jù)非空子集物品的個數(shù)(項集的個數(shù))放人到對應(yīng)的鏈表中，例如:11,13是第一條事務(wù)的其中一個子集，由于它包含兩個物品:11,13，所以應(yīng)放入List2 中.如果此鏈表已經(jīng)包含該子集，則將對應(yīng)的count+1，并重新將鏈表按照降序有序化;如果此鏈表不包含該子集，則在鏈表尾加人該子集，同時將對應(yīng)的count置1.依次類推，對每條事務(wù)都進行類似的處理.(2) 掃 描 增加數(shù)據(jù)庫db.掃描db實現(xiàn)增量數(shù)據(jù)挖掘.在時間比較充裕，即用戶不是急需計算結(jié)果的情況下，我們可以采用掃描DB的辦法處理db，再把處理的結(jié)

33、果鏈表和已保存的DB的結(jié)果鏈表進行迭加，以便今后的增量數(shù)據(jù)挖掘.在時 間 比 較緊迫，即用戶需要在短時間內(nèi)得到關(guān)聯(lián)規(guī)則的情況下，用戶急需知道的并不是所有的關(guān)聯(lián)規(guī)則，可能只是需要符合某種條件的關(guān)聯(lián)規(guī)則來進行決策.此時可以要求用戶按照他的需求先設(shè)置參數(shù)，這樣可以提高查找效率，節(jié)省查找時間.相關(guān)參數(shù)有:num : 用戶 想知道的最大的關(guān)聯(lián)物品數(shù)量;minsup :用戶設(shè)立的門檻值(即關(guān)聯(lián)物品在事務(wù)數(shù)據(jù)庫中出現(xiàn)的最小次數(shù)).根據(jù) num 值選擇以前保留的List1 ,List2,.,Listnum鏈表;然后掃描庫里的每一條事務(wù)，得出小于等于num的非空子集(用戶想知道的關(guān)聯(lián)規(guī)則的相關(guān)物品的個數(shù))，根據(jù)

34、非空子集中項集的個數(shù)放人到對應(yīng)的鏈表中，處理方法類似掃描DB的處理方法.4.2算法描述(1) 掃 描 DBfor( i= 0; i<n ;i+)/n代表所有物品的種類creat Listi=NULL;/建立鏈表，并初始化for all TDB doproduce all_subset;/代表非空子集for all_subset docount subset.i; /計 算 當前非空子集的項集個數(shù)if(listi.find(subset)=TRUE)listi.subset.count+listi.sort/排序elseinsert end of listilisti.subset.cou

35、nt+由于 D B 存儲的是海量數(shù)據(jù)，在本次掃描中將會花費很長的時間.為了提高效率，可以考慮并行運算，將DB分成幾個部分，各部分分別用多臺機器進行掃描運算，最后將各鏈表進行迭加，這樣做將大大提高運算速度.在CPU的計算及硬件v0的發(fā)展情況來看，多維陣列的存儲方式，可以有效提供較佳的搜尋速度;而以目前硬件配置的價格日趨下降的趨勢來看，資料的存放空間已經(jīng)不是一個嚴重的問題了(2) 掃 描 增量數(shù)據(jù)庫dbfor all Tdb doproduce all_subsetnum;/產(chǎn)生小于等于num的子集for all subset docount subset.i;/計 算 當前非空子集的項集個數(shù)if

36、(listi.find(subset)=TRUE )Listi.subset.count+ ;Listil.sort; /排 序elselinsert end of Listilisti.subset.count+這個算法的思想很簡單，文章就不再舉例說明了4.3算法分析算法優(yōu)點：(1) 由于處理每一條事務(wù)的時候都考慮的它的所有子集，該算法顯然具有可靠性(2) 該算法只要掃描一邊事務(wù)數(shù)據(jù)庫(3) 該算法利用鏈表實現(xiàn)，減少了程序運行的時間開銷，同時由于鏈表保存了散列結(jié)果，有利于對增量數(shù)據(jù)庫的處理算法缺點：該算法最大的缺點是面對同一事務(wù)中項比較多的時候處理得非常緩慢，而通常原始數(shù)據(jù)庫比較大，包含“長

37、事務(wù)”的可能性也較大，因此該算法處理原始數(shù)據(jù)庫的時候要花不少時間，雖然文章也提出了用并行算法來解決這個問題，但這卻增量了處理器開銷5增量挖掘算法在火鍋銷售數(shù)據(jù)庫中的應(yīng)用5.1算法的選擇通過對上述三個增量頻繁模式挖掘算法的介紹，我們對增量頻繁模式的挖掘有了一定的認識，基于融合思想的算法，由于規(guī)則制定的復(fù)雜性，可靠程度不高，而且對原始、增量數(shù)據(jù)庫的挖掘也是基于原始的Apriori算法或其改進型，效率不是很理想基于散列思想的算法，對于增量數(shù)據(jù)庫的處理比較合適，因為增量數(shù)據(jù)庫通常情況下都比較小，但它對原始數(shù)據(jù)庫的處理不太理想，開銷很大幸好前面介紹的基于事務(wù)線索樹的算法，對于原始數(shù)據(jù)庫的處理非常合適因此

38、文章決定將“事務(wù)線索樹”和“散列”兩種算法結(jié)合起來以實現(xiàn)對火鍋銷售數(shù)據(jù)庫的增量挖掘由于增量數(shù)據(jù)挖掘采用散列的算法，所以要求在“基于事務(wù)線索樹的一次掃描關(guān)聯(lián)規(guī)則增 量 挖 掘 算 法”中，不但要挖掘出頻繁項集，而且也要保存非頻繁的項集，這可以通過項集鏈表來現(xiàn)實算法的描述數(shù)據(jù)結(jié)構(gòu)struct listitemsupportnext其中item為項集名稱，support為項集的支持度計數(shù),next指向下一個結(jié)點，以構(gòu)成鏈表(1) BEGAIN(2) 輸入DB,minsup(3) 使用3.2節(jié)的算法構(gòu)造事務(wù)樹(4) creat listn/創(chuàng)建一個數(shù)據(jù)，每個元素為一個鏈表，且listn存放所有的n-項

39、集如list存放所有的項集n為索引表的結(jié)點的個數(shù)，也代表一條事務(wù)中最大可能出現(xiàn)的項集數(shù)(5) forEach Node in Index_table_for_Node/從結(jié)點索引表中的最后一個結(jié)點開始(6) list1.insert(node) 將該結(jié)點插入list1（1-項集）中(7) 根據(jù)結(jié)點索引表指針，尋找TT-Tree中的相同結(jié)點，再根據(jù)線索指針逆向搜索到根結(jié)點.產(chǎn)生以該結(jié)點為后綴的一條或多條路徑.(8) 利用3.3節(jié)定理2，計算各條路徑的支持度計數(shù)，利用定理3計算路徑交集的支持度計數(shù).(9) 將所有路徑及其支持度計數(shù)插入到相應(yīng)的list鏈表中(10) end for(11) get

40、db/輸入增量數(shù)據(jù)庫(12) for each item in db/對增量數(shù)據(jù)庫中的每一項進行處理(13) creat subset/產(chǎn)生這條事務(wù)的所有非空子集(14) for each subset/處理每一個非空子集(15) subset.count/計算子集包含的項的個數(shù)(16) if(listsubset.count.find(subset)=TRUE)(17) listsubset.count.subset.support+(18) else(19) (20) listsubset.count.add(subset)(21) listsubset.count.subset.supp

41、ort=1(22) (23) end for(24) end for(25) for i=1,i<=n,i+/輸出頻繁i-項集(26) if(listi.item.cupport>=minsup)(27) (28) output listi.item(29) item+(30) (31) end for(32) END5.2 實現(xiàn)過程5.2.1 用戶界面用戶界面基于一個對話框，其中包含兩大部分如圖5.1：圖5.1 用戶界面圖5.1中左邊的文本框用來輸出關(guān)聯(lián)規(guī)則的挖掘結(jié)果，右邊的設(shè)置框用來指導(dǎo)用戶輸入原始增量數(shù)據(jù)庫，以及支持度計數(shù)的值，當用戶按下“確定”按鍵，程序首先判斷應(yīng)該進行原始

42、還是增量數(shù)據(jù)庫的挖掘，并調(diào)用相應(yīng)過程挖掘原始或增量數(shù)據(jù)庫中的頻繁項集，并將結(jié)果輸出在左邊的文本框中5.2.2文件的組織為了增量挖掘的需要，程序需要將5.1節(jié)算法中，由事務(wù)線索樹挖掘而出的項集列表（本例命名為itemsetlist）保存在一個外部文件（本例為itemlist.dat）詳細說明請參考文獻9，后面使用散列算法挖掘增量數(shù)據(jù)庫挖掘時，先將這個文件讀入到內(nèi)存中，再將散列得到的結(jié)果直接添加到列表中，最后保存，以便于下次的增量關(guān)聯(lián)規(guī)則挖掘由于項集列表中保存了所有的項集，因此向用戶輸出結(jié)果的時候需要對照用戶指定的支持度閾值，并將滿足條件的結(jié)果輸出項集在內(nèi)存中以動態(tài)創(chuàng)建的樹的方式保存，樹中的結(jié)點采

43、用CStringArray10與CUIntArray12對像相結(jié)合的方法來保存數(shù)據(jù)，CStringArray可以方便地對字符串進行操作，CUIntArray對數(shù)組的操作十分便利基于增量挖掘的需要，程序要用到不至一個數(shù)據(jù)庫，因此程序所用數(shù)據(jù)源需要動態(tài)注冊，這個可以使用SQLConfigDataSource()11函數(shù)實現(xiàn)，整個程序結(jié)束后再將數(shù)據(jù)源注銷整個程序的流程如圖5.2：輸入?yún)?shù)程序開始參數(shù)有效?Itemlist.dat存在？挖掘原始數(shù)據(jù)庫挖掘增量數(shù)據(jù)庫從itemsetlist中讀出項集項集頻繁？輸出項集結(jié)束表尾？YNNYYNYN圖5.2增量頻繁模式挖掘流程圖圖5.3(a)為挖掘原始數(shù)據(jù)庫的

44、流程，圖增量數(shù)據(jù)庫5.3(b)為挖掘增量數(shù)據(jù)庫的流程，由于基于事務(wù)線索樹的算法，和基于散列思想的算法已經(jīng)在前面詳細介紹過了，這是不再敘述輸入原始數(shù)據(jù)庫圖5.3(a):原始數(shù)據(jù)庫挖掘流程圖5.3(b):增量數(shù)據(jù)庫挖掘流程開始挖掘原始數(shù)據(jù)庫讀取數(shù)據(jù)庫中的一條記錄最后一條記錄?構(gòu)建事務(wù)樹頭構(gòu)建itemsetlist表頭更新事務(wù)樹頭使用索引樹算法挖掘事務(wù)樹更新itemsetlist表結(jié)束NY將itemsetlist表存入Itemlist.dat注冊數(shù)據(jù)源注銷數(shù)據(jù)源開始挖掘增量數(shù)據(jù)庫輸入增量數(shù)據(jù)庫從Itemsettab.bat中讀取iitemsetlist讀取數(shù)據(jù)庫中的一條記錄使用列散算法處理更新ite

45、msetlist表最后一條記錄?將itemsetlist表存入Itemlist.dat結(jié)束YN注冊數(shù)據(jù)源注銷數(shù)據(jù)源5.2.3程序示例:設(shè)有如表5.2.3.1的原始數(shù)據(jù)庫和如表5.2.3.2的增量數(shù)據(jù)庫:表5.3.2.1 原始數(shù)據(jù)庫DB事務(wù)編號I1I2I3I4I511100120101030110041101051010060110071100811101911100表5.2.3.1 增量數(shù)據(jù)庫NB事務(wù)編號I1I2I3I4I5101011201110310101411000510101運行結(jié)果如圖5.4圖5.4示例程序運行結(jié)果結(jié)束語:文章通過對前面所述幾種算法的分析，根據(jù)數(shù)據(jù)挖掘?qū)崿F(xiàn)的需要，選擇了基于事務(wù)樹的算法和基于散列思想的算法分別進行原始增量數(shù)據(jù)庫的挖掘，提高了