基于改進(jìn)Apriori算法的商品智能推薦

張中秋

（南京鐵道職業(yè)技術(shù)學(xué)院 智能工程學(xué)院，南京 210000）

近年來(lái)，隨著互聯(lián)網(wǎng)特別是移動(dòng)互聯(lián)網(wǎng)的飛速發(fā)展，電商、實(shí)體店及O2O等商業(yè)模式覆蓋了人們衣食住行的方方面面，消費(fèi)者面對(duì)線上線下品類繁多的商品，往往選擇困難，也增加了購(gòu)物時(shí)間。同時(shí)各種面向C端互聯(lián)網(wǎng)平臺(tái)、會(huì)員系統(tǒng)、零售業(yè)信息系統(tǒng)的發(fā)展，使人們?cè)谌粘Ｉ钪挟a(chǎn)生了越來(lái)越多的消費(fèi)行為數(shù)據(jù)信息，如此大量的數(shù)據(jù)信息滿足了用戶在大數(shù)據(jù)時(shí)代對(duì)數(shù)據(jù)分析的需求。數(shù)據(jù)是互聯(lián)網(wǎng)時(shí)代最重要的資產(chǎn)，如何從大量的用戶歷史數(shù)據(jù)中發(fā)掘出有用信息，挖掘其特征，從而用于對(duì)消費(fèi)者進(jìn)行商品的智能推薦，是重要的研究課題，也是幫助用戶發(fā)現(xiàn)內(nèi)容、克服信息過(guò)載的現(xiàn)實(shí)需求。智能推薦一方面可以提升商品銷量，一方面可以提升消費(fèi)者購(gòu)物體驗(yàn)?；诨ヂ?lián)網(wǎng)的智能推薦系統(tǒng)在人們的生活中占了越來(lái)越大的比重[1-4]。

智能推薦的核心是算法。本文使用基于關(guān)聯(lián)規(guī)則的推薦算法來(lái)對(duì)商品銷售進(jìn)行推薦，關(guān)聯(lián)規(guī)則指從大量用戶行為數(shù)據(jù)中發(fā)現(xiàn)強(qiáng)關(guān)聯(lián)規(guī)則，是一種無(wú)監(jiān)督的推薦算法，適合事務(wù)數(shù)據(jù)庫(kù)的關(guān)聯(lián)規(guī)則挖掘。本文詳細(xì)闡述了Apriori算法的原理，以實(shí)例闡述了算法的實(shí)現(xiàn)過(guò)程并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析[5-8]。

1 關(guān)聯(lián)規(guī)則挖掘算法

關(guān)聯(lián)規(guī)則挖掘是大數(shù)據(jù)分析的重要手段，常見的關(guān)聯(lián)規(guī)則算法有Apriori算法和FP-Growth算法[9-10]。通過(guò)關(guān)聯(lián)規(guī)則可以挖掘出事務(wù)集中各項(xiàng)商品之間的關(guān)聯(lián)關(guān)系?；陉P(guān)聯(lián)規(guī)則的推薦算法就是根據(jù)大量的用戶行為數(shù)據(jù)挖掘出關(guān)聯(lián)規(guī)則，并通過(guò)特定的指標(biāo)參數(shù)對(duì)結(jié)果項(xiàng)進(jìn)行排序，生成結(jié)果推薦給用戶。關(guān)聯(lián)性越強(qiáng)，則推薦的結(jié)果越可能受到用戶喜歡。

實(shí)際應(yīng)用系統(tǒng)中，關(guān)聯(lián)規(guī)則挖掘的最大困難在于，由于系統(tǒng)的數(shù)據(jù)集比較大，即使開始的數(shù)據(jù)集小，隨著時(shí)間的推移，系統(tǒng)會(huì)積累越來(lái)越多的數(shù)據(jù)，每次關(guān)聯(lián)規(guī)則的計(jì)算的時(shí)候多次掃描數(shù)據(jù)，造成算法性能下降。如果存在很多商品的時(shí)候，可能的商品組合數(shù)目也會(huì)非常多，實(shí)際應(yīng)用中要根據(jù)業(yè)務(wù)特診對(duì)算法進(jìn)行優(yōu)化。本課題使用Apriori算法進(jìn)行日常商品的智能推薦。

