HLBPR:一種混合的基於局部相似度的BPR算法

摘 要：隨著電子商務的迅速發展，了解消費者在購物網站上的購買意向是一個十分重要且具有挑戰性的任務，迄今為止針對這個問題已經提出了許多的模型。在這些模型之中，貝葉斯個性化排序算法是第一個引入了對排序進行優化的著名算法。然而這個算法通常存在著數據稀疏性的問題。在這篇文章中，我們介紹一種混合的基於局部相似度的貝葉斯個性化排序（簡稱HLBPR）算法來解決數據稀疏性的問題。我們的主要思路是通過用戶消費記錄的局部相似性來發掘用戶感興趣的潛在商品，然後使用這些擴充的數據來優化物品排序。最後，我們通過在兩個實際數據集上的實驗來證明我們模型的有效性。

關鍵詞：推薦系統；稀疏；貝葉斯個性化排序（BPR）

引 言

近些年來，隨著電子商務這個新興產業的迅速發展，如何有效地捕捉消費者潛在興趣成為學術界爭相關注的熱點之一，圍繞著這個問題，研究者們提出了很多的方法。在這些方法之中，貝葉斯個性化排序（BPR）算法是一個公認的效果拔群的方法[6]。然而實際應用中數據往往存在著稀疏性的問題，用戶實際購買的物品通常只佔總體商品的一小部分。以Ta-Feng數據集為例，平均而言，每個用戶只購買了總共商品的0.4%。數據的稀疏將直接導致BPR算法的推薦精度上的低效性。現有的方法（例如SBPR等）通常要引入附加的信息（如社交信息等）來解決這類問題。但是，這類信息是在某些應用場景中本身就是相當稀少，甚至根本不存在的。為了緩解BPR算法數據稀疏性問題，並且儘可能的不引入可能不存在的額外信息，在本文中，我們介紹了一種混合的基於局部相似度的貝葉斯個性化排序（簡稱HLBPR）算法。與其他的現有方法相比，我們的方法有著以下的優點：

1）我們通過用戶購買歷史的局部相似性計算出用戶未來可能會購買的潛在商品，然後我們將這商品標記為已經購買過，通過這種方法我們擴充了用戶的購買歷史以避免稀疏性問題。

2）我們設計了兩種模式：一般模式和序列模式來計算用戶之間的相似度。

3）通過將（2）中的兩種模式混合，我們可以在商品推薦中獲得更好的性能。

我們在兩個實際交易的數據集上進行了大量的實驗，結果表明與傳統的BPR方法相比，我們的方法是相當有效的。

1、相關工作

推薦系統獲取用戶反饋的方式包括顯式反饋和隱式反饋。顯式反饋要求用戶對推薦的內容給出明確的評分或者通過填寫調查問卷的方式向系統提供自己的興趣，這雖然能更準確地表達用戶的興趣，但是需要用戶的額外操作，這種方式對用戶不是很友好。因此，可用的評分會很少，會出現數據稀疏問題，從而導致推薦質量不高。

相比之下，隱式反饋的收集要容易得多，隱式反饋包括用戶的點擊、瀏覽、收藏、購買等。一般網站的後臺伺服器會記錄用戶的在網站上的行為，並保存在日誌文件中。通過分析這些日誌文件，可以得到很多用戶對於商品的隱式反饋。

但是，隱式反饋的缺點是只能得到正反饋，也就是說，從隱式反饋一般只能推斷出用戶喜歡某個物品，而那些沒有觀察到的用戶-物品對，就可能包含兩種情況，一種是真的不喜歡，還有一種是用戶可能不知道這個商品。例如，通過用戶的購買記錄，可以推斷用戶對購買過的這些商品是感興趣的，而對於那些用戶沒有購買過的商品，並不一定就代表用戶不喜歡，也很有可能該用戶還沒有發現該商品，未來他知道後可能會購買。這種基於隱式反饋數據進行的推薦也被稱作one-class協同過濾。解決這類問題，一般有兩種方法：（1）基於評分的方法；（2）基於排序的方法。

