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

摘要：Apriori算法是第一個(gè)被提出的關(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ù)和方法。通過(guò)實(shí)驗(yàn)證明三種優(yōu)化算法相較于經(jīng)典Apriori算法取得了更優(yōu)的挖掘效率，對(duì)比分析了三種算法優(yōu)化效果和使用場(chǎng)景。

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

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

文章編號(hào)：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年同時(shí)提出的。經(jīng)過(guò)20多年的發(fā)展，關(guān)聯(lián)規(guī)則挖掘已經(jīng)是數(shù)據(jù)挖掘一個(gè)重要的分支領(lǐng)域，大量研究人員將關(guān)聯(lián)規(guī)則應(yīng)用到了其他領(lǐng)域[2，8]，或是利用關(guān)聯(lián)規(guī)則改進(jìn)協(xié)同過(guò)濾，精準(zhǔn)推薦等算法[3]。

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

1 Apriori算法

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

1.1 相關(guān)概念

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

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

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

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

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

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

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

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

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

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

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

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