基于改進Apriori算法的商品智能推薦

張中秋

（南京鐵道職業技術學院 智能工程學院，南京 210000）

近年來，隨著互聯網特別是移動互聯網的飛速發展，電商、實體店及O2O等商業模式覆蓋了人們衣食住行的方方面面，消費者面對線上線下品類繁多的商品，往往選擇困難，也增加了購物時間。同時各種面向C端互聯網平臺、會員系統、零售業信息系統的發展，使人們在日常生活中產生了越來越多的消費行為數據信息，如此大量的數據信息滿足了用戶在大數據時代對數據分析的需求。數據是互聯網時代最重要的資產，如何從大量的用戶歷史數據中發掘出有用信息，挖掘其特征，從而用于對消費者進行商品的智能推薦，是重要的研究課題，也是幫助用戶發現內容、克服信息過載的現實需求。智能推薦一方面可以提升商品銷量，一方面可以提升消費者購物體驗。基于互聯網的智能推薦系統在人們的生活中占了越來越大的比重[1-4]。

智能推薦的核心是算法。本文使用基于關聯規則的推薦算法來對商品銷售進行推薦，關聯規則指從大量用戶行為數據中發現強關聯規則，是一種無監督的推薦算法，適合事務數據庫的關聯規則挖掘。本文詳細闡述了Apriori算法的原理，以實例闡述了算法的實現過程并對實驗結果進行分析[5-8]。

1 關聯規則挖掘算法

關聯規則挖掘是大數據分析的重要手段，常見的關聯規則算法有Apriori算法和FP-Growth算法[9-10]。通過關聯規則可以挖掘出事務集中各項商品之間的關聯關系。基于關聯規則的推薦算法就是根據大量的用戶行為數據挖掘出關聯規則，并通過特定的指標參數對結果項進行排序，生成結果推薦給用戶。關聯性越強，則推薦的結果越可能受到用戶喜歡。

實際應用系統中，關聯規則挖掘的最大困難在于，由于系統的數據集比較大，即使開始的數據集小，隨著時間的推移，系統會積累越來越多的數據，每次關聯規則的計算的時候多次掃描數據，造成算法性能下降。如果存在很多商品的時候，可能的商品組合數目也會非常多，實際應用中要根據業務特診對算法進行優化。本課題使用Apriori算法進行日常商品的智能推薦。

1.1 項集與事務集

項集是數據項的集合，設集合I={i1，i2，…，ik}中有k個項，表示k項集。如集合{牛奶，面包，糖}是一個3項集。對于餐飲推薦問題來說，項集為該餐飲店的所有菜品的集合。事務集表示事務數據的集合，設集合T={t1，t2，…，tk}，即該餐飲店用戶訂單的數據集合，是用戶行為數據，一次點單ti是一個事務。顯然，ti?I。

1.2 關聯規則

關聯規則反映了一個事物與其他事物之間的相互依存性和關聯性。關聯規則如下定義：現有項集I，A?I，B?I，A≠?、B≠?且A∩B=?，則A?B表示關聯規則，A和B為項集I的非空子集，分別稱為關聯規則的前項和后項，符號?稱為關聯。

1.3 支持度與置信度

支持度（Support）和置信度（Confidence）是用來衡量關聯規則的強度的2個重要指標。

現有關聯規則A?B，支持度定義為：項集A和項集B同時發生的概率，表示規則在給定項集I中的頻繁程度。如式（1）所示

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

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

一個關聯規則稱為強規則，需同時滿足最小支持度閾值和最小置信度閾值。最小支持度閾值表示關聯規則在統計意義上的最低重要性，最小置信度表示關聯規則的最低可靠性。如果一個項集的支持度滿足預設的最小支持度閾值，稱為是頻繁項集，頻繁k項集記作Lk。

2 Apriori算法實現過程

Apriori算法的主要思想是找出事務數據集中的最大頻繁項集，設定關聯規則的最小置信度閾值，然后根據最大頻繁項集與預先設定的最小置信度閾值生成強關聯規則。算法實現步驟如下

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

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

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

