Apriori算法改進(jìn)研究

楊秋葉

摘要：Apriori算法作為數(shù)據(jù)挖掘技術(shù)中的經(jīng)典算法，它在事務(wù)數(shù)量少的數(shù)據(jù)庫中具有較好性能從而得到了人們的廣泛應(yīng)用，但該算法具有的兩個固有缺陷，影響了apriori算法在大數(shù)據(jù)庫中挖掘信息的效率。文中對apriori算法的兩個固有缺陷進(jìn)行改進(jìn)以便提高apriori算法在大數(shù)據(jù)庫中的挖掘效率。

關(guān)鍵詞：apriori算法；關(guān)聯(lián)規(guī)則；數(shù)據(jù)挖掘；頻繁項目集

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2013）09-2037-03

數(shù)據(jù)挖掘是近年來非?；钴S的一個研究領(lǐng)域，它是在機(jī)器學(xué)習(xí)、統(tǒng)計學(xué)、數(shù)據(jù)庫技術(shù)、信息科學(xué)的理論基礎(chǔ)上發(fā)展而成。數(shù)據(jù)挖掘（DM，Data Mining）就是從大量的、不完全的、有噪聲的、模糊的、隨機(jī)的數(shù)據(jù)中，提取隱含在其中的、人們事先不知道的、但又是潛在的有用信息和知識的過程[1]，其主要目的是從大量的數(shù)據(jù)源提取有用的并且用戶感興趣的知識和模式。數(shù)據(jù)挖掘的一個重要分支就是關(guān)聯(lián)規(guī)則挖掘，關(guān)聯(lián)規(guī)則反映的是一個事件跟其他事件之間的關(guān)聯(lián)或依賴，是事務(wù)內(nèi)部的規(guī)律或模式，體現(xiàn)了現(xiàn)實(shí)世界中事物的關(guān)聯(lián)關(guān)系，比如人們從超市銷售數(shù)據(jù)中發(fā)現(xiàn)購買啤酒的客戶很有可能購買尿布，因此超市管理人員根據(jù)這種關(guān)聯(lián)關(guān)系將啤酒和尿布擺放在相鄰的位置以促進(jìn)商品的銷售。

關(guān)聯(lián)規(guī)則的形式描述為：設(shè)I=[[I1，I2，I3，...，In]]是事務(wù)數(shù)據(jù)庫D中所有項的集合，D中每個事務(wù)T都有唯一的標(biāo)識符[Tid]，[T?I]，A、B為項集，關(guān)聯(lián)規(guī)則是形如 A=>B的蘊(yùn)涵式，其中[A?I，B?I，并且A?B=?]。

關(guān)聯(lián)規(guī)則有兩個重要的度量標(biāo)準(zhǔn)：支持度（support）和置信度（confidence）。通常人們在挖掘關(guān)聯(lián)規(guī)則時會設(shè)置最小支持度閾值（min_sup）和最小置信度閾值（min_conf），我們將支持度大于或等于最小支持度閾值的項集稱為頻繁項集，將同時滿足最小支持度閾值和最小置信度閾值的規(guī)則稱為強(qiáng)關(guān)聯(lián)規(guī)則，否則為弱關(guān)聯(lián)規(guī)則，強(qiáng)關(guān)聯(lián)規(guī)則才是用戶感興趣的關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則的挖掘過程分為兩個步驟：

第一步：根據(jù)最小支持度閾值從事務(wù)數(shù)據(jù)庫中找出所有的頻繁項集。

第二步：根據(jù)最小置信度閾值由頻繁項集生成強(qiáng)關(guān)聯(lián)規(guī)則。

其中，從事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)頻繁項集是關(guān)聯(lián)規(guī)則挖掘的關(guān)鍵步驟，該步驟決定了關(guān)聯(lián)規(guī)則挖掘的整體性能。

1 apriori算法

1.1 apriori算法基本思想

apriori算法是針對關(guān)聯(lián)規(guī)則挖掘的第一個步驟，也就是從事務(wù)數(shù)據(jù)庫中發(fā)現(xiàn)所有的頻繁項集，apriori算法采用逐層搜索的迭代方法來生成頻繁項集[2]，首先掃描事務(wù)數(shù)據(jù)庫D，根據(jù)用戶設(shè)置的最小支持度找出數(shù)據(jù)庫D中的1-項頻繁項集L1，然后由1-項頻繁項集L1進(jìn)行連接操作生成2-項候選項集C2，再次掃描事務(wù)數(shù)據(jù)庫從2-項候選項集C2中找出2-項頻繁項集L2，然后再由2-項頻繁項集L2進(jìn)行連接生成3-項候選項集C3，再次掃描事務(wù)數(shù)據(jù)庫找出3-項候選項集中的3-項頻繁項集L3，依次類推，直到?jīng)]有更大模式的k-項頻繁項集或候選項集為空，則apriori算法結(jié)束（如圖1）。

