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

1、第九章第九章 推荐系统推荐系统郭宇春郭宇春1 推荐系统模型推荐系统模型 基于内容的推荐基于内容的推荐 协同过滤协同过滤 潜在因素模型潜在因素模型2推荐系统模型推荐系统模型3从稀缺到丰富：推荐的需求从稀缺到丰富：推荐的需求 传统零售商的传统零售商的货架空间是稀货架空间是稀缺资源缺资源 还包括还包括: TV networks, movie theaters, 网络网络使零使零成本成本产品信息产品信息传播传播成为可能成为可能 从稀缺到从稀缺到丰富丰富The Long TailRhapsody：online music serviceWal-Malt: offline supermarketPhysi

2、cal vs Online5Read http:/ to learn more! 推荐推荐6ItemsItems搜索搜索推荐推荐Products, web Products, web sites, blogs, news sites, blogs, news items, items, 推荐类型推荐类型 编辑编辑 收藏列表收藏列表 要目列表要目列表 简单汇聚简单汇聚 Top 10,最流行最流行, 最新上载最新上载 为每个用户定制为每个用户定制 Amazon, Netflix, 严格模型严格模型 X 用户集用户集 S 项目集项目集 效用矩阵效用矩阵 Utility Matrix 效用函数效用函数

3、 Utility function u: R 评分集评分集 , 完全有完全有序集序集 例如例如, 0-5 星星, 0,1之间的实数之间的实数 关键问题关键问题1. 收集已知评分形成收集已知评分形成R矩阵矩阵 如何收集效用矩阵中的数据如何收集效用矩阵中的数据2. 根据已知的评根据已知的评分分推断未知的评分推断未知的评分 主要对未知的高评分感兴趣，只关心用户喜欢主要对未知的高评分感兴趣，只关心用户喜欢什么什么3. 评估推断方法评估推断方法 如何衡量推荐方法的性能如何衡量推荐方法的性能评分的收集评分的收集 显式评价显式评价 要求要求用户对项目给出评分用户对项目给出评分 实际中不太可行实际中不太可行困

4、扰用户困扰用户 隐式评价隐式评价 从用户的行为中学习其评分从用户的行为中学习其评分 e.g., 购买意味着高评分购买意味着高评分 什么代表低评分呢什么代表低评分呢?效用的推断效用的推断 关键问题关键问题: 效用矩阵效用矩阵U稀疏稀疏 大多数人没有评价过大多数项目大多数人没有评价过大多数项目 冷启动冷启动 新的项目没有评分新的项目没有评分 新的用户没有历史新的用户没有历史 3种方法种方法 基于内容基于内容 Content-based 协同过滤协同过滤 Collaborative Filtering 基于潜在因素（隐变量）基于潜在因素（隐变量）Latent factor based基于内容的推荐系

5、统基于内容的推荐系统12基于内容的推荐基于内容的推荐 主要思想主要思想: 向用户向用户 C 推荐与她评分高（喜欢）推荐与她评分高（喜欢）项目相类似的项目项目相类似的项目例子：例子： 电影推荐电影推荐 推荐相同演员、导演、流派推荐相同演员、导演、流派 Websites, blogs, news 推荐类似内容的网页推荐类似内容的网页13推荐的过程推荐的过程项模型项模型 item profile 对每个项目建立一份对每个项目建立一份 item profile Profile 是特征是特征features的集合的集合 movies: author, title, actor, director, te

6、xt: set of “important” words in document 文本特征文本特征关键词关键词 常用的启发式方法是常用的启发式方法是 TF.IDF (Term Frequency times Inverse Doc Frequency) 非文本项目特征非文本项目特征困难困难 邀请用户进行标记邀请用户进行标记Tag（词语、（词语、短语短语） Sunset at Malibu Tiananmen squareRecap：TF.IDFfij 文档文档 j 中词项中词项i 出现的频次出现的频次ni = 包含词项包含词项i的文档数的文档数N = 文档数文档数TF.IDF分值分值 wij

7、= TFij IDFiDoc profile = 有最高有最高 TF.IDF 值的词汇及其对应分值的词汇及其对应分数的集合数的集合Note: we normalize TF to discount for “longer” documents 用户模型用户模型User profiles User profile： 反映用户的特征偏好反映用户的特征偏好 根据项模型统计根据项模型统计 用户评过项目的项目用户评过项目的项目profile加权平均加权平均 启发式预测启发式预测 给定用户模型给定用户模型 x，项目模型，项目模型 i, 估计用户估计用户x对于项对于项目目 i 的效用值的效用值基于内容方法的