3）產生強關聯規則根據前面兩步得到頻繁k項集，這些項集都滿足了最小支持度閾值要求，如果也滿足最小置信度閾值要求，那么就是強關聯規則。

3 算法改進

1）減少數據庫訪問。因Apriori算法在尋找頻繁項集的過程中需要多次迭代，需頻繁訪問數據庫表數據，資源開銷大。隨著數據量的增大這將大大影響算法性能，同時也會對正常業務系統造成影響。為解決此問題，將原始訂單商品表數據經過處理后形成事務表，事務表以鍵值對形式存放在redis內存數據庫中，這樣只需開始一次掃描數據庫轉換事務集，后續使用Apriori算法尋找頻繁項集的過程中只需訪問redis，效率大大提高。

2）縮小事務集范圍。當生成Lk后，將事務集中項的個數少于k+1的事務數據刪除，從而減少遍歷事務集次數。如當前已生成了2項頻繁集，則后續要生成3項頻繁候選集C3，此時事務集中項的個數為2的事務已經無意義，因為項的個數不夠3，不需要參加支持度計數的計算。每次迭代后，事務集記錄數會大幅減小，大大提升計算效率。

4 應用實例與分析

實際應用中，一般情形一次顧客訂單包含多個商品，訂單和商品是1∶N關系，常見的顧客訂單商品數據庫表設計見表1。

表1 顧客點單數據表

將上述數據中的數據轉換成事務數據集，以方便關聯規則模型計算，按照訂單歸集數據，一個訂單為一個事務。為方便計算，將商品用符號表示，比如{牛肉，雞肉，牛奶}用{a，b，c}表示，并使用redis hash存儲，事務數據集見表2。

表2 訂單事務數據集

掃描事務集，設最小支持度閾值min_support=0.2，計算每個候選集的支持度，見表3。

表3 1

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

表4 L1

由L1自連接生成C2，由于C2的每個子集都是頻繁項集，不存在減枝步，計算支持度，見表5。

表5 C2

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

表6 L2

由L2和L1連接生成C3，減枝后，同時刪除事務集中項的個數為2的事務數據，刪除后，事務集變為1，4，5，6，7五條記錄，計算支持度，見表7。

表7 C3

候選集C3的支持度均大于min_support，無需剔除項集，則L3=C3，見表8。

表8 L3

由L3和L1生成C4，經過減枝后為?，即無4項頻繁候選項集，至此，迭代搜索結束，L1，L2，L3均為頻繁項集，L3為最大頻繁項集。計算各頻繁項集的置信度，令最小置信度min_conf=0.5，得到強關聯規則結果見表9。

表9 強關聯規則

以第一條關聯規則“c--b”為例，表示顧客同時購買商品b和商品c的概率為57.14%。購買了c商品，再購買b的商品的概率100%。實際應用系統中根據上述關聯規則進行智能推薦，在提升商品銷量的同時，顧客也得到了良好的購物體驗。

使用購物數據集，將優化前后的算法進行測試對比，分析運行時長隨最小支持度的變化情況，如圖1所示。從圖1中可以看出，支持度越低算法執行時間越長，因為符合要求的頻繁項集越多，在同樣的最小支持度閾值下改進后的Apriori算法在執行時間上明顯短于傳統的算法。

圖1 改進后Apriori算法不同支持度曲線

5 結論

智能推薦是機器學習的重要方面，屬于無監督學習范疇。商品智能推薦是現代網絡營銷的重要手段，對促進銷售起到了非常重要的作用，如常見的餐飲門店菜品推薦、電商購物推薦和電影推薦等，通過商品推薦更好地滿足了用戶的購物需求，給用戶帶來全新的購物體驗。基于關聯規則的推薦是目前最主流的推薦算法之一。本文介紹了基于關聯規則的Apriori算法原理和實現步驟，并針對實際應用系統中Apriori算法計算量大，數據庫訪問頻繁的問題，提出優化改進措施。最后以購物商品實例進行了算法實現的詳細步驟展示分析，得到了商品的強關聯規則，并據此規則進行用戶商品推薦，改進后的Apriori算法比傳統的Apriori算法在執行時間上明顯優化，該算法適合用于業務系統。