摘 要：在介紹Apriori算法原理和實(shí)現(xiàn)過程的基礎(chǔ)上，針對該算法存在的兩個(gè)缺陷，即多次掃描事務(wù)數(shù)據(jù)庫和產(chǎn)生大量的候選集，提出新的算法NewApriori，該算法改變由低維頻繁項(xiàng)目集到高維頻繁項(xiàng)目集的多次連接運(yùn)算，直接從1頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集，克服了Apriori算法的固有缺點(diǎn)，從而提高了運(yùn)算效率。

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

中圖分類號：TP311 文獻(xiàn)標(biāo)識碼：B 文章編號：1004373X(2008)1807803

Improvement of Apriori Algorithm in Association Rule Mining

ZHU Ye，YE Gaoying

(Chengdu University of Information Technology，Chengdu，610225，China)

Abstract：In this paper，the principle and performance of Apriori algorithm is introduced，and two defects of Apriori algorithm:scanning database too much and creating excessive candidate itemsets are analyzed.A new Apriori algorithm has been designed for finding out the highest dimension frequent itemsets from frequent 1itemset directly.A great number of linking operations in finding frequent itemsets dimension by dimension are canceled over all.The algorithm is improved efficiently.

Keywords：association rule mining;Apriori algorithm;frequent itemset;candidate itemset

1 引 言

數(shù)據(jù)挖據(jù)^［1］(Data Mining)是一個(gè)多學(xué)科交叉研究領(lǐng)域，是從大量數(shù)據(jù)中提取或“挖掘”出未知的、潛在的、有用的知識。從現(xiàn)狀來看，數(shù)據(jù)挖掘的研究仍然處于廣泛研究探索階段，主要包括特征化與比較、關(guān)聯(lián)規(guī)則挖掘、分類預(yù)測和聚類分析等方法。其中關(guān)聯(lián)規(guī)則挖掘(Association Rule Mining)是數(shù)據(jù)挖掘中最活躍的研究方法之一。

最早由Agrawal等人^［2］(1993年)針對購物籃分析(Basket Analysis)問題提出的，其目的是為了發(fā)現(xiàn)交易數(shù)據(jù)庫(Transaction Database)中不同商品之間的聯(lián)系規(guī)則。通過關(guān)聯(lián)規(guī)則發(fā)現(xiàn)算法尋找形如“如果<條件>，那么<結(jié)論>”的規(guī)則，這種規(guī)則以其簡潔性已經(jīng)多次成功應(yīng)用到?jīng)Q策支持系統(tǒng)，指導(dǎo)人們在各個(gè)領(lǐng)域中的活動(dòng)。在關(guān)聯(lián)規(guī)則挖掘算法的研究中，Agrawal提出的Apriori算法最為經(jīng)典，但該算法本身固有的缺陷^［3］是多次掃描數(shù)據(jù)庫，并產(chǎn)生龐大的候選數(shù)據(jù)集。

本文從這兩個(gè)缺陷入手，減少掃描數(shù)據(jù)庫的次數(shù)，并省去大量候選集的產(chǎn)生過程，從而提高算法效率。

2 關(guān)聯(lián)規(guī)則基本概念

一個(gè)事務(wù)數(shù)據(jù)庫中的關(guān)聯(lián)規(guī)則挖掘可以描述如下^［3］：設(shè)I={i1，i2，…，im}是一個(gè)項(xiàng)目集合，事務(wù)數(shù)據(jù)庫D={t₁，t2，…，t_n}是由一系列具有惟一標(biāo)識TID的事務(wù)組成，每個(gè)事務(wù)t_i(i=1，2，…，n)都對應(yīng)于I上的子集。

定義1 支持度(Support):

指包含項(xiàng)目集(Itemset)I₁(I₁∈I)的事務(wù)在D中所占的百分比。

定義2 信任度(Confidence):

在形如I₁I₂的關(guān)聯(lián)規(guī)則中(I₁∈I，I₂∈I)，信任度指包含I₁和I₂的事務(wù)數(shù)與包含I₁的事務(wù)數(shù)之比，即在I₁發(fā)生的情況下，I₂也發(fā)生的可能性。

定義3 頻繁項(xiàng)目集(Frequent Itemset)和最大頻繁項(xiàng)目集:

對項(xiàng)目集和事務(wù)數(shù)據(jù)庫D，T中所有滿足用戶指定的最小支持度的項(xiàng)目集稱為頻繁項(xiàng)目集。在頻繁項(xiàng)目集中挑選出所有不被其他元素包含的頻繁項(xiàng)目集稱為最大頻繁項(xiàng)目集。

定義4 強(qiáng)關(guān)聯(lián)規(guī)則(Strong Association Rule)：

指D在I上滿足最小支持度和用戶指定的最小信任度的關(guān)聯(lián)規(guī)則。

關(guān)聯(lián)規(guī)則挖掘問題就是通過最小支持度和最小信任度在一個(gè)事務(wù)數(shù)據(jù)庫中尋找強(qiáng)關(guān)聯(lián)規(guī)則的過程，劃分為2個(gè)子問題：

(1) 發(fā)現(xiàn)最大頻繁項(xiàng)目集；

(2) 在最大頻繁項(xiàng)目集中生成強(qiáng)關(guān)聯(lián)規(guī)則。第一個(gè)子問題是本文的研究重點(diǎn)，即提出一種新的算法來發(fā)現(xiàn)最大頻繁項(xiàng)目集。

3 Apriori算法及缺點(diǎn)分析

1994年Agrawal等人建立用于事務(wù)數(shù)據(jù)庫挖掘的項(xiàng)目集的格空間理論^［4］：頻繁項(xiàng)目集的子集是頻繁項(xiàng)目集，非頻繁項(xiàng)目集的超集是非頻繁項(xiàng)目集。Apriori算法^［3］依據(jù)此理論進(jìn)行剪枝。該算法是通過項(xiàng)目集數(shù)目不斷增長來逐步發(fā)現(xiàn)頻繁項(xiàng)目集的，算法輸入數(shù)據(jù)集D和最小支持?jǐn)?shù)minsupcount(最小支持度與事務(wù)數(shù)的乘積)，輸出頻繁項(xiàng)目集L。算法首先產(chǎn)生1頻繁項(xiàng)目L₁，然后是2頻繁項(xiàng)目集L₂，直至不再能擴(kuò)展頻繁項(xiàng)目集的元素?cái)?shù)目而算法停止。在第k次循環(huán)中，過程先產(chǎn)生k候選項(xiàng)目集的集合C_k，然后通過掃描數(shù)據(jù)庫得到C_K的支持度并測試產(chǎn)生k頻繁項(xiàng)目集L_k。算法過程^［5］是：連接→剪枝→生成C_k→掃描計(jì)數(shù)→比較→生成L_k。

從以上分析可以發(fā)現(xiàn)，Apriori算法使用逐層搜索的迭代方法，通過低維頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集^［4］。這樣，就致使Apriori算法存在2個(gè)致命的性能瓶頸：

(1) 多次掃描事務(wù)數(shù)據(jù)庫。每次k循環(huán)，候選集C_k中的每個(gè)元素都必須通過掃描數(shù)據(jù)庫1次來判斷其是否加入L_k。如果頻繁大項(xiàng)目集包含n項(xiàng)，則至少需要掃描事務(wù)數(shù)據(jù)庫n遍，需要很大的I/O負(fù)載。

(2) 可能產(chǎn)生龐大的候選集。由L_k-1產(chǎn)生k候選集C_k是呈指數(shù)增長的，例如104個(gè)1頻繁項(xiàng)目集有可能產(chǎn)生接近107個(gè)元素的2候選集，如此龐大的候選集對時(shí)間和存儲空間是一個(gè)挑戰(zhàn)。

4 改進(jìn)Apriori算法

Apriori算法使用候選集去找頻繁集，算法反復(fù)連接、剪枝，導(dǎo)致執(zhí)行效率低。因此，考慮使用其他方法來取代通過候選集去找頻繁集的過程，改變由低維頻繁項(xiàng)目集到高維頻繁項(xiàng)目集的多次連接運(yùn)算，這樣，既可以避免大量候選集的產(chǎn)生，又可以減少數(shù)據(jù)庫的掃描次數(shù)，從而提高算法效率。在介紹具體改進(jìn)措施之前，引入2條推論：

推論1 如果K頻繁項(xiàng)目集L_k中的項(xiàng)目集個(gè)數(shù)≤K時(shí)，則該集合為最大頻繁項(xiàng)目集的集合。

