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

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