融合AOBPR和SVD++的排序推薦算法

何靈敏, 杜民雙

(中國計量大學(xué) 信息工程學(xué)院，浙江 杭州 310018)

推薦系統(tǒng)可在海量數(shù)據(jù)中為用戶推薦對其有用的信息，有效緩解互聯(lián)網(wǎng)信息過載的問題.在大數(shù)據(jù)環(huán)境下進(jìn)行推薦是未來推薦系統(tǒng)的大方向[1].傳統(tǒng)的推薦算法以用戶的歷史評分信息為依據(jù)，可以將問題轉(zhuǎn)換成為對待推薦的物品進(jìn)行評分預(yù)測，然后基于預(yù)測評分進(jìn)行排序，為用戶提供Top-N推薦.將排序?qū)W習(xí)的思想應(yīng)用到推薦系統(tǒng)上面是現(xiàn)在比較熱門的研究方向.基于排序的推薦算法在沒有經(jīng)過對待推薦物品評分預(yù)測過程的情況下，能產(chǎn)生排好序的推薦列表，其核心思想是對每個用戶直接產(chǎn)生有序的推薦對象序列，而不是對每個推薦對象預(yù)測評分后再排序[2-3].在推薦系統(tǒng)中，常常碰到的一個問題是Top-N推薦，即為用戶提供個性化的N個推薦內(nèi)容.其中，可以挖掘的用戶歷史信息包括用戶對已購買物品的評分，以及用戶的瀏覽記錄等.前者是用戶顯式提供的，而后者是系統(tǒng)日志記錄，可能包含用戶的隱式偏好，本文分別將其稱之為顯式反饋和隱式反饋數(shù)據(jù).需要注意的是，在排序推薦模型中，一般只考慮隱式反饋數(shù)據(jù)，將顯式反饋數(shù)據(jù)也作為隱式反饋數(shù)據(jù)處理.

基于排序的推薦算法在近幾年取得了較快的發(fā)展.文獻(xiàn)[4]提出了一種面向排序的基于貝葉斯概率模型的推薦算法BPR，其關(guān)鍵思想是從用戶的隱式反饋數(shù)據(jù)中推出用戶喜好內(nèi)容的偏序?qū)?，然后利用該偏序?qū)碛?xùn)練一個推薦模型，如協(xié)同過濾模型或矩陣分解模型等.文獻(xiàn)[5]提出了基于組的貝葉斯個性化排序(Group preference based Bayesian Personal Rankind，GBPR)模型，該模型是在BPR模型基礎(chǔ)上考慮了用戶的鄰居對該用戶偏好的影響.文獻(xiàn)[6]提出了少即是好協(xié)同過濾(Collaborative Less-is-More Filtering，CLiMF)模型，CLiMF模型通過最大化評價指標(biāo)相關(guān)性排序 (Reciprocal Rank，RR) 對推薦對象進(jìn)行排序.文獻(xiàn)[7]提出了xCLiMF模型，xCLiMF模型通過直接優(yōu)化評價指標(biāo)ERR來對推薦對象進(jìn)行排序，是CLiMF模型的擴(kuò)展版.文獻(xiàn)[8]針對BPR收斂速度慢的問題提出了一個改進(jìn)的AOBPR(Adaptive 0versample Bayesian Personal Ranking)模型，該模型通過對非隱式反饋數(shù)據(jù)進(jìn)行非均勻采樣來加快收斂速度.

針對AOBPR只能利用隱式反饋數(shù)據(jù)的問題，本文提出了一種將AOBPR模型與經(jīng)典的基于矩陣分解的SVD++算法相結(jié)合的算法AOBPR_SVD++，該模型既可以利用顯式反饋數(shù)據(jù)又可以利用隱式反饋數(shù)據(jù)，并可以獲得更好的推薦結(jié)果.

1　改進(jìn)

1.1　BPR模型

(1)