基於評分的方法 基於評分的方法將隱式反饋當作絕對分數值來處理，例如一般將有反饋的項當作1，無反饋的項當作0。然後通過最小化平方損失去學習模型。[4]就是典型的利用這種思路解決推薦問題的方法。它利用不同的採樣策略來擴展觀察到的正反饋，然後利用現有的矩陣因子分解算法來學習一個推薦器。

基於排序的方法 基於排序的方法都相對較新。它們將隱式反饋當作相對偏好而不是絕對分數來處理。貝葉斯個性化排序（Bayesian personalized ranking，BPR）是其中最著名的方法。它直接優化一個類似AUC的排序目標。由於基於排序的方法取得了不錯的效果，有很多由BPR擴展而來的的新算法被提出來。在論文[11]中，社交信息被用來生成更多的商品偏好對，進而引導BPR算法在一個比較稠密的用戶-商品矩陣上進行採樣。在論文[5]中，作者提出一種可選採樣策略用來自適應地決定包含最多信息的商品偏好對。在論文[2]中，作者通過交互的頻繁程度，對有反饋數據集進行了更細緻的劃分，從而構造了更多的商品偏好對。

和上面這些工作相比，我們提出的混合的基於局部相似度的貝葉斯個性化排序（Hybrid Local Bayesian personalized ranking，HLBPR)算法在解決one-class協同過濾問題時的主要優勢是：

1）HLBPR能夠在無反饋商品之間建立更多的商品偏好對，進而幫助傳統的BPR算法在一定程度上緩解數據稀疏問題。

2）在HLBPR的整過推演過程中，不需要引入額外的任何信息。

2 問題定義

2.1 隱式反饋

我們首先形式化地定義基於隱式反饋的推薦問題。推薦系統的任務就是根據已知的用戶-物品交互行為來推測用戶對其餘物品的偏好。如圖1中最左邊的矩陣所示，加號表示觀察到該用戶對該物品有過交互行為，問號表示沒有觀察到該用戶對該物品有過交互行為。

傳統的解決隱式反饋的方法是，將其當作顯示評分預測問題來處理。具體處理方法如圖1所示，就是把加號當作1，把問號當作0，然後根據這些數據來訓練模型，最後預測出每個用戶對每個物品的評分，從而對用戶進行推薦。

使用這種簡單的處理辦法，推薦結果肯定不會太好。可以看到，通過這種方式訓練出來的模型，會使問號的值儘可能地接近0，而加號的值儘可能地接近1。這意味著，如果模型的表達能力足夠強，或者說模型夠複雜，那麼它最後的預測結果會總是0。而唯一能夠解決該問題的方法就是避免模型過擬合，例如正則化。

2.2 BPR的解決方案

正是由於將隱式反饋當作評分問題來處理會有諸多問題，因此Rendle等人提出了BPR模型。該模型不再以預測用戶對物品的評分為目標，而是通過最大化正例排在負例前面的概率。從而將評分問題轉化為排序問題來處理。具體思路如圖2所示，將左側的用戶-物品的大表分解為很多個右側的物品-物品的小表，而每個用戶對應一個。表中的每一項表示該用戶對任意兩個物品之間的相對偏好程度的大小。

BPR算法依據這樣兩個假設：1. 相比於沒有反饋的物品，用戶更喜歡有過反饋的物品；2. 對於都沒有反饋的任意兩個物品或者都有過反饋的任意兩個物品，用戶的偏好程度相同。依據以上的假設，可以構造出圖1中右側的表。然後利用已知的項去預測問號的內容，從而得到用戶對任意兩個物品間的偏好程度的相對大小，進而進行推薦。

2.3 HLBPR的解決方案

BPR模型雖然在一定程度上解決了基於隱式反饋的推薦問題，但是其還面臨數據稀疏的問題。也就是說，相比與巨大的物品總數，用戶有過反饋行為的物品是極少的，也就是說圖2中的矩陣的大部分內容都是問號，只有極少的項為加號。這極大地影響了推薦算法的準確率。

我們提出的HLBPR模型的主要思路是，對沒有反饋的物品集進行更進一步的細分，從而在不增加額外信息的情況下，挖掘出更多的用戶-物品對，以此解決BPR模型的數據稀疏問題。具體思路如圖3所示，圖中右側的表格中，標記為紅色的方格，在BPR模型中是問號。而通過我們在本文中提出的三種模型對無反饋數據集進行進一步細分，可以確定它們的值，從而解決數據稀疏問題。

