音樂個性化推薦算法RR-UBPMF的研究

王 猛, 葉西寧

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

音樂個性化推薦算法RR-UBPMF的研究

王 猛, 葉西寧

(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)

大規(guī)模隱式反饋數(shù)據(jù)的使用是推薦系統(tǒng)中的研究熱點(diǎn)和難點(diǎn)問題。針對隱式反饋數(shù)據(jù)高噪聲和缺少負(fù)反饋的特點(diǎn),以音樂推薦為背景,在研究概率矩陣分解模型(PMF)的基礎(chǔ)上提出了一種直接優(yōu)化排名倒數(shù)(RR)的概率矩陣分解模型(RR-PMF)。通過與User-based KNN算法相結(jié)合提出了RR-UBPMF算法,并利用交叉最小二乘法(ALS)進(jìn)行優(yōu)化學(xué)習(xí)。在last.fm數(shù)據(jù)集上的實(shí)驗結(jié)果表明,該算法在準(zhǔn)確率(Precision)、尤其是在標(biāo)準(zhǔn)化折算累加值(NDCG)等評價指標(biāo)上表現(xiàn)出極大的優(yōu)勢,能夠明顯提高預(yù)測準(zhǔn)確性,并且具有良好的可拓展性。

推薦系統(tǒng); 協(xié)同過濾; 排名倒數(shù); 概率矩陣分解; KNN

近年來,為了解決信息超載問題,推薦系統(tǒng)的研究受到了許多學(xué)者的關(guān)注[1]。從音樂推薦到社交網(wǎng)絡(luò),推薦系統(tǒng)在許多行業(yè)有著巨大的商業(yè)價值[2]。目前對于顯式反饋的推薦系統(tǒng)已經(jīng)有了很多研究[3-6],然而大多數(shù)推薦系統(tǒng)忽視了隱式反饋信息。相比于顯式反饋,隱式反饋有許多優(yōu)點(diǎn),數(shù)據(jù)收集成本低、應(yīng)用場景廣泛、不易引起用戶反感[7]。然而隱式反饋信息的使用卻面臨著挑戰(zhàn),缺少負(fù)反饋、存在大量的噪聲、數(shù)據(jù)量大且更稀疏[8]。

協(xié)同過濾(CF)是最早應(yīng)用于推薦系統(tǒng)的有效技術(shù)之一,該方法基于用戶的歷史行為而不需要專門的知識[9],現(xiàn)階段的大部分研究都是建立在其理論基礎(chǔ)之上。矩陣分解模型在顯式反饋中有著廣泛的應(yīng)用,但在解決隱式反饋問題時進(jìn)行0-1矩陣分解并不能取得理想的效果,因此一些學(xué)者提出將用戶與產(chǎn)品交互的頻率信息轉(zhuǎn)化為評分矩陣[10]。如Pacula等[11]提出一種具體的轉(zhuǎn)化公式,但效果并不太好且實(shí)際應(yīng)用比較困難。此外,直接利用隱式反饋的二元數(shù)據(jù)特征是目前比較常用的方法。Hu 等[8]根據(jù)隱式反饋數(shù)據(jù)生成二進(jìn)制用戶-項目交互矩陣,并根據(jù)交互的頻率賦予置信度(權(quán)值);Rendle等[12]提出了一種貝葉斯個性化排名算法(BPR),將隨機(jī)采樣的樣本作為負(fù)反饋,基于相關(guān)和不相關(guān)項目的成對比較來優(yōu)化目標(biāo)函數(shù)。為了優(yōu)化負(fù)反饋的不穩(wěn)定性,Pan等[13]設(shè)計出一種新的偏好學(xué)習(xí)算法,但引入負(fù)反饋的方法會不可避免地引入干擾。不同于以上方法,Shi 等[14]提出了一種優(yōu)化平均排名倒數(shù)(MRR)的矩陣分解算法(CLiMF),CLiMF通過平滑排名倒數(shù)(RR)指標(biāo)進(jìn)而最大化目標(biāo)函數(shù),但他并沒有充分利用排名倒數(shù)的特點(diǎn)。

