何云峰

摘要：Apriori算法雖是關聯(lián)規(guī)則中的基本算法，但其使用效率并不是太高。幸運的是經(jīng)過20多年的發(fā)展，迄今已經(jīng)相當成熟。除了外國學者不斷改進外，中國學者對此也花費了不少代價。從apriori算法的性質(zhì)，Apriori算法與其他算法的綜合使用等方面，對中國學者在Apriori算法的改進研究方面進行了比較全面的總結(jié)。

關鍵詞：Apriori算法；改進的Apriori算法；算法綜述

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2017）02-0153-01

1 引言

關聯(lián)規(guī)則挖掘中最經(jīng)典的Apriori算法在1993年被R.Agrawl等人于提出，該算法的目的在于從數(shù)據(jù)庫中找出最大項目集從而生成關聯(lián)規(guī)則。

隨后，其改進算法AprioriTid和AprioriHybird被提出，AprioriTid的特點是在第一次遍歷數(shù)據(jù)庫之后，就改用掃描生成的候選項集，同時計算出頻繁項集的支持度的思想，就不再掃描數(shù)據(jù)庫了。AprioriHybird算法則是結(jié)合了Apriori和AprioriTid的各自特點，即在開始時先用Apriori掃描數(shù)據(jù)庫，當生成的候選項集能夠存放到內(nèi)存中時，就要轉(zhuǎn)成AprioriTid，這樣開銷就小了很多。接下來，又有人提出了DHP算法。

2 正文

我國學者研究關聯(lián)規(guī)則挖掘始于2000年左右，主要思路也是跟著國外學者的想法。

從Apriori算法性質(zhì)方面有學者提出了改進，這些性質(zhì)主要包括：1）對于一個k維的Tk數(shù)據(jù)項集，如果Tk是k維最大項集，則在k-1維數(shù)據(jù)項集生成的集合Lk-1中包含k-1維子集的個數(shù)一定要不小于k。同時在Lk-1中的剪枝操作[1]也利用了這個性質(zhì)。2）對于k維頻繁項集，由其產(chǎn)生的所有k-1維子集都是頻繁的，而且子集的個數(shù)一定等于k。根據(jù)這一性質(zhì)提出改進，在產(chǎn)生頻繁1項集L1和頻繁2項集L2后，準備生成頻繁3項集時，先由頻繁2項集組合生成候選3項集C3，之后再把L2中每個元素順次取出，再與C3的子集比較，是則進行計數(shù)加1的操作，重復這個步驟得到C3中個元素的計數(shù)，計數(shù)等于3的就是3項頻繁集。重復這種方法就得到更多頻繁集的生成。

也有不少學者從數(shù)據(jù)庫掃描次數(shù)和數(shù)據(jù)庫容量消減方面提出了改進。有學者曾使用通過在頻繁項集Lk-1中的篩選，再在數(shù)據(jù)庫中找到不滿足最小支持度的元素及所包含它們的事務，從而把該（k-1）項目的事務刪除，即縮小了數(shù)據(jù)庫容量，同時也提高了剪枝操作的效率。在評估候選頻繁項集時使用概率法和用戶興趣度，從而篩選掉一些不太感興趣的事務，也能縮小數(shù)據(jù)庫的大小。有學者在2008年使用僅2次掃描數(shù)據(jù)庫的思路重組原始數(shù)據(jù)庫[2]。

在轉(zhuǎn)換數(shù)據(jù)庫存儲方式方面有很多學者也做了不少努力，在2004年有學者提出了用矩陣表示數(shù)據(jù)庫的思想，用矩陣的每一行來表示每一條事務，每行中有項目的位置逐次加1，最后可得到支持度矩陣[3]。過了2年，有人提出在轉(zhuǎn)為矩陣的基礎上[3]，再使用自定義的矩陣的方法去完成剪枝步驟；還有使用行向量內(nèi)積的方法去搜尋頻繁項集。2009年有學者提出了一種較新的處理事務的方法——二元組表示法，把原始事務數(shù)據(jù)庫用一個項目串和串的出現(xiàn)頻率的二維組來替換，當然這個二元組的創(chuàng)建需要把數(shù)據(jù)庫掃描一遍。例如這樣的形式[I1I2I3，3]。如果該二元組能用鏈表結(jié)構來表示，則能加快一定速度[4]。既然能通過普通鏈表實現(xiàn)存儲，那用十字鏈表方式存儲數(shù)據(jù)庫的事務也有學者進行了嘗試。還有學者直接把數(shù)據(jù)庫的存儲形式進行了改變，比如原來的表示方式是用第幾條事務是由哪幾個元素組成的，形如“M1A，C，F(xiàn)”，現(xiàn)在則變?yōu)槟男┰乇荒男┦聞瞻?，即“BM2M4M6M7”形式。這種方法實際并沒有帶來太大的改進效果，應該說只是換了個花樣。另外，把Hash技術、散列表技術應用于數(shù)據(jù)庫的處理中也起到了良好的效果。比如在產(chǎn)生1_頻繁項目集和2_頻繁項目集時，使用hash技術或散列表技術。

從Apriori算法與其他算法的綜合使用方面來看，可謂是多種多樣，精彩紛呈。有在IDS日志分析中使用Apriori算法與聚類算法相結(jié)合的。也有使用Apriori算法和遺傳算法相結(jié)合對數(shù)據(jù)庫進行處理的。還有在云計算中使用Apriori算法[5]以及在矩陣聚類法中使用Apriori算法的。

3 結(jié)語

Apriori算法經(jīng)過若干年的發(fā)展研究，出現(xiàn)了各種各樣的改進。無論從算法本身角度去發(fā)展還是和其他算法聯(lián)合使用，現(xiàn)今的Apriori算法已經(jīng)到了一種發(fā)展到頂?shù)奈兜?，似乎很難再有什么大的突破。

參考文獻

[1]胡吉明，鮮學豐.挖掘關聯(lián)規(guī)則中Apriori算法的研究與改進[J].計算機技術與發(fā)展，2006，16（4）：99-101.

[2]郭健美，宋順林，李世松.基于Apriori算法的改進算法[J].計算機工程與設計，2008，29（11）：2814-2815.

[3]馬盈倉.挖掘關聯(lián)規(guī)則中Apriori算法的改進[J].計算機應用與軟件，2004，21（11）：82-83.

[4]張春生.改進的數(shù)據(jù)庫一次掃描快速Apriori算法[J].計算機工程與設計，2009，30（16）：3811-3813.

[5]吳琪.基于云計算的Apriori挖掘算法[J].計算機測量與控制，2012，20（6）：1653-1655.