侯博宇

【摘要】Apriori算法是數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則中一種算法，其應(yīng)用比較廣泛，本論文主要介紹Apriori算法的基本思想、操作主要步驟、算法的描述、改進(jìn)的Apriori算法及其的具體應(yīng)用。

【關(guān)鍵詞】Apriori算法關(guān)聯(lián)研究與應(yīng)用

Apriori算法是一種挖掘關(guān)聯(lián)規(guī)則的頻繁項(xiàng)集算法，其算法應(yīng)用比較廣泛，尤其在商業(yè)領(lǐng)域。關(guān)聯(lián)規(guī)則的一個(gè)經(jīng)典的例子就是在超市對(duì)顧客購買物品的分析。通過顧客購買各種商品總結(jié)發(fā)現(xiàn)物品與物品之間的關(guān)系，分析顧客在購買過程中的習(xí)慣與心理。什么樣的商品被顧客頻繁地同時(shí)購買，這樣就可以有助于商家制定營銷策略。關(guān)聯(lián)規(guī)則的計(jì)算依賴于發(fā)現(xiàn)相關(guān)數(shù)據(jù)中頻繁出現(xiàn)的數(shù)據(jù)項(xiàng)，尋找數(shù)據(jù)子集間的關(guān)聯(lián)關(guān)系或者一些數(shù)據(jù)與其他數(shù)據(jù)之間的派生關(guān)系。

一、Apriori算法的基本思想

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

二、Apriori算法的主要步驟

1.對(duì)所有數(shù)據(jù)進(jìn)行第一次掃描，生成候選1-項(xiàng)集合C1，計(jì)算項(xiàng)集的支持?jǐn)?shù)，得到頻繁1-項(xiàng)集L1。

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

3.按以上重復(fù)，LK進(jìn)行自連接，生成候選K一項(xiàng)集CK，刪除CK中所有的非頻繁子集,生成K一頻繁項(xiàng)集LK。

4.重復(fù)3直到候選項(xiàng)集為空，不再產(chǎn)生頻繁項(xiàng)集，算法終止。

三、Apriori算法描述

Apriori具體的算法如下所示：

該算法的第一次遍歷計(jì)算第1個(gè)項(xiàng)集的支持度，以確定頻繁1-項(xiàng)集。然后的第k次遍歷包括兩個(gè)階段。

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

四、改進(jìn)Apriori算法

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

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

參考文獻(xiàn)

[1]劉曉霞. 數(shù)據(jù)挖掘技術(shù)在高校教學(xué)管理系統(tǒng)中的應(yīng)用研究. 中國海洋大學(xué)碩士論文，2010，8~16

[2]吳青，傅秀芬. 水平分布數(shù)據(jù)庫的正負(fù)關(guān)聯(lián)規(guī)則挖掘. 計(jì)算機(jī)技術(shù)與發(fā)展，2011，（6）：113~117