基于概率參數的Apriori改進算法

孫帥 劉子龍

摘 要：關聯規則可在龐大的數據集中找出不同事務之間隱藏的關系，其中Apriori算法是關聯規則分析中較為有效的辦法。然而，Apriori算法產生候選項集的效率較低且掃描數據過于頻繁，造成算法計算需要耗費較長時間。另外，初始定義的最小支持度與最小置信度也不足以過濾無用的關聯規則。針對以上問題，利用概率理論與有效的參數設置，在原有Apriori算法基礎上，提出一種基于概率事務壓縮的關聯規則改進算法。數值算例結果表明，新算法可在第二次迭代之后，大幅減少低效候選項集，從而提升經典Apriori算法效率。

關鍵詞：關聯規則;Apriori改進算法;概率參數

DOI：10. 11907/rjdk. 191099 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP312文獻標識碼：A 文章編號：1672-7800（2019）009-0085-03

Research on Improvement of Apriori Algorithm Based on Probability Parameter

SUN Shuai，LIU Zi-long

（School of Optical and Computer Engineering，University of Shanghai for Science and Technology， Shanghai 200093，China）

Abstract：Association rule mining is to find interesting hidden associations from huge number of initial data. Apriori algorithm is the effective way to find these association. Howerer，the original Apriori has its own drawbacks，such as low efficiency of candidate item sets and scanning data frequency. The minimum support and confidence are not enough to filter useless association rules. To recover the deficiencies，this paper proposed an improved algorithm based on marked transaction compression by probability and parameters. Experiments show that this algorithm has much better capability than the original Apriori algorithm. After the second iteration of the algorithm，the candidate sets are reduced 50%，it shows that the improved algorithm was more efficient than the original one.

Key Words： association rule;improved Apriori algorithm;probability parameters

1 Apriori算法簡介

關聯規則首先是由 Agrawal等提出的，該算法用來在龐大的初始數據庫中發現有趣的隱藏關聯[1]。其經典應用是通過對“啤酒”和“尿布”兩種商品的關聯分析[2]，使超市獲得了可觀的經濟收益。

Apriori 算法是關聯規則的經典算法，其最終目的是在所有事務集中找出最大頻繁項集[3]，再通過條件概率找出不同事務之間的關聯，通過層層迭代搜索，直到獲得滿足最小支持度與最小置信度的事務集[4]，同時保證該事務集中所含項數最多[5]。該算法核心理論是：“頻繁項集的子集仍然是頻繁項集，非頻繁項集的超集仍是非頻繁項集[6]”。算法實現過程包含連接和剪枝兩個步驟[7]，即首先在K項頻繁集的基礎上，通過連接形成k+1項候選項集，因為頻繁項集的子集仍是頻繁項集，對每個k+1項候選項集的子集進行驗證，刪除不滿足條件的候選項集，即剪枝[8]。直到候選項集合中不再存在任何項，便產生了最大頻繁項集[9]，算法結束。

然而，經典Apriori算法存在著掃描數據庫頻繁、產生候選項集多、耗時較長等不足[10]，針對以上不足，國內外學者提出了一些算法改進方案，例如：約束性關聯規則算法[11]、增量式關聯規則算法[12]、多層關聯規則算法[13]、關聯規則ECLAT算法[14]等。為過濾掉經典Apriori算法中無效與關聯程度較弱的候選項集，提升算法效率，本文嘗試引入相關概率計算與參數約束，通過對候選項集進行壓縮實現對Apriori算法的改進。數值算例實驗結果表明，改進算法相比經典Apriori算法大幅減少了候選項集，從而降低了算法復雜度。

2 基于概率事務壓縮的改進Apriori算法

2.1 經典Apriori算法理論分析

經典Apriori算法會設定某些參數作為初始閾值，例如最小支持度與最小置信度[15]，其中最小支持度定義為：衡量支持度的一個閾值，表示項目集統計意義上的最低重要性[16]。最小置信度定義為：衡量某個項集最低的置信程度[17]，再將樣本數據帶入標準算法迭代，從而產生一些因果關聯。然而，在某些情況下，僅通過最小支持度與最小置信度還不足以給出最終結果。通過以下例子說明該問題：用Support表示相應規則的支持度，Confidence表示置信度，假設購買一批商品，其中耳機（X）共有6 000件（包括耳機單件與電腦禮包中的耳機），電腦（Y）共有9 000臺（包括電腦單件與電腦禮包中的電腦），電腦禮包4 000件，將最小支持度設定為30%，最小置信度設定為60%，通過計算可得出如下關聯規則：

