基于臨時表的Apriori改進算法

1、基于臨時表的Apriori改良算法摘要Apriri算法在關(guān)聯(lián)規(guī)那么領(lǐng)域有很大的影響力，然而由于需要過于頻繁的掃描數(shù)據(jù)庫及較大的空間消耗，仍然有需要改良的地方。通過對Apriri算法進展深化研究，本文提出了基于臨時表的Apriri改良算法，通過比擬分析，獲得了較好的效率和性能。關(guān)鍵詞關(guān)聯(lián)規(guī)那么Apriri算法頻繁項集臨時表0引言數(shù)據(jù)挖掘Dataining)是數(shù)據(jù)庫知識發(fā)現(xiàn)KDD(KnledgeDisveryinDatabase)的核心,是指從數(shù)據(jù)庫中提取潛在的、有用的、最終可理解的知識的過程。關(guān)聯(lián)規(guī)那么算法那么是數(shù)據(jù)挖掘的一個重要研究方向,其側(cè)重于確定數(shù)據(jù)庫中不同領(lǐng)域間的聯(lián)絡(luò),找出滿足給定支持度

2、和可信度的多個域之間的互相關(guān)系4。簡單的說，關(guān)聯(lián)規(guī)那么就是給定一組工程Ite和一個記錄集合，通過分析記錄集合，推導(dǎo)出Ite間的相關(guān)性。1Apriri算法介紹1.1Apriri算法根本思想Apriri算法是發(fā)現(xiàn)關(guān)聯(lián)規(guī)那么領(lǐng)域的經(jīng)典算法。該算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)那么的過程分為兩個步驟：第一步通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集；第二步利用頻繁項集構(gòu)造出滿足用戶最小信任度的規(guī)那么5。詳細做法就是：首先找出頻繁1-項集，記為L1；然后利用L1來產(chǎn)生候選項集2，對2中的項進展斷定挖掘出L2，即頻繁2-項集；不斷如此循環(huán)下去直到無法發(fā)現(xiàn)更多的頻繁k-項集為止。每挖掘一層

3、Lk就需要掃描整個數(shù)據(jù)庫一遍。1.2Apriri算法描繪Apriri利用層次循環(huán)發(fā)現(xiàn)頻繁項集，算法如下：輸入：交易數(shù)據(jù)庫D，最小支持閾值in-sup輸出：D中的頻繁項集L然后利用Apriri性質(zhì)刪除那些子集為非頻繁項集的候選項集，一旦產(chǎn)生所有候選，就要掃描數(shù)據(jù)庫，對于數(shù)據(jù)庫中的每個交易利用subset函數(shù)來幫助發(fā)現(xiàn)該交易記錄的所有已成為候選項集的子集，由此累計每個候選項集的支持頻度。最終滿足最小支持頻度的候選項集組成了頻繁項集L。然而,像這樣產(chǎn)生候選集的開銷極大,特別是頻繁集很長或最小支持度非常小時。例如,當有104個頻繁1-項集時,Apriri算法就會產(chǎn)生多于107個的候選2-項集。針對Ap

4、riri算法的瓶頸，本文提出了一種基于臨時表的改良算法。2基于臨時表的Apriri改良算法2.1根本思想基于臨時表的Apriri改良算法利用了以下兩個事實：(1)對于規(guī)模的事務(wù)數(shù)據(jù)庫D，任意一個項集I的出現(xiàn)頻繁度與規(guī)模小于|I|的事務(wù)無關(guān)。所以在第|I|次掃描數(shù)據(jù)庫D時，可以刪除規(guī)模小于|I|的事務(wù)記錄。(2)k-候選項集中不包含任何(k-1)-項集的項集一定不是頻繁項集，因此k次掃描時可以將這樣的事務(wù)記錄立即刪除，從而減少了下次需要掃描的記錄數(shù)。用臨時表來完成頻繁項集的選擇。首先把(k-1)-項集中的第一個項集添加進臨時表中；然后把最后一項不同的其它項集添加進臨時表，生成k-項集，計算其頻繁