證明： 根據(jù)項(xiàng)目集格空間理論，假如存在K+1頻繁項(xiàng)目集L_k+1，那么對于L_k+1的K+1個(gè)K項(xiàng)目子集都是頻繁項(xiàng)目集，與題設(shè)項(xiàng)目集個(gè)數(shù)≤K矛盾，所以，如果頻繁項(xiàng)目L_k中項(xiàng)目集的個(gè)數(shù)≤K時(shí)，則無法產(chǎn)生K+1頻繁項(xiàng)目集L_k+1，因此，該推論成立。

推論2 最大頻繁項(xiàng)目集L_k的項(xiàng)目數(shù)K小于等于在所有事務(wù)中滿足支持計(jì)數(shù)的最大項(xiàng)目數(shù)k。對于事務(wù)T，若2項(xiàng)集的支持計(jì)數(shù)為sup₂，3項(xiàng)集的支持計(jì)數(shù)為sup₃，…，n-項(xiàng)集的支持計(jì)數(shù)為sup_n(n為所有事務(wù)中的最大項(xiàng)目數(shù))，其中，sup_k( Minsupport(2(k(n)且sup_k+1

證明： (反證法)假設(shè)K大于k，則存在頻繁項(xiàng)目集L_k滿足支持計(jì)數(shù)，而與滿足支持計(jì)數(shù)的項(xiàng)目數(shù)k最大矛盾，因此，最大頻繁項(xiàng)目數(shù)K不可能大于滿足支持計(jì)數(shù)的最大項(xiàng)目數(shù)k，推論得證。

一般地，只關(guān)心那些不被其他頻繁項(xiàng)目集所包含的最大項(xiàng)目集的集合，在這些頻繁項(xiàng)目集中發(fā)現(xiàn)關(guān)聯(lián)規(guī)則。所以，問題歸結(jié)為如何高效確定最大頻繁項(xiàng)目集。改變通常的做法，應(yīng)用上述推論，先確定最大頻繁項(xiàng)目集的項(xiàng)目數(shù)K，然后找出所有頻繁項(xiàng)集L_k。算法NewApriori描述如下：

輸入：事務(wù)數(shù)據(jù)T；最小支持?jǐn)?shù)minsupcount。

輸出：最大頻繁項(xiàng)目集L。

(1) C［n］=0; //初始化數(shù)組C［n］，n為所有事務(wù)中的最大項(xiàng)目數(shù)

(2)for each t_i∈Tdo begin

(3) i=|t_i|;//i為每個(gè)事務(wù)所含的項(xiàng)目數(shù)

(4) C［i］=C［i］+1

(5)end

(6) L₁={large 1-itemsets};//所有滿足支持計(jì)數(shù)的1頻繁項(xiàng)目集

(7)for i=nto 2do begin

(8)if(C［i］(minsupcount) then begin

(9) k=i;

//根據(jù)推論2，k≤i，由于找最大的頻繁項(xiàng)集，因此可以假定k=i

(10) C_k={large k-itemsets};//直接從L₁中生成C_k

(11) L_k={C_k|C_k.count(minsupcount and C_k.count(k};//根據(jù)推論1

(12)if L_k≠then

(13)return L_k

(14)end

(15)end

該算法的改進(jìn)主要體現(xiàn)在以下2方面：

(1) 最大頻繁集的產(chǎn)生過程改變?yōu)閺母呔S到低維的搜索過程，根據(jù)不同項(xiàng)目個(gè)數(shù)的出現(xiàn)頻率，直接從1頻繁項(xiàng)目集產(chǎn)生高維頻繁項(xiàng)目集，省去多次的連接運(yùn)算及大量候選集的產(chǎn)生，節(jié)約了運(yùn)行時(shí)間和主存空間。

(2) 減少掃描數(shù)據(jù)庫次數(shù)，該算法掃描數(shù)據(jù)庫的次數(shù)最少可以減少到3次(第1次，計(jì)算C\\；第2次，得到1頻繁項(xiàng)目集；第3次，計(jì)算大于支持計(jì)數(shù)的L_k)，而Apriori算法則需要掃描k次，因此，對于維數(shù)較高(k值較大)的頻繁項(xiàng)目集的計(jì)算，效率提高更明顯。

5 實(shí)例分析

下面給出一個(gè)服裝店的20個(gè)收款機(jī)事務(wù)記錄，每一事務(wù)T代表購買的商品集合，I1-I6分別表示不同的商品，最小支持?jǐn)?shù)minsupcount=3，見表1所示。

根據(jù)NewAgriori算法

(1) 計(jì)算C［n］，C［1］=4，C［2］=6，C［3］=5，C［4］=4，C［5］=1；

(2) 得到1頻繁項(xiàng)目集L₁={{I2}，{I3}，{I4}，{I5}，{I6}}；

(3) 由于C［5］minsupcount，則先假定最大頻繁項(xiàng)目集的項(xiàng)目數(shù)k=4，從L₁中產(chǎn)生所有4項(xiàng)目集，共5個(gè)，分別是：{I2，I3，I4，I5}，{I2，I3，I4，I6}，{I3，I4，I5，I6}，{I2，I4，I5，I6}，{I2，I3，I5，I6}，掃描數(shù)據(jù)庫計(jì)算該5個(gè)候選集的支持計(jì)數(shù)，求得滿足最小支持計(jì)數(shù)的項(xiàng)集為：{I2，I4，I5，I6}，其支持計(jì)數(shù)=4，根據(jù)推論1可知，該頻繁項(xiàng)目集即是最大頻繁項(xiàng)目集，計(jì)算結(jié)束。如果使用Apriori算法，則需要掃描4次數(shù)據(jù)庫，并且從1頻繁項(xiàng)目集到4頻繁項(xiàng)目集的連接計(jì)算共需產(chǎn)生24個(gè)候選集。而使用NewApriori算法，整個(gè)過程共掃描了3次數(shù)據(jù)庫，且只產(chǎn)生5個(gè)4項(xiàng)候選集，很明顯，無需產(chǎn)生大量的候選集同樣可以找到最大頻繁項(xiàng)目集，同時(shí)減少了掃描數(shù)據(jù)庫的次數(shù)。但從上述算法流程不難看出，如果第一次假定的k不是所要求的最大頻繁項(xiàng)目集的項(xiàng)目數(shù)時(shí)，則需要再次尋找符合要求的k值，多一次尋找，就多一次對數(shù)據(jù)庫的掃描，候選集的數(shù)量也會隨之增多。不過，數(shù)據(jù)庫的掃描次數(shù)不會超過k次，為了避免過多冗余的候選集，可以將1頻繁項(xiàng)目集按支持計(jì)數(shù)的大小順序排列，組合支持計(jì)數(shù)相對少的項(xiàng)目，及早發(fā)現(xiàn)非頻繁項(xiàng)目，以減少候選集的產(chǎn)生。因此，該算法特別適合于項(xiàng)目數(shù)比較大的最大頻繁項(xiàng)目的查找。

6 結(jié) 語

Apriori算法作為最經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法被廣泛使用，由于其固有的局限性，出現(xiàn)了大量的改進(jìn)算法。本文提出的NewApriori算法也針對引起性能瓶頸的缺點(diǎn)而做出的改進(jìn)，提高了系統(tǒng)運(yùn)行效率。但不足的是，此算法只能找到項(xiàng)數(shù)最大的頻繁項(xiàng)目集，也就是說，得到的頻繁項(xiàng)目集不夠完整，因此，還需要進(jìn)一步完善。

參 考 文 獻(xiàn)

［1］Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘概念與技術(shù)\\.范明，孟小峰，譯.北京:機(jī)械工業(yè)出版社，2001.

［2］Agrawal R，Imielinske T，Swami A.Mining Association Rules between Sets of Items in Large Databases.Proc.of the ACM SIGMOD International Conference on the Management of Data，Washington D.C.，1993:207216.

［3］毛國君，段立娟.數(shù)據(jù)挖掘原理與算法\\.北京:清華大學(xué)出版社，2005.

［4］Agrawal R，Srikant R.Fast Algorithms for Mining Association Rules.Proc.1994 Int.Conf.Very Large Database.Santiago，Chile，1994:487499.

［5］李小兵.關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)與優(yōu)化研究\\.廈門大學(xué)學(xué)報(bào):自然科學(xué)版，2005(7):468471.

［6］謝宗毅.關(guān)聯(lián)規(guī)則挖掘Apriori算法的研究與改進(jìn)\\.杭州電子科技大學(xué)學(xué)報(bào)，2006(6):7882.

作者簡介 朱 燁 女，1975年出生，陜西榆林人，博士研究生。主要研究方向?yàn)閿?shù)據(jù)庫與數(shù)據(jù)挖掘。

葉高英 男，1949年出生，陜西榆林人，研究員，博士生導(dǎo)師。主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用、計(jì)算數(shù)學(xué)。