Apriori算法研究與應用

侯博宇

【摘要】Apriori算法是數據挖掘中關聯規則中一種算法，其應用比較廣泛，本論文主要介紹Apriori算法的基本思想、操作主要步驟、算法的描述、改進的Apriori算法及其的具體應用。

【關鍵詞】Apriori算法關聯研究與應用

Apriori算法是一種挖掘關聯規則的頻繁項集算法，其算法應用比較廣泛，尤其在商業領域。關聯規則的一個經典的例子就是在超市對顧客購買物品的分析。通過顧客購買各種商品總結發現物品與物品之間的關系，分析顧客在購買過程中的習慣與心理。什么樣的商品被顧客頻繁地同時購買，這樣就可以有助于商家制定營銷策略。關聯規則的計算依賴于發現相關數據中頻繁出現的數據項，尋找數據子集間的關聯關系或者一些數據與其他數據之間的派生關系。

一、Apriori算法的基本思想

1994年，Agrawal等提出了Apriori算法用于發現數據庫中的頻繁項集，主要使用逐層搜索的迭代算法，通過掃描數據庫得出頻繁項集，一般來說，約定第n次掃描得頻繁k-項集，記為Lk，首先對事務數據庫進行第一次掃描，找出候選頻繁1-項集，記為L1，然后利用L1來產生候選項集C2，對C2中的項進行挖掘出L2，即頻繁2-項集，一直重復循環，直到無法發現更多的頻繁k-項集為止。Apriori算法每挖掘一層Lk就需要對整個數據庫進行掃描。如果在求解過程中某次計算Lk為空時，那么整個算法的求解過程自然結束。

二、Apriori算法的主要步驟

1.對所有數據進行第一次掃描，生成候選1-項集合C1，計算項集的支持數，得到頻繁1-項集L1。

2.由Apriori-gen（L1）函數中的連接和剪枝兩步生成候選2-項集C2，然后進行第二次掃描數據庫，計算項集的支持數，得到頻繁2-項集L2。

3.按以上重復，LK進行自連接，生成候選K一項集CK，刪除CK中所有的非頻繁子集,生成K一頻繁項集LK。

4.重復3直到候選項集為空，不再產生頻繁項集，算法終止。

三、Apriori算法描述

Apriori具體的算法如下所示：

該算法的第一次遍歷計算第1個項集的支持度，以確定頻繁1-項集。然后的第k次遍歷包括兩個階段。

首先，除第1次掃描為單元素項目集構成的，使用Apriori-gen函數產生在第（k-1）次遍歷中找到頻繁項集Lk-1和候選項集Ck。繼續掃描整個數據庫，計算Ck中候選的支持度。并且用函數subset來幫助尋找己成為候選項集的子集，同時記錄每個候選項集的支持頻度，連接滿足最小支持度的候選集，最終得到頻繁集L。

四、改進Apriori算法

通過對算法的分析，我們能夠得出結論，Apriori算法存在著兩個弊端，一是每次找到頻繁項集和候選項集時都要掃描數據庫。二是事務數據庫D事務量較大時，產生的頻繁項集和候選項集數量也會很龐大。為了提高Apriori算法的效率，當前Apriori算法的改進有基于散列（Hash）的方法、AprioriTid 算法、基于數據分割（Partition）的方法、基于采樣（Sampling）的方法以及事務壓縮技術等，下面介紹幾種改進算法，并在此基礎上得到自己的改進算法。

經典 Apriori 算法對候選集進行整理，主要是對其大小進行了壓縮，但是Ck的生成過程中還是需要對整個事務數據庫進行k 次掃描。所以，在海量的數據庫中，經典 Apriori 算法的效率就會大大降低，占用系統的開銷也很大。AprioriTid 算法在候選頻繁項目集 Ck 的生成過程中，掃描事務時刪除其中不需要的，進行壓縮和整理事務數據庫，這樣掃描的效率得到了提高，占用系統的開銷也很小。掃描第一次數據庫后，候選集將不再使用事務數據庫D計算支持度，從第二步開始循環處理生成Tk，直到再沒有頻繁項集。生成集合Tk的每個成員形式為（TID，{Xk}），該集合與數據庫中事務相關，TID是事務標識，其中每個XK都是一個潛在的頻繁k-項目集。

參考文獻

[1]劉曉霞. 數據挖掘技術在高校教學管理系統中的應用研究. 中國海洋大學碩士論文，2010，8~16

[2]吳青，傅秀芬. 水平分布數據庫的正負關聯規則挖掘. 計算機技術與發展，2011，（6）：113~117