基于概率參數(shù)的Apriori改進(jìn)算法

孫帥 劉子龍

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

關(guān)鍵詞：關(guān)聯(lián)規(guī)則;Apriori改進(jìn)算法;概率參數(shù)

DOI：10. 11907/rjdk. 191099 開(kāi)放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP312文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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算法簡(jiǎn)介

關(guān)聯(lián)規(guī)則首先是由 Agrawal等提出的，該算法用來(lái)在龐大的初始數(shù)據(jù)庫(kù)中發(fā)現(xiàn)有趣的隱藏關(guān)聯(lián)[1]。其經(jīng)典應(yīng)用是通過(guò)對(duì)“啤酒”和“尿布”兩種商品的關(guān)聯(lián)分析[2]，使超市獲得了可觀的經(jīng)濟(jì)收益。

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

然而，經(jīng)典Apriori算法存在著掃描數(shù)據(jù)庫(kù)頻繁、產(chǎn)生候選項(xiàng)集多、耗時(shí)較長(zhǎng)等不足[10]，針對(duì)以上不足，國(guó)內(nèi)外學(xué)者提出了一些算法改進(jìn)方案，例如：約束性關(guān)聯(lián)規(guī)則算法[11]、增量式關(guān)聯(lián)規(guī)則算法[12]、多層關(guān)聯(lián)規(guī)則算法[13]、關(guān)聯(lián)規(guī)則ECLAT算法[14]等。為過(guò)濾掉經(jīng)典Apriori算法中無(wú)效與關(guān)聯(lián)程度較弱的候選項(xiàng)集，提升算法效率，本文嘗試引入相關(guān)概率計(jì)算與參數(shù)約束，通過(guò)對(duì)候選項(xiàng)集進(jìn)行壓縮實(shí)現(xiàn)對(duì)Apriori算法的改進(jìn)。數(shù)值算例實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法相比經(jīng)典Apriori算法大幅減少了候選項(xiàng)集，從而降低了算法復(fù)雜度。

2 基于概率事務(wù)壓縮的改進(jìn)Apriori算法

2.1 經(jīng)典Apriori算法理論分析

經(jīng)典Apriori算法會(huì)設(shè)定某些參數(shù)作為初始閾值，例如最小支持度與最小置信度[15]，其中最小支持度定義為：衡量支持度的一個(gè)閾值，表示項(xiàng)目集統(tǒng)計(jì)意義上的最低重要性[16]。最小置信度定義為：衡量某個(gè)項(xiàng)集最低的置信程度[17]，再將樣本數(shù)據(jù)帶入標(biāo)準(zhǔn)算法迭代，從而產(chǎn)生一些因果關(guān)聯(lián)。然而，在某些情況下，僅通過(guò)最小支持度與最小置信度還不足以給出最終結(jié)果。通過(guò)以下例子說(shuō)明該問(wèn)題：用Support表示相應(yīng)規(guī)則的支持度，Confidence表示置信度，假設(shè)購(gòu)買一批商品，其中耳機(jī)（X）共有6 000件（包括耳機(jī)單件與電腦禮包中的耳機(jī)），電腦（Y）共有9 000臺(tái)（包括電腦單件與電腦禮包中的電腦），電腦禮包4 000件，將最小支持度設(shè)定為30%，最小置信度設(shè)定為60%，通過(guò)計(jì)算可得出如下關(guān)聯(lián)規(guī)則：

通過(guò)上述計(jì)算可知關(guān)聯(lián)規(guī)則（X→Y）的支持度和置信度都大于設(shè)定的最小支持度與最小置信度，因此可認(rèn)為關(guān)聯(lián)規(guī)則成立，即在購(gòu)買耳機(jī)的同時(shí)也會(huì)購(gòu)買電腦。

通過(guò)計(jì)算，X→Y關(guān)聯(lián)也滿足事先設(shè)定的最小支持度與最小置信度的閾值，所以其兩者之間也能構(gòu)成關(guān)聯(lián)規(guī)則，這兩種截然相反的關(guān)聯(lián)形成了悖論，可見(jiàn)僅滿足最小支持度和最小置信度計(jì)算閾值，即認(rèn)為關(guān)聯(lián)規(guī)則成立是存在問(wèn)題的。