當(dāng)前針對推薦系統(tǒng)的研究熱點(diǎn)主要集中在隱式反饋和情境感知推薦兩個方面[1],隱式反饋的主要難點(diǎn)在于缺少負(fù)反饋,Pan 等[15]將這一類問題定義為 One-Class 協(xié)同過濾(OCCF),目前的主要方法包括把隨機(jī)抽樣作為負(fù)反饋[12-13]、引入置信度[8,15]和直接優(yōu)化模型[14]等方法。

本文以音樂推薦為背景,在前人理論知識的基礎(chǔ)上結(jié)合交互數(shù)據(jù)的特點(diǎn),提出了一種直接優(yōu)化排名倒數(shù)的概率矩陣分解模型,并與User-based KNN推薦算法相結(jié)合對模型進(jìn)行優(yōu)化。

1 相關(guān)算法介紹

1.1 概率矩陣分解算法

概率矩陣分解(Probabilistic Matrix Factorization,PMF)最初被應(yīng)用于顯式評分的推薦系統(tǒng)中[5],該方法是從概率的角度預(yù)測用戶的評分,PMF模型如圖1所示。假設(shè)推薦系統(tǒng)中有M個用戶和N個推薦項目,Rui代表用戶u對于項目i的評分,U∈RMK是用戶特征矩陣,V∈RNK是項目特征矩陣,K表示選擇的特征個數(shù),其中列向量Uu和Vi為相應(yīng)的特征向量。該算法采用高斯噪聲的概率模型,評分矩陣的條件概率公式如下:

(1)

式中:N(x|μ,σ2)表示均值μ,方差σ2的高斯分布;Iui在該數(shù)據(jù)點(diǎn)有評分時為1,否則為0。用戶和項目的先驗分布假設(shè)是均值為0的高斯分布,公式如下:

(2)

(3)

圖1 概率矩陣分解模型

1.2 基本的KNN模型

K近鄰(K-Nearest Neighbor,KNN)思想是通過已知的K個相似鄰居對未知的項目I進(jìn)行評價[16],尋找相似用戶的方法叫做User-based KNN,找相似物品的方法叫做Item-based KNN,推薦步驟如下:(1)計算相似度;(2)選擇鄰居;(3)預(yù)測推薦。

2 基于排名倒數(shù)的RR-UBPMF算法

2.1 優(yōu)化排名倒數(shù)的概率矩陣分解模型

不同于Netflix prize競賽中的評分預(yù)測,TOP-N推薦形成一個分級的推薦列表[4],因其更加適用于實(shí)際應(yīng)用場景,近年來受到廣泛關(guān)注。在TOP-N推薦中,位于排名頂部的項目更為重要,這與用戶的瀏覽行為相一致,因此一些考慮排名的評價指標(biāo)被應(yīng)用于推薦系統(tǒng)中,如MRR[14]。給定用戶u的推薦列表,排名倒數(shù)的定義如下:

(4)

其中:N為項目的個數(shù);Yui表示用戶與項目有是否交互作用;I(x)為一個指示函數(shù),若x為真則I(x)為1,x不為真則I(x)為0;Rui表示項目在用戶列表中的排名,用如下的函數(shù)平滑表示:

(5)

其中g(shù)(x)=1/(1+e-x)。

