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

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

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

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

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

6、法分別挖掘出原始、增量數(shù)據(jù)庫中的頻繁項(xiàng)集，然后對它們進(jìn)行融合融合的時(shí)候需要以下三大結(jié)論的支持：設(shè)K是項(xiàng)集，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是頻繁項(xiàng)集，NDB是更新后的數(shù)據(jù)庫以上結(jié)論很容易根據(jù)頻繁項(xiàng)集的定義得到證明有了上面的理論，很多學(xué)者對此思想產(chǎn)生的算法進(jìn)行了一些研究、改進(jìn)，比如：只需要挖掘出原始數(shù)據(jù)庫中的頻繁項(xiàng)集，而用其

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

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

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

10、項(xiàng)目集掃描更新后的UD一次，找出所有候選項(xiàng)目集在UD中出現(xiàn)的次數(shù) ， 如果候選項(xiàng)目集X出現(xiàn)的次數(shù)，則這些項(xiàng)目集和更新后的LB、LMNI中的項(xiàng)目集合并一起成為更新數(shù)據(jù)庫中的高頻項(xiàng)目集算法的偽代碼描述:BEGAINApriori(DB,LDB,LMNI,LUB)/算法的第一步IUAMAR(DB,db，minsup)For each Transaction T in db/掃描db中的每項(xiàng)Updating(db,LDB,UMll);/用db中的記錄更新兩鏈表各項(xiàng)目集出現(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)生候選項(xiàng)目集CUDFor each itemset X in CUDif(Cx)/不滿足條件CUD=CUD-XLUB=LUBCUDEND2.3 實(shí)例說明表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)利用上述算法對其進(jì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)生候選項(xiàng)集:CUD=1,2,3

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

14、來也很容易缺點(diǎn)：首先先考慮算法的可靠性問題，這是人們對一個(gè)算法所最關(guān)心的文中所述的算法可以說是以原始數(shù)據(jù)庫中的頻繁項(xiàng)集和最小非高頻繁項(xiàng)集為基礎(chǔ)的但是算法對三大定義中的最后一條考慮不周試想，若增量數(shù)據(jù)庫比原始數(shù)據(jù)庫還大，并且在增量數(shù)據(jù)庫中出現(xiàn)了新的，在原始數(shù)據(jù)庫中不曾出現(xiàn)過的新項(xiàng)集，上述算法如何處理？不論是LDB還是LMNI都沒有該項(xiàng)集的出現(xiàn)，顯然根據(jù)上述算法新的頻繁項(xiàng)集丟失了，同樣的問題也出現(xiàn)在對“非最小非高頻繁項(xiàng)集的處理上”下來我們來做個(gè)實(shí)驗(yà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)生候選項(xiàng)集并檢查其在UB中的支持度計(jì)數(shù):CUD=5(8),6(8),56(6)，：最后得到LUB=5,6,56,

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

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

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

20、和項(xiàng)目I它的過程如下：step1創(chuàng)建一個(gè)新結(jié)點(diǎn)step2將結(jié)的點(diǎn)的項(xiàng)目集域設(shè)為Istep3將結(jié)點(diǎn)的suport域設(shè)為1step4將結(jié)點(diǎn)的首指針指向fatherNodestep5判斷索引表中是否存在該結(jié)點(diǎn)的記錄，若存在，相當(dāng)支持度計(jì)數(shù)加1,若不存在，則創(chuàng)建它，最后把索引表中的結(jié)點(diǎn)和樹中的相應(yīng)結(jié)點(diǎn)相連接下面舉個(gè)例子說明TT-Tree的構(gòu)造算法設(shè)事務(wù)數(shù)據(jù)庫如表3.2.1所示：表3.2.1 事務(wù)數(shù)據(jù)庫TID項(xiàng)集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é)點(diǎn)的線索指針指向父結(jié)點(diǎn)的指針結(jié)點(diǎn)索引表由上圖可知：如果從葉子結(jié)點(diǎn)逆向拆解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.證 明 ：因?yàn)椋鹤畲箢l繁集事務(wù)集所以：|最 大 頻 繁集的長度|事務(wù)集的長度|而 最長路徑的長度=max|事務(wù)集的長度|證 畢 .引理 1 頻繁集的全部非空子集都是頻

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

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

