Apriori算法研究與應用

侯博宇

【摘要】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