式(1)中，集合Ds中每一個元素(u,i,j)都滿足i>uj.BPR模型的最優(yōu)化目標(biāo)就是：給定任一個推薦模型Θ，對集合Ds中所有的偏序?qū)?u，最大化后驗(yàn)概率p(Θ|>u).

由貝葉斯概率理論可知

p(Θ|>u)∝p(>u|Θ)p(Θ).

(2)

式(2)中有[4]

p(>u|Θ)=∏(u,i,j)∈Dsp(i>uj|Θ). (3)

可定義

對于推薦模型Θ，可以選擇協(xié)同過濾模型也可以選擇矩陣分解模型，本文是基于矩陣分解[9]模型的.那么有

式(6)中，pu為用戶u的特征向量，qi為物品i的特征向量.

1.2　AOBPR模型

BPR模型是一個成對的選出兩個物品進(jìn)行比較的模型，這種選擇是一種均勻的采樣，模型的訓(xùn)練一般采用的是隨機(jī)梯度下降法.在實(shí)際的數(shù)據(jù)中，物品通常呈現(xiàn)長尾分布：流行度高的小部分物品經(jīng)常被選擇，而流行度低的大部分物品卻少有人問津.這樣的分布導(dǎo)致BPR模型在訓(xùn)練過程當(dāng)中大部分時候都是在做無用功.文獻(xiàn)[8]針對BPR收斂速度慢的問題提出了一個改進(jìn)的AOBPR(Adaptive 0versample Bayesian Personal Ranking)模型，該模型通過對非隱式反饋數(shù)據(jù)進(jìn)行非均勻采樣來加快收斂速度.AOBPR模型大大改善了BPR模型的收斂速度同時沒有降低推薦質(zhì)量,并且在大量真實(shí)數(shù)據(jù)集上都證明了該模型的有效性.本文在該模型的基礎(chǔ)上進(jìn)行了一些研究,并將傳統(tǒng)SVD+ +算法融入該模型以提高推薦質(zhì)量.

1.3　AOBPR_SVD+ +

SVD+ +算法是一個可以同時利用隱式反饋數(shù)據(jù)和顯式反饋數(shù)據(jù)的基于矩陣分解的推薦算法[10]，在SVD+ +算法中，用戶的特征向量表示為

(7)

(8)

本文用SVD++算法來作為AOBPR模型的推薦模型Θ，這樣改進(jìn)后的算法可以同時利用隱式反饋數(shù)據(jù)和顯式反饋數(shù)據(jù).在真實(shí)的數(shù)據(jù)集當(dāng)中通常都是雜糅著隱式反饋數(shù)據(jù)和顯式反饋數(shù)據(jù).例如我們在淘寶購物的時候，有的商品我們會明確給予評分(例如五星好評)，但是有的商品我們雖然購買但是沒有給出明確的評分，有的商品我們有過點(diǎn)擊行為.評分是用戶對商品喜愛程度的一種顯式表達(dá)，點(diǎn)擊行為則是一種隱式表達(dá).對于融合了以上兩種數(shù)據(jù)類型的數(shù)據(jù)集可以用本文提出的算法進(jìn)行處理.這樣可以更加全面地利用用戶的歷史行為信息.顯然，隱式反饋數(shù)據(jù)要比顯式反饋數(shù)據(jù)難處理得多.而AOBPR模型在處理數(shù)據(jù)的時候一般會將所有的數(shù)據(jù)都看成是隱式反饋數(shù)據(jù)，忽略用戶的顯式評分信息，這顯然沒有充分利用用戶的歷史行為信息.

在上文中式(5)的求解過程一般是使用隨機(jī)梯度下降法.由于本文的改進(jìn)其中的梯度求解會發(fā)生一些變化，下面給出具體的求導(dǎo)公式.我們的最優(yōu)化目標(biāo)是

模型Θ參數(shù)的梯度如下：

(10)

(11)