1.1 項(xiàng)集與事務(wù)集

項(xiàng)集是數(shù)據(jù)項(xiàng)的集合，設(shè)集合I={i1，i2，…，ik}中有k個(gè)項(xiàng)，表示k項(xiàng)集。如集合{牛奶，面包，糖}是一個(gè)3項(xiàng)集。對(duì)于餐飲推薦問(wèn)題來(lái)說(shuō)，項(xiàng)集為該餐飲店的所有菜品的集合。事務(wù)集表示事務(wù)數(shù)據(jù)的集合，設(shè)集合T={t1，t2，…，tk}，即該餐飲店用戶訂單的數(shù)據(jù)集合，是用戶行為數(shù)據(jù)，一次點(diǎn)單ti是一個(gè)事務(wù)。顯然，ti?I。

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

關(guān)聯(lián)規(guī)則反映了一個(gè)事物與其他事物之間的相互依存性和關(guān)聯(lián)性。關(guān)聯(lián)規(guī)則如下定義：現(xiàn)有項(xiàng)集I，A?I，B?I，A≠?、B≠?且A∩B=?，則A?B表示關(guān)聯(lián)規(guī)則，A和B為項(xiàng)集I的非空子集，分別稱為關(guān)聯(lián)規(guī)則的前項(xiàng)和后項(xiàng)，符號(hào)?稱為關(guān)聯(lián)。

1.3 支持度與置信度

支持度（Support）和置信度（Confidence）是用來(lái)衡量關(guān)聯(lián)規(guī)則的強(qiáng)度的2個(gè)重要指標(biāo)。

現(xiàn)有關(guān)聯(lián)規(guī)則A?B，支持度定義為：項(xiàng)集A和項(xiàng)集B同時(shí)發(fā)生的概率，表示規(guī)則在給定項(xiàng)集I中的頻繁程度。如式（1）所示

置信度定義為：項(xiàng)集A發(fā)生，則項(xiàng)集B發(fā)生的概率，即條件概率。表示包含項(xiàng)集A的事務(wù)中項(xiàng)集B出現(xiàn)的頻繁程度。如式（2）所示

令N為事務(wù)集中總事務(wù)個(gè)數(shù)，σ表示計(jì)數(shù)，則根據(jù)式（1），可求得支持度與置信度如式（3）和式（4）所示

一個(gè)關(guān)聯(lián)規(guī)則稱為強(qiáng)規(guī)則，需同時(shí)滿足最小支持度閾值和最小置信度閾值。最小支持度閾值表示關(guān)聯(lián)規(guī)則在統(tǒng)計(jì)意義上的最低重要性，最小置信度表示關(guān)聯(lián)規(guī)則的最低可靠性。如果一個(gè)項(xiàng)集的支持度滿足預(yù)設(shè)的最小支持度閾值，稱為是頻繁項(xiàng)集，頻繁k項(xiàng)集記作Lk。

2 Apriori算法實(shí)現(xiàn)過(guò)程

Apriori算法的主要思想是找出事務(wù)數(shù)據(jù)集中的最大頻繁項(xiàng)集，設(shè)定關(guān)聯(lián)規(guī)則的最小置信度閾值，然后根據(jù)最大頻繁項(xiàng)集與預(yù)先設(shè)定的最小置信度閾值生成強(qiáng)關(guān)聯(lián)規(guī)則。算法實(shí)現(xiàn)步驟如下

1）連接步，目的是找到最大頻繁項(xiàng)集。第1步：首先找頻繁1項(xiàng)集，對(duì)于給定的最小支持度閾值，在事務(wù)集中1項(xiàng)候選集C1，分別計(jì)算支持度，從中刪除支持度小于最小支持度閾值的項(xiàng)集，得到頻繁1項(xiàng)集L1。第2步：由L1和自身連接產(chǎn)生2項(xiàng)候選集C2，去除支持度小于最小支持度閾值的項(xiàng)集，得到頻繁2項(xiàng)集L2。第3步：由L2和L1連接產(chǎn)生3項(xiàng)候選集C3，保留C3中滿足約束條件的項(xiàng)集得到頻繁3項(xiàng)集L3。

