Apriori改進(jìn)算法綜述

何云峰

(泉州醫(yī)學(xué)高等?？茖W(xué)校，福建 泉州 362011)

AGRAWL R等人于1993年提出了挖掘關(guān)聯(lián)規(guī)則最具影響力的Apriori算法。該算法的基本思想是先找出事務(wù)數(shù)據(jù)庫中具有最小支持度的項目集(即最大項目集)，再根據(jù)最大項目集生成關(guān)聯(lián)規(guī)則。其中生成最大項目集是核心問題，其思想為：第一步，統(tǒng)計所有含一個元素項目集出現(xiàn)的頻率，并找出不小于最小支持度的項目集，從第二步開始循環(huán)處理直到再沒有最大項目集生成。循環(huán)過程是：在第k步中，根據(jù)第k-1步生成的k-1維最大項目集產(chǎn)生k維候選項目集，然后對數(shù)據(jù)庫進(jìn)行搜索，得到候選項目集的項集支持度，并與最小支持度比較，從而找到k維最大項目集。

之后，AGRAWL R等人又提出了Apriori算法的改進(jìn)算法AprioriTid算法和AprioriHybird算法。AprioriTid算法對Apriori算法做了調(diào)整，它的特點是在第一次遍歷數(shù)據(jù)庫之后，就不再掃描數(shù)據(jù)庫，而是用上次掃描生成的候選項目集，掃描的同時還會計算出頻繁項目集的支持度。該算法以候選項目集來代替原數(shù)據(jù)庫，從而減少了總是要掃描原數(shù)據(jù)庫統(tǒng)計支持計數(shù)的開銷。AprioriHybird算法則是Apriori和AprioriTid的結(jié)合，初始掃描數(shù)據(jù)庫時采用Apriori算法，當(dāng)生成的候選項目集大小可以存放到內(nèi)存中進(jìn)行處理時采再轉(zhuǎn)成AprioriTid算法。1995年P(guān)ARK等人提出了DHP算法，即在生成頻繁2-項目集時由于運算量大而引入Hash技術(shù)來產(chǎn)生頻繁2-項目集。以上4種算法屬于寬度優(yōu)先算法，還有深度優(yōu)先算法 (如 FP-growth算法、OP算法、TreeProjection算法)、數(shù)據(jù)集劃分算法、采樣算法、增量式更新算法等，由于后幾種算法本質(zhì)上已不同于Apriori算法，所以本文對其不再詳述。

我國學(xué)者開始研究關(guān)聯(lián)規(guī)則挖掘較晚，約在2000年左右。起初是跟著國外學(xué)者的思路先研究Apriori的改進(jìn)算法 AprioriTid[1]、AprioriHybird和 DHP,隨后從 Apriori算法的性質(zhì)、掃描數(shù)據(jù)庫的次數(shù)、消減數(shù)據(jù)庫容量、轉(zhuǎn)換數(shù)據(jù)庫存儲方式及與其他技術(shù)（如Hash）和算法聯(lián)合等方面對Apriori算法進(jìn)行了改進(jìn)。下面以改進(jìn)內(nèi)容為序，予以詳述。

1 利用Apriori算法性質(zhì)的改進(jìn)

2002年有學(xué)者根據(jù)Apriori算法中生成k維數(shù)據(jù)項集的一個推論：Tk是k維數(shù)據(jù)項集，如果所有k-1維高頻數(shù)據(jù)項集集合Lk-1中包含Tk的k-1維子集的個數(shù)小于 k，則 Tk不可能是k維最大數(shù)據(jù)項集,從而在原 Apriori算法從Ck中取元素，然后求該元素的子集，判斷該子集是否在｜Ck｜中需進(jìn)行的計算次數(shù)減少,即在判斷某一項集是頻繁時減少了判斷次數(shù)[2]。

2004年有學(xué)者根據(jù)性質(zhì):若k維數(shù)據(jù)項目集X＝{i1,i2,…,ik}中，存在一個 j∈X 使得|Lk-1(j)︳＜k-1,則 X 不是頻繁項目集。其中|Lk-1(j)︳表示k-1維頻繁項目集的集合Lk-1中所包含j的個數(shù)。在修剪頻繁集時進(jìn)行了改進(jìn)。又在連接步驟引入頭、尾結(jié)點生成函數(shù)和優(yōu)化連接函數(shù)改進(jìn)了連接步驟，同時按事務(wù)壓縮技術(shù)原理壓縮了數(shù)據(jù)庫容量[3]。

2006年有學(xué)者發(fā)現(xiàn)性質(zhì)：生成候選項集Ck時，在Lk-1中的一個項集I與Lk-1中所有項集進(jìn)行連接，把連接得到的不同k_項集存入TQ，然后立即確定包含項集I的所有符合剪枝后的候選k_項集。根據(jù)這一性質(zhì)省略了在Lk-1中尋找k_項集的所有(k-1)_子集的費時剪枝操作[4]。

