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

袁曉建, 張岐山, 甘智平， 陳煥輝， 傅龍?zhí)?/p>

(1. 福州外語外貿(mào)學(xué)院信息系， 福建 福州 350202; 2. 福州大學(xué)經(jīng)濟(jì)與管理學(xué)院, 福建 福州 350116; 3. 福州外語外貿(mào)學(xué)院教學(xué)發(fā)展中心， 福建 福州 350202)

0 引言

隨著信息技術(shù)的發(fā)展和政府對電子商務(wù)領(lǐng)域的積極推動， 我國的電子商務(wù)正以前所未有的速度蓬勃發(fā)展， 并在經(jīng)濟(jì)發(fā)展中日漸凸顯出帶動作用. 但隨著用戶數(shù)量和產(chǎn)品數(shù)量的急劇增長， 以及用戶需求的個性化、 多樣化， 這對電子商務(wù)企業(yè)營銷提出了更高的要求. 如何在存儲的海量數(shù)據(jù)當(dāng)中發(fā)現(xiàn)知識、 使用知識， 并結(jié)合實際情況向顧客推薦商品或者打折促銷， 關(guān)聯(lián)規(guī)則挖掘在現(xiàn)代營銷中扮演著重要的角色.

關(guān)聯(lián)規(guī)則挖掘是在數(shù)據(jù)中查找存在于項目集合中的頻繁模式、 關(guān)聯(lián)、 相關(guān)性及因果結(jié)構(gòu). Apriori算法是關(guān)聯(lián)規(guī)則挖掘重要的方法, 它是Agrawal等[1]在1994年提出的.

1 關(guān)聯(lián)規(guī)則和Apriori算法[2]

1.1 關(guān)聯(lián)規(guī)則

關(guān)聯(lián)規(guī)則提出的目的是為了尋找事務(wù)數(shù)據(jù)庫中隱藏的不同項之間的聯(lián)系， 在海量的數(shù)據(jù)庫中找出頻繁發(fā)生的項或子集， 以及項目之間的相互關(guān)聯(lián)性. 其經(jīng)典的應(yīng)用就是大家熟知的“啤酒和尿布”案例. 它的原理可描述為：

設(shè)D是一個待挖掘分析的事務(wù)數(shù)據(jù)庫，D中所有項目的項集為I={i1，i2， …，im}， 由此可知D中的每個事務(wù)都是I的一個子集. 并定義k項集為包含k個項目的集合. 記s(X)為項集X的支持度(sup)， 其含義是事務(wù)數(shù)據(jù)庫D中包含該項集的交易數(shù)據(jù)的條數(shù). 設(shè)定最小支持度(minsup)， 如果一個項集的支持度大于此最小支持度， 則稱它是頻繁的； 如果此項集的長度為k， 則稱其為頻繁k項集.

由以上表述， 本研究定義以下關(guān)聯(lián)規(guī)則. 設(shè)項集A和項集B， 其中A?I,B?I， 并且A∩B=?， 規(guī)則A?B的支持度s(A?B)定義為事務(wù)數(shù)據(jù)庫D中包含A∪B的事務(wù)所占的百分比， 由此可知， 支持度是一個百分比數(shù)值.

同樣， 本研究定義置信度. 規(guī)則A?B的置信度c(conf)定義為事務(wù)數(shù)據(jù)庫D中包含項集A∪B的事務(wù)數(shù)與包含項集A的事務(wù)數(shù)的比值. 設(shè)定最小置信度(minconf)， 若由此計算出來的置信度大于設(shè)定的最小置信度， 那么認(rèn)為挖掘到的規(guī)則是可信的.

關(guān)聯(lián)規(guī)則挖掘的任務(wù)是在事務(wù)數(shù)據(jù)庫D中找到支持度和置信度分別大于用戶指定的最小支持度minsup和最小置信度minconf的規(guī)則A?B. 關(guān)聯(lián)規(guī)則挖掘主要解決以下兩個問題： 1)找出D中所有的符合要求的頻繁項集； 2)從符合要求的頻繁項集中挖掘關(guān)聯(lián)規(guī)則.

1.2 Apriori算法及存在的困難

Apriori算法是基于關(guān)聯(lián)規(guī)則常用的方法， 此算法實現(xiàn)挖掘過程分為兩步： 1)通過多次迭代， 采集事務(wù)數(shù)據(jù)庫中所有的頻繁項集， 即采集所有支持度不低于用戶設(shè)定的最小支持度的項集； 2)利用上一步采集的頻繁項集， 構(gòu)造出滿足用戶設(shè)定的最小置信度的規(guī)則.

