Apriori算法的改進(jìn)及其在電子商務(wù)中的應(yīng)用

劉彬+程曉榮

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

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

中圖分類(lèi)號(hào)： TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)：1009-3044（2017）27-0274-02

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

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

1 Apriori算法

1.1 Apriori算法簡(jiǎn)介

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

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

1.2 基本概念

對(duì)于事件A和B：

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

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

例如購(gòu)物車(chē)記錄分析：泳衣和泳鏡。

支持度1%：只有1%的用戶同時(shí)購(gòu)買(mǎi)了泳衣和泳鏡。

置信度60%：購(gòu)買(mǎi)了泳衣的用戶有60%也同時(shí)購(gòu)買(mǎi)了泳鏡。

1.3 算法的實(shí)現(xiàn)

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

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

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

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

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

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

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

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

2 April算法的改進(jìn)

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

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

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

② 簡(jiǎn)化數(shù)據(jù)庫(kù)本身來(lái)減少Apriori算法的復(fù)雜度。

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

改進(jìn)后的算法步驟：

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

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

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

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

用實(shí)例數(shù)據(jù)來(lái)進(jìn)行比較：

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

3 改進(jìn)Apriori算法在電商中的應(yīng)用

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

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

4 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

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

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

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

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

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