实时推荐系统的3种方式

标签: 实时 推荐系统 | 发表时间:2016-03-24 10:18 | 作者:
出处:http://m635674608.iteye.com

推荐系统介绍

自从1992年施乐的科学家为了解决信息负载的问题,第一次提出协同过滤算法,个性化推荐已 经经过了二十几年的发展。1998年,林登和他的同事申请了“item-to-item”协同过滤技术的专利,经过多年的实践,亚马逊宣称销售的推荐占比 可以占到整个销售GMV(Gross Merchandise Volume,即年度成交总额)的30%以上。随后Netflix举办的推荐算法优化竞赛,吸引了数万个团队参与角逐,期间有上百种的算法进行融合尝试, 加快了推荐系统的发展,其中SVD(Sigular Value Decomposition,即奇异值分解,一种正交矩阵分解法)和Gavin Potter跨界的引入心理学的方法进行建模,在诸多算法中脱颖而出。其中,矩阵分解的核心是将一个非常稀疏的用户评分矩阵R分解为两个矩阵:User特 性的矩阵P和Item特性的矩阵Q,用P和Q相乘的结果R'来拟合原来的评分矩阵R,使得矩阵R'在R的非零元素那些位置上的值尽量接近R中的元素,通过 定义R和R'之间的距离,把矩阵分解转化成梯度下降等求解的局部最优解问题。Netflix最新的实时推荐系统如图9-5所示。

