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

1、Apriori 改進(jìn)算法綜述改進(jìn)算法綜述 戴 奇本文內(nèi)容簡介：本文內(nèi)容簡介：v1. 基本的Apriori算法v2. Apriori算法的改進(jìn)2.1 利用 Apriori 算法性質(zhì)的改進(jìn)2.2 數(shù)據(jù)庫掃描次數(shù)和消減容量的改進(jìn)2.3 轉(zhuǎn)換數(shù)據(jù)庫存儲方式2.4 Hash 技術(shù)與數(shù)據(jù)庫掃描次數(shù)及數(shù)據(jù)庫消減的合用2.5 轉(zhuǎn)換數(shù)據(jù)庫存儲方式與 Apriori 性質(zhì)或其他方面 的聯(lián)合使用2.6 Apriori 算法與其他算法的聯(lián)合使用v3. 參考文獻(xiàn)1. 1. 基本的基本的AprioriApriori算法算法vApriori算法是R.Agrawal和R.Srikant于1994年提出的為布爾關(guān)聯(lián)規(guī)則挖掘頻繁

2、項集的原創(chuàng)性算法。Apriori算法命名源于算法使用了頻繁項集性質(zhì)的先驗先驗（Prior）知識。 Apriori算法將發(fā)現(xiàn)關(guān)聯(lián)規(guī)則的過程分為兩個步驟： 通過迭代，檢索出事務(wù)數(shù)據(jù)庫中的所有頻繁項集，即支持度不低于用戶設(shè)定的閾值的項集； 利用頻繁項集構(gòu)造出滿足用戶最小置信度的規(guī)則。Apriori的性質(zhì)性質(zhì)： 頻繁項集的所有非空子集必為頻繁項集。 非頻繁項集的超集一定是非頻繁的。 Apriori的步驟步驟： 連接步：為找Lk ，通過將Lk-1與自身連接產(chǎn)生候選k項集的集合。 剪枝步：Ck是Lk 的超集，也就是說，Ck的成員可以是也可以不是頻繁的，但所有的頻繁k項集都包含在Ck中。 任何非頻繁的（k-

3、1）項集都不是頻繁k項集的子集。Apriori的缺點(diǎn)缺點(diǎn)：在每一次產(chǎn)生候選項集時都要掃描一遍數(shù)據(jù)庫D，而用于關(guān)聯(lián)規(guī)則挖掘的數(shù)據(jù)庫的規(guī)模通常是非常大的，所以這樣就無形之中增加了額外的開銷，影響了算法的效率。 v之后，R.Agrawal等人又提出了 Apriori 算法的改進(jìn)算法 AprioriTid AprioriTid 算法和 AprioriHybird AprioriHybird 算法。AprioriTid 算法對 Apriori 算法做了調(diào)整 特點(diǎn)：在第一次遍歷數(shù)據(jù)庫之后，就不再掃描數(shù)據(jù)庫 ，而是用上次掃描生成的候選項集，掃描的同時還會計算出頻繁項集的支持度。 該算法以候選項集來代替原數(shù)據(jù)

4、庫，從而減少了總是要掃描原數(shù)據(jù)庫統(tǒng)計支持度計數(shù)的開銷 。 AprioriHybird 算法則是 Apriori 和 AprioriTid 的結(jié)合 。 先采用Apriori算法掃描數(shù)據(jù)庫，然后計算修剪后的數(shù)據(jù)庫大小，若其可在內(nèi)存中進(jìn)行處理則采用AprioriTid 算法，直到找出所有的頻繁項集。v1995年P(guān)ARK等人提出了DHPDHP算法， 即在生成頻繁2-項集時由于運(yùn)算量大而引入Hash技術(shù)來產(chǎn)生頻繁2-項集。v以上 4 種算法屬于寬度優(yōu)先寬度優(yōu)先算法，還有深度優(yōu)先深度優(yōu)先算法 (如 FP-growth算法 、OP算法 、TreeProjection 算法)、數(shù)據(jù)集劃分算法、采樣算法、增量式

