侯博宇
【摘要】Apriori算法是數(shù)據(jù)挖掘中關聯(lián)規(guī)則中一種算法,其應用比較廣泛,本論文主要介紹Apriori算法的基本思想、操作主要步驟、算法的描述、改進的Apriori算法及其的具體應用。
【關鍵詞】Apriori算法關聯(lián)研究與應用
Apriori算法是一種挖掘關聯(lián)規(guī)則的頻繁項集算法,其算法應用比較廣泛,尤其在商業(yè)領域。關聯(lián)規(guī)則的一個經(jīng)典的例子就是在超市對顧客購買物品的分析。通過顧客購買各種商品總結(jié)發(fā)現(xiàn)物品與物品之間的關系,分析顧客在購買過程中的習慣與心理。什么樣的商品被顧客頻繁地同時購買,這樣就可以有助于商家制定營銷策略。關聯(lián)規(guī)則的計算依賴于發(fā)現(xiàn)相關數(shù)據(jù)中頻繁出現(xiàn)的數(shù)據(jù)項,尋找數(shù)據(jù)子集間的關聯(lián)關系或者一些數(shù)據(jù)與其他數(shù)據(jù)之間的派生關系。
一、Apriori算法的基本思想
1994年,Agrawal等提出了Apriori算法用于發(fā)現(xiàn)數(shù)據(jù)庫中的頻繁項集,主要使用逐層搜索的迭代算法,通過掃描數(shù)據(jù)庫得出頻繁項集,一般來說,約定第n次掃描得頻繁k-項集,記為Lk,首先對事務數(shù)據(jù)庫進行第一次掃描,找出候選頻繁1-項集,記為L1,然后利用L1來產(chǎn)生候選項集C2,對C2中的項進行挖掘出L2,即頻繁2-項集,一直重復循環(huán),直到無法發(fā)現(xiàn)更多的頻繁k-項集為止。Apriori算法每挖掘一層Lk就需要對整個數(shù)據(jù)庫進行掃描。如果在求解過程中某次計算Lk為空時,那么整個算法的求解過程自然結(jié)束。
二、Apriori算法的主要步驟
1.對所有數(shù)據(jù)進行第一次掃描,生成候選1-項集合C1,計算項集的支持數(shù),得到頻繁1-項集L1。
2.由Apriori-gen(L1)函數(shù)中的連接和剪枝兩步生成候選2-項集C2,然后進行第二次掃描數(shù)據(jù)庫,計算項集的支持數(shù),得到頻繁2-項集L2。
3.按以上重復,LK進行自連接,生成候選K一項集CK,刪除CK中所有的非頻繁子集,生成K一頻繁項集LK。
4.重復3直到候選項集為空,不再產(chǎn)生頻繁項集,算法終止。
三、Apriori算法描述
Apriori具體的算法如下所示:
該算法的第一次遍歷計算第1個項集的支持度,以確定頻繁1-項集。然后的第k次遍歷包括兩個階段。
首先,除第1次掃描為單元素項目集構(gòu)成的,使用Apriori-gen函數(shù)產(chǎn)生在第(k-1)次遍歷中找到頻繁項集Lk-1和候選項集Ck。繼續(xù)掃描整個數(shù)據(jù)庫,計算Ck中候選的支持度。并且用函數(shù)subset來幫助尋找己成為候選項集的子集,同時記錄每個候選項集的支持頻度,連接滿足最小支持度的候選集,最終得到頻繁集L。
四、改進Apriori算法
通過對算法的分析,我們能夠得出結(jié)論,Apriori算法存在著兩個弊端,一是每次找到頻繁項集和候選項集時都要掃描數(shù)據(jù)庫。二是事務數(shù)據(jù)庫D事務量較大時,產(chǎn)生的頻繁項集和候選項集數(shù)量也會很龐大。為了提高Apriori算法的效率,當前Apriori算法的改進有基于散列(Hash)的方法、AprioriTid 算法、基于數(shù)據(jù)分割(Partition)的方法、基于采樣(Sampling)的方法以及事務壓縮技術等,下面介紹幾種改進算法,并在此基礎上得到自己的改進算法。
經(jīng)典 Apriori 算法對候選集進行整理,主要是對其大小進行了壓縮,但是Ck的生成過程中還是需要對整個事務數(shù)據(jù)庫進行k 次掃描。所以,在海量的數(shù)據(jù)庫中,經(jīng)典 Apriori 算法的效率就會大大降低,占用系統(tǒng)的開銷也很大。AprioriTid 算法在候選頻繁項目集 Ck 的生成過程中,掃描事務時刪除其中不需要的,進行壓縮和整理事務數(shù)據(jù)庫,這樣掃描的效率得到了提高,占用系統(tǒng)的開銷也很小。掃描第一次數(shù)據(jù)庫后,候選集將不再使用事務數(shù)據(jù)庫D計算支持度,從第二步開始循環(huán)處理生成Tk,直到再沒有頻繁項集。生成集合Tk的每個成員形式為(TID,{Xk}),該集合與數(shù)據(jù)庫中事務相關,TID是事務標識,其中每個XK都是一個潛在的頻繁k-項目集。
參考文獻
[1]劉曉霞. 數(shù)據(jù)挖掘技術在高校教學管理系統(tǒng)中的應用研究. 中國海洋大學碩士論文,2010,8~16
[2]吳青,傅秀芬. 水平分布數(shù)據(jù)庫的正負關聯(lián)規(guī)則挖掘. 計算機技術與發(fā)展,2011,(6):113~117