8、基于内容方法的优点优点 不需要其他用户的数据不需要其他用户的数据 没有冷启动或者稀疏性的问题没有冷启动或者稀疏性的问题 能给品味一致的用户推荐能给品味一致的用户推荐 能给新项目或不流行项目推荐能给新项目或不流行项目推荐 没有第一个评价者的问题没有第一个评价者的问题 能够提供解释能够提供解释 可以对推荐项目给出对应的内容特征描述可以对推荐项目给出对应的内容特征描述18基于内容方法的基于内容方法的缺点缺点 找到适当的特征是困难的找到适当的特征是困难的 e.g., images, movies, music 过度集中过度集中 不会推荐用户内容偏好模型之外的项目不会推荐用户内容偏好模型之外的项目 人人

9、们们可能可能有多方面的兴趣有多方面的兴趣 不能利用其它用户的优质判断不能利用其它用户的优质判断 对新用户的推荐对新用户的推荐 如何给新用户建立模型如何给新用户建立模型?19协同过滤协同过滤 COLLABORATIVE FILTERING20协同过滤协同过滤 考虑用户考虑用户x 找到与找到与x有相似评分有相似评分的用户集合的用户集合 N 根据根据N中用户的评中用户的评分估计分估计 x的评分的评分21相似的用户相似的用户 令令 rx 为用户为用户 x的评分矢量的评分矢量 Jaccard 相似度相似度 问题：忽略了评分的分值问题：忽略了评分的分值 余弦相似度余弦相似度 Cosine similari

10、ty measure 问题：将缺失项目视为问题：将缺失项目视为“否定否定” 皮尔森相关系数皮尔森相关系数 Pearson correlation coefficient Sxy = 用户用户 x 和用户和用户 y共同评价过的项目集合共同评价过的项目集合缺失缺失 = 否定否定？ 直觉直觉: sim(A, B) sim(A, C) ，但是，但是 Jaccard similarity: 1/5 0.322 (接近接近) 原因：将缺失分量视为原因：将缺失分量视为“否定否定” （取（取0值，意味最低评价）值，意味最低评价） 解决措施解决措施: 减去减去(行行)均值均值 中心化中心化23sim A,B v

11、s. A,C: 0.092 -0.559 注意：cosine sim. 在以零为中心时，就是相关系数评分预测评分预测 rx ：为用户：为用户 x的评分矢量的评分矢量 N： 为对项目为对项目 i的评分与用户的评分与用户x最相似的最相似的 k 个用户个用户的集合的集合 用户用户x对项目对项目 s的评分预测的评分预测其他方法其他方法?基于项目的协同过滤基于项目的协同过滤 Item-Item CF 除了除了user-user，有另一个角度：，有另一个角度：item-item 对项目对项目i, 寻找其他相似的项目寻找其他相似的项目 根据相似项目的评分估计项目根据相似项目的评分估计项目i的评分的评分 可以

12、采用类似可以采用类似 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的优缺点的优缺点 适合于任何适合于任何item 不需要特征选择不需要特征选择

13、 Cold Start: 需要系统中有足够的用户进行匹配需要系统中有足够的用户进行匹配 稀疏性稀疏性: ratings 矩阵稀疏矩阵稀疏 ， 难以发现评价过相同项目的用户难以发现评价过相同项目的用户 第一个评价者第一个评价者 无法推荐一个没有被评价过的项目，无法推荐一个没有被评价过的项目， 新项目新项目, 隐秘项目隐秘项目 流行度偏差流行度偏差 无法给只有单一口味的用户推荐项目无法给只有单一口味的用户推荐项目 倾向于推荐流行项目倾向于推荐流行项目混合方法混合方法 实现两种或多种不同的推荐方法，并组合实现两种或多种不同的推荐方法，并组合预测结果预测结果 比如用线性组合比如用线性组合 将基于内容的

14、方法与将基于内容的方法与CF相结合相结合 建立建立item profile 解决新解决新item问题问题 利用人口统计信息解决新用户问题利用人口统计信息解决新用户问题评估及实际问题评估及实际问题353637评估预测性能评估预测性能 对比预测值与已知的评分对比预测值与已知的评分 Root-mean-square error (RMSE) Precision at top 10 Rank correlation 另一种方法另一种方法: 0/1 model 覆盖度覆盖度 系统能够预测的系统能够预测的items/users 数量数量 精确度精确度 预测的精度预测的精度 受试者工作特征受试者工作特征Re

15、ceiver operating characteristic (ROC) 虚报率虚报率 false positives 与漏报率与漏报率false negatives之间的均衡曲线之间的均衡曲线错误测度的问题错误测度的问题 有时狭隘有时狭隘地关注地关注精度没有精度没有意义意义 Prediction Diversity 预测多样性预测多样性 Prediction Context 预测情境预测情境 Order of predictions 预测顺序预测顺序 实际上仅仅关注对高分的预测实际上仅仅关注对高分的预测 RMSE 可能会对一个高分预测好低分预测差的可能会对一个高分预测好低分预测差的方法不利

16、方法不利CF：复杂度：复杂度 最费时的步骤是找到最费时的步骤是找到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,