通過(guò)上述實(shí)例，可發(fā)現(xiàn)僅通過(guò)設(shè)定最小支持度與最小置信度閾值，在某些特殊情況下會(huì)存在局限，主要由于經(jīng)典Apriori算法并沒(méi)有充分考慮反面事件的支持度與置信度。在實(shí)際使用中，相關(guān)事務(wù)的關(guān)聯(lián)需要證明僅是正相關(guān)的，不存在負(fù)相關(guān)的可能，因此算法不但需要驗(yàn)證正相關(guān)的關(guān)聯(lián)規(guī)則X→Y滿足最小支持度與最小置信度的設(shè)定條件，同時(shí)其支持度與置信度也必須大于X→Y。只有同時(shí)滿足正反兩方面的設(shè)定條件，才能認(rèn)為所獲得關(guān)聯(lián)規(guī)則是自洽的。

2.2 關(guān)聯(lián)條件概率分析

本文通過(guò)結(jié)合概率論進(jìn)行推導(dǎo)，以確定X→Y的支持度和置信度大于X→Y支持度和置信度的判定條件，具體指標(biāo)概率計(jì)算如表1所示。

通過(guò)上述推導(dǎo)，本文對(duì)經(jīng)典Apriori算法的改進(jìn)是通過(guò)增強(qiáng)非關(guān)聯(lián)的概率驗(yàn)證對(duì)候選事務(wù)集進(jìn)行壓縮，上述推導(dǎo)的C（Y→X）>[12]則變成一個(gè)固定閾值，具有方法應(yīng)用的不變性。

實(shí)際使用中，首先對(duì)滿足概率參數(shù)的候選項(xiàng)集進(jìn)行標(biāo)簽計(jì)數(shù)，例如對(duì)于關(guān)聯(lián)規(guī)則X→Y，若C（X→Y）>[12與]C（Y→X）>[12] 成立，則分別將X和Y計(jì)數(shù)為1，而在算法迭代結(jié)束后，為避免重復(fù)，所有項(xiàng)都需要減1，最后再刪除標(biāo)簽個(gè)數(shù)為0的項(xiàng)，即該項(xiàng)不滿足固定概率參數(shù)[12]的條件，通過(guò)標(biāo)簽計(jì)數(shù)刪減候選項(xiàng)，一方面可以減少不必要的算法檢驗(yàn)時(shí)間，另一方面也可避免產(chǎn)生無(wú)效候選集。

2.3 算法過(guò)程

為了增強(qiáng)負(fù)相關(guān)性，對(duì)Apriori算法進(jìn)行刪減，具體實(shí)施步驟如下：

（1）首先，讀取數(shù)據(jù)庫(kù)中所有數(shù)據(jù)集，確定每一項(xiàng)的支持度，利用設(shè)定的最小支持度進(jìn)行過(guò)濾，得到一項(xiàng)頻繁集L1。

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

（3）由L2′ 生成三項(xiàng)候選集C3，再用改進(jìn)后的算法進(jìn)行迭代操作，得到三項(xiàng)頻繁集L3′。當(dāng)所有項(xiàng)的標(biāo)簽個(gè)數(shù)為0時(shí)，算法結(jié)束。

3 算例實(shí)驗(yàn)

為驗(yàn)證改進(jìn)算法的有效性，結(jié)合具體數(shù)據(jù)實(shí)例對(duì)算法有效性進(jìn)行分析，如表2所示。表中包含T1～T9共9個(gè)事務(wù)，每個(gè)事務(wù)由B1、B2、B3、B4、B5中的若干個(gè)項(xiàng)組成，并設(shè)最小支持度為[29]。

兩項(xiàng)候選集是在算法第二次迭代過(guò)程中，由一項(xiàng)頻繁集L1′ 產(chǎn)生的[20]。表4顯示了兩項(xiàng)候選集的支持度，并且計(jì)算每個(gè)關(guān)聯(lián)規(guī)則C（X→Y）和C（Y→X）的置信度（兩項(xiàng)候選集中，前者對(duì)應(yīng)為X，后者對(duì)應(yīng)為Y），刪除置信度C（Y[→X]）≤[12]的候選項(xiàng)，而對(duì)于超過(guò)[12]的候選項(xiàng)通過(guò)貼上標(biāo)簽1，得到兩項(xiàng)候選集。最后統(tǒng)計(jì)B1～B5的標(biāo)簽數(shù)，分別為2、2、2、1、2，再減1，刪去為0的項(xiàng)（B4），得到兩項(xiàng)頻繁集如表5所示。

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