以此類推，由Lk-1與L1連接產(chǎn)生候選集Ck，去除不滿足約束條件的，最終得到最大頻繁項(xiàng)集Lk。

2）減枝步，目的是縮小Ck搜索空間。根據(jù)頻繁項(xiàng)集的性質(zhì)，任一頻繁項(xiàng)集的非空子集一定也是頻繁項(xiàng)集，在連接產(chǎn)生候選集Ck后，對(duì)Ck中的每個(gè)項(xiàng)集進(jìn)行非空子集進(jìn)行掃描，如果該非空子集不是頻繁的，那該項(xiàng)集肯定不是頻繁的，則從Ck中刪除該項(xiàng)集，不符合該性質(zhì)的項(xiàng)集去除，縮小了Ck的長(zhǎng)度，稱為減枝。

3）產(chǎn)生強(qiáng)關(guān)聯(lián)規(guī)則根據(jù)前面兩步得到頻繁k項(xiàng)集，這些項(xiàng)集都滿足了最小支持度閾值要求，如果也滿足最小置信度閾值要求，那么就是強(qiáng)關(guān)聯(lián)規(guī)則。

3 算法改進(jìn)

1）減少數(shù)據(jù)庫(kù)訪問(wèn)。因Apriori算法在尋找頻繁項(xiàng)集的過(guò)程中需要多次迭代，需頻繁訪問(wèn)數(shù)據(jù)庫(kù)表數(shù)據(jù)，資源開銷大。隨著數(shù)據(jù)量的增大這將大大影響算法性能，同時(shí)也會(huì)對(duì)正常業(yè)務(wù)系統(tǒng)造成影響。為解決此問(wèn)題，將原始訂單商品表數(shù)據(jù)經(jīng)過(guò)處理后形成事務(wù)表，事務(wù)表以鍵值對(duì)形式存放在redis內(nèi)存數(shù)據(jù)庫(kù)中，這樣只需開始一次掃描數(shù)據(jù)庫(kù)轉(zhuǎn)換事務(wù)集，后續(xù)使用Apriori算法尋找頻繁項(xiàng)集的過(guò)程中只需訪問(wèn)redis，效率大大提高。

2）縮小事務(wù)集范圍。當(dāng)生成Lk后，將事務(wù)集中項(xiàng)的個(gè)數(shù)少于k+1的事務(wù)數(shù)據(jù)刪除，從而減少遍歷事務(wù)集次數(shù)。如當(dāng)前已生成了2項(xiàng)頻繁集，則后續(xù)要生成3項(xiàng)頻繁候選集C3，此時(shí)事務(wù)集中項(xiàng)的個(gè)數(shù)為2的事務(wù)已經(jīng)無(wú)意義，因?yàn)轫?xiàng)的個(gè)數(shù)不夠3，不需要參加支持度計(jì)數(shù)的計(jì)算。每次迭代后，事務(wù)集記錄數(shù)會(huì)大幅減小，大大提升計(jì)算效率。

4 應(yīng)用實(shí)例與分析

實(shí)際應(yīng)用中，一般情形一次顧客訂單包含多個(gè)商品，訂單和商品是1∶N關(guān)系，常見的顧客訂單商品數(shù)據(jù)庫(kù)表設(shè)計(jì)見表1。

表1 顧客點(diǎn)單數(shù)據(jù)表

將上述數(shù)據(jù)中的數(shù)據(jù)轉(zhuǎn)換成事務(wù)數(shù)據(jù)集，以方便關(guān)聯(lián)規(guī)則模型計(jì)算，按照訂單歸集數(shù)據(jù)，一個(gè)訂單為一個(gè)事務(wù)。為方便計(jì)算，將商品用符號(hào)表示，比如{牛肉，雞肉，牛奶}用{a，b，c}表示，并使用redis hash存儲(chǔ)，事務(wù)數(shù)據(jù)集見表2。

表2 訂單事務(wù)數(shù)據(jù)集

掃描事務(wù)集，設(shè)最小支持度閾值min_support=0.2，計(jì)算每個(gè)候選集的支持度，見表3。