5、更新算法等，由于后幾種算法本質(zhì)上已不同于 Apriori 算法，所以本文對其不再詳述。2. Apriori2. Apriori算法的改進(jìn)算法的改進(jìn)v我國學(xué)者開始研究關(guān)聯(lián)規(guī)則挖掘較晚，約在2000年左右。起初是跟著國外學(xué)者的思路先研究 Apriori 的改進(jìn)算法AprioriTid11、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)容為序，予以詳述。2.1 2.1 利用利用 Apriori Apriori 算法性質(zhì)的改進(jìn)算法性質(zhì)

6、的改進(jìn)v2002年有學(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ù)22。v2004年有學(xué)者根據(jù)性質(zhì) : 若k維數(shù)據(jù)項集 X =i1,i2,ik中，存在一個 jX 使得|Lk-1(j)|k-1, 則 X 不是頻繁項集。其中|Lk-1(j)|表示k -1維頻繁項集的集合Lk-1中所包含j的

7、個數(shù)。在修剪頻繁集時進(jìn)行了改進(jìn)。又在連接步驟引入頭、尾結(jié)點(diǎn)生成函數(shù)和優(yōu)化連接函數(shù)改進(jìn)了連接步驟，同時按事務(wù)壓縮技術(shù)原理壓縮了數(shù)據(jù)庫容量33。v2006年有學(xué)者發(fā)現(xiàn)性質(zhì)：生成候選項集Ck時 ，在Lk-1中的一個項集 I 與 Lk-1中所有項集進(jìn)行連接 ， 把連接得到的不同 k_項集存入 TQ，然后立即確定包含項集I 的所有符合剪枝后的候選 k_項集 。 根據(jù)這一性質(zhì)省略了在 Lk-1中尋找 k_項集的所有(k-1)_子集的費(fèi)時剪枝操作 4 4。v2008 年有學(xué)者根據(jù) k_維頻繁項集所有k-1維子集均是頻繁的且子集個數(shù)為 k 這一性質(zhì)提出兩點(diǎn)改進(jìn)如果 Ck-1中存在不符合最小支持度的元素， 則刪

8、除它；而且將項數(shù)等于(k-1)的事務(wù)與 k 項事務(wù)有交集的事務(wù)刪除。 二次掃描數(shù)據(jù)庫，分別產(chǎn)生頻繁 1、2 項集 L1、L2，在生成頻繁3項集時，首先由頻繁2項集自乘生成候選3項集C3， 依次取出 L2中各元素，檢查其是否為 C3的子集，若是則計數(shù)加1，掃描完 L2中各元素后，看C3中各元素的計數(shù)，最終計數(shù)等于3的則為3項頻繁的。更多項頻繁集也是這種方法的重復(fù) 5 5。2.2 2.2 數(shù)據(jù)庫掃描次數(shù)和消減容量的改進(jìn)數(shù)據(jù)庫掃描次數(shù)和消減容量的改進(jìn)v2003年有學(xué)者以減少掃描數(shù)據(jù)庫的次數(shù)為目的， 引入了概率估算候選頻繁項集的思想66。v2005年有學(xué)者利用頻繁項集Lk-1對數(shù)據(jù)庫進(jìn)行篩選，如果在

