關于改進的Apriori算法綜述

何云峰

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

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

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

1 引言

關聯規則挖掘中最經典的Apriori算法在1993年被R.Agrawl等人于提出，該算法的目的在于從數據庫中找出最大項目集從而生成關聯規則。

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

2 正文

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

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

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

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

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

3 結語

Apriori算法經過若干年的發展研究，出現了各種各樣的改進。無論從算法本身角度去發展還是和其他算法聯合使用，現今的Apriori算法已經到了一種發展到頂的味道，似乎很難再有什么大的突破。

參考文獻

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

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

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

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

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