王 猛, 葉西寧
(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)
音樂(lè)個(gè)性化推薦算法RR-UBPMF的研究
王 猛, 葉西寧
(華東理工大學(xué)信息科學(xué)與工程學(xué)院,上海 200237)
大規(guī)模隱式反饋數(shù)據(jù)的使用是推薦系統(tǒng)中的研究熱點(diǎn)和難點(diǎn)問(wèn)題。針對(duì)隱式反饋數(shù)據(jù)高噪聲和缺少負(fù)反饋的特點(diǎn),以音樂(lè)推薦為背景,在研究概率矩陣分解模型(PMF)的基礎(chǔ)上提出了一種直接優(yōu)化排名倒數(shù)(RR)的概率矩陣分解模型(RR-PMF)。通過(guò)與User-based KNN算法相結(jié)合提出了RR-UBPMF算法,并利用交叉最小二乘法(ALS)進(jìn)行優(yōu)化學(xué)習(xí)。在last.fm數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明,該算法在準(zhǔn)確率(Precision)、尤其是在標(biāo)準(zhǔn)化折算累加值(NDCG)等評(píng)價(jià)指標(biāo)上表現(xiàn)出極大的優(yōu)勢(shì),能夠明顯提高預(yù)測(cè)準(zhǔn)確性,并且具有良好的可拓展性。
推薦系統(tǒng); 協(xié)同過(guò)濾; 排名倒數(shù); 概率矩陣分解; KNN
近年來(lái),為了解決信息超載問(wèn)題,推薦系統(tǒng)的研究受到了許多學(xué)者的關(guān)注[1]。從音樂(lè)推薦到社交網(wǎng)絡(luò),推薦系統(tǒng)在許多行業(yè)有著巨大的商業(yè)價(jià)值[2]。目前對(duì)于顯式反饋的推薦系統(tǒng)已經(jīng)有了很多研究[3-6],然而大多數(shù)推薦系統(tǒng)忽視了隱式反饋信息。相比于顯式反饋,隱式反饋有許多優(yōu)點(diǎn),數(shù)據(jù)收集成本低、應(yīng)用場(chǎng)景廣泛、不易引起用戶反感[7]。然而隱式反饋信息的使用卻面臨著挑戰(zhàn),缺少負(fù)反饋、存在大量的噪聲、數(shù)據(jù)量大且更稀疏[8]。
協(xié)同過(guò)濾(CF)是最早應(yīng)用于推薦系統(tǒng)的有效技術(shù)之一,該方法基于用戶的歷史行為而不需要專門的知識(shí)[9],現(xiàn)階段的大部分研究都是建立在其理論基礎(chǔ)之上。矩陣分解模型在顯式反饋中有著廣泛的應(yīng)用,但在解決隱式反饋問(wèn)題時(shí)進(jìn)行0-1矩陣分解并不能取得理想的效果,因此一些學(xué)者提出將用戶與產(chǎn)品交互的頻率信息轉(zhuǎn)化為評(píng)分矩陣[10]。如Pacula等[11]提出一種具體的轉(zhuǎn)化公式,但效果并不太好且實(shí)際應(yīng)用比較困難。此外,直接利用隱式反饋的二元數(shù)據(jù)特征是目前比較常用的方法。Hu 等[8]根據(jù)隱式反饋數(shù)據(jù)生成二進(jìn)制用戶-項(xiàng)目交互矩陣,并根據(jù)交互的頻率賦予置信度(權(quán)值);Rendle等[12]提出了一種貝葉斯個(gè)性化排名算法(BPR),將隨機(jī)采樣的樣本作為負(fù)反饋,基于相關(guān)和不相關(guān)項(xiàng)目的成對(duì)比較來(lái)優(yōu)化目標(biāo)函數(shù)。為了優(yōu)化負(fù)反饋的不穩(wěn)定性,Pan等[13]設(shè)計(jì)出一種新的偏好學(xué)習(xí)算法,但引入負(fù)反饋的方法會(huì)不可避免地引入干擾。不同于以上方法,Shi 等[14]提出了一種優(yōu)化平均排名倒數(shù)(MRR)的矩陣分解算法(CLiMF),CLiMF通過(guò)平滑排名倒數(shù)(RR)指標(biāo)進(jìn)而最大化目標(biāo)函數(shù),但他并沒(méi)有充分利用排名倒數(shù)的特點(diǎn)。
當(dāng)前針對(duì)推薦系統(tǒng)的研究熱點(diǎn)主要集中在隱式反饋和情境感知推薦兩個(gè)方面[1],隱式反饋的主要難點(diǎn)在于缺少負(fù)反饋,Pan 等[15]將這一類問(wèn)題定義為 One-Class 協(xié)同過(guò)濾(OCCF),目前的主要方法包括把隨機(jī)抽樣作為負(fù)反饋[12-13]、引入置信度[8,15]和直接優(yōu)化模型[14]等方法。
本文以音樂(lè)推薦為背景,在前人理論知識(shí)的基礎(chǔ)上結(jié)合交互數(shù)據(jù)的特點(diǎn),提出了一種直接優(yōu)化排名倒數(shù)的概率矩陣分解模型,并與User-based KNN推薦算法相結(jié)合對(duì)模型進(jìn)行優(yōu)化。
1.1 概率矩陣分解算法
概率矩陣分解(Probabilistic Matrix Factorization,PMF)最初被應(yīng)用于顯式評(píng)分的推薦系統(tǒng)中[5],該方法是從概率的角度預(yù)測(cè)用戶的評(píng)分,PMF模型如圖1所示。假設(shè)推薦系統(tǒng)中有M個(gè)用戶和N個(gè)推薦項(xiàng)目,Rui代表用戶u對(duì)于項(xiàng)目i的評(píng)分,U∈RMK是用戶特征矩陣,V∈RNK是項(xiàng)目特征矩陣,K表示選擇的特征個(gè)數(shù),其中列向量Uu和Vi為相應(yīng)的特征向量。該算法采用高斯噪聲的概率模型,評(píng)分矩陣的條件概率公式如下:
(1)
式中:N(x|μ,σ2)表示均值μ,方差σ2的高斯分布;Iui在該數(shù)據(jù)點(diǎn)有評(píng)分時(shí)為1,否則為0。用戶和項(xiàng)目的先驗(yàn)分布假設(shè)是均值為0的高斯分布,公式如下:
(2)
(3)
圖1 概率矩陣分解模型
1.2 基本的KNN模型
K近鄰(K-Nearest Neighbor,KNN)思想是通過(guò)已知的K個(gè)相似鄰居對(duì)未知的項(xiàng)目I進(jìn)行評(píng)價(jià)[16],尋找相似用戶的方法叫做User-based KNN,找相似物品的方法叫做Item-based KNN,推薦步驟如下:(1)計(jì)算相似度;(2)選擇鄰居;(3)預(yù)測(cè)推薦。
2.1 優(yōu)化排名倒數(shù)的概率矩陣分解模型
不同于Netflix prize競(jìng)賽中的評(píng)分預(yù)測(cè),TOP-N推薦形成一個(gè)分級(jí)的推薦列表[4],因其更加適用于實(shí)際應(yīng)用場(chǎng)景,近年來(lái)受到廣泛關(guān)注。在TOP-N推薦中,位于排名頂部的項(xiàng)目更為重要,這與用戶的瀏覽行為相一致,因此一些考慮排名的評(píng)價(jià)指標(biāo)被應(yīng)用于推薦系統(tǒng)中,如MRR[14]。給定用戶u的推薦列表,排名倒數(shù)的定義如下:
(4)
其中:N為項(xiàng)目的個(gè)數(shù);Yui表示用戶與項(xiàng)目有是否交互作用;I(x)為一個(gè)指示函數(shù),若x為真則I(x)為1,x不為真則I(x)為0;Rui表示項(xiàng)目在用戶列表中的排名,用如下的函數(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表示用戶對(duì)項(xiàng)目的選擇傾向程度,x越大則f(x)越大,表明項(xiàng)目的排名越靠前。對(duì)于音樂(lè)推薦系統(tǒng)而言,用戶u對(duì)項(xiàng)目i的播放次數(shù)越多則項(xiàng)目i在列表中的排名越高,說(shuō)明用戶越傾向于播放該音樂(lè);然而僅考慮播放次數(shù)并不足以反映用戶的傾向程度,例如有的用戶很喜歡聽(tīng)音樂(lè),許多歌曲的播放次數(shù)都過(guò)高,而有的用戶播放次數(shù)則很少,這會(huì)造成許多歌曲之間的排名沒(méi)有區(qū)分度,且不同用戶傾向程度的評(píng)價(jià)標(biāo)準(zhǔn)存在很大差異。因此,用一種相對(duì)選擇傾向程度計(jì)算排名倒數(shù)。
(6)
定義項(xiàng)目i在用戶u的列表中的排名倒數(shù)為
(7)
排名倒數(shù)矩陣的條件概率公式如下:
(8)
其中:RR為用戶-項(xiàng)目排名倒數(shù)矩陣;M為用戶的個(gè)數(shù);N為項(xiàng)目個(gè)數(shù);Uu為用戶u的特征向量;Vi為項(xiàng)目i的特征向量;Iui為指示函數(shù),表示用戶u播放過(guò)項(xiàng)目i。
通過(guò)最大化后驗(yàn)概率對(duì)數(shù)學(xué)習(xí)特征矩陣參數(shù),對(duì)后驗(yàn)概率取對(duì)數(shù)可得[5]
(9)
其中:M為用戶的個(gè)數(shù);N為項(xiàng)目個(gè)數(shù);K為隱含特征個(gè)數(shù);C是常量。最大化對(duì)數(shù)后驗(yàn)概率公式(9)相當(dāng)于最小化目標(biāo)函數(shù)F,如公式(10)所示。
(10)
這種通過(guò)概率矩陣分解法直接優(yōu)化項(xiàng)目的排名倒數(shù),不僅可緩解數(shù)據(jù)稀疏的問(wèn)題,而且能夠有效提取用戶的隱含特征,實(shí)現(xiàn)比較好的推薦效果。
2.2 基于K近鄰的概率矩陣分解模型
RR-PMF算法是從全局的視角來(lái)發(fā)現(xiàn)數(shù)據(jù)內(nèi)部的聯(lián)系,而User-based KNN算法能夠從局部的視角來(lái)理解數(shù)據(jù)。本文綜合這兩種算法的優(yōu)缺點(diǎn),將User-based KNN算法與RR-PMF算法相結(jié)合對(duì)用戶進(jìn)行推薦,提出了基于排名倒數(shù)的User-based KNN概率矩陣分解算法(RR-UBPMF),其模型如圖2所示。
圖2 基于排名倒數(shù)的 User-based KNN 概率矩陣分解模型
該模型利用用戶的特征矩陣和與其最相似的K個(gè)用戶的特征矩陣,共同計(jì)算用戶u對(duì)項(xiàng)目i的排名倒數(shù),其中RRui表示項(xiàng)目i在用戶u列表中的排名倒數(shù),Tu(k)是與用戶u最相似的前K個(gè)用戶的用戶特征矩陣的集合。
在該模型中,需優(yōu)化如下目標(biāo)函數(shù):
(11)
其中:α∈(0,1)表示推薦結(jié)果受近鄰影響的程度,α值越小推薦結(jié)果受近鄰影響的程度越大;Suk表示用戶u與用戶k之間的相似系數(shù);λ為正則化因子,防止過(guò)度擬合。Suk采用對(duì)熱門物品添加懲罰項(xiàng)的用戶相似度計(jì)算:
(12)
其中N(i)是對(duì)物品i有過(guò)交互行為的用戶集合。
RR-UBPMF通過(guò)降維,在低維空間對(duì)用戶和產(chǎn)品建模,有效地緩解了數(shù)據(jù)稀疏的問(wèn)題,提高了模型的抗噪能力。與其他協(xié)同過(guò)濾方法不同的是,該方法能夠提取大規(guī)模數(shù)據(jù)的內(nèi)在特征和局部特征;與顯式反饋方法不同的是,RR-UBPMF并不是擬合具體的評(píng)分值,而是直接去優(yōu)化項(xiàng)目的排名倒數(shù)(RR),非常適合處理只有隱式反饋信息的場(chǎng)景。
2.3 模型的優(yōu)化
在推薦系統(tǒng)的模型優(yōu)化算法中,隨機(jī)梯度下降法(SGD)的應(yīng)用使得大規(guī)模的數(shù)據(jù)處理成為了可能[3],但是并行化 SGD 卻面臨著巨大的挑戰(zhàn);交叉最小二乘法(ALS)的迭代計(jì)算復(fù)雜度相對(duì)較高[17],但它非常適合并行化。
(13)
(14)
(15)
3.1 實(shí)驗(yàn)設(shè)置
本文采用的實(shí)驗(yàn)平臺(tái)為 PC(Intel(R),CPU i7-4510,RAM(4 GB),Windows10操作系統(tǒng),開(kāi)發(fā)工具使用PyCharm Edu,算法使用Python語(yǔ)言編寫。
3.2 數(shù)據(jù)集
last.fm是著名的音樂(lè)網(wǎng)站,有來(lái)自世界各地的活躍用戶群體,它提供API供研究者使用,本文實(shí)驗(yàn)建立在last.fm數(shù)據(jù)集的基礎(chǔ)上。Chris Meller dataset網(wǎng)站提供有一部分真實(shí)last.fm用戶數(shù)據(jù),從中隨機(jī)選取一部分用戶,利用API函數(shù)采集用戶近幾年的播放記錄,并篩選出有效用戶進(jìn)行實(shí)驗(yàn),采集的數(shù)據(jù)形式為
表1 數(shù)據(jù)集信息
為了更加符合真實(shí)的應(yīng)用場(chǎng)景,本文按時(shí)間劃分訓(xùn)練集和測(cè)試集,用于預(yù)測(cè)將來(lái)一段時(shí)間用戶的播放傾向,且用戶在訓(xùn)練集中播放過(guò)的音樂(lè)不包含在測(cè)試集中,即只向用戶推薦沒(méi)有播放過(guò)的音樂(lè)。
3.3 評(píng)價(jià)標(biāo)準(zhǔn)
(16)
其中:T(u)表示測(cè)試集中用戶u的列表;Nu表示對(duì)用戶u生成的TOP-N推薦列表。
NDCG是信息檢索領(lǐng)域常用的評(píng)價(jià)指標(biāo),被廣泛用于度量一個(gè)排序列表的好壞,推薦效果越好NDCG值越大,NDCG@N定義如下:
(17)
當(dāng)推薦的第i個(gè)物品屬于測(cè)試集T(u)中物品時(shí),rui為1,否則為0,式(17)中IDCG 是完美匹配時(shí)的DCG 值。
3.4 實(shí)驗(yàn)結(jié)果分析
3.4.1 推薦結(jié)果 根據(jù)隱式反饋場(chǎng)景應(yīng)用的特點(diǎn),本文選取比較流行的推薦算法作為對(duì)比,分別是基于用戶的協(xié)同過(guò)濾(UB-KNN)[16]、基于隱式反饋的矩陣分解(WR-iMF)[8]、貝葉斯個(gè)性化排序(BPR)[12]、百分比正規(guī)化矩陣分解(MF with percentile-normalized,PNMF)[11],其中User-based KNN算法選取的近鄰數(shù)為50,其余算法的隱含特征數(shù)均選為30。
通過(guò)在測(cè)試集上仿真,各種算法的Precision@N折線圖如圖3所示,NDCG@N折線圖如圖4所示。由圖3和圖4可以看出,與其他算法相比,RR-BUPMF表現(xiàn)出的效果最佳。
以TOP-10仿真結(jié)果為例,分別對(duì)不同算法在Precision@10和NDCG@10上的推薦效果進(jìn)行比較,其中提升效果表示RR-UBPMF算法與對(duì)應(yīng)算法在Precsion@10和NDCG@10上提升的百分比,具體結(jié)果如表2所示。
從對(duì)比表中844用戶數(shù)數(shù)據(jù)集的實(shí)驗(yàn)結(jié)果可得,RR-UBPMF算法在Precision@10上分別比BPR和WR-iMF提升了72.96%和30.58%,明顯優(yōu)于其他幾種算法;在NDCG@10評(píng)價(jià)標(biāo)準(zhǔn)上更是分別提高了89.11%和40.08%,說(shuō)明RR-UBPMF算法在TOP-N推薦中具有非常大的優(yōu)勢(shì)。不論在準(zhǔn)確度評(píng)價(jià)指標(biāo)Precision還是考慮排序的評(píng)價(jià)指標(biāo)NDCG上,RR-UBPMF算法均表現(xiàn)出了巨大的優(yōu)勢(shì)。從時(shí)間效率來(lái)看,RR-UBOMF算法的復(fù)雜度相對(duì)較大,但ALS優(yōu)化算法能夠很方便地實(shí)現(xiàn)并行化計(jì)算,因此本文提出的算法具有較強(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í)驗(yàn)結(jié)果表明,本文提出的算法明顯優(yōu)于傳統(tǒng)隱式反饋的推薦算法,通過(guò)對(duì)算法進(jìn)行并行化計(jì)算,在大規(guī)模隱式反饋推薦系統(tǒng)中具有很大的優(yōu)勢(shì),完全適用于大規(guī)模數(shù)據(jù)的處理。
3.4.2 參數(shù)α的影響分析 分別選取不同的α值進(jìn)行實(shí)驗(yàn),研究α值對(duì)推薦結(jié)果的影響,K近鄰固定為20,在844用戶數(shù)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果如圖5所示。從圖5中可以看出,在TOP-10之前,當(dāng)α=0.80時(shí)效果較好,之后準(zhǔn)確率沒(méi)有表現(xiàn)出太大差異,但在NDCG指標(biāo)上,α為0.80左右時(shí)表現(xiàn)出較好的效果,在排名推薦中具有一定優(yōu)勢(shì)。
圖5 不同α值的比較結(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評(píng)價(jià)指標(biāo)上具有很大的優(yōu)勢(shì),能夠有效地緩解數(shù)據(jù)稀疏問(wèn)題和缺少負(fù)反饋的問(wèn)題,并且該算法能夠很方便地進(jìn)行并行化計(jì)算,具有良好的可移植性和拓展性。
[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
國(guó)家自然科學(xué)基金(60974066)
王 猛(1991-),男,河南人,碩士生,主要研究方向?yàn)閿?shù)據(jù)挖掘、圖像處理。 E-mail:sheepwm@foxmail.com
葉西寧,E-mail:yexining@ecust.edu.cn
TP391
A