式(11)中的k為所在向量的分量，θ為模型參數(shù)Θ的一個具體值，通過以上的公式可以迭代求出全部的模型參數(shù)Θ，由于我們改進(jìn)的算法可以更多的利用用戶的歷史行為信息，所以可以得出更加精確的推薦結(jié)果.而且本文的算法是在最新提出的AOBPR模型上做的改進(jìn)因此在模型的訓(xùn)練過程當(dāng)中也有更好的收斂速度.

2　實(shí)　驗(yàn)

2.1　實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

本文所有算法都是在ubuntu系統(tǒng)下基于java代碼實(shí)現(xiàn)的.反復(fù)運(yùn)行各個算法10次后取平均結(jié)果作為該算法的最終運(yùn)行結(jié)果.

本文分別使用用兩個數(shù)據(jù)集對改進(jìn)后的算法進(jìn)行試驗(yàn).

1)Filmtrust數(shù)據(jù)集：其中包括1 508個用戶對2 071部電影進(jìn)行25 497條評分記錄.

2)MovieLens 1M數(shù)據(jù)集：其中包括6 040個用戶對3 900部電影進(jìn)行了1 000 209條評分記錄.

選取不同的數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)的原因是可以在不同的數(shù)據(jù)上驗(yàn)證改進(jìn)的算法的有效性.目前沒有公開可以獲取的數(shù)據(jù)集同時包含隱式反饋數(shù)據(jù)和顯式反饋數(shù)據(jù)，因此，從顯式反饋數(shù)據(jù)中創(chuàng)建隱式反饋數(shù)據(jù)來進(jìn)行實(shí)驗(yàn).具體的方法是：從訓(xùn)練數(shù)據(jù)中，隨機(jī)選取一定比例(本文取隱式與顯式反饋比為2∶1)的評分?jǐn)?shù)據(jù)，不關(guān)心其具體的評分，將其轉(zhuǎn)換為二值隱式反饋數(shù)據(jù).對于訓(xùn)練集和測試集的劃分，將候選數(shù)據(jù)按4∶1劃分成兩個部分，分別作為訓(xùn)練集和測試集.

2.2　測量指標(biāo)

基于排序的算法我們需要評估的是一個序列的好壞，是各個個體的相互關(guān)系，而不是大部分機(jī)器學(xué)習(xí)算法那樣評估的是每個個體的處理好壞.本實(shí)驗(yàn)采用在排名問題上非常廣泛的評價指標(biāo)AUC(Area Under the receiver operating characteristic Curve)、標(biāo)準(zhǔn)化折算累加值(Normalized Discounted Cumulative Gain，NDCG)對改進(jìn)后的算法的準(zhǔn)確度進(jìn)行驗(yàn)證.

AUC是一個概率值，如果AUC的值越大代表當(dāng)前分類算法越有可能將用戶更喜歡的物品排在前面，從而能夠更好地分類.NDCG(Normalized Discounted Cumulative Gain)是標(biāo)準(zhǔn)化折算累加值，整體質(zhì)量越高的列表NDCG值越大.

2.3　實(shí)驗(yàn)結(jié)果與討論

本文設(shè)計了兩組實(shí)驗(yàn)，即分別在Filmtrust和MovieLens 1M數(shù)據(jù)集上將BPR、AOBPR、CLiMF算法和本文提出的改進(jìn)算法AOBPR_SVD++進(jìn)行比較.

實(shí)驗(yàn)結(jié)果如圖1～4.

圖1　MovieLens 1M數(shù)據(jù)集AUC實(shí)驗(yàn)圖Figure 1　AUC achieved from MovieLens 1M data set

圖2　MovieLens 1M數(shù)據(jù)集NDCG實(shí)驗(yàn)圖Figure 2　NDCG achieved from MovieLens 1M data set

圖3　Filmtrust數(shù)據(jù)集AUC實(shí)驗(yàn)圖Figure 3　AUC achieved from Filmtrust data set