在此理論基礎(chǔ)上,本文提出了一種直接優(yōu)化排名倒數(shù)的概率矩陣分解模型(RR-PMF)。根據(jù)隱式反饋數(shù)據(jù)的特點(diǎn),選用函數(shù)f(x)=x/(1+x)平滑表示排名倒數(shù),其中x表示用戶對項目的選擇傾向程度,x越大則f(x)越大,表明項目的排名越靠前。對于音樂推薦系統(tǒng)而言,用戶u對項目i的播放次數(shù)越多則項目i在列表中的排名越高,說明用戶越傾向于播放該音樂;然而僅考慮播放次數(shù)并不足以反映用戶的傾向程度,例如有的用戶很喜歡聽音樂,許多歌曲的播放次數(shù)都過高,而有的用戶播放次數(shù)則很少,這會造成許多歌曲之間的排名沒有區(qū)分度,且不同用戶傾向程度的評價標(biāo)準(zhǔn)存在很大差異。因此,用一種相對選擇傾向程度計算排名倒數(shù)。

(6)

定義項目i在用戶u的列表中的排名倒數(shù)為

(7)

排名倒數(shù)矩陣的條件概率公式如下:

(8)

其中:RR為用戶-項目排名倒數(shù)矩陣;M為用戶的個數(shù);N為項目個數(shù);Uu為用戶u的特征向量;Vi為項目i的特征向量;Iui為指示函數(shù),表示用戶u播放過項目i。

通過最大化后驗概率對數(shù)學(xué)習(xí)特征矩陣參數(shù),對后驗概率取對數(shù)可得[5]

(9)

其中:M為用戶的個數(shù);N為項目個數(shù)；K為隱含特征個數(shù)；C是常量。最大化對數(shù)后驗概率公式(9)相當(dāng)于最小化目標(biāo)函數(shù)F,如公式(10)所示。

(10)

這種通過概率矩陣分解法直接優(yōu)化項目的排名倒數(shù),不僅可緩解數(shù)據(jù)稀疏的問題,而且能夠有效提取用戶的隱含特征,實(shí)現(xiàn)比較好的推薦效果。

2.2 基于K近鄰的概率矩陣分解模型

RR-PMF算法是從全局的視角來發(fā)現(xiàn)數(shù)據(jù)內(nèi)部的聯(lián)系,而User-based KNN算法能夠從局部的視角來理解數(shù)據(jù)。本文綜合這兩種算法的優(yōu)缺點(diǎn),將User-based KNN算法與RR-PMF算法相結(jié)合對用戶進(jìn)行推薦,提出了基于排名倒數(shù)的User-based KNN概率矩陣分解算法(RR-UBPMF),其模型如圖2所示。

圖2 基于排名倒數(shù)的 User-based KNN 概率矩陣分解模型

該模型利用用戶的特征矩陣和與其最相似的K個用戶的特征矩陣,共同計算用戶u對項目i的排名倒數(shù),其中RRui表示項目i在用戶u列表中的排名倒數(shù),Tu(k)是與用戶u最相似的前K個用戶的用戶特征矩陣的集合。

在該模型中,需優(yōu)化如下目標(biāo)函數(shù):

(11)

其中:α∈(0,1)表示推薦結(jié)果受近鄰影響的程度,α值越小推薦結(jié)果受近鄰影響的程度越大;Suk表示用戶u與用戶k之間的相似系數(shù);λ為正則化因子,防止過度擬合。Suk采用對熱門物品添加懲罰項的用戶相似度計算:

(12)

其中N(i)是對物品i有過交互行為的用戶集合。

RR-UBPMF通過降維,在低維空間對用戶和產(chǎn)品建模,有效地緩解了數(shù)據(jù)稀疏的問題,提高了模型的抗噪能力。與其他協(xié)同過濾方法不同的是,該方法能夠提取大規(guī)模數(shù)據(jù)的內(nèi)在特征和局部特征;與顯式反饋方法不同的是,RR-UBPMF并不是擬合具體的評分值,而是直接去優(yōu)化項目的排名倒數(shù)(RR),非常適合處理只有隱式反饋信息的場景。

2.3 模型的優(yōu)化