3 我們的模型：HLBPR

為了解決傳統BPR算法中存在的數據稀疏問題，我們的模型主要關注於如何在用戶沒買的商品中區分用戶對於不同商品的喜好程度，進而構建出更多的商品偏好對。本章首先從兩種不同的模式出發考慮用戶可能購買的商品，然後將兩種模式有機的結合以達到更好的推薦精度。

在具體闡述模型之前，我們希望通過一個例子來說明我們構建模型時考慮的因素和動機，如圖1。假設李明是一個旅行愛好者，他在某個電子商務網站上的購買列表中有帳篷，衝鋒衣，登山鞋等，同時他在昨天在該網站上買了一個手機。根據前一個行為，我們可以推斷李明很可能在下一次的購買中買關於旅行的商品，例如登山褲，墨鏡，防曬霜等。但是根據後一個行為，我們可能會推斷李明可能下一次購買的是手機電池或者手機殼等。因此根據這兩種不同的推薦行為，我們首先採用兩種不同的模式來構建推薦系統。

我們假設U代表用戶的集合，I代表商品的集合。給定一個用戶-商品矩陣R∈〖{0,1}〗^(|U|×|I|), 其中R_ui=1表示用戶u∈U購買過商品i∈I。R_ui=1表示u未買過商品i。

3.1 基於非時間序列的BPR模型

在這一節中，我們直接利用用戶的購買信息來構建模型。我們把構建商品偏好對這個任務分成三部分：1. 計算用戶的相似度；2.根據用戶相似度計算用戶對於自己未買過的商品的喜好得分；3. 根據閾值來構建pair。

1）計算用戶的相似度

首先我們根據用戶的購買信息來構建用戶的表示向量，例如一個用戶u的購買記錄是{(a,b),(a,d),(c)}，這代表u進行了三次購買，在第一次購買中買了商品a和b，第二次買了商品a和d，第三次買了c。我們直接把u表示成R_u={a:2,b:1,c:1,d:1 }(Fig4)。對於兩個用戶u,v ∈U ，我們採用cosin距離來表示用戶的相似度，公式如下：

計算用戶對不同商品的喜好得分：

我們取和指定用戶最接近的K個用戶，然後統計他們中有哪些購買了指定物品。具體來說,我們用nsp_score(u,i)來表示用戶u對商品i的喜好得分，我們根據和用戶u購買記錄相似的用戶對商品i的行為記錄來推斷出用戶u對商品i的喜好，公式如下：

這裡T(i，K)代表和用戶u最接近的K個用戶中，購買過商品i的用戶集合。

2）構建商品偏好對

根據用戶對於物品的得分，我們對用戶未買過的物品進行劃分，進而構建商品偏好對。顯然，這裡構建商品偏好對的方式有很多，例如根據用戶u對不同商品i和j的得分差，或者可以先根據某一固定的閾值th來直接把用戶劃分成兩部分，然後在兩部分之間構造商品偏好對。經過大量的實驗我們發現後一種方法效果比前者好很多。我們可以將這一方法形式化表示成：

3.2 基於時間序列的BPR模型

目前，已經有大量的工作[1,9,7]證明，用戶的潛在興趣可以從海量的的用戶行為序列中推理得來。直觀來說，例如，如果已經存在大量的用戶在先買了手機後就買了手機殼，那麼如果當前有一個用戶購買了手機，那麼我們就有理由預測這個用戶在下一時刻可能會購買手機殼。因此在這一章節中，我們利用時間序列這一模式來捕獲用戶的潛在興趣。

構建商品偏好對的過程和基於非時間序列的BPR模型一樣，首先我們用[7]中的方法表示用戶向量，例如，上面提到的用戶u，其向量可以表示為S_u={a→a:1,a→d:1,b→a:1,b→d:1,a→c:1,d→c:1}(Fig5)。我們同樣使用cosin距離來計算用戶u和v的相似度sp_simi(u,i)。

根據[9]，用戶u對商品i的喜好程度可以通過下面的公式計算：