2008年有學(xué)者根據(jù)k_維頻繁項集所有k-1維子集均是頻繁的且子集個數(shù)為k這一性質(zhì)提出兩點改進(jìn):(1)如果Ck-1中存在不符合最小支持度的元素，則刪除它；而且將項數(shù)等于(k-1)的事務(wù)與k項事務(wù)有交集的事務(wù)刪除。(2)二次掃描數(shù)據(jù)庫，分別產(chǎn)生頻繁1、2項集 L1、L2，在生成頻繁3項集時，首先由頻繁 2項集自乘生成候選3項集C3，依次取出L2中各元素，檢查其是否為 C3的子集，若是則計數(shù)加 1，掃描完 L2中各元素后，看 C3中各元素的計數(shù)，最終計數(shù)等于3的則為3項頻繁的。更多項頻繁集也是這種方法的重復(fù)[5]。

2 數(shù)據(jù)庫掃描次數(shù)和消減容量的改進(jìn)

2003年有學(xué)者以減少掃描數(shù)據(jù)庫的次數(shù)為目的，引入了概率估算候選頻繁項集的思想[6]。

2005年有學(xué)者利用頻繁項集Lk-1對數(shù)據(jù)庫進(jìn)行篩選，如果在Lk-1沒有包含它們的集合則從數(shù)據(jù)庫中刪掉這部分不符合最小支持度的元素,而且將項數(shù)等于k-1的事務(wù)刪除，從而減少了數(shù)據(jù)庫容量[7]。

2008年有學(xué)者通過第一次掃描數(shù)據(jù)庫及最小支持度確定頻繁1項集，之后根據(jù)頻繁1項集重新組織數(shù)據(jù)庫，再次掃描，把每個子集出現(xiàn)的次數(shù)統(tǒng)計出來，再根據(jù)最小支持度篩出頻繁k_項集[8]。該方法僅掃描2次數(shù)據(jù)庫，節(jié)約了時間，但在處理數(shù)據(jù)庫中每項事務(wù)(即拆成子集)、統(tǒng)計其次數(shù)等上需花費一定的空間和時間。

2009年有學(xué)者利用如果某事務(wù)項目數(shù)小于k_頻繁項目集的項目個數(shù)，則在更新頻繁項目集時可以不掃描的性質(zhì)，壓縮了數(shù)據(jù)庫事務(wù)集；為提高剪枝效率，首次支持度裁剪后，比較非頻繁項集項目數(shù)和頻繁項集項目數(shù)，取小值進(jìn)行剪枝操作[9]。

2011年有學(xué)者引入了用戶興趣項，從而可以比較大范圍地縮減數(shù)據(jù)庫容量；同時使用數(shù)組方式表示數(shù)據(jù)庫，減少了數(shù)據(jù)庫的掃描次數(shù)[10]。

3 轉(zhuǎn)換數(shù)據(jù)庫存儲方式

2004年有學(xué)者把數(shù)據(jù)庫轉(zhuǎn)換成矩陣表示,事務(wù)為行，具體的項目為列，若第i條事務(wù)在第j列有項目，則該處記為1，否則為0。掃描數(shù)據(jù)庫時，該矩陣的對應(yīng)項也隨之以加1的頻率改寫。最后考察矩陣的對應(yīng)項與支持度的關(guān)系[11]。

2006年有學(xué)者在以往學(xué)者提出的把數(shù)據(jù)庫轉(zhuǎn)為矩陣的基礎(chǔ)上[11]，使用自定義的矩陣運算，產(chǎn)生新的數(shù)據(jù)庫矩陣及完成相應(yīng)的剪枝步驟。在生成關(guān)聯(lián)規(guī)則時使用了概率論的基本性質(zhì)，減少了計算量[12]。

2007年有學(xué)者在以往學(xué)者提出的把數(shù)據(jù)庫轉(zhuǎn)為矩陣的基礎(chǔ)上[11]，使用行向量內(nèi)積的方法搜尋頻繁項集，該方法僅掃描一次數(shù)據(jù)庫，但要多次使用矩陣相乘獲取頻繁項集[13]。

2009年有學(xué)者提出了一種事務(wù)的二元組表示法，該二元組直接用字段的值串和串的出現(xiàn)次數(shù)來替換原始事務(wù)數(shù)據(jù)庫，并在此基礎(chǔ)上掃描一遍數(shù)據(jù)庫。例如通過掃描、處理后得到項目串和支持?jǐn)?shù)[I1I2，2]。該表示法所占內(nèi)存大小只取決于數(shù)據(jù)庫的基，即各元素取值種類的乘積。例，數(shù)據(jù)庫有4個字段，每個字段的取值個數(shù)分別為(2，3，5，3)，則該二元組數(shù)目不大于 2×3×5×3=90。 同時用鏈表結(jié)構(gòu)來表示該二元組，能加快一定速度[14]。