17、480,000 users, 17,770 movies 6 years of data: 2000-2005 Test data Last 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 R43U

18、tility Matrix R: Evaluation44BellKor Recommender System Netflix 挑战赛的获胜者挑战赛的获胜者 对数据的多尺度建模对数据的多尺度建模 全局特征全局特征 Global effects 用户用户/电影的总体偏差电影的总体偏差 区域特征区域特征 Regional effects Factorization 局域特征局域特征 Local pattern CF45Global effects Factorization Collaborative filtering 本地及全局特征的模型化本地及全局特征的模型化 全局全局 电影的平均评分：电影

19、的平均评分：3.7星星 电影电影 The Sixth Sense的评分比均值高的评分比均值高0.5星星 用户用户Joe 的评分比均值低的评分比均值低0.2星星基本估计（基本估计（baseline）：）：Joe对对The Sixth Sense评分评分4星星 局域（局域（CF/NN） Joe 不喜欢相关的电影不喜欢相关的电影 Signs最终最终估计：估计：Joe对对The Sixth Sense评分评分3.8星星 46回顾：协同过滤回顾：协同过滤CF 最早的最流行的最早的最流行的CF方法方法 根据相似的电影推测未知的评分根据相似的电影推测未知的评分 (item-item variant) 定义定

20、义i , j 两个两个item的相似度的相似度 sij 选择选择k个最近邻居，计算个最近邻居，计算rating N(i; x): 用户用户x 评价过的与评价过的与i最接近的项目集合最接近的项目集合47改进评分估计改进评分估计 引入全局偏置量引入全局偏置量48插入权重值插入权重值 采用加权和代替加权平均值采用加权和代替加权平均值(;) ：用户：用户 x 评价过的类似电影评价过的类似电影 i 的电影的电影集合集合 ：插入权重：插入权重(实数值实数值) 允许允许 (,) 模拟电影对的关系模拟电影对的关系 (不依赖于用户不依赖于用户 x) 49如何确定插入权值如何确定插入权值 误差测度误差测度SSE(

21、Sum of Squares) 在训练数据上找到令在训练数据上找到令SSE最小的权值最小的权值 模拟模拟item i与其邻居与其邻居j 的关系的关系 可以根据用户可以根据用户x和评价过和评价过i的所有其他用户学的所有其他用户学习习/估计估计50用最优化求解推荐问题用最优化求解推荐问题 目标：好的目标：好的推荐推荐 用用SSE评价优度评价优度 SSE最小化最小化 对用户未评价过的项目进行好的推荐对用户未评价过的项目进行好的推荐很难很难实际实际实现实现 选择选择w矩阵矩阵, 使其对已知的使其对已知的 (user, item) rating的最优的最优 期望此期望此w对对未知的未知的rating 也

22、有好的预测性能也有好的预测性能 如何确定如何确定w的取值？的取值？ 思路：确定目标函数，求解最优化问题思路：确定目标函数，求解最优化问题 在训练数据上找到使在训练数据上找到使SSE最小的最小的wij51梯度下降法求解最梯度下降法求解最优优的的w Iterate until convergence: where is gradient (derivative evaluated on data): 52Nabla目标：最小化目标：最小化SSE53求解（学习）权值求解（学习）权值小结小结 求解权求解权值值 基于角色确定权重基于角色确定权重wij取值，取值，不用任意的相似度不用任意的相似度 显式地考

23、虑相邻电影的相显式地考虑相邻电影的相互关系互关系 下一步：下一步： LFM 提取区域关系提取区域关系54LFM55LFM R Q PT R有一些缺失项，暂时忽略有一些缺失项，暂时忽略 现在的目标是对已知的评分重建误差最小现在的目标是对已知的评分重建误差最小 可以近似视为可以近似视为“SVD (Singular Value Decomposition)”56SVD: A = U VT评分评分 = Factor的乘积的乘积 如何估计缺失的用户如何估计缺失的用户x对项目对项目i的的评分值？评分值？57xiixiffxfrqpqp评分评分 = Factor的乘积的乘积 如何估计缺失的用户如何估计缺失的

24、用户x对项目对项目i的的评分值？评分值？58xiixiffxfrqpqp2.4Latent Factor Model59Latent Factor Model60回顾：回顾：SVD SVD Netflix data上上 A=R，Q=U， PT= VT R还有缺失项还有缺失项61LFM62 有缺失项的情况下不能直接用有缺失项的情况下不能直接用SVD 确定确定 P, Q 的方法的方法 P, Q 的列不一定正交或者等长的列不一定正交或者等长 P, Q 是是 users/movies 到潜在空间的映射到潜在空间的映射 Netflix参赛队中最常用的方法参赛队中最常用的方法Factor的数量的数量 目标：对不可见的测试数据最小化目标：对不可见的测试数据最小化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 ne