9、Lk-1沒有包含它們的集合則從數(shù)據(jù)庫中刪掉這部分不符合最小支持度的元素, 而且將項數(shù)等于 k-1的事務(wù)刪除，從而減少了數(shù)據(jù)庫容量 7 7 。v2008年有學(xué)者通過第一次掃描數(shù)據(jù)庫及最小支持度確定頻繁1項集，之后根據(jù)頻繁1項集重新組織數(shù)據(jù)庫，再次掃描，把每個子集出現(xiàn)的次數(shù)統(tǒng)計出來，再根據(jù)最小支持度篩出頻繁 k_項集88。 該方法僅掃描 2 次數(shù)據(jù)庫，節(jié)約了時間，但在處理數(shù)據(jù)庫中每項事務(wù)(即拆成子集)、統(tǒng)計其次數(shù)等上需花費(fèi)一定的空間和時間。v2009年有學(xué)者利用如果某事務(wù)項目數(shù)小于k_頻繁項目集的項目個數(shù)，則在更新頻繁項目集時可以不掃描的性質(zhì)，壓縮了數(shù)據(jù)庫事務(wù)集；為提高剪枝效率，首次支持度裁剪后，

10、比較非頻繁項集項目數(shù)和頻繁項集項目數(shù)，取小值進(jìn)行剪枝操作99。v2011年有學(xué)者引入了用戶興趣項，從而可以比較大范圍地縮減數(shù)據(jù)庫容量 ； 同時使用數(shù)組方式表示數(shù)據(jù)庫，減少了數(shù)據(jù)庫的掃描次數(shù)1010。2.3 2.3 轉(zhuǎn)換數(shù)據(jù)庫存儲方式轉(zhuǎn)換數(shù)據(jù)庫存儲方式v2004年有學(xué)者把數(shù)據(jù)庫轉(zhuǎn)換成矩陣表示，事務(wù)為行，具體的項目為列，若第i條事務(wù)在第j列有項 目，則該處記為 1，否則為 0。掃描數(shù)據(jù)庫時，該矩陣的對應(yīng)項也隨之以加1的頻率改寫。最后考察矩陣的對應(yīng)項與支持度的關(guān)系1111。v2006年有學(xué)者在以往學(xué)者提出的把數(shù)據(jù)庫轉(zhuǎn)為矩陣的基 礎(chǔ)上1111， 使用自定義的矩陣運(yùn)算，產(chǎn)生 新的數(shù)據(jù)庫矩陣及完成相應(yīng)的剪

11、枝步驟。 在生成關(guān)聯(lián)規(guī)則時使用了概率論的基本性質(zhì)，減少了計算量1212。v2007年有學(xué)者在以往學(xué)者提出的把數(shù)據(jù)庫轉(zhuǎn)為矩陣的基 礎(chǔ)上1111， 使用行向量內(nèi)積的方法搜尋頻繁項集，該方法僅掃描一次數(shù)據(jù)庫，但要多次使用矩陣相乘獲取頻繁項集1313。v2009年有學(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ù)目不大于 235

12、3=90。同時用鏈表結(jié)構(gòu)來表示該二元組，能加快一定速度1414。v2009年有學(xué)者改變了數(shù)據(jù)庫的存儲形式 ， 即由原來的第幾條事務(wù)包含有哪幾個元素(例 如“T1 A，B，E”)變?yōu)槟膫€元素被哪些事務(wù)包含 (例如 “A T1 T4 T8 T9”)。根據(jù)最小支持度可生成1_項頻繁集，再通過交集運(yùn)算生成2_項頻繁集(例如“AB T1 T8”)。又根據(jù)連接時的一個定理，即Lk-1和 L1連接時只需考察 Lk-1的最后一項與 L1中各項在 L1中索引的大小關(guān)系, 從而減少了不必要的重復(fù)連接1515。v2009年有學(xué)者把數(shù)據(jù)庫的事務(wù)轉(zhuǎn)為十字鏈表方式存儲。該方法僅掃描一次數(shù)據(jù)庫，節(jié)約了時間，但十字鏈表結(jié)構(gòu)復(fù)