1.2 Apriori算法的缺陷

1） 每次由候選項集生成頻繁項集時都需要掃描數(shù)據(jù)庫，而數(shù)據(jù)庫一般都存放在外存上，這樣就導(dǎo)致該算法在執(zhí)行過程中需要很大的I/O負(fù)載。

2） 頻繁項集進(jìn)行自我連接時會產(chǎn)生大量的候選項集，這些候選項集的存放需要很大的空間，而且由候選項集經(jīng)過再次掃描數(shù)據(jù)庫生成頻繁項集時也需要大量的時間來處理。

2 apriori算法改進(jìn)方法

apriori算法執(zhí)行過程中需要經(jīng)過數(shù)據(jù)庫掃描操作和頻繁項集連接操作，我們針對這兩個操作進(jìn)行改進(jìn)以便提高apriori算法的執(zhí)行效率。改進(jìn)的基本思想是：每次由候選項集生成頻繁項集時需要掃描數(shù)據(jù)庫，而每次掃描數(shù)據(jù)庫時并不需要掃描數(shù)據(jù)庫中的所有事務(wù)數(shù)據(jù)，所以我們對每次掃描的數(shù)據(jù)庫進(jìn)行優(yōu)化，就可以減少掃描數(shù)據(jù)庫的IO操作；另外，頻繁項集進(jìn)行連接操作生成的候選項集中，不是所有的候選項集經(jīng)過數(shù)據(jù)庫掃描后會轉(zhuǎn)化為頻繁項集，因此，在每次生成候選項集之前，我們對已有的頻繁項集進(jìn)行優(yōu)化，既可以減少頻繁項集的連接操作，也可以減少生成的候選項集轉(zhuǎn)化為頻繁項集的處理時間，我們從數(shù)據(jù)庫優(yōu)化、頻繁項集優(yōu)化、連接操作優(yōu)化這三個方面對Apriori算法來進(jìn)行改進(jìn)。

2.1 數(shù)據(jù)庫優(yōu)化

Apriori算法每次迭代生成頻繁項集時，都需要掃描數(shù)據(jù)庫中的所有數(shù)據(jù)，以便將候選項集中支持度大于或等于最小支持度閾值的項集找出來構(gòu)成新的頻繁項集，比如頻繁項集中包含10個分項，則apriori算法就必須迭代10次，apriori算法執(zhí)行過程中就必須對數(shù)據(jù)庫中的所有數(shù)據(jù)掃描10次。根據(jù)性質(zhì)1：如果頻繁項集的長度為k，則長度小于k的事務(wù)肯定不滿足頻繁項集的要求，我們在生成k-項頻繁項集掃描數(shù)據(jù)庫時就可以跳過長度小于k的事務(wù)，這樣可以減少數(shù)據(jù)庫掃描時間。

根據(jù)性質(zhì)1，我們可以減少數(shù)據(jù)庫掃描時的事務(wù)個數(shù)，在剩下的數(shù)據(jù)庫事務(wù)中還存在對生成頻繁項集不起作用的事務(wù)，如果我們將剩下的對生成頻繁項集不起作用的的事務(wù)再一次進(jìn)行優(yōu)化，就可以進(jìn)一步減少掃描數(shù)據(jù)庫中事務(wù)的個數(shù)，從而進(jìn)一步減少apriori算法的IO操作。

性質(zhì)2：我們將數(shù)據(jù)庫中所有的不同項作為一個集合，記為集合A，將所有頻繁項集中的不同項作為一個集合，記為集合B，則任何一個事務(wù)T在集合A的分項個數(shù)一定大于在集合B中的分項個數(shù)，即[|TB|<=|TA|]。

證明：因?yàn)轭l繁項集B中的所有項都是來自于集合A，因此有[B?A]，對于數(shù)據(jù)庫中的任意事務(wù)T，T中的任意分項[Ii]（[1<=i<=|T|]），如果[Ii∈B]則[Ii∈A]，此時有[|TB|=|TA|]，如果T中存在任一項[Ii?B]，此時有[|TB|<|TA|]，因此，有[|TB|<=|TA|]。

