摘  要： 介紹了近十幾年中國學者對Apriori算法的寬度優(yōu)先算法的改進研究。
關鍵詞： Apriori算法； Apriori改進算法； 寬度優(yōu)先算法

    AGRAWL R等人于1993年提出了挖掘關聯規(guī)則最具影響力的Apriori算法。該算法的基本思想是先找出事務數據庫中具有最小支持度的項目集(即最大項目集)，再根據最大項目集生成關聯規(guī)則。其中生成最大項目集是核心問題，其思想為：第一步，統(tǒng)計所有含一個元素項目集出現的頻率，并找出不小于最小支持度的項目集，從第二步開始循環(huán)處理直到再沒有最大項目集生成。循環(huán)過程是：在第k步中，根據第k-1步生成的k-1維最大項目集產生k維候選項目集，然后對數據庫進行搜索，得到候選項目集的項集支持度，并與最小支持度比較，從而找到k維最大項目集。
    之后，AGRAWL R等人又提出了Apriori算法的改進算法AprioriTid算法和AprioriHybird算法。AprioriTid算法對Apriori算法做了調整，它的特點是在第一次遍歷數據庫之后，就不再掃描數據庫，而是用上次掃描生成的候選項目集，掃描的同時還會計算出頻繁項目集的支持度。該算法以候選項目集來代替原數據庫，從而減少了總是要掃描原數據庫統(tǒng)計支持計數的開銷。AprioriHybird算法則是Apriori和AprioriTid的結合，初始掃描數據庫時采用Apriori算法，當生成的候選項目集大小可以存放到內存中進行處理時采再轉成AprioriTid算法。1995年PARK等人提出了DHP算法，即在生成頻繁2-項目集時由于運算量大而引入Hash技術來產生頻繁2-項目集。以上4種算法屬于寬度優(yōu)先算法，還有深度優(yōu)先算法(如FP-growth算法、OP算法、TreeProjection算法)、數據集劃分算法、采樣算法、增量式更新算法等，由于后幾種算法本質上已不同于Apriori算法，所以本文對其不再詳述。
    我國學者開始研究關聯規(guī)則挖掘較晚，約在2000年左右。起初是跟著國外學者的思路先研究Apriori的改進算法AprioriTid[1]、AprioriHybird和DHP,隨后從Apriori算法的性質、掃描數據庫的次數、消減數據庫容量、轉換數據庫存儲方式及與其他技術（如Hash）和算法聯合等方面對Apriori算法進行了改進。下面以改進內容為序，予以詳述。
1 利用Apriori算法性質的改進
    2002年有學者根據Apriori算法中生成k維數據項集的一個推論：Tk 是k維數據項集，如果所有k-1維高頻數據項集集合Lk-1中包含Tk的k-1維子集的個數小于k，則Tk不可能是k維最大數據項集,從而在原Apriori算法從Ck中取元素，然后求該元素的子集，判斷該子集是否在|Ck|中需進行的計算次數減少,即在判斷某一項集是頻繁時減少了判斷次數[2]。
    2004年有學者根據性質:若k維數據項目集X={i1,i2,…,ik}中，存在一個j∈X使得?襔Lk-1(j)︳<k-1,則X不是頻繁項目集。其中?襔Lk-1(j)︳表示k-1維頻繁項目集的集合Lk-1中所包含j的個數。在修剪頻繁集時進行了改進。又在連接步驟引入頭、尾結點生成函數和優(yōu)化連接函數改進了連接步驟，同時按事務壓縮技術原理壓縮了數據庫容量[3]。
    2006年有學者發(fā)現性質：生成候選項集Ck時，在Lk-1中的一個項集I與Lk-1中所有項集進行連接，把連接得到的不同k_項集存入TQ，然后立即確定包含項集I的所有符合剪枝后的候選k_項集。根據這一性質省略了在Lk-1中尋找k_項集的所有(k-1)_子集的費時剪枝操作[4]。
    2008年有學者根據k_維頻繁項集所有k-1維子集均是頻繁的且子集個數為k這一性質提出兩點改進:(1)如果Ck-1中存在不符合最小支持度的元素，則刪除它；而且將項數等于(k-1)的事務與k項事務有交集的事務刪除。(2)二次掃描數據庫，分別產生頻繁1、2項集L1、L2，在生成頻繁3項集時，首先由頻繁2項集自乘生成候選3項集C3，依次取出L2中各元素，檢查其是否為C3的子集，若是則計數加1，掃描完L2中各元素后，看C3中各元素的計數，最終計數等于3的則為3項頻繁的。更多項頻繁集也是這種方法的重復[5]。