2009年有學(xué)者改變了數(shù)據(jù)庫的存儲形式，即由原來的第幾條事務(wù)包含有哪幾個元素(例如“T1 A，B，E”)變?yōu)槟膫€元素被哪些事務(wù)包含 (例如 “A T1 T4 T8 T9”)。根據(jù)最小支持度可生成1_項頻繁集，再通過交集運算生成 2_項頻繁集(例如 “AB T1 T8”)。又根據(jù)連接時的一個定理，即Lk-1和L1連接時只需考察Lk-1的最后一項與L1中各項在L1中索引的大小關(guān)系,從而減少了不必要的重復(fù)連接[15]。

2009年有學(xué)者把數(shù)據(jù)庫的事務(wù)轉(zhuǎn)為十字鏈表方式存儲。該方法僅掃描一次數(shù)據(jù)庫，節(jié)約了時間，但十字鏈表結(jié)構(gòu)復(fù)雜，其生成也需消耗時間[16]。

4 Hash技術(shù)與數(shù)據(jù)庫掃描次數(shù)及數(shù)據(jù)庫消減的合用

2003年有學(xué)者用散列技術(shù)把生成的(k+1)_項集散列到散列表中并計數(shù)，同時考察支持度；同時使用性質(zhì)：不包含任何k_項集的事務(wù)不可能包含任何(k+1)_項集[17]，來壓縮事務(wù)數(shù)據(jù)庫。

2004年有學(xué)者提出在掃描數(shù)據(jù)庫時引入散列技術(shù)，以達(dá)到降低數(shù)據(jù)庫的掃描次數(shù)，同時根據(jù)支持度的要求減少不可能成為頻繁項目集的候選項，從而了提高數(shù)據(jù)項集頻度的統(tǒng)計速度[18]。

2007年有學(xué)者提出在產(chǎn)生1_頻繁項目集和2_頻繁項目集時，使用Hash技術(shù)；在產(chǎn)生k_頻繁項目集時使用事務(wù)壓縮優(yōu)化方法[19]。

5 轉(zhuǎn)換數(shù)據(jù)庫存儲方式與Apriori性質(zhì)或其他方面的聯(lián)合使用

2008年有學(xué)者在原數(shù)據(jù)庫轉(zhuǎn)成布爾矩陣的基礎(chǔ)上，根據(jù)交易記錄各項是按字典排序的，從而生成的候選項集和頻繁項集也是有序的這一性質(zhì)，減少了判斷次數(shù)；同時利用k_維數(shù)據(jù)項目集的頻繁項集的必要條件使它的所有k-1維子集均是頻繁項目集這一性質(zhì)，在一定程度上優(yōu)化了頻繁項集的修剪[20]。

2011年有學(xué)者對2_項集使用了散列表技術(shù)，能較快速地獲得頻繁2_項集。同時對數(shù)據(jù)庫生成候選k_項集(k≥3)時轉(zhuǎn)為前學(xué)者[15]的矩陣方式存儲，如ABC出現(xiàn)在第 1、3、4條事務(wù)中則表示為(1011)，再根據(jù)支持度就可生成頻繁k_項集[21]。

2012年有學(xué)者在前學(xué)者[16]十字鏈表的基礎(chǔ)上，利用k維頻繁項集的所有k-1維子集均是頻繁項集這一性質(zhì)，優(yōu)化了候選頻繁項集的生成和數(shù)據(jù)庫的掃描[22]。同時也引出了其他學(xué)者對十字鏈表的改進(jìn)。

6 Apriori算法與其他算法的聯(lián)合使用

2007年有學(xué)者提出Apriori算法與聚類算法相結(jié)合應(yīng)用于IDS日志分析中[23]。

2010年有學(xué)者提出用遺傳算法對數(shù)據(jù)庫進(jìn)行性編碼、評估和遺傳，再使用 Apriori的連接、剪枝和提取步驟完成整個挖掘過程[24]。

2012年有學(xué)者把Apriori算法應(yīng)用于矩陣聚類法中[25]。

2012年有學(xué)者把云計算的兩個重要步驟：Map函數(shù)(映射)和 Reduce函數(shù)（歸約），分別引入到 Apriori算法的連接和剪枝步驟中，該思想豐富了Apriori的內(nèi)容[26]。

