Apriori優(yōu)化算法評測

楊豐源 梁燕 陶以政 唐定勇 李龔亮

摘要：Apriori算法是第一個被提出的關(guān)聯(lián)規(guī)則挖掘算法，也是數(shù)據(jù)挖掘十大算法之一。從其誕生至今眾多研究者致力于從不同角度改進(jìn)Apriori算法，以提高挖掘關(guān)聯(lián)規(guī)則的效率。為了深入比較各優(yōu)化算法的特性，選取自頂向下、I-Apriori和T-Apriori等三種應(yīng)用廣泛的Apriori改進(jìn)算法，詳細(xì)介紹其優(yōu)化的依據(jù)和方法。通過實驗證明三種優(yōu)化算法相較于經(jīng)典Apriori算法取得了更優(yōu)的挖掘效率，對比分析了三種算法優(yōu)化效果和使用場景。

關(guān)鍵詞：Apriori算法;優(yōu)化;關(guān)聯(lián)規(guī)則;自頂向下;數(shù)據(jù)挖掘

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2021）25-0044-04

Abstract：Apriori algorithm is the first association rule mining algorithm proposed and one of the top ten algorithms for data mining. Since its birth， many researchers have devoted themselves to improving the Apriori algorithm from different perspectives to improve the efficiency of mining association rules. Three widely used Apriori improved algorithms， top-down， I-Apriori and T-Apriori， are selected， and the basis and methods of their optimization are introduced in detail. Experiments show that the three optimization algorithms have achieved better mining efficiency than the classic Apriori algorithm. The optimization effects and usage scenarios of the three algorithms are compared and analyzed.

Key words： Apriori algorithm; optimization; association rule; top-down; data mining

關(guān)聯(lián)規(guī)則挖掘理論與Apriori算法是由R.Agrawal等[1]在1994年同時提出的。經(jīng)過20多年的發(fā)展，關(guān)聯(lián)規(guī)則挖掘已經(jīng)是數(shù)據(jù)挖掘一個重要的分支領(lǐng)域，大量研究人員將關(guān)聯(lián)規(guī)則應(yīng)用到了其他領(lǐng)域[2，8]，或是利用關(guān)聯(lián)規(guī)則改進(jìn)協(xié)同過濾，精準(zhǔn)推薦等算法[3]。

關(guān)聯(lián)規(guī)則挖掘算法主要是從給定的事務(wù)數(shù)據(jù)集中找出形如A→B的關(guān)聯(lián)規(guī)則。該過程又可以被分解為兩個子過程：首先從事務(wù)數(shù)據(jù)集中找出所有滿足閾值的頻繁項目集;再利用頻繁項目集生成關(guān)聯(lián)規(guī)則。其中，耗費(fèi)時間更多的往往是第一步從數(shù)據(jù)集中挖掘出頻繁項集。因此，更多的研究關(guān)注于優(yōu)化挖掘頻繁項目集的過程，也提出了一些非常經(jīng)典的算法，如完全不同于Apriori算法思想的FP-growth算法。但Apriori算法作為關(guān)聯(lián)規(guī)則挖掘的第一個算法，仍然在關(guān)聯(lián)規(guī)則挖掘領(lǐng)域具有非常重要的地位，被IEEE會議選為數(shù)據(jù)挖掘十大算法之一。盡管Apriori算法如此經(jīng)典，依然有它的局限性，不斷有Apriori算法的優(yōu)化方法被提出[4-7]。本文對Apriori經(jīng)典算法及該算法的幾種優(yōu)化算法詳細(xì)描述，并通過實驗對比分析其優(yōu)化效果和適應(yīng)場景。

1 Apriori算法

設(shè)項的全集為I=（I1，I2，… ，Im），數(shù)據(jù)集為D，其中的每個事務(wù)T有唯一的主鍵標(biāo)識自己，記為TID。

1.1 相關(guān)概念

定義1? 設(shè)A、B為項集，并且是I的非空子集，則形如A→B的式子就是一條關(guān)聯(lián)規(guī)則。

對于每條關(guān)聯(lián)規(guī)則，我們定義了如下的支持度和置信度來衡量關(guān)聯(lián)的強(qiáng)度。

定義2? 對于一條關(guān)聯(lián)規(guī)則，它的支持度s是數(shù)據(jù)集的事務(wù)中包含所有項集的比例，如A→B的支持度就是D中事務(wù)包含A∪B的概率，即

support（A→B）=P（A∪B）=count（A∪B）/count（D）

置信度c則是D中包含A的事務(wù)同時包含B的比例P（B|A），即

confidence（A→B）=P（B|A）

= support（A∪B）/support（A） =count（A∪B）/count（A）

對支持度大于閾值min_sup且置信度大于閾值min_conf的關(guān)聯(lián)規(guī)則，稱為強(qiáng)關(guān)聯(lián)規(guī)則。

包含k個項的集合被稱為k-項集。滿足最小支持度的項集被稱為頻繁項集。若一個頻繁項集內(nèi)部只包含k-項集，則該頻繁項集被稱為頻繁k-項集或k-頻繁項集。對于頻繁項集，有以下幾條性質(zhì)。

性質(zhì)1? 任何頻繁項集的非空子集是頻繁項集， 非頻繁項集的超集是非頻繁項集。

性質(zhì)2? 如果頻繁k-項集還能產(chǎn)生頻繁k+1-項集， 則頻繁k-項集中的項集的個數(shù)必大于k。顯然，若頻繁2-項集中只包含{（I1，I2）}，則不可能形成頻繁3-項集;若是包含{（I1，I2），（I2，I3）}則有可能生成頻繁3-項集{（I1，I2，I3）}。

性質(zhì)3? 支持頻繁項集Lk的任意一條事務(wù)至少支持Lk-1中的k個k-1項集。