13、雜，其生成也需消耗時間1616。2.4 Hash 2.4 Hash 技術(shù)與數(shù)據(jù)庫掃描次數(shù)及數(shù)據(jù)庫消減的合用技術(shù)與數(shù)據(jù)庫掃描次數(shù)及數(shù)據(jù)庫消減的合用v2003年有學(xué)者用散列技術(shù)把生成的 (k+1)_項集散列到散列表中并計數(shù)，同時考察支持度；同時使用性質(zhì)：不包含任何 k_項集的事務(wù)不可能包含任何(k+1)_項集1717，來壓縮事務(wù)數(shù)據(jù)庫。v2004 年有學(xué)者提出在掃描數(shù)據(jù)庫時引入散列技術(shù) ，以達(dá)到降低數(shù)據(jù)庫的掃描次數(shù)，同時根據(jù)支持度的要求減少不可能成為頻繁項目集的候選項，從而了提高數(shù)據(jù)項集頻度的統(tǒng)計速度1818。v2007年有學(xué)者提出在產(chǎn)生1_頻繁項集和 2_頻繁項集時，使用 Hash 技術(shù)；在產(chǎn)生

14、 k_頻繁項集時使用事務(wù)壓縮優(yōu)化方法1919。2.5 2.5 轉(zhuǎn)換數(shù)據(jù)庫存儲方式與轉(zhuǎn)換數(shù)據(jù)庫存儲方式與 Apriori Apriori 性質(zhì)或其他方面的聯(lián)合使用性質(zhì)或其他方面的聯(lián)合使用v2008年有學(xué)者在原數(shù)據(jù)庫轉(zhuǎn)成布爾矩陣的基 礎(chǔ)上 ，根據(jù)交易記錄各項是按字典排序的，從而生成的候選項集和頻繁項集也是有序的這一性質(zhì)，減少了判斷次數(shù)；同時利用 k_維數(shù)據(jù)項目集的頻繁項集的必要條件使它的所有k-1維子集均是頻繁項目集這一性質(zhì)，在一定程度上優(yōu)化了頻繁項集的修剪2020。v2011年有學(xué)者對 2_項集使用了散列表技術(shù)，能較快速地獲得頻繁 2_項集。 同時對數(shù)據(jù)庫生成候選k_項集(k3)時轉(zhuǎn)為前學(xué)者15

15、15的矩陣方式存儲，如 ABC 出現(xiàn)在第 1、3、4 條事務(wù)中則表示為(1011)，再根據(jù)支持度就可生成頻繁 k_項集2121。v2012 年有學(xué)者在前學(xué)者1616十字鏈表的基礎(chǔ)上，利用k 維頻繁項集的所有k-1維子集均是頻繁項集這 一性質(zhì)，優(yōu)化了候選頻繁項集的生成和數(shù)據(jù)庫的掃描2222。同時也引出了其他學(xué)者對十字鏈表的改進(jìn)。2.6 Apriori 2.6 Apriori 算法與其他算法的聯(lián)合使用算法與其他算法的聯(lián)合使用v2007 年有學(xué)者提出 Apriori 算法與聚類算法相結(jié)合應(yīng)用于IDS日志分析中2323。v2010年有學(xué)者提出用遺傳算法對數(shù)據(jù)庫進(jìn)行性編碼、評估和遺傳，再使用Aprior

16、i的連接、剪枝和 提取步驟完成整個挖掘過程2424。v2012年有學(xué)者把 Apriori 算法應(yīng)用于矩陣聚類法中2525。v2012年有學(xué)者把云計算的兩個重要步驟：Map 函數(shù)( 映射 ) 和 Reduce 函數(shù) （ 歸約 ），分別引入到 Apriori 算法的連接和剪枝步驟中，該思想豐富了 Apriori 的內(nèi)容2626。v從上面的論述中可以看到，起初對 Apriori 算法的改進(jìn)著重于算法本身，比如利用其性質(zhì)改進(jìn)頻繁項集的生成、縮減數(shù)據(jù)庫容量、掃描次數(shù)等。后來算法本身的改進(jìn)點(diǎn)基本都被挖掘出來了，就轉(zhuǎn)向了數(shù)據(jù)庫存儲方式的改進(jìn)，如轉(zhuǎn)成布爾型矩陣、鏈表，數(shù)據(jù)庫存儲方式的改進(jìn)可謂是開創(chuàng)了 Apri