5、度，假設(shè)頻繁度大于最小頻繁度，那么生成該頻繁項并保存，否那么刪除。依此循環(huán)，直至生成所有的頻繁項。2.2改良算法的描繪輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值in_sup輸出：D的頻繁項集L變量說明：k：k-候選項集Lk：k-頻繁項集Dk：第k次掃描后的數(shù)據(jù)庫L1=large1-itesets;/D中的1-項集3改良前后的分析比擬為便于算法的比擬,選取文獻6中Apriri算法使用的AllEletrnis某分店的事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)進展算法模擬,如表1所示。TID項的列表T100I1,I2,I5T200I2,I4T300I2,I3T400I1,I2,I4T500I1,I3T600I2,I3T700I1,

6、I3T800I1,I2,I3,I5T900I1,I2,I3表1假定in_sup=2,Apriri算法執(zhí)行過程:(1)算法第一次掃描數(shù)據(jù)庫，確定1-項集及各元素的覆蓋頻度。如圖1所示：(2)利用L1L1來產(chǎn)生候選2-項集2，由2確定頻繁2-項集。如圖2所示：(3)利用L2L2進展連接操作，獲得候選3-項集3，為(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)。根據(jù)Apriri“一個頻繁項集的所有子集也是頻繁的的性質(zhì)，可以確定后四個項集不可能是頻繁的，因此可以刪除它們，從而減少了掃描次數(shù)。結(jié)果如圖3所示：圖3(4)利用L3L3進展連接操作

7、得到4，根據(jù)Apriri性質(zhì)可知4=。算法至此完畢。由此可見，Apriri算法每次掃描都要徹底掃描整個數(shù)據(jù)庫D，而改良后的算法及時的將不符合要求的項集刪除，從而減少了下次掃描數(shù)據(jù)庫的記錄數(shù)；Apriri算法進展連接操作時需生成完好的項集，而使用臨時表那么只需將最后一個不同的項進展連接，從而節(jié)省了大量的存儲空間。算法比擬結(jié)果如下表所示：表2說明：表2中數(shù)據(jù)庫規(guī)模是指數(shù)據(jù)庫中的記錄數(shù)，空間消耗是指生成的候選項集所占的空間。從表2可以看到，在掃描規(guī)模上，Apriri每次需要對所有的事務(wù)數(shù)據(jù)庫進展掃描，而基于臨時表的改良算法在第二趟數(shù)據(jù)掃描后，數(shù)據(jù)中二元組T200，T300，T500，T600，T70

8、0被刪除，第三次的掃描量減至4。在空間消耗上，第一次對5個單項進展判斷每一個單項占一位空間，需要的空間消耗為5。第二次進展JIN運算時，需要14+13+12+112=102=20個單元空間，第三次進展JIN運算，需要13+12+113=18個單元空間。臨時表壓縮算法采用了逐個動態(tài)生成頻繁項，依次所需空間均為1。4.完畢語本文在對Apriri挖掘算法的深化研究根底上，提出了基于臨時表的改良算法。通過分析比擬，在減少掃描數(shù)據(jù)庫中記錄數(shù)量和進展連接操作所需空間消耗上，獲得了較好的效果。與Apriri相比，基于臨時表的改良算法在數(shù)據(jù)規(guī)模及空間消耗上均占有優(yōu)勢，隨數(shù)據(jù)規(guī)模的增大，這種優(yōu)勢將更加明顯。參考

9、文獻：1RAgraal,Rrikant.FastAlgrithsfriningAssiatinRulesinLargeDatabases.Pr,20thintlnf.Verylargedatabases.1994：4784992argarentH.Dunha.DatainingIntrdutryandAdvanedTpis.SuthernehdistUniversity.20223BrinS,taniR.DynaiItesetuntingandIpliatinRulesfrarketBasketData.In:Pr.fthe1997A_SIGDInt1nf,ntheanageentfData.NeYrk:APress,19974陳江平,傅仲良,徐志紅.一種Apriri的改良算法.武漢大學(xué)學(xué)報(信息科學(xué)版),2022,2.5李雄飛，李軍.數(shù)據(jù)挖掘與知識發(fā)現(xiàn).北京：高等教育出版社，2022.6韓家煒.數(shù)據(jù)挖掘概念與技術(shù).北京:機械工業(yè)出版社,20017SavasereA,ngB,itbanderB.AneffiientalgrithfriningassiatinrulesinlargedatabasesA.InPr1995,IntnfVeryLargeDa