資源描述：
《基于臨時表的apriori改進算法》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在應(yīng)用文檔-天天文庫。
1、從本學科出發(fā)，應(yīng)著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果基于臨時表的Apriori改進算法摘要Apriori算法在關(guān)聯(lián)規(guī)則領(lǐng)域有很大的影響力，然而由于需要過于頻繁的掃描數(shù)據(jù)庫及較大的空間消耗，仍然有需要改進的地方。通過對Apriori算法進行深入研究，本文提出了，通過比較分析，獲得了較好的效率和性能。關(guān)鍵詞關(guān)聯(lián)規(guī)則Apriori算法頻繁項集臨時表0引言數(shù)據(jù)挖掘的子集，由此累計每個候選項集的支持頻度。最終滿足最小支持頻度的候選項集組成
2、了頻繁項集L。然而,像這樣產(chǎn)生候選集的開銷極大,特別是頻繁集很長或最小支持度非常小時。例如,當有104個頻繁1-項集時,Apriori算法就會產(chǎn)生多于107個的候選2-項集。針對Apriori算法的瓶頸，本文提出了一種基于臨時表的改進算法。2基于臨時表的Apriori改進算法基本思想利用了以下兩個事實：(1)對于已知規(guī)模的事務(wù)數(shù)據(jù)庫D，任意一個項集I的出現(xiàn)頻繁度與規(guī)模小于
3、I
4、的事務(wù)無關(guān)。所以在第
5、I
6、次掃描數(shù)據(jù)庫D時，可以刪除規(guī)模小于
7、I
8、的事務(wù)記錄。(2)k-候選項集中不包含任何(k-1)-項集的項集一定
9、不是頻繁項集，因此k次掃描時可以將這樣的事務(wù)記錄立即刪除，從而減少了下次需要掃描的記錄數(shù)。用臨時表來完成頻繁項集的選擇。首先把(k-1)-項集中的第一個項集添加進臨時表中；然后把最后一項不同的其它項集添加進臨時表，生成k-項集，計算課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙嫛谋緦W科出發(fā)，應(yīng)著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果其頻繁度，若頻繁度大于最小頻繁度，則
10、生成該頻繁項并保存，否則刪除。依此循環(huán)，直至生成所有的頻繁項。2.改進算法的描述輸入：事務(wù)數(shù)據(jù)庫D；最小支持度閾值min_sup輸出：D的頻繁項集L變量說明：Ck：k-候選項集Lk：k-頻繁項集Dk：第k次掃描后的數(shù)據(jù)庫L1={large1-itemsets};//D中的1-項集改進前后的分析比較為便于算法的比較,選取文獻[6]中Apriori算法使用的AllElectronics某分店的事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)進行算法模擬,如表1所示。TID項的列表T100I1,I2,I5T200I2,I4T300I2,I3T4
11、00I1,I2,I4T500I1,I3T600I2,I3T700I1,I3T800I1,I2,I3,I5T900I1,I2,I3表1假定min_sup=2,Apriori算法執(zhí)行過程:(1)算法第一次掃描數(shù)據(jù)庫，確定1-項集及各元素的覆蓋頻度。如圖1所示：(2)利用L1⊕L1來產(chǎn)生候選2-項集C2，由C2確定頻繁2-項集。如圖2所示：(3)利用L2⊕L2進行連接操作，獲得候選3-項集C3，為{(I1,I2,I3),(I1,I2,I5),(I1,I3,I5),(I2,I3,I5),(I2,I4,I5)}。根據(jù)A
12、priori“一個頻繁項集的所有子集也是頻繁的”的性質(zhì)，可以確定后四個項集不可能是頻繁的，因此可以刪除它們，從而減少了掃描次數(shù)。結(jié)果如圖3所示：圖3(4)課題份量和難易程度要恰當，博士生能在二年內(nèi)作出結(jié)果，碩士生能在一年內(nèi)作出結(jié)果，特別是對實驗條件等要有恰當?shù)墓烙嫛谋緦W科出發(fā)，應(yīng)著重選對國民經(jīng)濟具有一定實用價值和理論意義的課題。課題具有先進性，便于研究生提出新見解，特別是博士生必須有創(chuàng)新性的成果利用L3⊕L3進行連接操作得到C4，根據(jù)Apriori性質(zhì)可知C4=Φ。算法至此結(jié)束。由此可見，Apriori算法
13、每次掃描都要徹底掃描整個數(shù)據(jù)庫D，而改進后的算法及時的將不符合要求的項集刪除，從而減少了下次掃描數(shù)據(jù)庫的記錄數(shù)；Apriori算法進行連接操作時需生成完整的項集，而使用臨時表則只需將最后一個不同的項進行連接，從而節(jié)省了大量的存儲空間。算法比較結(jié)果如下表所示：表2說明：表2中數(shù)據(jù)庫規(guī)模是指數(shù)據(jù)庫中的記錄數(shù)，空間耗費是指生成的候選項集所占的空間。從表2可以看到，在掃描規(guī)模上，Apriori每次需要對所有的事務(wù)數(shù)據(jù)庫進行掃描，而基于臨時表的改進算法在第二趟數(shù)據(jù)掃描后，數(shù)據(jù)中二元組T200，T300，T500，T60
14、0，T700被刪除，第三次的掃描量減至4。在空間耗費上，第一次對個單項進行判斷每一個單項占一位空間，需要的空間耗費為。第二次進行JOIN運算時，需要×2=10×2=20個單元空間，第三次進行JOIN運算，需要×3=18個單元空間。臨時表壓縮算法采用了逐個動態(tài)生成頻繁項，依次所需空間均為1。4.結(jié)束語本文在對Apriori挖掘算法的深入研究基礎(chǔ)上，提出了基于臨時表的改進算法。通過分析比較，在減少掃描數(shù)
