Apriori優化算法評測

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

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

關鍵詞：Apriori算法;優化;關聯規則;自頂向下;數據挖掘

中圖分類號：G642? ? ? ? 文獻標識碼：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

關聯規則挖掘理論與Apriori算法是由R.Agrawal等[1]在1994年同時提出的。經過20多年的發展，關聯規則挖掘已經是數據挖掘一個重要的分支領域，大量研究人員將關聯規則應用到了其他領域[2，8]，或是利用關聯規則改進協同過濾，精準推薦等算法[3]。

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

1 Apriori算法

設項的全集為I=（I1，I2，… ，Im），數據集為D，其中的每個事務T有唯一的主鍵標識自己，記為TID。

1.1 相關概念

定義1? 設A、B為項集，并且是I的非空子集，則形如A→B的式子就是一條關聯規則。

對于每條關聯規則，我們定義了如下的支持度和置信度來衡量關聯的強度。

定義2? 對于一條關聯規則，它的支持度s是數據集的事務中包含所有項集的比例，如A→B的支持度就是D中事務包含A∪B的概率，即

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

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

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

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

對支持度大于閾值min_sup且置信度大于閾值min_conf的關聯規則，稱為強關聯規則。

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

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

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

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