基于臨時(shí)表的Apriori改進(jìn)算法

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

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

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

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

5、度，假設(shè)頻繁度大于最小頻繁度，那么生成該頻繁項(xiàng)并保存，否那么刪除。依此循環(huán)，直至生成所有的頻繁項(xiàng)。2.2改良算法的描繪輸入：事務(wù)數(shù)據(jù)庫(kù)D；最小支持度閾值in_sup輸出：D的頻繁項(xiàng)集L變量說明：k：k-候選項(xiàng)集Lk：k-頻繁項(xiàng)集Dk：第k次掃描后的數(shù)據(jù)庫(kù)L1=large1-itesets;/D中的1-項(xiàng)集3改良前后的分析比擬為便于算法的比擬,選取文獻(xiàn)6中Apriri算法使用的AllEletrnis某分店的事務(wù)數(shù)據(jù)庫(kù)中的數(shù)據(jù)進(jìn)展算法模擬,如表1所示。TID項(xiàng)的列表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ù)庫(kù)，確定1-項(xiàng)集及各元素的覆蓋頻度。如圖1所示：(2)利用L1L1來產(chǎn)生候選2-項(xiàng)集2，由2確定頻繁2-項(xiàng)集。如圖2所示：(3)利用L2L2進(jìn)展連接操作，獲得候選3-項(xiàng)集3，為(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)。根據(jù)Apriri“一個(gè)頻繁項(xiàng)集的所有子集也是頻繁的的性質(zhì)，可以確定后四個(gè)項(xiàng)集不可能是頻繁的，因此可以刪除它們，從而減少了掃描次數(shù)。結(jié)果如圖3所示：圖3(4)利用L3L3進(jìn)展連接操作

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

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

9、文獻(xiàn)：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é)報(bào)(信息科學(xué)版),2022,2.5李雄飛，李軍.數(shù)據(jù)挖掘與知識(shí)發(fā)現(xiàn).北京：高等教育出版社，2022.6韓家煒.數(shù)據(jù)挖掘概念與技術(shù).北京:機(jī)械工業(yè)出版社,20017SavasereA,ngB,itbanderB.AneffiientalgrithfriningassiatinrulesinlargedatabasesA.InPr1995,IntnfVeryLargeDa