劉彬+程曉榮

摘要：Apriori算法是關聯(lián)模型中的經(jīng)典算法，但是當數(shù)據(jù)庫很大時Apriori算法的復雜度將會指數(shù)上升，因此該文對Apriori算法掃描數(shù)據(jù)庫的方式進行了改進，改進后的算法有效地降低了算法的復雜度。并將Apriori算法粗淺的應用于在電子商務中的推薦環(huán)節(jié)。

關鍵詞：Apriori算法；關聯(lián)規(guī)則；算法改良；電商平臺

中圖分類號： TP393 文獻標識碼： A 文章編號：1009-3044（2017）27-0274-02

隨著我國經(jīng)濟的迅速發(fā)展，互聯(lián)網(wǎng)得到了極大的普及。電子商務作為一種新的銷售方式，迅速地占據(jù)了我國零售業(yè)很大的比重。電子商務開辟了新的市場，新的購物方式。近年來我國的電子商務交易量迅速增長，其運營模式的創(chuàng)新日益增加，電子商務呈現(xiàn)出多層次、多元化的發(fā)展趨勢[1]。其中淘寶、京東、唯品會等平臺占領了90%的市場份額。而且隨著互聯(lián)網(wǎng)的發(fā)展，怎樣讓用戶消費行為更加簡潔，怎樣吸引更多的用戶成為了各大電商平臺關注的焦點。

Apriori算法是一種基于關聯(lián)規(guī)則的算法，根據(jù)關聯(lián)規(guī)則可以推薦給用戶想要的商品，從而節(jié)省了用戶的購物時間，使用戶購物更為方便快捷，從而可以吸引更多的用戶，然而傳統(tǒng)的Apriori算法在處理海量的數(shù)據(jù)時，復雜度較高，必須對Apriori算法進行改良使之能夠適用于現(xiàn)在大數(shù)據(jù)的時代，本文對Apriori算法進行了簡單的介紹，并提出了一種改良的方法。并簡單的驗證了改良后的算法。

1 Apriori算法

1.1 Apriori算法簡介

Apriori算法是關聯(lián)規(guī)則模型中的經(jīng)典算法，它是R.Agrawal等人于1994年在AIS算法基礎上提出的改進算法，是數(shù)據(jù)挖掘問題中的一個重要研究內(nèi)容。Apriori算法在發(fā)現(xiàn)關聯(lián)規(guī)則問題方面有非常的大的影響力[2]。

Apriori算法是一種挖掘關聯(lián)規(guī)則的頻繁項集的寬度優(yōu)先的算法，這個算法的核心思想是通過掃描數(shù)據(jù)庫，生成候選集和逐級的監(jiān)測來發(fā)現(xiàn)數(shù)據(jù)庫的頻繁項集。通過對數(shù)據(jù)庫的多次掃描來發(fā)現(xiàn)所有的頻繁項目集，在每一次掃描中只考慮具有同一長度的所有候選集[3]。

1.2 基本概念

對于事件A和B：

①支持度：P（A∩B），A事件和B事件同時發(fā)生的概率。

②置信度：P（B|A），在事件A已經(jīng)發(fā)生的條件下事件B發(fā)生的概率。也可以記為P（AB）/P（A）。

例如購物車記錄分析：泳衣和泳鏡。

支持度1%：只有1%的用戶同時購買了泳衣和泳鏡。

置信度60%：購買了泳衣的用戶有60%也同時購買了泳鏡。

1.3 算法的實現(xiàn)

Apriori算法是一種最有影響的挖掘布爾關聯(lián)規(guī)則頻繁項集的算法Apriori使用一種稱作逐層搜索的迭代方法，“K-1項集”用于搜索“K項集”[4]

首先，需要找到數(shù)據(jù)庫的頻繁“1項集”的集合，這個集合記為L1。L1用來尋找頻繁“2項集”的集合L2，而L2則用來尋找L3。依次類推循環(huán)下去，直到不能找到“K項集”。在這個過程中，每尋找到一個LK，都需要完整的掃描一次數(shù)據(jù)庫。

核心步驟：連接步和剪枝步。連接步是自連接（LK和Lk連接），連接的規(guī)則是保證每一項的前k-2項是相同的。依次按字典序連接。剪枝步，是使任一頻繁項集的所有非空子集也必須是頻繁的。反之，如果某個候選的非空子集不是頻繁的，那么該候選集肯定不是頻繁的，從而可以將其從Ck中刪除，產(chǎn)生Lk。[5]

簡單地講，發(fā)現(xiàn)頻繁項集過程可以歸結為：①掃描；②計數(shù)；③比較；④產(chǎn)生頻繁項集；⑤連接、剪枝，產(chǎn)生候選項集。

重復步驟①-⑤直到不能發(fā)現(xiàn)更大的頻集。

例如有如下數(shù)據(jù)庫：

經(jīng)過三次掃描三次比較找到數(shù)據(jù)庫的3項集，Apriori算法求解得出ABE三項關聯(lián)度最高。

但是Apriori算法的缺點也顯而易見：每找出一個頻繁項集Lk，需要完整地掃描一次數(shù)據(jù)庫；而且這樣產(chǎn)生的候選項集也非常龐大。當數(shù)據(jù)庫結構較為簡單時，Apriori算法可以較好的工作，但是當數(shù)據(jù)庫較為龐大時，Apriori算法復雜度就會很高。例如長度為500的頻繁集{X1，X2，X3，……，X500}，將會 產(chǎn)生10000個候選項集[6]。因此我們必須對Apriori算法進行改進。