Apriori算法的三大缺點為產(chǎn)生大量的候選集, 需要重復(fù)掃描數(shù)據(jù)庫， 最小閾值難于合理設(shè)定. 自該算法提出以來， 眾多學(xué)者就以上兩方面的問題做了大量的研究工作， Apriori類算法日趨成熟.

但是， 經(jīng)典Apriori算法或者基于效率改進(jìn)的算法仍然面臨一個巨大的困難. 首先， 考慮下面這個問題.

表1 某汽車用品電子商務(wù)事務(wù)數(shù)據(jù)庫

某經(jīng)營汽車用品的電商的事務(wù)數(shù)據(jù)庫如表1所示.

數(shù)據(jù)庫中有10個事務(wù)(即上文所說的10條交易記錄)， 則有|D|=10. 該數(shù)據(jù)庫包含5種商品. 其中，i1： 車載香水；i2： 汽車腳墊；i3： 行車記錄儀；i4： 除塵車撣；i5： 安全座椅. 若設(shè)定最小支持minsup=40%， 最小置信度 minconf=60%， 按傳統(tǒng)的Apriori算法， 挖掘到如下兩條規(guī)則：

i2?i4，i4?i2

以上的挖掘結(jié)果表明： 將汽車腳墊和除塵車撣捆綁銷售， 或者用戶購買其中一樣的時候推銷另外一樣， 將有利于促進(jìn)兩者的互銷， 為商家?guī)砀玫氖找? 不過， 對于負(fù)責(zé)銷售或者運營的電商管理者而言， 這樣的信息是在“情理之中”. 如果只是挖掘到這類“自然”的知識， 這樣的數(shù)據(jù)挖掘是不令人滿意， 是失敗的.

對電子商務(wù)企業(yè)或者賣家來說， 最大限度地增加營業(yè)額或者利潤， 是經(jīng)營過程中最重要的問題. 所以， 經(jīng)營者最感興趣的是盈利程度遠(yuǎn)高于其他商品的行車記錄儀(i3)的銷售數(shù)量. 經(jīng)營者想通過數(shù)據(jù)挖掘， 掌握到哪種商品的打折銷售最容易誘導(dǎo)顧客購買行車記錄儀(i3)， 以及買了行車記錄儀(i3)的顧客還會購買哪些商品. 其中， 第一個問題是經(jīng)營者或者營銷者最關(guān)心的問題. 可是， 傳統(tǒng)的Apriori算法卻挖掘不到任何有關(guān)行車記錄儀(i3)的信息.

由此， 本研究總結(jié)出經(jīng)典Apriori及基于效率改進(jìn)的挖掘方法主要存在以下兩方面問題：

1) 給事務(wù)數(shù)據(jù)庫中D各項目賦予了相同的權(quán)重. 但是， 在實際的經(jīng)營中， 電商需要根據(jù)季節(jié)、 營銷節(jié)日、 項目(即商品)的利潤、 銷量等方面有重點地對商品進(jìn)行推薦和推銷.

2) 最小閾值難以合理設(shè)定. 算法實現(xiàn)過程中， 需根據(jù)設(shè)定的最小閾值， 對不滿足閾值條件的候選頻繁項集進(jìn)行剪枝操作. 閾值設(shè)置太高， 容易遺漏重要的關(guān)聯(lián)規(guī)則； 設(shè)置太低， 又會發(fā)現(xiàn)太多沒有意義的甚至是虛假的關(guān)聯(lián)規(guī)則， 降低算法效率[3].

為解決以上問題， 學(xué)者們引入了加權(quán)關(guān)聯(lián)規(guī)則挖掘. 加權(quán)關(guān)聯(lián)規(guī)則既考慮了規(guī)則中所有項目出現(xiàn)的次數(shù)， 又考慮了不同項目的重要性.

2 加權(quán)關(guān)聯(lián)規(guī)則挖掘和W-Apriori算法簡述

2.1 加權(quán)關(guān)聯(lián)規(guī)則挖掘

