大数据存储与处理-推荐系统

第九章推荐系统郭宇春1•推荐系统模型•基于内容的推荐•协同过滤•潜在因素模型2推荐系统模型3从稀缺到丰富：推荐的需求•传统零售商的货架空间是稀缺资源–还包括:TVnetworks,movietheaters,…•网络使零成本产品信息传播成为可能–从稀缺到丰富TheLongTailRhapsody：onlinemusicserviceWal-Malt:offlinesupermarketPhysicalvsOnline5Read!推荐6Items搜索推荐Products,websites,blogs,newsitems,…推荐类型•编辑–收藏列表–要目列表•简单汇聚–Top10,最流行,最新上载•为每个用户定制–Amazon,Netflix,…严格模型•X用户集•S项目集•效用矩阵UtilityMatrix–效用函数Utilityfunctionu:–R评分集,完全有序集–例如,0-5星,[0,1]之间的实数关键问题1.收集已知评分形成R矩阵–如何收集效用矩阵中的数据2.根据已知的评分推断未知的评分–主要对未知的高评分感兴趣，只关心用户喜欢什么3.评估推断方法–如何衡量推荐方法的性能评分的收集•显式评价–要求用户对项目给出评分•实际中不太可行—困扰用户•隐式评价–从用户的行为中学习其评分•e.g.,购买意味着高评分•什么代表低评分呢?效用的推断•关键问题:效用矩阵U稀疏–大多数人没有评价过大多数项目–冷启动•新的项目没有评分•新的用户没有历史•3种方法–基于内容Content-based–协同过滤CollaborativeFiltering–基于潜在因素（隐变量）Latentfactorbased基于内容的推荐系统12基于内容的推荐•主要思想:向用户C推荐与她评分高（喜欢）项目相类似的项目例子：•电影推荐–推荐相同演员、导演、流派…•Websites,blogs,news–推荐类似内容的网页13推荐的过程likesItemprofilesRedCirclesTrianglesUserprofilematchrecommendbuild项模型itemprofile•对每个项目建立一份itemprofile•Profile是特征features的集合–movies:author,title,actor,director,…–text:setof“important”wordsindocument•文本特征——关键词–常用的启发式方法是TF.IDF(TermFrequencytimesInverseDocFrequency)•非文本项目特征——困难–邀请用户进行标记Tag（词语、短语）•SunsetatMalibu•TiananmensquareRecap：TF.IDFfij文档j中词项i出现的频次ni=包含词项i的文档数N=文档数TF.IDF分值wij=TFijIDFiDocprofile=有最高TF.IDF值的词汇及其对应分数的集合Note:wenormalizeTFtodiscountfor“longer”documents用户模型Userprofiles•Userprofile：–反映用户的特征偏好–根据项模型统计•用户评过项目的项目profile加权平均•启发式预测–给定用户模型x，项目模型i,估计用户x对于项目i的效用值基于内容方法的优点•不需要其他用户的数据–没有冷启动或者稀疏性的问题•能给品味一致的用户推荐•能给新项目或不流行项目推荐–没有第一个评价者的问题•能够提供解释–可以对推荐项目给出对应的内容特征描述18基于内容方法的缺点•找到适当的特征是困难的–e.g.,images,movies,music•过度集中–不会推荐用户内容偏好模型之外的项目–人们可能有多方面的兴趣–不能利用其它用户的优质判断•对新用户的推荐–如何给新用户建立模型?19协同过滤COLLABORATIVEFILTERING20协同过滤•考虑用户x–找到与x有相似评分的用户集合N–根据N中用户的评分估计x的评分21相似的用户•令rx为用户x的评分矢量•Jaccard相似度–问题：忽略了评分的分值•余弦相似度Cosinesimilaritymeasure–问题：将缺失项目视为“否定”•皮尔森相关系数Pearsoncorrelationcoefficient–Sxy=用户x和用户y共同评价过的项目集合缺失=否定？•直觉:sim(A,B)sim(A,C)，但是–Jaccardsimilarity:1/52/4–Cosinesimilarity:0.3860.322(接近)•原因：将缺失分量视为“否定”（取0值，意味最低评价）•解决措施:减去(行)均值——中心化23simA,Bvs.A,C:0.092-0.559注意：cosinesim.在以零为中心时，就是相关系数评分预测•rx：为用户x的评分矢量•N：为对项目i的评分与用户x最相似的k个用户的集合•用户x对项目s的评分预测–其他方法?基于项目的协同过滤Item-ItemCF•除了user-user，有另一个角度：item-item–对项目i,寻找其他相似的项目–根据相似项目的评分估计项目i的评分–可以采用类似user-usermodel的相似度测度2627282930CF：基本操作•定义项目i和j的相似度sij•选择k个最近邻居N(i;x)–用户x评价过的最类似i的项目•以加权平均估计评分rxi31Item-ItemvsUser-User•实际中，item-item比user-user的效果好•原因？Item更简单，user往往有多重品味32CF的优缺点•适合于任何item–不需要特征选择•ColdStart:–需要系统中有足够的用户进行匹配•稀疏性:–ratings矩阵稀疏，难以发现评价过相同项目的用户•第一个评价者–无法推荐一个没有被评价过的项目，新项目,隐秘项目•流行度偏差–无法给只有单一口味的用户推荐项目–倾向于推荐流行项目混合方法•实现两种或多种不同的推荐方法，并组合预测结果–比如用线性组合•将基于内容的方法与CF相结合–建立itemprofile解决新item问题–利用人口统计信息解决新用户问题评估及实际问题353637评估预测性能•对比预测值与已知的评分–Root-mean-squareerror(RMSE)–Precisionattop10–Rankcorrelation•另一种方法:0/1model–覆盖度•系统能够预测的items/users数量–精确度•预测的精度–受试者工作特征Receiveroperatingcharacteristic(ROC)•虚报率falsepositives与漏报率falsenegatives之间的均衡曲线错误测度的问题•有时狭隘地关注精度没有意义–PredictionDiversity预测多样性–PredictionContext预测情境–Orderofpredictions预测顺序•实际上仅仅关注对高分的预测–RMSE可能会对一个高分预测好低分预测差的方法不利CF：复杂度•最费时的步骤是找到k个最相似的用户:O(|X|)•无法实时完成–可以预先计算•Naïvepre-computationtakestimeO(N·|C|)•大数据处理方法–高维数据中的最近邻居搜索(LSH)–聚类Clustering–降维Dimensionalityreduction40潜在因素模型LATENTFACTORMODELS41NetflixPrize•Trainingdata–100millionratings,480,000users,17,770movies–6yearsofdata:2000-2005•Testdata–Lastfewratingsofeachuser(2.8million)–Evaluationcriterion:rootmeansquarederror(RMSE)–NetflixCinematchRMSE:0.9514•Competition–2700+teams–$1millionprizefor10%improvementonCinematch42TheNetflixUtilityMatrixR43UtilityMatrixR:Evaluation44BellKorRecommenderSystem•Netflix挑战赛的获胜者•对数据的多尺度建模–全局特征Globaleffects•用户/电影的总体偏差–区域特征Regionaleffects•Factorization–局域特征Localpattern•CF45GlobaleffectsFactorizationCollaborativefiltering本地及全局特征的模型化•全局–电影的平均评分：3.7星–电影TheSixthSense的评分比均值高0.5星–用户Joe的评分比均值低0.2星基本估计（baseline）：Joe对TheSixthSense评分4星•局域（CF/NN）–Joe不喜欢相关的电影Signs最终估计：Joe对TheSixthSense评分3.8星46回顾：协同过滤CF•最早的最流行的CF方法•根据相似的电影推测未知的评分(item-itemvariant)•定义i,j两个item的相似度sij•选择k个最近邻居，计算rating–N(i;x):用户x评价过的与i最接近的项目集合47改进评分估计•引入全局偏置量48插入权重值•采用加权和代替加权平均值–𝑵(𝒊;𝒙)：用户x评价过的类似电影i的电影集合–𝒘𝒊𝒋：插入权重(实数值)•允许𝒋∈𝑵(𝒊,𝒙)𝒘𝒊𝒋≠𝟏•𝒘𝒊𝒋模拟电影对的关系(不依赖于用户x)49如何确定插入权值•误差测度SSE(SumofSquares)•在训练数据上找到令SSE最小的权值𝒘𝒊𝒋–模拟itemi与其邻居j的关系•可以根据用户x和评价过i的所有其他用户学习/估计𝒘𝒊𝒋50用最优化求解推荐问题•目标：好的推荐–用SSE评价优度—SSE最小化–对用户未评价过的项目进行好的推荐——很难实际实现–选择w矩阵,使其对已知的(user,item)rating的最优•期望此w对未知的rating也有好的预测性能•如何确定w的取值？–思路：确定目标函数，求解最优化问题–在训练数据上找到使SSE最小的wij51梯度下降法求解最优的w•Iterateuntilconvergence:𝒘−𝜵𝒘•where𝜵𝒘isgradient(derivativeevaluatedondata):52Nabla∇目标：最小化SSE53求解（学习）权值小结•求解权值–基于角色确定权重wij取值，不用任意的相似度–显式地考虑相邻电影的相互关系•下一步：LFM–提取区域关系54LFM55LFM•R≈Q·PT•R有一些缺失项，暂时忽略•现在的目标是对已知的评分重建误差最小•可以近似视为“SVD(SingularValueDecomposition)”56SVD:A=UVT评分=Factor的乘积•如何估计缺失的用户x对项目i的评分值？57ˆxiixiffxfrqpqp评分=Factor的乘积•如何估计缺失的用户x对项目i的评分值？58ˆxiixiffxfrqpqp2.4LatentFactorModel59LatentFactorModel60回顾：SVD•SVD•Netflixdata上–A=R，Q=U，PT=VT–R还有缺失项61LFM62•有缺失项的情况下不能直接用SVD•确定P,Q的方法–P,Q的列不一定正交或者等长–P,Q是users/movies到潜在空间的映射–Netflix参赛队中最常用的方法Factor的数量•目标：对不可见的测试数据最小化SSE•思想：在训练数据上最小化SSE–Wantlargef(#offactors)tocapt