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

1、第九章 推荐系统郭宇春1推荐系统模型基于内容的推荐协同过滤潜在因素模型2推荐系统模型3从稀缺到丰富：推荐的需求传统零售商的货架空间是稀缺资源还包括: TV networks, movie theaters,网络使零成本产品信息传播成为可能从稀缺到丰富The Long TailRhapsody：online music serviceWal-Malt: offline supermarketPhysical vs OnlineRead /wired/archive/12.10/tail.html to learn more! 5推荐Items搜索推荐Products, web sites, bl

2、ogs, news items, 6推荐类型编辑收藏列表要目列表简单汇聚Top 10,最流行, 最新上载为每个用户定制Amazon, Netflix, 严格模型X 用户集S 项目集效用矩阵 Utility Matrix效用函数 Utility function u: R 评分集 , 完全有序集例如, 0-5 星, 0,1之间的实数 关键问题收集已知评分形成R矩阵如何收集效用矩阵中的数据根据已知的评分推断未知的评分主要对未知的高评分感兴趣，只关心用户喜欢什么评估推断方法如何衡量推荐方法的性能评分的收集显式评价要求用户对项目给出评分实际中不太可行困扰用户隐式评价 从用户的行为中学习其评分e.g.,

3、 购买意味着高评分什么代表低评分呢?效用的推断关键问题: 效用矩阵U稀疏大多数人没有评价过大多数项目冷启动新的项目没有评分新的用户没有历史3种方法基于内容 Content-based协同过滤 Collaborative Filtering基于潜在因素（隐变量）Latent factor based基于内容的推荐系统12基于内容的推荐主要思想: 向用户 C 推荐与她评分高（喜欢）项目相类似的项目例子：电影推荐推荐相同演员、导演、流派 Websites, blogs, news推荐类似内容的网页13推荐的过程likesItem profilesRedCirclesTrianglesUser pro

4、filematchrecommendbuild项模型 item profile对每个项目建立一份 item profileProfile 是特征features的集合movies: author, title, actor, director,text: set of “important” words in document文本特征关键词常用的启发式方法是 TF.IDF (Term Frequency times Inverse Doc Frequency)非文本项目特征困难邀请用户进行标记Tag（词语、短语）Sunset at MalibuTiananmen squareRecap：TF.

5、IDFfij 文档 j 中词项i 出现的频次ni = 包含词项i的文档数N = 文档数TF.IDF分值 wij = TFij IDFiDoc profile = 有最高 TF.IDF 值的词汇及其对应分数的集合Note: we normalize TF to discount for “longer” documents 用户模型User profilesUser profile：反映用户的特征偏好根据项模型统计用户评过项目的项目profile加权平均启发式预测给定用户模型 x，项目模型 i, 估计用户x对于项目 i 的效用值基于内容方法的优点不需要其他用户的数据没有冷启动或者稀疏性的问题能给

6、品味一致的用户推荐能给新项目或不流行项目推荐没有第一个评价者的问题能够提供解释可以对推荐项目给出对应的内容特征描述18基于内容方法的缺点找到适当的特征是困难的e.g., images, movies, music过度集中不会推荐用户内容偏好模型之外的项目人们可能有多方面的兴趣不能利用其它用户的优质判断对新用户的推荐如何给新用户建立模型?19协同过滤 collaborative filtering20协同过滤考虑用户x找到与x有相似评分的用户集合 N根据N中用户的评分估计 x的评分21相似的用户令 rx 为用户 x的评分矢量Jaccard 相似度问题：忽略了评分的分值余弦相似度 Cosine s

7、imilarity measure问题：将缺失项目视为“否定”皮尔森相关系数 Pearson correlation coefficientSxy = 用户 x 和用户 y共同评价过的项目集合缺失 = 否定？直觉: sim(A, B) sim(A, C) ，但是Jaccard similarity: 1/5 0.322 (接近)原因：将缺失分量视为“否定” （取0值，意味最低评价）解决措施: 减去(行)均值 中心化sim A,B vs. A,C: 0.092 -0.559 注意：cosine sim. 在以零为中心时，就是相关系数23评分预测rx ：为用户 x的评分矢量 N： 为对项目 i的评

8、分与用户x最相似的 k 个用户的集合用户x对项目 s的评分预测其他方法?基于项目的协同过滤 Item-Item CF除了user-user，有另一个角度：item-item 对项目i, 寻找其他相似的项目根据相似项目的评分估计项目i的评分可以采用类似 user-user model的相似度测度2627282930CF：基本操作定义项目i 和j 的相似度sij选择k个最近邻居N(i;x)用户x评价过的最类似i的项目以加权平均估计评分rxi31Item-Item vs User-User实际中，item-item 比user-user的效果好原因？ Item 更简单，user往往有多重品味32CF

9、的优缺点适合于任何item不需要特征选择Cold Start: 需要系统中有足够的用户进行匹配稀疏性: ratings 矩阵稀疏 ， 难以发现评价过相同项目的用户第一个评价者无法推荐一个没有被评价过的项目， 新项目, 隐秘项目流行度偏差无法给只有单一口味的用户推荐项目倾向于推荐流行项目混合方法实现两种或多种不同的推荐方法，并组合预测结果比如用线性组合将基于内容的方法与CF相结合建立item profile 解决新item问题 利用人口统计信息解决新用户问题评估及实际问题353637评估预测性能对比预测值与已知的评分Root-mean-square error (RMSE)Precision a