2 數據庫掃描次數和消減容量的改進
    2003年有學者以減少掃描數據庫的次數為目的，引入了概率估算候選頻繁項集的思想[6]。
    2005年有學者利用頻繁項集Lk-1對數據庫進行篩選，如果在Lk-1沒有包含它們的集合則從數據庫中刪掉這部分不符合最小支持度的元素,而且將項數等于k-1的事務刪除，從而減少了數據庫容量[7]。
    2008年有學者通過第一次掃描數據庫及最小支持度確定頻繁1項集，之后根據頻繁1項集重新組織數據庫，再次掃描，把每個子集出現的次數統(tǒng)計出來，再根據最小支持度篩出頻繁k_項集[8]。該方法僅掃描2次數據庫，節(jié)約了時間，但在處理數據庫中每項事務(即拆成子集)、統(tǒng)計其次數等上需花費一定的空間和時間。
   2009年有學者利用如果某事務項目數小于k_頻繁項目集的項目個數，則在更新頻繁項目集時可以不掃描的性質，壓縮了數據庫事務集；為提高剪枝效率，首次支持度裁剪后，比較非頻繁項集項目數和頻繁項集項目數，取小值進行剪枝操作[9]。
    2011年有學者引入了用戶興趣項，從而可以比較大范圍地縮減數據庫容量；同時使用數組方式表示數據庫，減少了數據庫的掃描次數[10]。
3 轉換數據庫存儲方式
    2004年有學者把數據庫轉換成矩陣表示,事務為行，具體的項目為列，若第i條事務在第j列有項目，則該處記為1，否則為0。掃描數據庫時，該矩陣的對應項也隨之以加1的頻率改寫。最后考察矩陣的對應項與支持度的關系[11]。
    2006年有學者在以往學者提出的把數據庫轉為矩陣的基礎上[11]，使用自定義的矩陣運算，產生新的數據庫矩陣及完成相應的剪枝步驟。在生成關聯規(guī)則時使用了概率論的基本性質，減少了計算量[12]。
    2007年有學者在以往學者提出的把數據庫轉為矩陣的基礎上[11]，使用行向量內積的方法搜尋頻繁項集，該方法僅掃描一次數據庫，但要多次使用矩陣相乘獲取頻繁項集[13]。
    2009年有學者提出了一種事務的二元組表示法，該二元組直接用字段的值串和串的出現次數來替換原始事務數據庫，并在此基礎上掃描一遍數據庫。例如通過掃描、處理后得到項目串和支持數[I1I2，2]。該表示法所占內存大小只取決于數據庫的基，即各元素取值種類的乘積。例，數據庫有4個字段，每個字段的取值個數分別為(2，3，5，3)，則該二元組數目不大于2×3×5×3=90。同時用鏈表結構來表示該二元組，能加快一定速度[14]。
    2009年有學者改變了數據庫的存儲形式，即由原來的第幾條事務包含有哪幾個元素(例如“T1 A，B，E”)變?yōu)槟膫€元素被哪些事務包含(例如“A T1 T4 T8 T9”)。根據最小支持度可生成1_項頻繁集，再通過交集運算生成2_項頻繁集(例如 “AB T1 T8”)。又根據連接時的一個定理，即Lk-1和L1連接時只需考察Lk-1的最后一項與L1中各項在L1中索引的大小關系,從而減少了不必要的重復連接[15]。
    2009年有學者把數據庫的事務轉為十字鏈表方式存儲。該方法僅掃描一次數據庫，節(jié)約了時間，但十字鏈表結構復雜，其生成也需消耗時間[16]。
4 Hash技術與數據庫掃描次數及數據庫消減的合用
    2003年有學者用散列技術把生成的(k+1)_項集散列到散列表中并計數，同時考察支持度；同時使用性質：不包含任何k_項集的事務不可能包含任何(k+1)_項集[17]，來壓縮事務數據庫。
    2004年有學者提出在掃描數據庫時引入散列技術，以達到降低數據庫的掃描次數，同時根據支持度的要求減少不可能成為頻繁項目集的候選項，從而了提高數據項集頻度的統(tǒng)計速度[18]。
     2007年有學者提出在產生1_頻繁項目集和2_頻繁項目集時，使用Hash技術；在產生k_頻繁項目集時使用事務壓縮優(yōu)化方法[19]。
5 轉換數據庫存儲方式與Apriori性質或其他方面的聯合使用
     2008年有學者在原數據庫轉成布爾矩陣的基礎上，根據交易記錄各項是按字典排序的，從而生成的候選項集和頻繁項集也是有序的這一性質，減少了判斷次數；同時利用k_維數據項目集的頻繁項集的必要條件使它的所有k-1維子集均是頻繁項目集這一性質，在一定程度上優(yōu)化了頻繁項集的修剪[20]。
    2011年有學者對2_項集使用了散列表技術，能較快速地獲得頻繁2_項集。同時對數據庫生成候選k_項集(k≥3)時轉為前學者[15]的矩陣方式存儲，如ABC出現在第1、3、4條事務中則表示為(1011)，再根據支持度就可生成頻繁k_項集[21]。
    2012年有學者在前學者[16]十字鏈表的基礎上，利用k維頻繁項集的所有k-1維子集均是頻繁項集這一性質，優(yōu)化了候選頻繁項集的生成和數據庫的掃描[22]。同時也引出了其他學者對十字鏈表的改進。