通過上述計算可知關聯規則（X→Y）的支持度和置信度都大于設定的最小支持度與最小置信度，因此可認為關聯規則成立，即在購買耳機的同時也會購買電腦。

通過計算，X→Y關聯也滿足事先設定的最小支持度與最小置信度的閾值，所以其兩者之間也能構成關聯規則，這兩種截然相反的關聯形成了悖論，可見僅滿足最小支持度和最小置信度計算閾值，即認為關聯規則成立是存在問題的。

通過上述實例，可發現僅通過設定最小支持度與最小置信度閾值，在某些特殊情況下會存在局限，主要由于經典Apriori算法并沒有充分考慮反面事件的支持度與置信度。在實際使用中，相關事務的關聯需要證明僅是正相關的，不存在負相關的可能，因此算法不但需要驗證正相關的關聯規則X→Y滿足最小支持度與最小置信度的設定條件，同時其支持度與置信度也必須大于X→Y。只有同時滿足正反兩方面的設定條件，才能認為所獲得關聯規則是自洽的。

2.2 關聯條件概率分析

本文通過結合概率論進行推導，以確定X→Y的支持度和置信度大于X→Y支持度和置信度的判定條件，具體指標概率計算如表1所示。

通過上述推導，本文對經典Apriori算法的改進是通過增強非關聯的概率驗證對候選事務集進行壓縮，上述推導的C（Y→X）>[12]則變成一個固定閾值，具有方法應用的不變性。

實際使用中，首先對滿足概率參數的候選項集進行標簽計數，例如對于關聯規則X→Y，若C（X→Y）>[12與]C（Y→X）>[12] 成立，則分別將X和Y計數為1，而在算法迭代結束后，為避免重復，所有項都需要減1，最后再刪除標簽個數為0的項，即該項不滿足固定概率參數[12]的條件，通過標簽計數刪減候選項，一方面可以減少不必要的算法檢驗時間，另一方面也可避免產生無效候選集。

2.3 算法過程

為了增強負相關性，對Apriori算法進行刪減，具體實施步驟如下：

（1）首先，讀取數據庫中所有數據集，確定每一項的支持度，利用設定的最小支持度進行過濾，得到一項頻繁集L1。

（2）由于所有非空頻繁項集的子集必須是頻繁的，因此可以用一項頻繁集L1產生兩項候選集C2，通過C2計算每條規則的支持度。根據之前的概率理論，刪除支持度C（Y→X）≤[1/2]的候選項，并且對支持度超過1/2的項添加標簽1，統計所有項的標簽數，在算法迭代結束后，所有項都需要減1，刪除標有0的項，從而形成了兩項頻繁集L2′ 。

（3）由L2′ 生成三項候選集C3，再用改進后的算法進行迭代操作，得到三項頻繁集L3′。當所有項的標簽個數為0時，算法結束。

3 算例實驗

為驗證改進算法的有效性，結合具體數據實例對算法有效性進行分析，如表2所示。表中包含T1～T9共9個事務，每個事務由B1、B2、B3、B4、B5中的若干個項組成，并設最小支持度為[29]。

兩項候選集是在算法第二次迭代過程中，由一項頻繁集L1′ 產生的[20]。表4顯示了兩項候選集的支持度，并且計算每個關聯規則C（X→Y）和C（Y→X）的置信度（兩項候選集中，前者對應為X，后者對應為Y），刪除置信度C（Y[→X]）≤[12]的候選項，而對于超過[12]的候選項通過貼上標簽1，得到兩項候選集。最后統計B1～B5的標簽數，分別為2、2、2、1、2，再減1，刪去為0的項（B4），得到兩項頻繁集如表5所示。