這裡〖last〗_u表示用戶u的最後一次消費記錄，S(〖last〗_u,i)表示{v|v包含序列對(k,i),k∈〖last〗_u}。得到用戶u對商品i的喜好得分後，商品偏好對的構造方式和上面的方法相似。

3.3 混合的BPR模型

為了同時獲得基於時間序列和基於非時間序列模型各自的優勢，本節把上面的兩個模型結合起來建模（fig6）。令hybrid_score(u,i)表示混合模型中用戶u對商品i的喜好得分。顯然，這裡利用nsp_score(u,i)和sp_score(u,i)生成hybrid_score(u,i)的方式有很多，我們深入研究了兩種方式，即最大值池化方法和均值池化方法。

1）最大值池化

hybrid_score(u,i)由nsp_score(u,i)和sp_score(u,i)中的最大值確定，公式如下：

2）均值池化

hybrid_score(u,i)由nsp_score(u,i)和sp_score(u,i)的加權平均值確定，公式如下：

其中參數a是用來平衡nsp_score(u,i)和sp_score(u,i)兩部分的權重。

3.4 模型的學習方法

在構建了更多的商品偏好對之後，我們採用與傳統的BPR學習算法類似的方法，在擴展後的商品偏好對上採用隨機梯度下降算法來求解HLBPR的參數。我們假設傳統的BPR模型中用戶商品偏好對集合為D={(u,i,j)|i∈I/I^-,j∈I^-}, 這裡I表示所有的物品集合，I^-表示用戶未購買過的商品集合。算法的偽代碼如圖7所示。

4 實驗結果與分析

在本章中，為了說明我們算法的有效性，我們設計並實現了大量的測試實驗。首先，我們介紹用來驗證推薦算法的數據集，基準算法和評價指標。然後，我們對實驗結果進行了和分析。

4.1 數據集

Ta-Feng: 本數據集是Recsys大會公開的真實的用戶消費記錄數據集，產品種類囊括食品，水果，辦公用品等。

BBG:本數據集是真實的大型電子商務網站雲猴網（http://www.yunhou.com/）上的採樣數據。

在我們的試驗中我們過濾掉消費次數小於10次的用戶和被消費次數小於10次的商品，並且將數據集按照70/30的原則構建訓練/測試集合。我們在表1中列出了這兩個數據集的統計信息。

4.2 基準算法

TOP-POP：這是一種非個性化的靜態推薦算法，對於每一個用戶，該算法都推薦給他最受歡迎（購買次數最多）的商品。

NMF：非負矩陣分解（Non-negative matrix factorization）是一種效果突出的矩陣分解算法，該算法同時要求用戶矩陣，商品矩陣都滿足所有元素都不為負的性質，元素的非負性使得分解結果更容易解釋。在具體實現這個算法的時候，我們採用的是公認度比較高的公開代碼（http://cogsys.imm.dtu.dk/toolbox/nmf）進行的實驗。

BPR：傳統的貝葉斯個性化排序（Bayesian personalized ranking）模型。其主要思想是利用貝葉斯最大後驗估計求出物品對之間的全序關係，從而獲得用戶對物品的個性化排序。在實現的過程中，我們利用嘗試了不同的參數，並且在學習率α=0.05, 規則化係數λ_w=0.002, λ_(H^+ )=λ_(H^- )=0.0001時得到了最好的結果。

NSP-BPR:基於非時間序列的BPR模型。在這個模型中我們的用戶相似度的計算方法是直接考慮用戶購買的商品數目，而未考慮購買商品的前後順序。

SP-BPR: 基於時間序列的BPR模型。在這個模型中，我們計算用戶相似度時考慮了用戶購買商品的先後順序。

HLBPR:混合BPR模型。在實現這個模型的過程中我們通過大量的嘗試和反覆的實驗最終在α=0.45, th_upper= th_lower=0.001時得到了最好的結果，同時我們已經將我們模型的代碼公開到了https://github.com/gearsuccess上。

4.3 評價指標

準確率：Precision，也叫查準率。在推薦系統中，準確率指的是正確推薦的商品數與推薦商品總數的比率。

召回率：Recall,也叫查全率。在推薦系統中，召回率指的是正確推薦的商品數與總商品數的比率。

F1值：F1-Score，又稱平衡F分數（balanced F Score），它被定義為準確率和召回率的調和平均數。