17、ori 算法改進(jìn)的一個新紀(jì)元。可是接下來似乎有點(diǎn)山窮水盡的味道，研究轉(zhuǎn)向了與其他算法的合作，如與遺傳算法、云計算的合作。Apriori算法的寬度優(yōu)先算法改進(jìn)前途是否依然光明，我們拭目以待。3. 3. 參考文獻(xiàn)參考文獻(xiàn)v 1 顏雪松 , 蔡之華.一種基于Apriori的高效關(guān)聯(lián)規(guī)則挖掘算法的研究J. 計算機(jī)工程與應(yīng)用, 2002, 32（10）：209-211v 2 李緒成 , 王保保 . 挖掘關(guān)聯(lián)規(guī)則中Apriori算法的一種改進(jìn)J. 計算機(jī)工程, 2002,28（7）：104-105v 3 徐章艷 , 劉美玲 , 張師超 , 等Apriori算法的三種優(yōu)化方法 J 計算機(jī)工程與應(yīng)用 , 20

18、04,40（36）： 190 -192 v 4 胡吉明 , 鮮學(xué)豐 挖掘關(guān)聯(lián)規(guī)則中Apriori算法的研究與改進(jìn)J計算機(jī)技術(shù)與發(fā)展, 2006,16（4）：99-101v 5 楊啟昉 , 馬廣平 關(guān)聯(lián)規(guī)則挖掘 Apriori 算法的改進(jìn) J 計算機(jī)應(yīng)用, 2008,28（12）：217-218v 6 陳江平 , 傅仲良 , 徐志紅 一種 Apriori 的改進(jìn)算法 J 武漢大學(xué)學(xué)報（信息科學(xué)版）, 2003,28（1）：94-98v 7 馮興杰 , 周諄 Apriori 算法的改進(jìn) J 計算機(jī)工程 , 2005 , 31( 增刊 ) : 172 -173v 8 郭健美 , 宋順林 , 李世松

19、基于 Apriori 算法的改進(jìn)算法 J 計算機(jī)工程與設(shè)計, 2008,29（11）：2814-2815v 9 吳斌 , 肖剛 , 陸佳煒 基于關(guān)聯(lián)規(guī)則挖掘領(lǐng)域的Apriori 算法的優(yōu)化研究J計算機(jī)工程與科學(xué), 2009,31(6)：116-118 v 10 劉維曉 , 陳俊麗 , 屈世富 , 等 一種改進(jìn)的 Apriori 算法 J 計算機(jī)工程與應(yīng)用, 2011,47(11)：149-151v 11 馬盈倉 挖掘關(guān)聯(lián)規(guī)則中 Apriori 算法的改進(jìn) J 計算機(jī)應(yīng)用與軟件, 2004,21（11）：82-83v 12 李超 , 余昭平 基于矩陣的 Apriori 算法改進(jìn) J 計算機(jī)工程,

20、2006,32(23)：68-69v 13 劉以安 , 羊斌 關(guān)聯(lián)規(guī)則挖掘中對 Apriori 算法的一種改進(jìn)研究J計算機(jī)應(yīng)用, 2007,27(2)：418-420v 14 張春生 改進(jìn)的數(shù)據(jù)庫一次掃描快速 Apriori 算法 J 計算機(jī)工程與設(shè)計, 2009,30(16)：3811-3813v 15 劉華婷 , 郭仁祥 , 姜浩關(guān)聯(lián)規(guī)則挖掘 Apriori 算法的研究與改進(jìn)J計算機(jī)應(yīng)用與軟件, 2009,26（1）：146-148v 16 黃建明 , 趙文靜 , 王星星 基于十字鏈表的 Apriori 改進(jìn)算法J計算機(jī)工程, 2009,35(2)：37-38v 17 黃進(jìn) , 尹治本 關(guān)聯(lián)規(guī)則挖掘