表3 1

保留支持度大于min_support的，得到1項(xiàng)頻繁項(xiàng)集L1，見表4。

表4 L1

由L1自連接生成C2，由于C2的每個(gè)子集都是頻繁項(xiàng)集，不存在減枝步，計(jì)算支持度，見表5。

表5 C2

保留支持度大于min_support的，得到2項(xiàng)頻繁項(xiàng)集2。見表6。

表6 L2

由L2和L1連接生成C3，減枝后，同時(shí)刪除事務(wù)集中項(xiàng)的個(gè)數(shù)為2的事務(wù)數(shù)據(jù)，刪除后，事務(wù)集變?yōu)?，4，5，6，7五條記錄，計(jì)算支持度，見表7。

表7 C3

候選集C3的支持度均大于min_support，無(wú)需剔除項(xiàng)集，則L3=C3，見表8。

表8 L3

由L3和L1生成C4，經(jīng)過(guò)減枝后為?，即無(wú)4項(xiàng)頻繁候選項(xiàng)集，至此，迭代搜索結(jié)束，L1，L2，L3均為頻繁項(xiàng)集，L3為最大頻繁項(xiàng)集。計(jì)算各頻繁項(xiàng)集的置信度，令最小置信度min_conf=0.5，得到強(qiáng)關(guān)聯(lián)規(guī)則結(jié)果見表9。

表9 強(qiáng)關(guān)聯(lián)規(guī)則

以第一條關(guān)聯(lián)規(guī)則“c--b”為例，表示顧客同時(shí)購(gòu)買商品b和商品c的概率為57.14%。購(gòu)買了c商品，再購(gòu)買b的商品的概率100%。實(shí)際應(yīng)用系統(tǒng)中根據(jù)上述關(guān)聯(lián)規(guī)則進(jìn)行智能推薦，在提升商品銷量的同時(shí)，顧客也得到了良好的購(gòu)物體驗(yàn)。

使用購(gòu)物數(shù)據(jù)集，將優(yōu)化前后的算法進(jìn)行測(cè)試對(duì)比，分析運(yùn)行時(shí)長(zhǎng)隨最小支持度的變化情況，如圖1所示。從圖1中可以看出，支持度越低算法執(zhí)行時(shí)間越長(zhǎng)，因?yàn)榉弦蟮念l繁項(xiàng)集越多，在同樣的最小支持度閾值下改進(jìn)后的Apriori算法在執(zhí)行時(shí)間上明顯短于傳統(tǒng)的算法。

圖1 改進(jìn)后Apriori算法不同支持度曲線

5 結(jié)論

智能推薦是機(jī)器學(xué)習(xí)的重要方面，屬于無(wú)監(jiān)督學(xué)習(xí)范疇。商品智能推薦是現(xiàn)代網(wǎng)絡(luò)營(yíng)銷的重要手段，對(duì)促進(jìn)銷售起到了非常重要的作用，如常見的餐飲門店菜品推薦、電商購(gòu)物推薦和電影推薦等，通過(guò)商品推薦更好地滿足了用戶的購(gòu)物需求，給用戶帶來(lái)全新的購(gòu)物體驗(yàn)?；陉P(guān)聯(lián)規(guī)則的推薦是目前最主流的推薦算法之一。本文介紹了基于關(guān)聯(lián)規(guī)則的Apriori算法原理和實(shí)現(xiàn)步驟，并針對(duì)實(shí)際應(yīng)用系統(tǒng)中Apriori算法計(jì)算量大，數(shù)據(jù)庫(kù)訪問(wèn)頻繁的問(wèn)題，提出優(yōu)化改進(jìn)措施。最后以購(gòu)物商品實(shí)例進(jìn)行了算法實(shí)現(xiàn)的詳細(xì)步驟展示分析，得到了商品的強(qiáng)關(guān)聯(lián)規(guī)則，并據(jù)此規(guī)則進(jìn)行用戶商品推薦，改進(jìn)后的Apriori算法比傳統(tǒng)的Apriori算法在執(zhí)行時(shí)間上明顯優(yōu)化，該算法適合用于業(yè)務(wù)系統(tǒng)。