命中率：Hit-Ratio，指的是正確推薦的商品數與用戶總數的比率。

NDCG：Normalized Discounted Cumulative Gain，是一種用來衡量排序質量的指標，其主要依據以下兩個假設：1. 強相關的文檔出現在結果列表越靠前越有用；2. 強相關文檔比弱相關文檔有用，同樣弱相關文檔比不相關文檔有用。通常用在衡量搜尋引擎或推薦系統的結果列表的質量。

4.4 結果分析

我們在圖8中展現了在數據集Ta-Feng 和BBG的實驗結果。我們對實驗結果簡要分析如下：

（1）TOP-POP方法由於對不同的用戶推薦同樣的物品，而根本沒有考慮到不同用戶的不同興趣，因此在各項指標的表現上都是最差的。

（2）傳統的BPR算法由於直接優化用戶對不同商品的排序，因此其效果優於矩陣分解NMF算法。

（3）我們的模型NSP-BPR，SP-BPR，HLBPR在各項指標上均超過傳統的BPR算法。其中NSP-BPR在兩個數據集上的表現均好於SP-BPR，這說明我們的數據集表現出的時間序列特徵沒有非時間序列特徵明顯。由於同時考慮了兩種特徵，因此我們的混合模型HLBPR表現的比前面的兩種模型都好。

（4）和傳統的BPR相比，我們最終的混合模型HLBPR在Ta-Feng和BBG兩個數據集上的F1值分別提升了19.79%和9.2%。

5 結論

本文為了解決傳統BPR中數據稀疏的問題，首先利用時間序列和非時間序列模型來構建額外的pair，然後我們將這兩種模型進行混合以提升最終的推薦精度。在未來的工作中，我們將主要關注於兩個方面，一方面是利用更多的方法來構建更多的商品偏好對。從而進一步緩解數據稀疏的問題。另一方面，探索更加有效的結合不同模型的方式。

參考文獻:

C. Chand, A. Thakkar, and A. Ganatra. Sequential pattern mining: Survey and current research challenges. International Journal of Soft Computing and Engineering, 2(1):185-193, 2012.

L. Lerche and D. Jannach. Using graded implicit feedback for bayesian personalized ranking. In Proceedings of the 8th ACM Conference on Recommender systems, pages 353-356. ACM, 2014.

C.-b. Lin. Projected gradient methods for nonnegative matrix factorization. Neural computation, 19(10):2756-2779, 2007.

R. Pan, Y. Zhou, B. Cao, N. N. Liu, R. Lukose, M. Scholz, and Q. Yang. One-class collaborative filtering. In Data Mining, 2008. ICDM'08. Eighth IEEE International Conference on, pages 502-511. IEEE, 2008.

S. Rendle and C. Freudenthaler. Improving pairwise learning for item recommendation from implicit feedback. In Proceedings of the 7th ACM international conference on Web search and data mining, pages 273-282. ACM, 2014.

S. Rendle, C. Freudenthaler, Z. Gantner, and L. Schmidt-Thieme. Bpr: Bayesian personalized ranking from implicit feedback. In Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence, pages 452-461. AUAI Press, 2009.

S. Rendle, C. Freudenthaler, and L. Schmidt-Thieme. Factorizing personalized markov chains for next-basket recommendation. In Proceedings of the 19th international conference on World wide web, pages 811-820. ACM, 2010.

P. Wang, J. Guo, Y. Lan, J. Xu, S. Wan, and X. Cheng. Learning hierarchical representation model for next basket recommendation. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 403-412. ACM, 2015.

G.-E. Yap, X.-L. Li, and S. Y. Philip. Effiective next-items recommendation via personalized sequential pattern mining. In Database Systems for Advanced Applications, pages 48-64. Springer, 2012.

Y. Zhang, M. Zhang, Y. Zhang, Y. Liu, and S. Ma. Understanding the sparsity: Augmented matrix factorization with sampled constraints on unobservables. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 1189-1198. ACM, 2014.

T. Zhao, J. McAuley, and I. King. Leveraging social connections to improve personalized ranking for collaborative filtering. In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 261-270. ACM, 2014. 

(責編：王妍（實習）、燕帥)