24、ex_table_for_Node/從結(jié)點(diǎn)索引表中的最后一個(gè)結(jié)點(diǎn)開始step2 if Node.spportminsuport/不滿足條件continue ;step3 elsestep4 將該結(jié)點(diǎn)插入FS1（頻繁1-項(xiàng)集）中根據(jù)結(jié)點(diǎn)索引表指針，尋找TT-Tree中的相同結(jié)點(diǎn)，再根據(jù)線索指針逆向搜索到根結(jié)點(diǎn).產(chǎn)生以該結(jié)點(diǎn)為后綴的一條或多條路徑.step5 利用定理2計(jì)算各條路徑的支持度計(jì)數(shù)，利用定理3計(jì)算路徑交集的支持度計(jì)數(shù).step6 產(chǎn) 生頻繁集step7 end for下面以圖3.2.1為例說明該算法是如何工作的(設(shè)最小支持度計(jì)數(shù)為)首先查找結(jié)點(diǎn)索引表中的最后一個(gè)元素：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，路徑支持度計(jì)數(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最大長度為的頻繁項(xiàng)集（簡記為FS4）FS4=再計(jì)算路徑的交集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é)點(diǎn)索引表中的I4開始，F(xiàn)S1=I5:2,I4,2，搜索到root的各路徑：I1,I2,I4:1,I2,I4:1這兩條路徑本身不產(chǎn)生頻繁項(xiàng)集，考慮它們的交集I1,I2,I4:1I2,I4:1=I2,I4:2，更新FS2得FS2=I1,I2:2,I1,I5:2,I2,I4:2,I2,I5:2注意：此處所說的更新是指用最新的支持度計(jì)數(shù)代替原來的支持度計(jì)數(shù)而并非疊加因?yàn)榻贿\(yùn)算本身就處理了需要疊加的情況然后，從結(jié)點(diǎn)I3開始，F(xiàn)S1=I5:2,I4:2,I3:6，搜索I3到root的各路徑I1,I2,I3:2,I1,I3:2,I2,I3:2三條路徑

27、本身便是頻繁項(xiàng)集，更新相應(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計(jì)算路徑交集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)的頻繁項(xià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所示的頻繁項(xiàng)集：表格3.3.1 最終的頻繁項(xiàng)集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)點(diǎn)：(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)生頻繁項(xiàng)集，不但節(jié)省了存貯空間，而且由于鏈表在內(nèi)存操作中的高速性，節(jié)省了算法實(shí)現(xiàn)后程序運(yùn)行的時(shí)間開銷(4) 算法從整個(gè)數(shù)據(jù)庫著眼，從最大項(xiàng)集入手，對索引樹中的元素逐個(gè)處理，保證了產(chǎn)生頻繁項(xiàng)集的完整性，而支持度的合理更新，也保證了不會出現(xiàn)錯(cuò)誤的冗余項(xiàng)集算法的缺點(diǎn)：(1) 若有增量數(shù)據(jù)庫加入，需要重新由TT-tree產(chǎn)生頻繁項(xiàng)集，上次挖掘產(chǎn)生的

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

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

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

33、果鏈表和已保存的DB的結(jié)果鏈表進(jìn)行迭加，以便今后的增量數(shù)據(jù)挖掘.在時(shí) 間 比 較緊迫，即用戶需要在短時(shí)間內(nèi)得到關(guān)聯(lián)規(guī)則的情況下，用戶急需知道的并不是所有的關(guān)聯(lián)規(guī)則，可能只是需要符合某種條件的關(guān)聯(lián)規(guī)則來進(jìn)行決策.此時(shí)可以要求用戶按照他的需求先設(shè)置參數(shù)，這樣可以提高查找效率，節(jié)省查找時(shí)間.相關(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)物品的個(gè)數(shù))，根據(jù)

34、非空子集中項(xiàng)集的個(gè)數(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; /計(jì) 算 當(dāng)前非空子集的項(xiàng)集個(gè)數(shù)if(listi.find(subset)=TRUE)listi.subset.count+listi.sort/排序elseinsert end of listilisti.subset.cou

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

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

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

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

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

40、db/輸入增量數(shù)據(jù)庫(12) for each item in db/對增量數(shù)據(jù)庫中的每一項(xiàng)進(jìn)行處理(13) creat subset/產(chǎn)生這條事務(wù)的所有非空子集(14) for each subset/處理每一個(gè)非空子集(15) subset.count/計(jì)算子集包含的項(xiàng)的個(gè)數(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-項(xiàng)集(26) if(listi.item.cupport>=minsup)(27) (28) output listi.item(29) item+(30) (31) end for(32) END5.2 實(shí)現(xiàn)過程5.2.1 用戶界面用戶界面基于一個(gè)對話框，其中包含兩大部分如圖5.1：圖5.1 用戶界面圖5.1中左邊的文本框用來輸出關(guān)聯(lián)規(guī)則的挖掘結(jié)果，右邊的設(shè)置框用來指導(dǎo)用戶輸入原始增量數(shù)據(jù)庫，以及支持度計(jì)數(shù)的值，當(dāng)用戶按下“確定”按鍵，程序首先判斷應(yīng)該進(jìn)行原始

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

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

44、流程，圖增量數(shù)據(jù)庫5.3(b)為挖掘增量數(shù)據(jù)庫的流程，由于基于事務(wù)線索樹的算法，和基于散列思想的算法已經(jīng)在前面詳細(xì)介紹過了，這是不再敘述輸入原始數(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運(yùn)行結(jié)果如圖5.4圖5.4示例程序運(yùn)行結(jié)果結(jié)束語:文章通過對前面所述幾種算法的分析，根據(jù)數(shù)據(jù)挖掘?qū)崿F(xiàn)的需要，選擇了基于事務(wù)樹的算法和基于散列思想的算法分別進(jìn)行原始增量數(shù)據(jù)庫的挖掘，提高了