從上面的論述中可以看到，起初對Apriori算法的改進(jìn)著重于算法本身，比如利用其性質(zhì)改進(jìn)頻繁項集的生成、縮減數(shù)據(jù)庫容量、掃描次數(shù)等。后來算法本身的改進(jìn)點基本都被挖掘出來了，就轉(zhuǎn)向了數(shù)據(jù)庫存儲方式的改進(jìn)，如轉(zhuǎn)成布爾型矩陣、鏈表，數(shù)據(jù)庫存儲方式的改進(jìn)可謂是開創(chuàng)了Apriori算法改進(jìn)的一個新紀(jì)元。可是接下來似乎有點山窮水盡的味道，研究轉(zhuǎn)向了與其他算法的合作，如與遺傳算法、云計算的合作。Apriori算法的寬度優(yōu)先算法改進(jìn)前途是否依然光明，我們拭目以待。

[1]顏雪松,蔡之華.一種基于 Apriori的高效關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計算機工程與應(yīng)用,2002,32(10)：209-211.

[2]李緒成,王保保.挖掘關(guān)聯(lián)規(guī)則中Apriori算法的一種改進(jìn)[J].計 算 機 工 程,2002,28(7)：104-105.

[3]徐章艷,劉美玲,張師超,等.Apriori算法的三種優(yōu)化方法[J].計算機工程與應(yīng)用,2004，40(36)：190-192.

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

[5]楊啟昉,馬廣平.關(guān)聯(lián)規(guī)則挖掘 Apriori算法的改進(jìn)[J].計算機應(yīng)用,2008,28(12)：217-218.

[6]陳江平,傅仲良,徐志紅.一種 Apriori的改進(jìn)算法[J].武漢大學(xué)學(xué)報（信息科學(xué)版）,2003,28(1)：94-98.

[7]馮興杰,周諄.Apriori算法的改進(jìn)[J].計算機工程,2005,31(增刊):172-173.

[8]郭健美,宋順林,李世松.基于 Apriori算法的改進(jìn)算法[J].計算機工程與設(shè)計,2008,29(11)：2814-2815.

[9]吳斌,肖剛,陸佳煒.基于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的 Apriori算法的優(yōu)化研究[J].計算機工程與科學(xué),2009,31(6)：116-118.

[10]劉維曉,陳俊麗,屈世富,等.一種改進(jìn)的 Apriori算法[J].計算機工程與應(yīng)用,2011,47(11)：149-151.

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

[12]李超,余昭平.基于矩陣的 Apriori算法改進(jìn)[J].計算機工程,2006,32(23)：68-69.

[13]劉以安,羊斌.關(guān)聯(lián)規(guī)則挖掘中對 Apriori算法的一種改進(jìn) 研 究[J].計 算 機 應(yīng) 用,2007,27(2)：418-420.

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

[15]劉華婷,郭仁祥,姜浩.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)[J].計算機應(yīng)用與軟件,2009,26（1）：146-148.

[16]黃建明,趙文靜,王星星.基于十字鏈表的 Apriori改進(jìn)算法[J].計 算 機 工 程,2009,35(2)：37-38.

[17]黃進(jìn),尹治本.關(guān)聯(lián)規(guī)則挖掘的 Apriori算法的改進(jìn)[J].電子科技大學(xué)學(xué)報,2003,32(1)：76-79.

[18]王創(chuàng)新.關(guān)聯(lián)規(guī)則提取中對 Apriori算法的一種改進(jìn)[J].計算機工程與應(yīng)用,2004,40(34)：183-185.

[19]柴華昕,王勇.Apriori挖掘頻繁項目集算法的改進(jìn)[J].計算機工程與應(yīng)用,2007,43（24）：158-161.

[20]錢光超,賈瑞玉,張然,等.Apriori算法的一種優(yōu)化方法[J].計算機工程,2008,34(23)：196-198.

[21]栗曉聰,滕少華.頻繁項集挖掘的Apriori改進(jìn)算法研究[J].江西師范大學(xué)學(xué)報（自然科學(xué)版）,2011,35（5）：498-501.

[22]劉玉文.基于十字鏈表的 Apriori算法的研究與改進(jìn)[J].計算機應(yīng)用與軟件,2012,29（5）：267-269.

[23]朱金清,王建新,陳志泊.基于 APRIORI的層次化聚類算法及其在IDS日志分析中的應(yīng)用[J].計算機研究與發(fā)展,2007,44(增刊)：326-330.

[24]詹芹,張幼明.一種改進(jìn)的動態(tài)遺傳 Apriori挖掘算法[J].計算機應(yīng)用研究,2010,27（8）：2929-2930.

[25]陳立寧,羅可.基于 Apriori算法的確定指定精度矩陣聚類方法[J].計算機工程與應(yīng)用,2012,48(7)：139-141.

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