在推薦系統(tǒng)的模型優(yōu)化算法中,隨機(jī)梯度下降法(SGD)的應(yīng)用使得大規(guī)模的數(shù)據(jù)處理成為了可能[3],但是并行化 SGD 卻面臨著巨大的挑戰(zhàn);交叉最小二乘法(ALS)的迭代計算復(fù)雜度相對較高[17],但它非常適合并行化。

(13)

(14)

(15)

3 實(shí)驗結(jié)果及分析

3.1 實(shí)驗設(shè)置

本文采用的實(shí)驗平臺為 PC(Intel(R),CPU i7-4510,RAM(4 GB),Windows10操作系統(tǒng),開發(fā)工具使用PyCharm Edu,算法使用Python語言編寫。

3.2 數(shù)據(jù)集

last.fm是著名的音樂網(wǎng)站,有來自世界各地的活躍用戶群體,它提供API供研究者使用,本文實(shí)驗建立在last.fm數(shù)據(jù)集的基礎(chǔ)上。Chris Meller dataset網(wǎng)站提供有一部分真實(shí)last.fm用戶數(shù)據(jù),從中隨機(jī)選取一部分用戶,利用API函數(shù)采集用戶近幾年的播放記錄,并篩選出有效用戶進(jìn)行實(shí)驗,采集的數(shù)據(jù)形式為。為了驗證本文方法的有效性和可行性及其相對其他算法具有較優(yōu)的推薦精確度,分別選取306和844個用戶驗證算法,數(shù)據(jù)集信息如表1所示。

表1 數(shù)據(jù)集信息

為了更加符合真實(shí)的應(yīng)用場景,本文按時間劃分訓(xùn)練集和測試集,用于預(yù)測將來一段時間用戶的播放傾向,且用戶在訓(xùn)練集中播放過的音樂不包含在測試集中,即只向用戶推薦沒有播放過的音樂。

3.3 評價標(biāo)準(zhǔn)

(16)

其中:T(u)表示測試集中用戶u的列表;Nu表示對用戶u生成的TOP-N推薦列表。

NDCG是信息檢索領(lǐng)域常用的評價指標(biāo),被廣泛用于度量一個排序列表的好壞,推薦效果越好NDCG值越大,NDCG@N定義如下:

(17)

當(dāng)推薦的第i個物品屬于測試集T(u)中物品時,rui為1,否則為0,式(17)中IDCG 是完美匹配時的DCG 值。

3.4 實(shí)驗結(jié)果分析

3.4.1 推薦結(jié)果 根據(jù)隱式反饋場景應(yīng)用的特點(diǎn),本文選取比較流行的推薦算法作為對比,分別是基于用戶的協(xié)同過濾(UB-KNN)[16]、基于隱式反饋的矩陣分解(WR-iMF)[8]、貝葉斯個性化排序(BPR)[12]、百分比正規(guī)化矩陣分解(MF with percentile-normalized,PNMF)[11],其中User-based KNN算法選取的近鄰數(shù)為50,其余算法的隱含特征數(shù)均選為30。

通過在測試集上仿真,各種算法的Precision@N折線圖如圖3所示,NDCG@N折線圖如圖4所示。由圖3和圖4可以看出,與其他算法相比,RR-BUPMF表現(xiàn)出的效果最佳。

以TOP-10仿真結(jié)果為例,分別對不同算法在Precision@10和NDCG@10上的推薦效果進(jìn)行比較,其中提升效果表示RR-UBPMF算法與對應(yīng)算法在Precsion@10和NDCG@10上提升的百分比,具體結(jié)果如表2所示。

從對比表中844用戶數(shù)數(shù)據(jù)集的實(shí)驗結(jié)果可得,RR-UBPMF算法在Precision@10上分別比BPR和WR-iMF提升了72.96%和30.58%,明顯優(yōu)于其他幾種算法;在NDCG@10評價標(biāo)準(zhǔn)上更是分別提高了89.11%和40.08%,說明RR-UBPMF算法在TOP-N推薦中具有非常大的優(yōu)勢。不論在準(zhǔn)確度評價指標(biāo)Precision還是考慮排序的評價指標(biāo)NDCG上,RR-UBPMF算法均表現(xiàn)出了巨大的優(yōu)勢。從時間效率來看,RR-UBOMF算法的復(fù)雜度相對較大,但ALS優(yōu)化算法能夠很方便地實(shí)現(xiàn)并行化計算,因此本文提出的算法具有較強(qiáng)的拓展性和可移植性。

圖3 不同算法的準(zhǔn)確率比較結(jié)果

圖4 不同算法的NDCG比較結(jié)果

用戶數(shù)算法 Precision@10提升效果/%NDCG@10提升效果/%306UserBasedKNN0．02359164．770．02109213．03BPR0．0398756．660．0359283．79PNMF0．02559144．080．02456168．81WR?iMF0．0468433．350．0455245．04RR?UBPMF0．06246-0．06602-844UserBasedKNN0．02710135．390．02913142．02BPR0．0368872．960．0372889．11PNMF0．02114201．760．02490183．13WR?iMF0．0488530．580．0503340．08RR?UBPMF0．06379-0．07050-

實(shí)驗結(jié)果表明,本文提出的算法明顯優(yōu)于傳統(tǒng)隱式反饋的推薦算法,通過對算法進(jìn)行并行化計算,在大規(guī)模隱式反饋推薦系統(tǒng)中具有很大的優(yōu)勢,完全適用于大規(guī)模數(shù)據(jù)的處理。

3.4.2 參數(shù)α的影響分析 分別選取不同的α值進(jìn)行實(shí)驗,研究α值對推薦結(jié)果的影響,K近鄰固定為20,在844用戶數(shù)數(shù)據(jù)集上進(jìn)行實(shí)驗,實(shí)驗結(jié)果如圖5所示。從圖5中可以看出,在TOP-10之前,當(dāng)α=0.80時效果較好,之后準(zhǔn)確率沒有表現(xiàn)出太大差異,但在NDCG指標(biāo)上,α為0.80左右時表現(xiàn)出較好的效果,在排名推薦中具有一定優(yōu)勢。

圖5 不同α值的比較結(jié)果

4 結(jié)束語

本文在研究概率矩陣分解(PMF)矩陣分解的基礎(chǔ)上,根據(jù)排名倒數(shù)(RR)的平滑表示理論,提出了直接優(yōu)化排名倒數(shù)的概率矩陣分解模型RR-PMF,在此基礎(chǔ)上與User-based KNN算法相結(jié)合提出了RR-UBPMF算法。該算法充分利用了隱式反饋數(shù)據(jù)的內(nèi)在聯(lián)系和局部特征關(guān)系,相比其他傳統(tǒng)算法在Precsion和NDCG評價指標(biāo)上具有很大的優(yōu)勢,能夠有效地緩解數(shù)據(jù)稀疏問題和缺少負(fù)反饋的問題,并且該算法能夠很方便地進(jìn)行并行化計算,具有良好的可移植性和拓展性。

[1]ADOMAVICIUS G,TUZHILIN A.Toward the next generation of recommender systems:A survey of the state-of-the-art and possible extensions[J].IEEE Transactions on Knowledge and Data Engineering,2005,17(6):734-749.

[2]RICCI F,ROKACH L,SHAPIRA B.Recommender Systems Handbook[M].US:Springer,2015.

[3]KOREN Y,BELL R,VOLINSKY C.Matrix factorization techniques for recommender systems[J].Computer,2009 (8):30-37.

[4]CREMONESI P,KOREN Y,TURRIN R.Performance of recommender algorithms on top-n recommendation tasks[C]//Proceedings of the Fourth ACM Conference on Recommender Systems.USA:ACM,2010:39-46.

[5]SALAKHUTDINOV R,MNIH A.Probabilistic matrix factorization[C]//International Conference on Machine Learning.[s.l.]:[s.n.].2012:880-887.

[6]KUMAR R,VERMA B K,RASTOGI S S.Social popularity based SVD++ recommender system[J].International Journal of Computer Applications,2014,87(14):33-37.

[7]POTTER G.Putting the collaborator back into collaborative filtering[C]//Proceedings of the 2nd KDD Workshop on Large-Scale Recommender Systems and the Netflix Prize Competition.USA:ACM,2008:1487-1490.

[8]HU Y,KOREN Y,VOLINSKY C.Collaborative filtering for implicit feedback datasets[C]//Eighth IEEE International Conference on Data Mining.Pisa,Italy:IEEE,2008:263-272.

[9]GOLDBERG D,NICHOLS D,OKI B M,etal.Using collaborative filtering to weave an information tapestry[J].Communications of the ACM,1992,35(12):61-70.

[10]CELMA O.Music Recommendation[M].Berlin Heidelberg:Springer,2010.

[11]PACULA M.A matrix factorization algorithm for music recommendation using implicit feedback[EB/OL].[2009-10-10].https://www.researchgate.net/publication/228520470.

[12]RENDLE S,FREUDENTHALER C,GANTNER Z,etal.BPR:Bayesian personalized ranking from implicit feedback[C]//Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence.Montreal,Canada:AUAI Press,2009:452-461.

[13]PAN W,ZHONG H,XU C,etal.Adaptive bayesian personalized ranking for heterogeneous implicit feedbacks[J].Knowledge-Based Systems,2015,73:173-180.

[14]SHI Y,KARATZOGLOU A,BALTRUNAS L,etal.CLiMF:Learning to maximize reciprocal rank with collaborative less-is-more filtering[C]//Proceedings of the sixth ACM conference on Recommender systems.USA:ACM,2012:139-146.

[15]PAN R,ZHOU Y,CAO B,etal.One-class collaborative filtering[C]//Eighth IEEE International Conference on Data Mining.USA:IEEE,2008:502-511.

[16]JI H,CHEN X,HE M,etal.Improved recommendation system via propagated neighborhoods based collaborative filtering[C]//2014 IEEE International Conference on Service Operations and Logistics,and Informatics (SOLI).Qingdao:IEEE,2014:119-122.

[17]PILáSZY I,ZIBRICZKY D,TIKK D.Fast als-based matrix factorization for explicit and implicit feedback datasets[C]//Proceedings of the Fourth ACM Conference on Recommender Systems.Barcelona,Spain:ACM,2010:71-78.

RR-UBPMF，A Personalized Music Recommendation Algorithm

WANG Meng, YE Xi-ning

(School of Information Science and Engineering,East China University of Science and Technology,Shanghai 200237,China)

The application of massive implicit feedback data is one of hot and difficult issues in the research of recommendation system.Aiming at the high noise and less negative feedback of implicit feedback data,this paper proposes a model of RR-PMF based on probabilistic matrix factorization (PMF),which optimizes the ranked reciprocal (RR) directly.By combining with the user-based KNN,this paper proposes a RR-UBPMF method,which is optimized via alternative least squares (ALS).The experiment via the last.fm dataset shows that the proposed algorithm has great advantages in the evaluation index of precision and NDCG,and can significantly improve the prediction accuracy and has good scalability.

recommended system; collaborative filtering; reciprocal rank; probabilistic matrix factorization; KNN

1006-3080(2017)01-0113-06

10.14135/j.cnki.1006-3080.2017.01.018

2016-07-20

國家自然科學(xué)基金(60974066)

王 猛(1991-),男,河南人,碩士生,主要研究方向為數(shù)據(jù)挖掘、圖像處理。 E-mail:sheepwm@foxmail.com

葉西寧,E-mail:yexining@ecust.edu.cn

TP391

A