加權(quán)關(guān)聯(lián)規(guī)則描述如下： 設(shè)I={i1,i2, …,im}為數(shù)據(jù)庫中的全部項集， 對應(yīng)I的權(quán)重集為W={w1,w2, …,wm}， 其中，wi表示項目ii的重要程度， 且0≤wi≤1. 此外X?I,Y?I， 并且X∩Y=F， 記sup(X)和conf(X)分別為X的支持度和置信度. 由于引入了項目權(quán)重， 還需要定義項目集X的加權(quán)支持度和加權(quán)置信度， 設(shè)定最小加權(quán)支持度閾值minwsup和最小置信度閾值minwconf.

目前加權(quán)關(guān)聯(lián)規(guī)則研究的學(xué)者較多， 簡單整理如下.

為了解決以上算法在電子商務(wù)數(shù)據(jù)挖掘和推薦的不足， 本研究同時考慮了屬性個數(shù)和屬性權(quán)值的影響， 提出了一種新的加權(quán)關(guān)聯(lián)規(guī)則支持度和置信度的計算方法， 并將此方法應(yīng)用到W-Apriori算法[8]中. W-Apriori承接了Apriori算法的思想， 分步實現(xiàn)： 首先找出滿足最小加權(quán)支持度約束的所有加權(quán)頻繁項集， 然后利用頻繁項集產(chǎn)生滿足最小加權(quán)置信度約束的所有規(guī)則.

2.2 相關(guān)定義

本研究綜合考慮商品的利潤和銷量， 以此來定義項集的推薦權(quán)值.

定義1利潤權(quán)重.

同樣條件下， 銷售同一類的商品， 推銷或者銷售利潤高的商品對商家盈利更有利. 對于某在銷商品i的利潤(Profit)權(quán)重定義如下：

其中: Profit(i)表示商品i的利潤，D表示事務(wù)數(shù)據(jù)庫中的所有商品.

定義2銷量權(quán)重.

同樣條件下， 熱銷產(chǎn)品或者銷售量大的產(chǎn)品， 說明其市場潛力大， 客戶接受程度高， 值得向客戶推薦. 銷量(Volume)權(quán)重定義如下：

其中: Volume(i) 表示商品i的銷量.

定義3推薦權(quán)值.

結(jié)合以上兩個定義， 得到某商品i的推薦(Recommendation)權(quán)值為：

定義4加權(quán)支持度和加權(quán)置信度.

設(shè)I={i1,i2, …,im}為數(shù)據(jù)庫中商品的集合， 對應(yīng)推薦權(quán)值向量記為W={w1,w2, …,wm}, (wi∈[0, 1])，m指某一事務(wù)項包含的商品數(shù). 則(X，w(X))表示加權(quán)項集， 其中X?I，w(X)指項集X的權(quán)值. 項集X的加權(quán)支持度記為wsup(X)= sup(X)·w(X)， 同時定義項集X的權(quán)值如下：

其中:X?I,Y?I. 若wsup(X∪Y)和wsup(X?Y)分別滿足minwsup和minwconf， 規(guī)則X?Y即為強(qiáng)關(guān)聯(lián)規(guī)則.

3 有效性分析

3.1 挖掘結(jié)果對比

考慮到加權(quán)值W(i)計算后數(shù)值較小， 在實際實現(xiàn)過程中， 需要乘以一個調(diào)節(jié)系數(shù)K， 該系數(shù)可根據(jù)商品的種類和銷售數(shù)量靈活設(shè)定.

目前Apriori算法的改進(jìn)多集中在算法運行效率的優(yōu)化上， 也積累了較多的測試數(shù)據(jù)集， 如IBM Almadel 中心提供的標(biāo)準(zhǔn)數(shù)據(jù)集T10I4D100K和T40I10D100K. 在考慮權(quán)重方面， 也有較多學(xué)者進(jìn)行算法優(yōu)化， 但是測試集大多來自作者自行采集， 沒有成熟的數(shù)據(jù)集可用， 尤其是本研究考慮了單品的利潤因素， 包括著名的比利時零售市場數(shù)據(jù)集也無法利用.

表2利用經(jīng)典Apriori算法挖掘的結(jié)果

Tab.2TheresultsusingclassicalApriorialgorithm(%)

鑒于以上情況， 本研究在國內(nèi)某超市一組銷售數(shù)據(jù)的基礎(chǔ)上， 構(gòu)造生成5 000條購物籃數(shù)據(jù)， 在C#.Net環(huán)境下， 與經(jīng)典Apriori算法進(jìn)行挖掘?qū)Ρ龋?表2是利用經(jīng)典的Apriori算法挖掘的結(jié)果， 表中支持度和置信度是系統(tǒng)計算得到的數(shù)值. 表3是利用上文所述改進(jìn)的算法， 分別設(shè)置不同的支持度、 置信度和調(diào)節(jié)系數(shù)后挖掘的結(jié)果， 表格的頂部注明了具體的參數(shù)數(shù)值.