圖4　Filmtrust數(shù)據(jù)集NDCG實(shí)驗(yàn)圖Figure 4　NDCG achieved from Filmtrust data set

通過在兩個數(shù)據(jù)集上的實(shí)驗(yàn)可以看出：改進(jìn)后的算法AOBPR_SVD++在兩個排序指標(biāo)AUC、NDCG上相比其他算法都有一定的改進(jìn).收斂速度上要比BPR和CLiMF算法更快.

3　結(jié)　語

本文提出的AOBPR_SVD++算法能同時利用用戶的顯式反饋數(shù)據(jù)和隱式反饋數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明此算法推薦質(zhì)量與其他算法相比有所提高.在實(shí)際的數(shù)據(jù)中，用戶的隱式反饋數(shù)據(jù)可能要更加復(fù)雜，如用戶的點(diǎn)擊行為、收藏行為、購買行為在評價用戶的喜好程度的時候是占有不同權(quán)重的，如何利用用戶的歷史行為信息更好的挖掘用戶的興趣是今后的工作重點(diǎn).

【參考文獻(xiàn)】

[1]朱揚(yáng)勇, 孫婧. 推薦系統(tǒng)研究進(jìn)展[J].計算機(jī)科學(xué)與探索, 2015, 9(5): 513-525.

ZHU Y Y, SUN J .Recommender system:Up to now[J] .JournalofFrontiersofComputerScienceandTechnology,2015, 9(5): 513-525.

[2]黃震華，張佳雯，田春岐，等.基于排序?qū)W習(xí)的推薦算法研究綜述 [J].軟件學(xué)報，2016, 27 (3):691-713.

HUANG Z H , ZHANG J W , TIAN C Q .Survey on learning-to-rank based recommendation algorithms [J].JournalofSoftware,2016, 27 (3):691-713.

[3]李改.融合顯/隱式反饋的協(xié)同排序算法[J].計算計應(yīng)用，2015,35(5):1328-1332,1341.

LI G. Collaborative ranking algorithm by explicit and implicit feedback fusion[J].JournalofComputer, 2015,35(5):1328- 1332,1341.

[4]RENDLE S, FREUDENTHALER C, GANTNER Z, et al. BPR: Bayesian personalized ranking from implicit feedback [C] //Proceedingsofthe25thConferenceonUncertaintyinArtificialIntelligence(UAI09). Arlington, Virginia, USA: AUAI Press, 2009: 452-461.

[5]PAN W， LI C. GBPR: group preference based Bayesian per- sonalized ranking for one-class collaborative filtering[C]//Proceedingsofthe26thInternationalConferenceonKnowledgeDiscoveryandDataMining. New York: ACM,2009: 667-676.

[6]SHI Y，KARATZOGLOU A，BALTRUNAS L，et al.CLiMF:Collaborative Less-is-More Filtering[C]//Proceedingsofthe23rdInternationalConferenceonArtificialIntelligence. New York: ACM，2013: 3077-3081.

[7]SHI Y, KARATZOGLOU A, BALTRUNAS L, et al. xCLiMF: Optimizing expected reciprocal rank for data with multiple levels of rele vance[C]//Proceedingsofthe6thACMConferenceonRecommenderSystems. New York: ACM，2013: 431-434.

[8]RENDLE S,FREUDENTHALER C. Improving pairwise learning for item recommendation from implicit feedback[C]//WebSearchandDataMining.WSDM: ACM,2014: 273-282.

[9]KOREN Y，BEL R，VOLINSKY C.Matrix factorization techniques for recommender systems[J].Computer，2009，42(8): 30-37.

[10]KOREN Y．Factorization meets the neighborhood: a multifaceted collaborative filtering model[C]//Proceedingsofthe14thACMSIGKDDInternationalConferenceonknowledgeDiscoveryandDataMining. New York: ACM,2008: 426-434.