netflixprize中的协同过滤算法.ppt

Netflix Prize 中的协同过滤算法,吴金龙导师：鄂维南、李铁军,2010-05-28,目录,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,2,Part I：背景介绍推荐系统Netflix Prize协同过滤（Collaborative Filtering）问题Part II：协同过滤（Collaborative Filtering）模型评分预测模型模型组合方法Part III：三维协同过滤：立方填补应用背景评分预测模型Part IV：总结与展望,Part I：背景介绍,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,3,推荐系统Netflix Prize协同过滤（Collaborative Filtering）问题,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,4,Yep，推荐系统!,Part I：背景介绍推荐系统,依据信息检索的方式，互联网的发展可分为三个阶段门户网站阶段，典型代表为 Yahoo为互联网上的重要信息提供导航搜索引擎阶段，典型代表为 Google依据用户输入的关键词，返回给用户与关键词相关的网页个性化推荐阶段依据用户的特点和需求，为用户提供个性化的服务推荐系统作用利用历史，预测现在与未来常用领域传统的零售行业互联网行业搜索引擎：Google电子商务：Amazon社会化网络服务（SNS）：Facebook,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,5,推荐系统的分类,Part I：背景介绍推荐系统,基于内容的过滤（content-based filtering，简记为 CBF）根据事先抽取出的产品或用户特征产生推荐主要缺点需要预处理产品以得到代表它们的特征无法发现用户并不熟悉但具有潜在兴趣的产品种类协同过滤（collaborative filtering，简记为 CF）收集用户过去的行为以获得其对产品的显式或隐式信息优点不需要预处理产品或用户的特征，故而不依赖于特定的应用领域主要缺点冷启动：对于新用户或新产品，无法产生可靠推荐可扩展性：算法往往需要较大的时间和空间复杂度两者的组合（hybrid）组合上面两种方法，以克服它们各自的缺点，并融合它们特有的优点,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,6,Netflix Prize 介绍,Part I：背景介绍Netflix Prize,Netflix：美国一家提供在线电影租赁服务的公司2006年10月，Netflix建立了Netflix Prize竞赛，并对外发布了一个电影评分（评分为1,5的整数）数据集Netflix Prize竞赛最终的目标是在Cinematch推荐系统的基础上获得10%的改进，其预测精度由均方根误差（RMSE）来衡量：Grand Prize，奖金为一百万美元第一个达到10%改进的参赛团队Progress Prize，奖金为五万美元每年排名第一的参赛团队,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,7,Netflix Prize 数据集的结构,Part I：背景介绍Netflix Prize,给出了整体训练数据集（WTS）中的评分值及对应的评分时间参赛团队提交整个Qualifying Set上的预测评分值,Complete Netflix PrizeDataset,480,189个用户17,770部电影,First Part of TrainingSet(FPTS),99,072,112个评分,Held OutSet(HOS),4,225,526个评分,Whole TrainingSet(WTS),100,480,507个评分,ProbeSet,QuizSet,TestSet,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,8,Netflix Prize 竞赛的里程碑,Part I：背景介绍Netflix Prize,2009年6月26日团队BellKors Pragmatic Chaos(BPC)的提交在Quiz Set上获得0.8558的预测误差，改进首次超过10%，竞赛进入最后三十天角逐2009年9月10日Netflix Prize官方正式宣布BPC为竞赛的最终胜利者，获得Grand Prize，整个竞赛正式结束已颁发的奖项及获奖团队,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,9,Netflix Prize 数据集的特点,Part I：背景介绍Netflix Prize,极度稀疏性WTS 中包括了480,189个用户对17,770部电影的评分，而评分值只有100,480,507个，也即近99%的评分值未知长尾性大部分用户只对极少的电影进行了评分四分之一的用户只对少于36部电影进行了评分大部分电影只收到极少的用户评分四分之一的电影只收到少于190个用户的评分时间性数据集中评分的特点随着时间的变化在不断变化,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,10,Ha，协同过滤（CF）?,Part I：背景介绍推荐系统,矩阵填补问题给定矩阵的少部分元素，预测其它未知元素的值E.Cands et al.(Found.of Comput.Math.,2008;SIAM J.on Optimization,2008;Proc.of IEEE,2009;)探讨了矩阵填补的理论和算法但他们的算法目前还无法应用于实际数据集,Part II：协同过滤（Collaborative Filtering）模型,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,11,常用模型邻居（kNN）模型受限玻尔兹曼机（RBM）模型因子模型矩阵分解（MF）模型二项矩阵分解（BMF）模型修正模糊聚类（MFCM）模型模型组合方法,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,12,常用模型,Part II：CF模型常用模型,邻居（kNN）模型（R.Bell et al.,ICDM,2007;G.Takcs et al.,SIGKDD,2007;）根据相似用户对此电影的评分（或此用户对相似电影的评分）获得推荐特点易于编程实现好的可解释性空间复杂度很高受限玻尔兹曼机（RBM）模型（R.Salakhutdinov et al.,ICML,2007）一层隐藏单元（hidden units）H代表用户特征一层可视化单元（visible units）R代表评分特点好的预测精度时间复杂度很高,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,13,因子（Factor）模型,Part II：CF模型Factor,因子模型假设（R.Bell）每个用户和电影都可由少数若干个因子来刻画当一个用户和某部电影的因子向量相匹配时，此用户会对该部电影给予高的评分原始因子模型（通常称为矩阵分解模型）的表达式为其中 和 分别为用户和电影的潜在因子矩阵上述表达式是奇异值分解的一种简化形式,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,14,因子（Factor）模型的特点,Part II：CF模型Factor,因子模型 vs.邻居模型因子模型可以获得更高的预测精度因子模型 vs.受限玻尔兹曼机模型因子模型需要更少的训练时间,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,15,矩阵分解（MF）模型,Part II：CF模型Factor MF,矩阵分解模型（Matrix Factorization，简记为MF）可以看成是一种有向图模型（D.Lin ICML,2008）,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,16,矩阵分解（MF）的模型假设,Part II：CF模型FactorMF,用户和电影的因子向量各自满足正态分布且相互独立用户u 对电影m 的评分随机变量 满足均值为，方差为 的正态分布以上的正态分布对于不同的 u 或 m 是相互独立的,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,17,矩阵分解（MF）模型假设的不合理性,Part II：CF模型FactorMF,MF假设在给定因子向量时，用户 u 对电影 m 的评分变量满足正态分布此假设对于离散协同过滤（CF）问题并不合理例如，对于Netflix Prize问题，真实的评分只在1,2,3,4,5内使用多项分布表示评分（Marlin,NIPS,2003;masters thesis,2004）但多项分布的各个取值之间是无序的，它可能是多峰的（multimodal）的我们建议使用二项分布表示评分（J.Wu,ICDM,2009）,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,18,二项矩阵分解（Binomial MF）,Part II：CF模型FactorBMF,使用二项分布表示评分的直观意义对于Netflix Prize问题，用户可以给予一部电影1至5颗用户以某个固定的喜好程度把每颗星星放入两篮（“喜爱”与“不喜爱”）中的其中一个其中的喜好程度与相应的用户和电影有关最终获得的评分即满足二项分布，如上图中评分为 3,喜 爱,不 喜 爱,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,19,二项矩阵分解（BMF）的模型假设,Part II：CF模型FactorBMF,用户和电影的因子向量各自满足正态分布且相互独立用户u 对电影m 的评分随机变量 满足二项分布其中的S为界定允许评分范围的定值（对于Netflix Prize问题，S=5），而偏好参数,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,20,二项矩阵分解（BMF）的模型训练,Part II：CF模型FactorBMF,BMF中因子P和Q的对数后验分布为使用两种方法最大化此后验分布或数据似然梯度上升法（Gradient Ascent）BMF算法变分EM法（Variational EM）PBMF算法算法的具体过程见博士论文P56-60 或 J.Wu(ICDM,2009),吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,21,实验结果：算法MF vs.算法BMF,Part II：CF模型Factor实验结果,当固定因子数K=40，惩罚系数分别为0.025和0.0015时，算法MF和BMF获得的预测误差见下表对于两个算法，更小的学习率都可以产生更低的预测误差，但同时算法的收敛速度也变得更慢逐渐降低学习率经过77次迭代后算法BMF的Probe RMSE降至0.9098具体过程见博士论文P70-71 或 J.Wu(ICDM,2009),吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,22,实验结果：算法PMF vs.算法PBMF,Part II：CF模型Factor实验结果,当因子数K 取不同值时，算法PMF和PBMF获得的 Probe RMSE随着迭代步数的变化图,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,23,MF和BMF模型的优势与劣势,Part II：CF模型Factor,优势程序容易实现较低的时间和空间复杂度（使用梯度上升法求解）可以获得很好的预测精度劣势推荐结果没有很好的可解释性结果中的用户和电影因子到底是什么,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,24,MF模型 vs.Fuzzy C-means模型,Part II：CF模型FactorMFCM,较之MF模型的因子解释，聚类思想更被人认可典型的聚类模型包括k-means和fuzzy c-means（FCM）聚类模型在Netflix Prize上不能获得很高的预测精度能否构造单一模型，使得它拥有MF模型的精度，并具有聚类模型好的可解释性具体地说，如何组合MF模型和FCM模型,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,25,Fuzzy C-means（FCM）聚类模型介绍,Part II：CF模型FactorMFCM,FCM最小化目标函数（D.Lin k=1,.,K）：在获得了模型参数值后，使用下式获得预测评分,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,26,修正模糊聚类（Modified FCM）模型,Part II：CF模型FactorMFCM,如何改进FCM既然最终使用 获得预测评分，为什么不直接最小化训练数据集上的预测误差相比于FCM的目标函数，一个更加直接且自然的目标函数为其中 Z 为概率矩阵，满足 Z 0，且 Z1=1。修正模糊聚类（MFCM）模型求解优化问题,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,27,FCM模型 vs.MFCM模型,Part II：CF模型FactorMFCM,如果取FCM目标函数中的指数参数=2，并取其中的范数为2-范数，则目标函数而MFCM的目标函数可以写为MFCM不能使用交替更新中心C和概率Z的方法进行求解使用（非）零动量梯度下降法求解MFCM使用两种方法处理其中的约束条件惩罚处理约束方法 MFCM1算法指数融入约束方法 MFCM2算法具体算法见博士论文P64-66 或 J.Wu&T.Li(2nd Netflix-KDD Workshop,2008),吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,28,MF模型 vs.MFCM模型,Part II：CF模型Factor实验结果,当因子数K=40，算法MF和MFCM1的惩罚系数=0.025，而算法MFCM2的惩罚系数=0.0002且对应的动量=0.85时，各个算法获得的预测误差见下表结果表明算法MFCM1的预测精度高于MF，但MFCM1最终获得的概率矩阵并不严格满足约束条件算法MFCM2的预测精度低于MF，但MFCM2最终获得的概率矩阵严格满足约束条件,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,29,MF模型 vs.MFCM模型,Part II：CF模型Factor实验结果,类似于MF算法，对于更小的学习率，MFCM1和MFCM2算法获得更低的预测误差，但同时收敛速度也变得更慢同样可以使用逐渐降低学习率的方法在更少的迭代次数中获得更高的预测精度具体见 J.Wu&T.Li(2nd Netflix-KDD Workshop,2008),吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,30,模型组合方法,Part II：CF模型模型组合方法,单个模型通常只考虑可以产生推荐的因素中的某个方面邻居模型只考虑评分数据中的局部作用因子模型只考虑评分数据中的全局作用组合多个模型的预测结果以便同时考虑多种因素,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,31,组合方法的基本框架,Part II：CF模型模型组合方法,训练利用FPTS分别训练各个模型；记第k个模型对Probe Set的预测评分为，并记把Probe Set放回FPTS，使用WTS重新训练每个模型（训练过程中所使用的模型参数完全同上一步）；记第k个模型对Qualifying Set的预测评分为，并记组合利用各个模型获得的Probe Set上的预测评分X以及Probe Set上的真实评分b，训练模型组合方法f()；最终获得Qualifying Set上的组合预测评分f(Y),First Part of TrainingSet(FPTS),ProbeSet,QuizSet,TestSet,First Part of TrainingSet(FPTS),ProbeSet,Qualifying Set,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,32,组合模型预测结果的常用方法,Part II：CF模型模型组合方法,线性回归简单线性回归即 f(X)=X，其中回归系数可以通过最小化如下目标函数获得：也即分片线性回归把X中的评分按照某种规则进行分片，然后在每片中使用简单线性回归通常使用评分支持度进行分片神经网络其输出层只有一个神经单元其他预测模型,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,33,实验结果,Part II：CF模型模型组合方法,我们选出93个模型预测结果，这些结果来源于邻居模型（12个）受限玻尔兹曼机模型（15个）因子模型（41个）聚类模型（7个）几个模型的（序贯）组合结果（18个）使用简单线性回归方法组合这93个预测结果，最终的组合预测评分在Probe Set上的RMSE为0.8717 在Quiz Set上的RMSE为0.8747这93个模型名称具体见博士论文P84-85,Part III：三维协同过滤立方填补,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,34,立方填补的实际应用立方填补模型邻居（kNN）模型贝叶斯聚类（Bayesian Clustering）模型立方聚类（Cube Clustering）模型立方分解（Cube Factorization）模型实验结果,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,35,三维协同过滤：立方填补,Part III：立方填补,从数学上来讲，二维的协同过滤问题是矩阵填补问题把矩阵填补扩展至三维的立方填补（Cube Completion）现实中存在立方填补的应用吗存在！,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,36,实际应用1个性化网页搜索,Part III：立方填补实际应用,关键词,网页,用户,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,37,实际应用2个性化广告投放,Part III：立方填补实际应用,用户,产品,广告,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,38,术语和记号,Part III：立方填补,记三个维度分别为X、Y和Z统称三个维度上的事物为对象记三个维度上的对象数量分别记为I、J 和K只考虑评分取二态值，即0或1,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,39,邻居（kNN）模型,Part III：立方填补KNN,难以应用：已知评分过于稀疏（2 X 10-4）无法获得可靠的相似度,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,40,贝叶斯聚类（Bayesian Clustering）模型,Part III：立方填补BC,贝叶斯聚类（BC）模型是一种图模型，它假设每个方向上的对象都可以被聚类,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,41,贝叶斯聚类（BC）的模型假设,Part III：立方填补BC,假设每个方向上的对象分别来源于不同的类别而评分只依赖于相应对象所属的类别具体模型训练方法见博士论文P90-92,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,42,立方聚类（Cube Clustering）模型,Part III：立方填补CC,立方聚类（CC）模型使用联合聚类（Co-clustering,I.Dhillon et al.,SIGKDD,2003）的思想，同时聚类不同维度上的对象它的目标函数为其中 表示 X 方向上的第 i 个对象所属的类别通过迭代更新对象的类别标识及其喜好参数 最小化此目标函数具体更新方法见博士论文P93-95,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,43,立方分解（Cube Factorization）模型,Part III：立方填补CF,Lathauwer et al.(SIAM J.Matrix Anal.Appl.,2000)把二维的奇异值分解方法推广至高维一个三阶张量 R，它的第(i,j,k)个元素可以表达为其中 X、Y 和 Z 为酉矩阵，而 C 为满足全正交条件的三阶张量,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,44,立方分解（Cube Factorization）模型,Part III：立方填补CF,把二维情形下的矩阵分解（MF）模型推广至三维情形，得到立方分解（Cube Factorization）模型立方分解模型的目标函数为：和二维情形类似，可以使用梯度下降法最小化此目标函数具体算法见博士论文P96-97,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,45,贝叶斯聚类&立方聚类&立方分解,Part III：立方填补实验结果,验证三个模型对数据稀疏度的敏感性实验数据根据模型的假设抽取得到具体抽取步骤见论文P99与P102抽取数据时所使用的参数值见下表,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,46,贝叶斯聚类的实验结果,Part III：立方填补实验结果,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,47,立方聚类的实验结果,Part III：立方填补实验结果,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,48,立方分解的实验结果,Part III：立方填补实验结果,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,49,贝叶斯聚类&立方聚类&立方分解,Part III：立方填补实验结果,在训练集稀疏程度不太严重时贝叶斯聚类和立方聚类都获得了与最优预测模型相近的预测误差在训练集稀疏程度严重时贝叶斯聚类比立方聚类获得更好的预测精度但贝叶斯聚类所需的计算复杂度也更大最优预测（Optimal）的预测效果比立方分解更差在生成数据集时，对非整数评分使用了强制取整（以0.5作为分界点截断）策略与贝叶斯聚类和立方聚类模型结果不同立方分解模型的预测误差随着数据稀疏程度的加剧缓慢增加,Part IV：总结与展望,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,50,总结展望协同过滤（Collaborative Filtering）中尚待解决的一些问题,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,51,总结,Part IV：总结与展望,发展了因子模型使用更加合理的二项分布假设：BMF模型结合MF模型的预测精度以及FCM模型的可解释性：MFCM模型组合了 93 个模型结果最终的组合预测评分在Probe Set上的RMSE为0.8717，而在Quiz Set上的RMSE为0.8747把二维的协同过滤推广至三维的立方填补构造了一些有效的算法在人造数据上对这些算法进行了检验,吴金龙 SMS(2010-05-28),Netflix Prize 中的协同过滤算法,52,展望：协同过滤中尚待解决的一些问题,Part IV：总结与展望,算法理论依据的缺乏目前的主要研究集中在发展实用的推荐算法从理论上来讲，矩阵填充在什么条件下真的可以实现评分的非随机缺失性协同过滤问题中的评分缺失并不满足随机缺失性数据的稀疏性如何收集和利用更多有用的用户使用数据（如隐式信息）算法的可扩展性如何降低模型的训练时间如何并行化一些经典算法（如SVD）与基于内容的过滤（CBF）算法的组合如何更加高效地实现它们之间的组合,|_|_|_|_|_|_|_|_|_|,_ _ _ _ _ _ _ _ _ _ _ _ _ _ _,A,