在算法的第三次迭代中，由兩項頻繁集L2′ 產生三項候選集L3[20]。由于改進算法的概率參數限制，只產生{B1 B2 B3}和{B1 B2 B5}2個候選項集，而經典Apriori算法則會產生4個。另外由于在此次迭代結束后，B1、B2、B3、B5的標簽次數減1的結果均為0，因此該算法結束，從而避免了對{B1 B2 B3 B5}的掃描，而{B1 B2 B3}和{B1 B2 B5}兩項候選集滿足最小支持度，所以最大頻繁項集為{B1 B2 B3}和{B1 B2 B5}。

在Matlab實驗環境下對上述實例進行驗證，由于改進算法的概率參數與標簽計數為固定的，在產生三項頻繁集過程中，需要處理的候選項集數目相對經典算法減少了一半，同時通過標簽計數又避免了一些項再次迭代，使改進算法與初始算法相比，較為明顯地降低了計算復雜度。圖1對比了兩種算法不同迭代次數下的計算復雜度。

4 結語

本文針對傳統Apriori算法的問題進行分析，通過概率推導提出一種基于固定概率參數的Apriori改進算法。該算法可以過濾掉關聯程度較弱的候選項集，并篩選出負相關關聯的候選項，從而減少了算法運算所需時間。可以預測，隨著約束條件的增加，產生的無效候選項集會減少，算法效率也將得到提升。同時算例實驗結果表明，改進算法在保證關聯規則正相關的前提下，能有效降低候選項集個數，從而有利于減少掃描次數，既避免產生無效的關聯規則，又提升了算法結果的有效性。

參考文獻：

[1] 周英，卓金武，卞月青. 大數據挖掘系統方法與實例分析[M]. 北京：機械工業出版社，2016.

[2] 章艷，劉美玲，張師超，等. Apriori算法的三種優化方法[J]. 計算機工程與應用，2004（36）：190-192.

[3] ALMAOLEGI M， ARKOK B. An improved Apriori algorithm for association rules[J]. ?Eprint Arxiv， 2014，3：21-28.

[4] 劉維曉，陳俊麗，屈世富，等. 一種改進的Apriori 算法[J]. 計算機工程與應用，2011（11）：149-151，159.

[5] CHENG X，SU S，XU S，et al. DP-Apriori： a differentially private frequent itemset mining algorithm based on transaction splitting[J]. Computers & Security， 2015（8）：74-90.

[6] 饒正嬋，范年柏. 關聯規則挖掘Apriori算法研究綜述[J]. 計算機時代，2012，30（9）：11-13.

[7] PRAKASH S， PARVATHI R M S. An enhanced scaling Apriori for association rule mining efficiency[J]. European Journal of Scientific Research， 2010（2）：66-68.

[8] ZENG X W. The study of the association rules and data mining methods[J]. Computer and Modernization，2006（6）：90-93.

[9] 廖芹，郝志峰，陳志宏. 數據挖掘與數學建模[M]. 北京：國防工業出版社，2016.

[10] 張慧霞. 常用數據挖掘算法的分析對比[J]. 河南科技，2014（19）：22-23.

[11] 朱嗣珍. 基于FP-tree的多層關聯規則挖掘算法的研究[D]. 西安：西安科技大學，2011.

[12] 范明，孟小峰. 數據挖掘：概念與技術[M]. 北京：機械工業出版社，2011.

[13] 王偉. 關聯規則中的Apriori算法的研究與改進[D]. 青島：中國海洋大學，2012.

[14] 劉敏嫻，馬強，寧以風. 基于頻繁矩陣的Apriori算法改進[J]. 計算機工程與設計，2012，33（11）：35-39.

[15] 戴珂，王占俊，張仁平. 關聯規則挖掘算法的改進和實現[J]. 后勤工程學院學報，2008（2）：78-81.

[16] 姚全珠，李如瓊，王美君. 項約束先過濾的最大頻繁項集挖掘算法[J]. 計算機工程，2012，38（4）：73-75.

[17] ZENG X W. The study of the association rules and data mining methods[J]. Computer and Modernization，2006，9：90-93.

[18] CHEN Y S，DENG X G，JIANG X Y. Apriori algorithm for frequent itemsets mining in the realization[J]. Computer Technology and Development，2006，16（3）：58-60.

[19] CHEN A，CHEN N. Data mining technology and application[M]. Beijing： Science Press，2006.

[20] 王振武，徐輝. 數據挖掘算法原理與實現[M]. 北京：清華大學出版社，2014.

（責任編輯：黃 健）