表3 利用改進(jìn)的加權(quán)算法挖掘的結(jié)果

3.2 挖掘結(jié)果對比

此計算方法和算法， 克服了人為設(shè)置權(quán)值帶來的不足， 從利潤和銷量兩方面的實際情況進(jìn)行計算.

從上面的挖掘結(jié)果可以看出， 改進(jìn)后的算法不僅在考慮利潤方面有了明顯的優(yōu)勢， 而且考慮銷量后， 還挖掘出另外一個“有趣”的購買習(xí)慣： 該數(shù)據(jù)樣本來自我國西部某地的超市. 汾酒和苦蕎面， 是“晉汾三絕”中的其中兩樣商品, 改變挖掘系數(shù)后， 也可從結(jié)果中看到苦蕎面和陳醋的購買組合.

該改進(jìn)算法也有不足之處. 比如在電子商務(wù)企業(yè)創(chuàng)建之初， 可能會出現(xiàn)因為銷量權(quán)重過低， 產(chǎn)生挖掘到的都是推薦貴重(相對利潤比較高)商品的情況， 這需要根據(jù)實際情況進(jìn)行人為的干預(yù).

另外， 可以根據(jù)不同季節(jié)的節(jié)假日促銷， 設(shè)置其它的權(quán)重， 限于篇幅在此不再闡述.

4 結(jié)論

隨著網(wǎng)購的迅猛發(fā)展， 精準(zhǔn)營銷和數(shù)據(jù)挖掘技術(shù)的運用越來越重要. 怎樣有效地留住網(wǎng)上的用戶， 從客戶的消費數(shù)據(jù)中挖掘關(guān)聯(lián)消費商品， 同時又能有效地增強(qiáng)電子商務(wù)企業(yè)的盈利能力， 將是未來電商企業(yè)競爭的主要問題[9].

本研究依據(jù)電子商務(wù)企業(yè)的實際運營情況， 在考慮商品利潤和銷量的基礎(chǔ)上， 提出基于Apriori算法的加權(quán)關(guān)聯(lián)規(guī)則模型， 為電子商務(wù)企業(yè)的經(jīng)營決策打下堅實的理論基礎(chǔ).

參考文獻(xiàn)：

[1] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules in large databases[C]// International Conference on Very Large Data Bases. San Francisco： Morgan Kaufmann Publishers Inc， 1994: 487-499.

[2] 韓家煒. 數(shù)據(jù)挖掘概念與技術(shù)[M]. 北京： 機(jī)械工業(yè)出版社， 2012： 160.

[3] 余紹黔. Apriori算法改進(jìn)及在超市數(shù)據(jù)挖掘中應(yīng)用[J]. 微計算機(jī)信息, 2011(11): 165-167.

[4] CAI C H, FU A W C, CHENG C H,etal. Mining association rules with weighted items[C]// Proceedings of the 1998 International Symposium on Database Engineering and Applications. Washington D C： IEEE Computer Society, 1998: 68.

[5] 張文獻(xiàn), 陸建江. 加權(quán)布爾型關(guān)聯(lián)規(guī)則的研究[J]. 計算機(jī)工程， 2003， 29(9): 55-57.

[6] 張智軍, 方穎, 許云濤. 基算法的水平加權(quán)關(guān)聯(lián)規(guī)則挖掘[J]. 計算機(jī)工程與應(yīng)用, 2003, 39(14): 197-199.

[7] SANDHU P S, DHALIWAL D S, PANDA S N,etal. An improvement in Apriori algorithm using profit and quantity[C]// International Conference on Computer and Network Technology. Washington D C： IEEE Computer Society, 2010: 3-7.

[8] 李中良. 基于Web日志挖掘和關(guān)聯(lián)規(guī)則的個性化推薦系統(tǒng)模型研究[D]. 重慶： 西南大學(xué), 2014.

[9] 賈桂霞， 趙錫英， 劉熠琦. 電子商務(wù)中關(guān)聯(lián)推薦算法的應(yīng)用研究[J]. 工業(yè)儀表與自動化裝置， 2016(1)： 43-45.