在Matlab實(shí)驗(yàn)環(huán)境下對(duì)上述實(shí)例進(jìn)行驗(yàn)證，由于改進(jìn)算法的概率參數(shù)與標(biāo)簽計(jì)數(shù)為固定的，在產(chǎn)生三項(xiàng)頻繁集過(guò)程中，需要處理的候選項(xiàng)集數(shù)目相對(duì)經(jīng)典算法減少了一半，同時(shí)通過(guò)標(biāo)簽計(jì)數(shù)又避免了一些項(xiàng)再次迭代，使改進(jìn)算法與初始算法相比，較為明顯地降低了計(jì)算復(fù)雜度。圖1對(duì)比了兩種算法不同迭代次數(shù)下的計(jì)算復(fù)雜度。

4 結(jié)語(yǔ)

本文針對(duì)傳統(tǒng)Apriori算法的問(wèn)題進(jìn)行分析，通過(guò)概率推導(dǎo)提出一種基于固定概率參數(shù)的Apriori改進(jìn)算法。該算法可以過(guò)濾掉關(guān)聯(lián)程度較弱的候選項(xiàng)集，并篩選出負(fù)相關(guān)關(guān)聯(lián)的候選項(xiàng)，從而減少了算法運(yùn)算所需時(shí)間?？梢灶A(yù)測(cè)，隨著約束條件的增加，產(chǎn)生的無(wú)效候選項(xiàng)集會(huì)減少，算法效率也將得到提升。同時(shí)算例實(shí)驗(yàn)結(jié)果表明，改進(jìn)算法在保證關(guān)聯(lián)規(guī)則正相關(guān)的前提下，能有效降低候選項(xiàng)集個(gè)數(shù)，從而有利于減少掃描次數(shù)，既避免產(chǎn)生無(wú)效的關(guān)聯(lián)規(guī)則，又提升了算法結(jié)果的有效性。

參考文獻(xiàn)：

[1] 周英，卓金武，卞月青. 大數(shù)據(jù)挖掘系統(tǒng)方法與實(shí)例分析[M]. 北京：機(jī)械工業(yè)出版社，2016.

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

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

[4] 劉維曉，陳俊麗，屈世富，等. 一種改進(jìn)的Apriori 算法[J]. 計(jì)算機(jī)工程與應(yīng)用，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] 饒正嬋，范年柏. 關(guān)聯(lián)規(guī)則挖掘Apriori算法研究綜述[J]. 計(jì)算機(jī)時(shí)代，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] 廖芹，郝志峰，陳志宏. 數(shù)據(jù)挖掘與數(shù)學(xué)建模[M]. 北京：國(guó)防工業(yè)出版社，2016.

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

[11] 朱嗣珍. 基于FP-tree的多層關(guān)聯(lián)規(guī)則挖掘算法的研究[D]. 西安：西安科技大學(xué)，2011.

[12] 范明，孟小峰. 數(shù)據(jù)挖掘：概念與技術(shù)[M]. 北京：機(jī)械工業(yè)出版社，2011.

[13] 王偉. 關(guān)聯(lián)規(guī)則中的Apriori算法的研究與改進(jìn)[D]. 青島：中國(guó)海洋大學(xué)，2012.

[14] 劉敏嫻，馬強(qiáng)，寧以風(fēng). 基于頻繁矩陣的Apriori算法改進(jìn)[J]. 計(jì)算機(jī)工程與設(shè)計(jì)，2012，33（11）：35-39.

[15] 戴珂，王占俊，張仁平. 關(guān)聯(lián)規(guī)則挖掘算法的改進(jìn)和實(shí)現(xiàn)[J]. 后勤工程學(xué)院學(xué)報(bào)，2008（2）：78-81.

[16] 姚全珠，李如瓊，王美君. 項(xiàng)約束先過(guò)濾的最大頻繁項(xiàng)集挖掘算法[J]. 計(jì)算機(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] 王振武，徐輝. 數(shù)據(jù)挖掘算法原理與實(shí)現(xiàn)[M]. 北京：清華大學(xué)出版社，2014.

（責(zé)任編輯：黃 ?。?/p>