音乐个性化推荐算法RR-UBPMF的研究

王 猛, 叶西宁

(华东理工大学信息科学与工程学院,上海 200237)

音乐个性化推荐算法RR-UBPMF的研究

王 猛, 叶西宁

(华东理工大学信息科学与工程学院,上海 200237)

大规模隐式反馈数据的使用是推荐系统中的研究热点和难点问题。针对隐式反馈数据高噪声和缺少负反馈的特点,以音乐推荐为背景,在研究概率矩阵分解模型(PMF)的基础上提出了一种直接优化排名倒数(RR)的概率矩阵分解模型(RR-PMF)。通过与User-based KNN算法相结合提出了RR-UBPMF算法,并利用交叉最小二乘法(ALS)进行优化学习。在last.fm数据集上的实验结果表明,该算法在准确率(Precision)、尤其是在标准化折算累加值(NDCG)等评价指标上表现出极大的优势,能够明显提高预测准确性,并且具有良好的可拓展性。

推荐系统; 协同过滤; 排名倒数; 概率矩阵分解; KNN

近年来,为了解决信息超载问题,推荐系统的研究受到了许多学者的关注[1]。从音乐推荐到社交网络,推荐系统在许多行业有着巨大的商业价值[2]。目前对于显式反馈的推荐系统已经有了很多研究[3-6],然而大多数推荐系统忽视了隐式反馈信息。相比于显式反馈,隐式反馈有许多优点,数据收集成本低、应用场景广泛、不易引起用户反感[7]。然而隐式反馈信息的使用却面临着挑战,缺少负反馈、存在大量的噪声、数据量大且更稀疏[8]。

协同过滤(CF)是最早应用于推荐系统的有效技术之一,该方法基于用户的历史行为而不需要专门的知识[9],现阶段的大部分研究都是建立在其理论基础之上。矩阵分解模型在显式反馈中有着广泛的应用,但在解决隐式反馈问题时进行0-1矩阵分解并不能取得理想的效果,因此一些学者提出将用户与产品交互的频率信息转化为评分矩阵[10]。如Pacula等[11]提出一种具体的转化公式,但效果并不太好且实际应用比较困难。此外,直接利用隐式反馈的二元数据特征是目前比较常用的方法。Hu 等[8]根据隐式反馈数据生成二进制用户-项目交互矩阵,并根据交互的频率赋予置信度(权值);Rendle等[12]提出了一种贝叶斯个性化排名算法(BPR),将随机采样的样本作为负反馈,基于相关和不相关项目的成对比较来优化目标函数。为了优化负反馈的不稳定性,Pan等[13]设计出一种新的偏好学习算法,但引入负反馈的方法会不可避免地引入干扰。不同于以上方法,Shi 等[14]提出了一种优化平均排名倒数(MRR)的矩阵分解算法(CLiMF),CLiMF通过平滑排名倒数(RR)指标进而最大化目标函数,但他并没有充分利用排名倒数的特点。

当前针对推荐系统的研究热点主要集中在隐式反馈和情境感知推荐两个方面[1],隐式反馈的主要难点在于缺少负反馈,Pan 等[15]将这一类问题定义为 One-Class 协同过滤(OCCF),目前的主要方法包括把随机抽样作为负反馈[12-13]、引入置信度[8,15]和直接优化模型[14]等方法。

本文以音乐推荐为背景,在前人理论知识的基础上结合交互数据的特点,提出了一种直接优化排名倒数的概率矩阵分解模型,并与User-based KNN推荐算法相结合对模型进行优化。

1 相关算法介绍

1.1 概率矩阵分解算法

概率矩阵分解(Probabilistic Matrix Factorization,PMF)最初被应用于显式评分的推荐系统中[5],该方法是从概率的角度预测用户的评分,PMF模型如图1所示。假设推荐系统中有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 优化排名倒数的概率矩阵分解模型

不同于Netflix prize竞赛中的评分预测,TOP-N推荐形成一个分级的推荐列表[4],因其更加适用于实际应用场景,近年来受到广泛关注。在TOP-N推荐中,位于排名顶部的项目更为重要,这与用户的浏览行为相一致,因此一些考虑排名的评价指标被应用于推荐系统中,如MRR[14]。给定用户u的推荐列表,排名倒数的定义如下:

(4)

其中:N为项目的个数;Yui表示用户与项目有是否交互作用;I(x)为一个指示函数,若x为真则I(x)为1,x不为真则I(x)为0;Rui表示项目在用户列表中的排名,用如下的函数平滑表示:

(5)

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

