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

王 猛, 葉西寧

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

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

王 猛, 葉西寧

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

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

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

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

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

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

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

1 相關算法介紹

1.1 概率矩陣分解算法

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

(1)

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

(2)

(3)

圖1 概率矩陣分解模型

1.2 基本的KNN模型

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

2 基于排名倒數的RR-UBPMF算法

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

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

(4)

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

(5)

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

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

(6)

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

(7)

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

(8)

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

通過最大化后驗概率對數學習特征矩陣參數,對后驗概率取對數可得[5]

(9)

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

(10)

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

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

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

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

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

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

(11)

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

(12)

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

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

2.3 模型的優(yōu)化

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

(13)

(14)

(15)

3 實驗結果及分析

3.1 實驗設置

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

3.2 數據集

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

表1 數據集信息

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

3.3 評價標準

(16)

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

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

(17)

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

3.4 實驗結果分析

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

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

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

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

圖3 不同算法的準確率比較結果

圖4 不同算法的NDCG比較結果

用戶數算法 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-

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

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

圖5 不同α值的比較結果

4 結束語

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

[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

國家自然科學基金(60974066)

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

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

TP391

A