增量數據挖掘初探

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

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

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

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

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

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

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

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

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

10、項目集掃描更新后的UD一次，找出所有候選項目集在UD中出現的次數 ， 如果候選項目集X出現的次數，則這些項目集和更新后的LB、LMNI中的項目集合并一起成為更新數據庫中的高頻項目集算法的偽代碼描述:BEGAINApriori(DB,LDB,LMNI,LUB)/算法的第一步IUAMAR(DB,db，minsup)For each Transaction T in db/掃描db中的每項Updating(db,LDB,UMll);/用db中的記錄更新兩鏈表各項目集出現的次數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()產生候選項目集CUDFor each itemset X in CUDif(Cx)/不滿足條件CUD=CUD-XLUB=LUBCUDEND2.3 實例說明表2.3.1 事務數據庫編號事務編號事務11,2,361,3,4,521,4,573,4,531,3,582,344,5,691,3,4,552,3,6102,6表格 2.3.1設DB為表2.3.1中第條事務，db為表2.3.1中第條事務，minsup=0.4現利用上述算法對其進行增量挖

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)其中小括號中的數字是該集合在相應數據庫中出現的總次數用db更新鏈表后變為: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)經過第三步的處理，各鏈表變為:LDB=1,3,4,5,13,15,45;LMNI=2,35;LUB=1,2,3,4,5,13,15,35,45調用gen()函數產生候選項集:CUD=1,2,3

13、,4,5,13,15,45,12,23,24,25,123,125,245,35,135,345，檢查其在UB中的支持度計數：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,算法結束2.4 算法分析優點：顯然，該算法通過引入“最小非高頻繁項集”的概念巧妙得處理了經典Apriori算法產生候選項集過多的問題，再加上鏈表的應用速度明顯提高，內存占用也不大，用代碼實現起

14、來也很容易缺點：首先先考慮算法的可靠性問題，這是人們對一個算法所最關心的文中所述的算法可以說是以原始數據庫中的頻繁項集和最小非高頻繁項集為基礎的但是算法對三大定義中的最后一條考慮不周試想，若增量數據庫比原始數據庫還大，并且在增量數據庫中出現了新的，在原始數據庫中不曾出現過的新項集，上述算法如何處理？不論是LDB還是LMNI都沒有該項集的出現，顯然根據上述算法新的頻繁項集丟失了，同樣的問題也出現在對“非最小非高頻繁項集的處理上”下來我們來做個實驗：設原始數據庫仍為表2.3.1中的前條，新的增量數據庫ndb如下：表2.3.2 增量數據庫ndb編號事務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更新鏈表后變為: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)經過第三步的處理，各鏈表變為:LDB=5;LMNI=6;LUB=5,6調用gen()函數產生候選項集并檢查其在UB中的支持度計數:CUD=5(8),6(8),56(6)，：最后得到LUB=5,6,56,

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

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

18、稱該指針為線索.定 義 4 葉子結點所處的層數稱為路徑長度L定 義 5 結點索引表是由項目集I中的每一個項目I及支持度計數以及指向事務線索樹中I，的結點鏈指針組成定義TT-tree中的結點由兩個域構成，Item域保存項目集的名稱，suport域保存該項目集當前的支持度計數3.2 TT -t re e構 造 算 法輸入事務數據庫D輸出TT-tree算法步驟:stepl 打開事務數據庫;創建一個root結點.step2 while(事務數據庫結束?)step3 讀一條事務T=step4 將事務中的項目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個子函數Match,Updat和Insert,分別定義如下:Match (TT-tree,I)函數從根結點開始匹配事務項目集序列和TT-tree上的一條路徑，如果匹配則返回true，否則返回false.Update(TT-tree,Node)函數將鏈表中Node的計數加1，再將結點索引表的計數加1.Insert (fatherNode,I)函數，形參為父結點fatherNode

20、和項目I它的過程如下：step1創建一個新結點step2將結的點的項目集域設為Istep3將結點的suport域設為1step4將結點的首指針指向fatherNodestep5判斷索引表中是否存在該結點的記錄，若存在，相當支持度計數加1,若不存在，則創建它，最后把索引表中的結點和樹中的相應結點相連接下面舉個例子說明TT-Tree的構造算法設事務數據庫如表3.2.1所示：表3.2.1 事務數據庫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同結點的線索指針指向父結點的指針結點索引表由上圖可知：如果從葉子結點逆向拆解TT-Tree，可以把圖還原為原來的事務數據庫，由此得到以下性質： 性質壓縮的TT-tree和事務數據庫是互逆的3.3 由TT-tree到關聯規則的產生定 理 1 最大頻繁集的長度小于等于線索樹中最長路徑的長度L.證 明 ：因為：最大頻繁集事務集所以：|最 大 頻 繁集的長度|事務集的長度|而 最長路徑的長度=max|事務集的長度|證 畢 .引理 1 頻繁集的全部非空子集都是頻

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

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

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

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

27、本身便是頻繁項集，更新相應的FS得：FS3=I1,I2,I3:2,I1,I2,I5:2，FS2=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，更新相應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 更新相應的頻繁項集: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算法結束最后得到如表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 算法分析算法優點：(1) 該算法支持增量頻繁模式挖掘，算法結束后，將TT-tree保存，若有新的

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

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

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

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

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

34、非空子集中項集的個數放人到對應的鏈表中，處理方法類似掃描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; /計 算 當前非空子集的項集個數if(listi.find(subset)=TRUE)listi.subset.count+listi.sort/排序elseinsert end of listilisti.subset.cou

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

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

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

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

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

40、db/輸入增量數據庫(12) for each item in db/對增量數據庫中的每一項進行處理(13) creat subset/產生這條事務的所有非空子集(14) for each subset/處理每一個非空子集(15) subset.count/計算子集包含的項的個數(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 實現過程5.2.1 用戶界面用戶界面基于一個對話框，其中包含兩大部分如圖5.1：圖5.1 用戶界面圖5.1中左邊的文本框用來輸出關聯規則的挖掘結果，右邊的設置框用來指導用戶輸入原始增量數據庫，以及支持度計數的值，當用戶按下“確定”按鍵，程序首先判斷應該進行原始

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

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

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

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