2 April算法的改進

Apriori算法在現(xiàn)如今大數(shù)據(jù)時代存在的缺陷極為明顯，大數(shù)據(jù)時代，數(shù)據(jù)以PB為起步，在這么大的數(shù)據(jù)庫中運用Apriori算法來尋求關聯(lián)度，其復雜度不可想象的。

根據(jù)Apriori算法的特性，改進主要可以由以下兩方面來進行：

① 自連接和剪枝步驟采用更優(yōu)的策略。

② 簡化數(shù)據(jù)庫本身來減少Apriori算法的復雜度。

本文主要討論從數(shù)據(jù)庫方面來進行優(yōu)化，Apriori算法每篩選一次候選集都需要對數(shù)據(jù)庫進行一次掃描，因此我們隊數(shù)據(jù)庫進行優(yōu)化，在每次計算Ck支持度的過程中，將CK中沒有的所有事物都標記出來，并且在以后的掃描中不考慮這些已經(jīng)被標記的事物，由此在實際計算候選集支持度所涉及的數(shù)據(jù)庫將小于真實數(shù)據(jù)庫，并且隨著k值的增大，這一差值也不斷增大，因此可以有效地降低掃描時間，減小候選集的計算速度，提升了整個算法的效率。

改進后的算法步驟：

① 選取最小的支持度，對初始數(shù)據(jù)庫進行掃描，計算出各個1項集的度，得到1-項集L1。

② 連接剪枝（與原算法相同）。

③ 將Ck中沒有的元素標記，刪除被標記的元素得到新的數(shù)據(jù)庫DK，再重掃掃描DK，計算Ck+1各元素的支持度。

④ 將Ck中不滿足最小支持度的項集刪掉，并形成Lk；②-④，直到不能產(chǎn)生新的頻繁項目集時終止。endprint

用實例數(shù)據(jù)來進行比較：

由圖2和圖3可以看出來，在篩選C3時，數(shù)據(jù)庫簡化變?yōu)镈1，商品由10項減少為9項，而在下一步中，數(shù)據(jù)庫D2減少為7項，因此節(jié)省了掃描數(shù)據(jù)庫的時間，而當數(shù)據(jù)庫越大，這種改進方法節(jié)省的時間將越多，因此這樣的改進是可行的，但是由于改進算法又增加了新的數(shù)據(jù)庫，生成新的數(shù)據(jù)庫也將會占用一定的時間，所以該算法的改進還有待進一步提升。

3 改進Apriori算法在電商中的應用

隨著時代的發(fā)展，電子商務在整體商務中占到的比重越來越大，面對紛繁復雜的商品，電商平臺如何推薦給用戶想要的商品，如何吸引更多的用戶，這都是店商平臺在考慮的問題。

Apriori根據(jù)關聯(lián)規(guī)則計算關聯(lián)度較高的方法，電商平臺可以根據(jù)用戶的消費行為，以及各種商品的關聯(lián)度，來推薦給用戶想要的商品，從而節(jié)省了用戶搜索商品的時間，給用戶更好的購物體驗，從而吸引更多的用戶。

4 結束語

Apriori算法是一種基于關聯(lián)規(guī)則的推薦算法，但是隨著時代的發(fā)展，大數(shù)據(jù)環(huán)境下數(shù)據(jù)庫越來越大，Apriori算法的缺陷也越來越明顯，本文對算法進行了改良，使其適用范圍更廣，可以應用到電商平臺，給以用戶推薦可能的商品，但是這樣的改進還有很多缺陷，下一步的工作將會對算法繼續(xù)進行改進，使之能夠在大數(shù)據(jù)時代有用武之地。

參考文獻：

[1] 聶林海. “互聯(lián)網(wǎng)+”時代的電子商務[J]. 中國流通經(jīng)濟，2015，29（06）：53-57. [2017-08-10]. DOI：10.14089/j.cnki.cn11-3664/f.2015.06.008

[2] 羅可，黃園芳，郭鋒. 用Visual Foxpro實現(xiàn)Apriori算法的研究[J]. 長沙電力學院學報：自然科學版，2001，（4）：16-19. [2017-08-10].

[3] 羅可，賀才望. 基于Apriori算法改進的關聯(lián)規(guī)則提取算法[J]. 計算機與數(shù)字工程，2006，（04）：48-51+55. [2017-08-10].

[4] 郅芬香，王留芳. 基于關聯(lián)規(guī)則的Apriori算法改進研究[J]. 信息與電腦：理論版，2014，（09）：169-170. [2017-08-10].

[5] 佘為，謝會娟. 改進的Apriori算法在高校選修課系統(tǒng)和應對氣候變化相關統(tǒng)計工作中的應用[J]. 信息與電腦：理論版，2015，（11）：179-181. [2017-08-10].

[6] 麥丞程. 基于Apriori算法的關聯(lián)規(guī)則挖掘系統(tǒng)設計與實現(xiàn)[J]. 電腦編程技巧與維護，2015，（11）：33-35. [2017-08-10]. DOI：10.16184/j.cnki.comprg.2015.11.014endprint