10、t top 10Rank correlation另一种方法: 0/1 model覆盖度系统能够预测的items/users 数量精确度预测的精度 受试者工作特征Receiver operating characteristic (ROC)虚报率 false positives 与漏报率false negatives之间的均衡曲线错误测度的问题有时狭隘地关注精度没有意义Prediction Diversity 预测多样性Prediction Context 预测情境Order of predictions 预测顺序实际上仅仅关注对高分的预测RMSE 可能会对一个高分预测好低分预测差的方法不利CF

11、：复杂度最费时的步骤是找到k个最相似的用户: O(|X|) 无法实时完成可以预先计算Nave pre-computation takes time O(N |C|) 大数据处理方法高维数据中的最近邻居搜索 (LSH) 聚类Clustering 降维Dimensionality reduction 40潜在因素模型Latent factor models 41Netflix Prize Training data 100 million ratings, 480,000 users, 17,770 movies 6 years of data: 2000-2005 Test data Last

12、few ratings of each user (2.8 million) Evaluation criterion: root mean squared error (RMSE) Netflix Cinematch RMSE: 0.9514 Competition 2700+ teams $1 million prize for 10% improvement on Cinematch42The Netflix Utility Matrix R43Utility Matrix R: Evaluation44BellKor Recommender SystemNetflix 挑战赛的获胜者对

13、数据的多尺度建模全局特征 Global effects用户/电影的总体偏差区域特征 Regional effectsFactorization局域特征 Local patternCFGlobal effects Factorization Collaborative filtering 45本地及全局特征的模型化全局电影的平均评分：3.7星电影 The Sixth Sense的评分比均值高0.5星用户Joe 的评分比均值低0.2星基本估计（baseline）：Joe对The Sixth Sense评分4星 局域（CF/NN）Joe 不喜欢相关的电影 Signs最终估计：Joe对The Sixt

14、h Sense评分3.8星 46回顾：协同过滤CF最早的最流行的CF方法根据相似的电影推测未知的评分 (item-item variant) 定义i , j 两个item的相似度 sij 选择k个最近邻居，计算ratingN(i; x): 用户x 评价过的与i最接近的项目集合47改进评分估计引入全局偏置量48插入权重值采用加权和代替加权平均值(;) ：用户 x 评价过的类似电影 i 的电影集合 ：插入权重(实数值) 允许 (,) 模拟电影对的关系 (不依赖于用户 x) 49如何确定插入权值误差测度SSE(Sum of Squares)在训练数据上找到令SSE最小的权值 模拟item i与其邻居

15、j 的关系可以根据用户x和评价过i的所有其他用户学习/估计50用最优化求解推荐问题目标：好的推荐用SSE评价优度 SSE最小化对用户未评价过的项目进行好的推荐很难实际实现选择w矩阵, 使其对已知的 (user, item) rating的最优期望此w对未知的rating 也有好的预测性能如何确定w的取值？思路：确定目标函数，求解最优化问题在训练数据上找到使SSE最小的wij51梯度下降法求解最优的wIterate until convergence: where is gradient (derivative evaluated on data): Nabla目标：最小化SSE5253求解（学

16、习）权值小结求解权值基于角色确定权重wij取值，不用任意的相似度显式地考虑相邻电影的相互关系下一步： LFM提取区域关系54LFM55LFMR Q PTR有一些缺失项，暂时忽略现在的目标是对已知的评分重建误差最小可以近似视为“SVD (Singular Value Decomposition)”SVD: A = U VT56评分 = Factor的乘积如何估计缺失的用户x对项目i的评分值？57评分 = Factor的乘积如何估计缺失的用户x对项目i的评分值？2.458Latent Factor Model59Latent Factor Model60回顾：SVDSVDNetflix data上

17、 A=R，Q=U， PT=VTR还有缺失项61LFM有缺失项的情况下不能直接用SVD 确定 P, Q 的方法P, Q 的列不一定正交或者等长P, Q 是 users/movies 到潜在空间的映射Netflix参赛队中最常用的方法62Factor的数量目标：对不可见的测试数据最小化SSE思想： 在训练数据上最小化SSE Want large f (# of factors) to capture all the signals But, SSE on test data begins to rise for f 2 Regularization is needed! Allow rich mo

18、del where there are sufficient data Shrink aggressively where data are scarce 63梯度下降找到最优的矩阵P和Q, 满足Iterative optimizer64随机梯度下降6566随机梯度下降 SGD6768LFM中引入偏差因素Baseline 预测： 根据统计平均和用户及项目偏差，直接估计用户x对电影i的评分预测总的评价均值 , 用户x的偏差 bx ,项目i的偏差 bi在LFM中引入baseline predictionBaseline69适应新模型70717273747576启示:增加数据利用所有数据不要试图减少数据规模，让