图9-5 NetFlix的实时推荐系统系统架构图(来源: http://techblog.netflix.com/2013/03/system-architectures-for.html

与 此同时,Pandora、LinkedIn、Hulu、Last.fm等一些网站在个性化推荐领域都展开了不同程度的尝试,使得推荐系统在垂直领域有了不 少突破性进展,但是在全品类的电商、综合的广告营销上,进展还是缓慢,仍然有很多的工作需要探索。特别是在全品类的电商中,单个模型在母婴品类的效果还比 较好,但在其他品类就可能很差,很多时候需要根据品类、推荐栏位、场景等不同,设计不同的模型。同时由于用户、SKU不停地增加,需要定期对数据进行重新 分析,对模型进行更新,但是定期对模型进行更新,无法保证推荐的实时性,一段时间后,由于模型训练也要相当时间,可能传统的批处理的Hadoop的方法, 无法再缩短更新频率,最终推荐效果会因为实时性问题达到一个瓶颈。

推荐算法主要有基于人口统计学的推荐、基于内容的推荐、基于协同过滤的推 荐等,而协同过滤算法又有基于邻域的方法(又称基于记忆的方法)、隐语义模型、基于图的随机游走算法等。基于内容的推荐解决了商品的冷启动问题,但是解决 不了用户的冷启动问题,并且存在过拟合问题(往往在训练集上有比较好的表现,但在实际预测中效果大打折扣),对领域知识要求也比较高,通用性和移植性比较 差,换一个产品形态,往往需要重新构建一套,对于多媒体文件信息特征提取难度又比较大,往往只能通过人工标准信息。基于邻域的协同过滤算法,虽然也有冷启 动问题和数据稀疏性等问题,但是没有领域知识要求,算法通用性好,增加推荐的新颖性,并且对行为丰富的商品,推荐准确度较高。基于模型的协同过滤算法在一 定程度上解决了基于邻域的推荐算法面临的一些问题,在RMSE(Root Mean Squared Error,即均方根误差)等推荐评价指标上更优,但是通常算法复杂,计算开销大,所以目前基于邻域的协同过滤算法仍然是最为流行的推荐算法。

基于邻域的协同过滤主要分为User CF和Item CF,根据以下条件不同,各自又有不同的使用场景。

计算量大小不同。基于邻域的协同过滤的时间复杂度为

, 其中 n为用户数, m为产品数,应用SVD等降维方法可以降低算法复杂度,但是分解矩阵又会花费一定的时间。

数 据稀疏性倾斜度不同。例如,User CF主要基于用户对共同项目的评分,如果用户远远多于物品,没有足够评分将导致两个用户很少有共同评分的项目,找最近邻用户非常的不准确,虽然通过基于 BP神经网络、朴素贝叶斯分类、基于内容的预测等方法可以填充矩阵,但是都会不同程度地带来的计算时间。

对于用户数量远远大于产品,并且产 品相对稳定的电商系统,计算产品相似度计算量小,适用Item CF,否则用户量大,并且如果用户购买频繁,计算用户相似度计算量很大,极端情况下,100个用户对应2个产品,一个要计算C1002次相似度,一个只要 计算C22,即一次相似度;反之,对于更新频繁,物品数量海量的新闻、博客、微博等系统,User CF效果更好。

当然,虽然SVD在分解 矩阵上花费了一定时间,同时降维也会导致用户-项目矩阵中的信息丢失,但是用户-项目矩阵降维后, 运算复杂度大大降低,同时矩阵稀疏性问题得到了较好地解决,作为Netflix比赛中最终提升效果较好的两个方法之一,被众多网站采用。用户-项目矩阵中 的信息丢失问题可以通过选取合适的保留维数 k在一定程度上得到缓解。

在一个电商系统中,有商品、类目、品牌、团购、闪购、搜 索、店铺、广告、促销活动、抵用券等诸多实体;有首页的大轮播、猜你喜欢栏位,详情页的看了还看、看了还买、推荐品牌等栏位,购物车页面的买了还买、凑单 免邮等栏位。如何在不同的栏位融入不同的推荐算法给用户推荐相应的实体,构建出属于电商自己的场景引擎,实现全站精准化,让网站的GMV或者利润达到最 高,是每一个电商需要思考的问题。在实际中,很多推荐算法不一定要求实时,实时推荐在哪些场景下能带给栏位更高的GMV转化率,也是需要一定时间摸索和试 错的。

目前基于用户画像的推荐,主要用在基于内容的推荐,从最近的RecSys大会(ACM Recommender Systems)上来看,不少公司和研究者也在尝试基于用户画像做Context-Aware的推荐(情境感知,又称上下文感知)。利用用户的画像,结合 时间、天气等上下文信息,给用户做一些更加精准化的推荐是一个不错的方向。

 实时推荐系统的方法

目前的商用推 荐系统,当用户数和商品数达到一定数目时,推荐算法都面临严重的可扩展性问题,推荐的实效性变得非常差,如何在算法和架构上提高推荐速度是很多公司不得不 思考的问题。目前,在算法上主要通过引入聚类技术和改进实时协同过滤算法提高推荐速度;在架构上,目前实时推荐主要有基于Spark、Kiji框架和 Storm的流式计算3种方法。

1.聚类技术和实时协同过滤算法

在算法上,一般采用EM(Expectation- Maximization)、K-means、吉布斯(Gibbs Sampling)、模糊聚类等聚类技术提高推荐速度。因为使用聚类技术可以大大缩小用户或项目的最近邻居搜索范围,从而提高推荐的实时性,如表9-1所 示。

除 此之外,实时协同过滤算法本身一直是人们研究的热点,早在2003年,Edward F. Harrington就第一次提出了基于感知器的实时协同过滤算法,但是这种方法需要所有用户的偏好,实用性较差;2010年,杨强等提出了实时进化的协 同过滤算法,给予新得分更高的权重来增量更新User和Item的相似度;2011年,UC Berkeley的Jacob Abernethy等人提出了OCF-SGD算法,我们知道传统的矩阵分解把用户评分矩阵R分解成多个矩阵,比如R≈P*Q,该方法提出当新来一个 User到Item的得分,把更新R矩阵的问题转换成更新P和Q矩阵,从而达到实时协同过滤;近几年的RecSys大会上,实时协同过滤也是讨论的热 点,OCF-SGD算法每次只考虑一个用户,忽略了用户之间的关系,Jialei Wang等人提出了基于多任务学习的实时协同过滤算法,把每一个用户当做一个任务,定义一个表示各个任务间相似性和交互程度的矩阵A,当新来一个User 到Item的得分,通过矩阵A来更新其他用户的得分。

2.基于Spark的方式

在架构上,第一种是使用Spark把模型计算放在内存中,加快模型计算速度,Hadoop中作业的中间输出结果是放到硬盘的HDFS中,而Spark是直接保存在内存中,因此Spark能更好地适用于数据挖掘与机器学习等需要迭代的模型计算,如表9-2所示。

(来源: http://www.csdn.net/article/2014-05-19/2819831-TDW-Shuffle/2

3.基于Kiji框架的方式

第 二种是使用Kiji,它是一个用来构建大数据应用和实时推荐系统的开源框架,本质上是对HBase上层的一个封装,用Avro来承载对象化的数据,使得用 户能更容易地用HBase管理结构化的数据,使得用户姓名、地址等基础信息和点击、购买等动态信息都能存储到一行,在传统数据库中,往往需要建立多张表, 在计算的时候要关联多张表,影响实时性。Kiji与HBase的映射关系如表9-3所示。

Kiji 提供了一个KijiScoring模块,它可以定义数据的过期策略,如综合产品点击次数和上次的点击时间,设置数据的过期策略把数据刷新到 KijiScoring服务器中,并且根据自己定义的规则,决定是否需要重新计算得分。如用户有上千万浏览记录,一次的行为不会影响多少总体得分,不需要 重新计算,但如果用户仅有几次浏览记录,一次的行为,可能就要重新训练模型。Kiji也提供了一个Kiji模型库,使得改进的模型部署到生产环境时不用停 掉应用程序,让开发者可以轻松更新其底层的模型。

4.基于Storm的方式

最后一种基于 Storm 的实时推荐系统。在实时推荐上,算法本身不能设计的太复杂,并且很多网站的数据库是TB、PB级别,实时读写大表比较耗时。可以把算法分成离线部分和实时 部分,利用Hadoop离线任务尽量把查询数据库比较多的、可以预先计算的模型先训练好,或者把计算的中间数据先计算好,比如,线性分类器的参数、聚类算 法的群集位置或者协同过滤中条目的相似性矩阵,然后把少量更新的计算留给Storm实时计算,一般是具体的评分阶段。

基于Storm的实时推荐系统

基于本章前面的学习,我们可以设计图9-6所示的实时推荐系统。

图9-6 实时推荐系统(图片来源PRANAB GHOSH,Big Data Cloud meetup。版权归原书作者所有)

用HBase或HDFS存储历史的浏览、购买行为信息,用Hadoop基于User CF的协同过滤,先把用户的相似度离线生成好,用户到商品的矩阵往往比较大,运算比较耗时,把耗时的运行先离线计算好,实时调用离线的结果进行轻量级的计算有助于提高产品的实时性。

我 们来简单回顾一下协同过滤算法(如图9-7所示):首先程序获取用户和产品的历史偏好,得到用户到产品的偏好矩阵,利用Jaccard相似系数 (Jaccard coefficient)、向量空间余弦相似度(Cosine similarity)、皮尔逊相关系数(Pearson correlation coefficient)等相似度计算方法,得到相邻的用户(User CF)或相似商品(Item CF)。在User CF中,基于用户历史偏好的相似度得到邻居用户,将邻居用户偏好的产品推荐给该用户;在Item CF中,基于用户对物品的偏好向量得到相似产品,然后把这款产品推荐给喜欢相似产品的其他用户。

图9-7 协同过滤算法过程

然后通过Kafka或者Redis队列,保存前端的最新浏览等事件流,在Storm的Topology中实时读取里面的信息,同时获取缓存中用户topN个邻居用户,把邻居用户喜欢的商品存到缓存中,前端从缓存中取出商品,根据一定的策略,组装成推荐商品列表。

当 然除了相似性矩阵,其他模型大体实现也相似,比如实际的全品类电商中不同的品类和栏位,往往要求不同的推荐算法,如母婴产品,如图9-8所示,如果结合商 品之间的序列模式和母婴年龄段的序列模式,效果会比较好,可以把模型通过Hadoop预先生成好,然后通过Storm实时计算来预测用户会买哪些产品。

图9-8 序列模式在母婴类目推荐中的应用

 

 

http://www.epubit.com.cn/article/27



已有 0 人发表留言,猛击->> 这里<<-参与讨论


ITeye推荐



相关 [实时 推荐系统] 推荐:

实时推荐系统的3种方式

- - zzm
自从1992年施乐的科学家为了解决信息负载的问题,第一次提出协同过滤算法,个性化推荐已 经经过了二十几年的发展. 1998年,林登和他的同事申请了“item-to-item”协同过滤技术的专利,经过多年的实践,亚马逊宣称销售的推荐占比 可以占到整个销售GMV(Gross Merchandise Volume,即年度成交总额)的30%以上.

使用implicit搭建实时推荐系统

- - 标点符
Implicit是一个开源的系统过滤项目,其包含多种流行的推荐算法,主要应用场景是针对隐性反馈行为进行推荐. ALS(alternating least squares),最小交替二乘法. BRP(Bayesian Personalized Ranking),贝叶斯个性化排序. 使用Cosine, TFIDF 或 BM25的近邻模型.

Min-Hash和推荐系统

- - xlvector - Recommender System
前几年看Google News Recommendation的那篇Paper,对里面提到的MinHash的算法基本没有注意,因为之前的习惯都是只注意论文的模型那块,至于怎么优化模型一般都只是扫一眼. 不过最近看了大量的Google Paper,发现Google在实现一个算法方面确实有很多独到之处. 其实,Min-Hash是LSH(Locality Sensitive Hash)的一种,我之前对LSH的了解仅仅限于知道它能把两个相似的东西Hash成两个汉明距离接近的2进制数.

推荐系统实战

- - 博客园_首页
推荐算法:基于特征的推荐算法. 推荐算法准确度度量公式:. 其中,R(u)表示对用户推荐的N个物品,T(u)表示用户u在测试集上喜欢的物品集合. 集合相似度度量公式(N维向量的距离度量公式):. 其中,N(u)表示用户u有过正反馈的物品集合. 其中,S(u,k)表示和用户u兴趣最接近的K个用户集合;N(i)表示对物品i有过正反馈的用户集合;w(u,v)表示用户u和用户v的兴趣相似度;r(v,i)表示用户v对物品i的兴趣.

推荐系统杂谈

- - 后端技术杂谈 | 飒然Hang
推荐系统是近些年非常火的技术,不管是电商类软件还是新闻类app,都号称有精准的推荐系统能给你推送你最感兴趣的内容. 现象级的资讯类app“今日头条”就得益于此成为了势头非常猛的一款产品. 本文就针对推荐系统讲述一些相关概念和实践经验. 首先需要明确的就是推荐系统的目标,一般来说不外乎以下几个:. 用户满意性:首当其冲的,推荐系统主要就是为了满足用户的需求,因此准确率是评判一个推荐系统好坏的最关键指标.

个性化推荐系统综述

- Tony - 所有文章 - UCD大社区
上个月写过一篇产品推荐的文章,详情请见《我所了解的产品推荐》,内容很泛,多为工作心得. 本周读了几篇相关的论文,收获颇多,分享点干货. 以下内容摘自《个性化推荐系统的研究进展》,该文发表于2009年1月的《自然科学进展》专题评述,作者是刘建国、周涛、汪秉宏. 我略去了具体的算法和许多公式,重点看原理、思路和比较.

推荐系统开源工具 – SVDFeature

- Roger - Resys China
SVDFeature是我们(上海交大Apex实验室)在参加KDDCUP 2011期间开发的. 通过这个工具,我们和港科大(HKUST)的联合小组InnerPeace在KDDCUP 2011中获得Track 1第三名,并创造单模型最好成绩. 在此分享给大家,并希望和大家有更多的交流. (1)基于feature的可扩展性 —— SVDFeature实现了我们的基础模型feature-based matrix factorization.

Reculike : 开源论文推荐系统

- votis - Resys China
今天这篇博文主要总结一下reculike的系统架构. 两周前我们宣布发布了reculike的alpha版. 本着分享的原则,今天在这儿介绍一下我们的各个模块的设计方法. 我们这个项目一开始叫paperlens,这是因为我们想学习业界的前辈movielens,开发一个源代码和数据都开源的系统. 关于数据的开源,我想当用户数达到一定程度后,每个月会dump一次我们所有的数据库(密码等隐私信息除外),放到网络上供大家下载.

推荐系统那些事儿1

- - 冰火岛
知识库:用户知识库,Item知识库,用户评分数据(显性和隐性)等.不同的业务背景不一样,譬如电商,社交网络,视频,app应用等. 协同过滤引擎:根据用户评分数据集,通过collaborative filtering方法,计算用户喜欢的top N item. 数据格式: userid, itemid,score.

下一代个性化推荐系统

- - 技术改变世界 创新驱动中国 - 《程序员》官网
本文结合技术及社会需求发展的大背景,讲述了当前推荐系统的价值及所面临的挑战,并指出了下一代个性化推荐系统的设计思路及需要注意的问题. 作为个性化推荐系统核心的协同过滤(Collabora-tive Filtering)算法,是Goldberg等人在1992年的一篇学术论文中最早提出的. 他们在这篇文章中提出一种方法,在一个新闻组中,根据 用户下载的新闻计算他们之间在口味上的相似程度,并利用这种相似程度为他们进一步推荐相关的新闻.