在此理论基础上,本文提出了一种直接优化排名倒数的概率矩阵分解模型(RR-PMF)。根据隐式反馈数据的特点,选用函数f(x)=x/(1+x)平滑表示排名倒数,其中x表示用户对项目的选择倾向程度,x越大则f(x)越大,表明项目的排名越靠前。对于音乐推荐系统而言,用户u对项目i的播放次数越多则项目i在列表中的排名越高,说明用户越倾向于播放该音乐;然而仅考虑播放次数并不足以反映用户的倾向程度,例如有的用户很喜欢听音乐,许多歌曲的播放次数都过高,而有的用户播放次数则很少,这会造成许多歌曲之间的排名没有区分度,且不同用户倾向程度的评价标准存在很大差异。因此,用一种相对选择倾向程度计算排名倒数。

(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)

这种通过概率矩阵分解法直接优化项目的排名倒数,不仅可缓解数据稀疏的问题,而且能够有效提取用户的隐含特征,实现比较好的推荐效果。

2.2 基于K近邻的概率矩阵分解模型

RR-PMF算法是从全局的视角来发现数据内部的联系,而User-based KNN算法能够从局部的视角来理解数据。本文综合这两种算法的优缺点,将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个用户的用户特征矩阵的集合。

在该模型中,需优化如下目标函数:

(11)

其中:α∈(0,1)表示推荐结果受近邻影响的程度,α值越小推荐结果受近邻影响的程度越大;Suk表示用户u与用户k之间的相似系数;λ为正则化因子,防止过度拟合。Suk采用对热门物品添加惩罚项的用户相似度计算:

(12)

其中N(i)是对物品i有过交互行为的用户集合。

RR-UBPMF通过降维,在低维空间对用户和产品建模,有效地缓解了数据稀疏的问题,提高了模型的抗噪能力。与其他协同过滤方法不同的是,该方法能够提取大规模数据的内在特征和局部特征;与显式反馈方法不同的是,RR-UBPMF并不是拟合具体的评分值,而是直接去优化项目的排名倒数(RR),非常适合处理只有隐式反馈信息的场景。

2.3 模型的优化

在推荐系统的模型优化算法中,随机梯度下降法(SGD)的应用使得大规模的数据处理成为了可能[3],但是并行化 SGD 却面临着巨大的挑战;交叉最小二乘法(ALS)的迭代计算复杂度相对较高[17],但它非常适合并行化。

(13)

(14)

(15)

3 实验结果及分析

3.1 实验设置

本文采用的实验平台为 PC(Intel(R),CPU i7-4510,RAM(4 GB),Windows10操作系统,开发工具使用PyCharm Edu,算法使用Python语言编写。

3.2 数据集

last.fm是著名的音乐网站,有来自世界各地的活跃用户群体,它提供API供研究者使用,本文实验建立在last.fm数据集的基础上。Chris Meller dataset网站提供有一部分真实last.fm用户数据,从中随机选取一部分用户,利用API函数采集用户近几年的播放记录,并筛选出有效用户进行实验,采集的数据形式为。为了验证本文方法的有效性和可行性及其相对其他算法具有较优的推荐精确度,分别选取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 推荐结果 根据隐式反馈场景应用的特点,本文选取比较流行的推荐算法作为对比,分别是基于用户的协同过滤(UB-KNN)[16]、基于隐式反馈的矩阵分解(WR-iMF)[8]、贝叶斯个性化排序(BPR)[12]、百分比正规化矩阵分解(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%,明显优于其他几种算法;在NDCG@10评价标准上更是分别提高了89.11%和40.08%,说明RR-UBPMF算法在TOP-N推荐中具有非常大的优势。不论在准确度评价指标Precision还是考虑排序的评价指标NDCG上,RR-UBPMF算法均表现出了巨大的优势。从时间效率来看,RR-UBOMF算法的复杂度相对较大,但ALS优化算法能够很方便地实现并行化计算,因此本文提出的算法具有较强的拓展性和可移植性。

图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-

实验结果表明,本文提出的算法明显优于传统隐式反馈的推荐算法,通过对算法进行并行化计算,在大规模隐式反馈推荐系统中具有很大的优势,完全适用于大规模数据的处理。

3.4.2 参数α的影响分析 分别选取不同的α值进行实验,研究α值对推荐结果的影响,K近邻固定为20,在844用户数数据集上进行实验,实验结果如图5所示。从图5中可以看出,在TOP-10之前,当α=0.80时效果较好,之后准确率没有表现出太大差异,但在NDCG指标上,α为0.80左右时表现出较好的效果,在排名推荐中具有一定优势。

图5 不同α值的比较结果

4 结束语

本文在研究概率矩阵分解(PMF)矩阵分解的基础上,根据排名倒数(RR)的平滑表示理论,提出了直接优化排名倒数的概率矩阵分解模型RR-PMF,在此基础上与User-based KNN算法相结合提出了RR-UBPMF算法。该算法充分利用了隐式反馈数据的内在联系和局部特征关系,相比其他传统算法在Precsion和NDCG评价指标上具有很大的优势,能够有效地缓解数据稀疏问题和缺少负反馈的问题,并且该算法能够很方便地进行并行化计算,具有良好的可移植性和拓展性。

[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