根據(jù)性質(zhì)2，我們由生成的所有頻繁項集中的不同分項構(gòu)成一個集合B，如果數(shù)據(jù)庫中的某個事務(wù)T在集合B中的分項個數(shù)小于本次迭代生成的頻繁項集中的分項個數(shù)，則這樣的事務(wù)對下一次迭代生成頻繁項集不起作用，我們就可以刪除該事務(wù)或跳過該事務(wù)的掃描，從而減少Apriori算法的IO操作。

2.2頻繁項集優(yōu)化

性質(zhì)3 k-維數(shù)據(jù)項目集是頻繁項集的必要條件為它的所有k-1 維子集均是頻繁項集[3]，也就是，如果k-項集X的任意一個 （k-1）-項子集不是頻繁的，則X也不是頻繁的[4]。

性質(zhì)4 若存在k-項集X={[i1，i2，…ik]}，該項集X中如果存在項j[∈X使得|Lk-1（j）|]

證明： k-項集X={[i1，i2，…ik]}有k個（k-1）-項子集，并且只有一個（k-1）-項子集不包含項j（ j為K項集X中任意項），由性質(zhì)3可得，項集X為頻繁項集時有[|Lk-1（j）|=（k-1）]，故[|Lk-1（j）|<（k-1）]時說明項集X不是頻繁項集。

我們根據(jù)性質(zhì)4，在頻繁項集進(jìn)行連接操作前就可以判斷連接操作后生成的候選項集是否為更大模式的頻繁項集，如果生成的候選項集肯定不是更大模式的頻繁項集，我們就可以在連接操作前對這樣的頻繁項集不進(jìn)行連接操作，從而減少連接操作的時間及候選項集轉(zhuǎn)化為更大模式的頻繁項集的處理時間。

2.3 連接操作優(yōu)化

連接操作是apriori算法執(zhí)行過程中的一個重要步驟，只有進(jìn)行連接操作后才能生成更大模式的候選項集，只有生成更大模式的候選項集，通過再次掃描數(shù)據(jù)庫后才能得到更大模式的頻繁項集。兩個頻繁項集進(jìn)行連接操作必須滿足下面這個條件：這兩個頻繁項集的最后一項不能相同，除最后一項外，這兩個頻繁項集的其他項必須分別相同，即滿足條件

[l1[1]=l2[1]∧l1[2]=l2[2]∧…∧l1[k-2]=l2[k-2]∧l1[k-1]]<[l2[k-1]]

[l1]、[l2]都是（k-1）-頻繁項集，并且在頻繁項集[L（k-1）]中項集[l2]位于項集[l1]的后面位置，由于頻繁項集及頻繁項集中的分項都是有序排列的，根據(jù)項集的這個有序性，如果頻繁項集[l1]與頻繁項集[l2]不滿足連接條件，則位于頻繁項集[l2]后面的頻繁項集也不滿足與頻繁項集[l1]的連接條件，這樣，就可以減少大量的連接操作次數(shù)，從而提高apriori算法的效率。

3 實(shí)驗(yàn)結(jié)果分析

改進(jìn)后的apriori算法我們記為apriori-1算法，測試環(huán)境是：操作系統(tǒng)為Microsoft Windows XP Professional，CPU 為Intel（R） Pentium（R） 4，3.00 GHz，內(nèi)存為 512M，實(shí)驗(yàn)樣本數(shù)據(jù)由IBM公司Almaden中心提供的標(biāo)準(zhǔn)數(shù)據(jù)集[5]，測試結(jié)果如圖2。

從圖2中可以得到，在支持度閾值相同的條件下，Apriori-1算法的運(yùn)行時間要比Apriori算法的運(yùn)行時間少，原因有：1） Apriori-1算法中每次掃描的事務(wù)個數(shù)比傳統(tǒng)的Apriori算法要少。2） Apriori-1算法在連接操作前對[Lk-1]中的項集進(jìn)行優(yōu)化，減少了生成k-項候選項集集合[Ck]的連接操作次數(shù)和剪枝操作次數(shù)。3） Apriori-1算法利用項的有序性，減少連接操的次數(shù)。

參考文獻(xiàn)：

[1] 邵峰晶，于忠清.數(shù)據(jù)挖掘原理與算法[M].北京：中國水利水電出版社，2003：2-3.

[2] 楊金鳳，劉鋒.一種新的改進(jìn)Apriori算法[J].微型機(jī)與應(yīng)用，2010（1）：55-57.

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

[4] 陳寧軍，高志年.一種改進(jìn)的正負(fù)關(guān)聯(lián)規(guī)則挖掘算法[J].計算機(jī)科學(xué)，2011，38（12）：191-193，212.

[5] Apriori算法樣本數(shù)據(jù)集下載網(wǎng)址：http：//fimi.ua.ac.be/data/chess.dat.