6 Apriori算法與其他算法的聯合使用
    2007年有學者提出Apriori算法與聚類算法相結合應用于IDS日志分析中[23]。
    2010年有學者提出用遺傳算法對數據庫進行性編碼、評估和遺傳，再使用Apriori的連接、剪枝和提取步驟完成整個挖掘過程[24]。
    2012年有學者把Apriori算法應用于矩陣聚類法中[25]。
    2012年有學者把云計算的兩個重要步驟：Map函數(映射)和Reduce函數（歸約），分別引入到Apriori算法的連接和剪枝步驟中，該思想豐富了Apriori的內容[26]。
    從上面的論述中可以看到，起初對Apriori算法的改進著重于算法本身，比如利用其性質改進頻繁項集的生成、縮減數據庫容量、掃描次數等。后來算法本身的改進點基本都被挖掘出來了，就轉向了數據庫存儲方式的改進，如轉成布爾型矩陣、鏈表，數據庫存儲方式的改進可謂是開創(chuàng)了Apriori算法改進的一個新紀元。可是接下來似乎有點山窮水盡的味道，研究轉向了與其他算法的合作，如與遺傳算法、云計算的合作。Apriori算法的寬度優(yōu)先算法改進前途是否依然光明，我們拭目以待。
參考文獻
[1] 顏雪松,蔡之華．一種基于Apriori的高效關聯規(guī)則挖掘算法的研究[J]．計算機工程與應用,2002,32(10)：209-211．
[2] 李緒成,王保保. 挖掘關聯規(guī)則中Apriori算法的一種改進[J]．計算機工程,2002,28(7)：104-105．
[3] 徐章艷,劉美玲,張師超,等．Apriori算法的三種優(yōu)化方法[J]．計算機工程與應用,2004，40(36)：190-192．
[4] 胡吉明,鮮學豐．挖掘關聯規(guī)則中Apriori算法的研究與改進[J]．計算機技術與發(fā)展,2006,16(4)：99-101．
[5] 楊啟昉,馬廣平．關聯規(guī)則挖掘Apriori算法的改進[J]．計算機應用,2008,28(12)：217-218．
[6] 陳江平,傅仲良,徐志紅．一種Apriori的改進算法[J]．武漢大學學報（信息科學版）,2003,28(1)：94-98．
[7] 馮興杰,周諄．Apriori算法的改進[J]．計算機工程,2005,31(增刊):172-173．
[8] 郭健美,宋順林,李世松．基于Apriori算法的改進算法[J]．計算機工程與設計,2008,29(11)：2814-2815．
[9] 吳斌,肖剛,陸佳煒．基于關聯規(guī)則挖掘領域的Apriori算法的優(yōu)化研究[J]．計算機工程與科學,2009,31(6)：116-118．
[10] 劉維曉,陳俊麗,屈世富,等．一種改進的Apriori算法[J]．計算機工程與應用,2011,47(11)：149-151．
[11] 馬盈倉．挖掘關聯規(guī)則中Apriori算法的改進[J]．計算機應用與軟件,2004,21（11）：82-83．
[12] 李超,余昭平．基于矩陣的Apriori算法改進[J]．計算機工程,2006,32(23)：68-69．
[13] 劉以安,羊斌．關聯規(guī)則挖掘中對Apriori算法的一種改進研究[J]．計算機應用,2007,27(2)：418-420．
[14] 張春生．改進的數據庫一次掃描快速Apriori算法[J]．計算機工程與設計,2009,30(16)：3811-3813．
[15] 劉華婷,郭仁祥,姜浩．關聯規(guī)則挖掘Apriori算法的研究與改進[J]．計算機應用與軟件,2009,26（1）：146-148．
[16] 黃建明,趙文靜,王星星．基于十字鏈表的Apriori改進算法[J]．計算機工程,2009,35(2)：37-38．
[17] 黃進,尹治本．關聯規(guī)則挖掘的Apriori算法的改進[J]．電子科技大學學報,2003,32(1)：76-79．
[18] 王創(chuàng)新．關聯規(guī)則提取中對Apriori算法的一種改進[J]．計算機工程與應用,2004,40(34)：183-185．
[19] 柴華昕,王勇．Apriori挖掘頻繁項目集算法的改進[J]．計算機工程與應用,2007,43（24）：158-161．
[20] 錢光超,賈瑞玉,張然,等．Apriori算法的一種優(yōu)化方法[J]．計算機工程,2008,34(23)：196-198．
[21] 栗曉聰,滕少華． 頻繁項集挖掘的Apriori改進算法研究[J]．江西師范大學學報（自然科學版）,2011,35（5）：498-501．
[22] 劉玉文．基于十字鏈表的Apriori算法的研究與改進[J]．計算機應用與軟件,2012,29（5）：267-269．
[23] 朱金清,王建新,陳志泊．基于APRIORI的層次化聚類算法及其在IDS日志分析中的應用[J]．計算機研究與發(fā)展,2007,44(增刊)：326-330．
[24] 詹芹,張幼明．一種改進的動態(tài)遺傳Apriori挖掘算法[J]．計算機應用研究,2010,27（8）：2929-2930．
[25] 陳立寧,羅可．基于Apriori算法的確定指定精度矩陣聚類方法[J]．計算機工程與應用,2012,48(7)：139-141．
[26] 吳琪．基于云計算的Apriori挖掘算法[J]．計算機測量與控制,2012,20（6）：1653-1655．