基于用户的推荐算法
仅仅基于用户行为数据设计的推荐算法一般称为协同过滤算法.学术界对协同过滤算法进行了深入研究,提出了很多方法,包括基于邻域的方法(neighborhood-based),隐语义模型(latent factor model),基于图的随机游走算法(random walk on graph)等等.在这些方法中,最著名,在业界得到最广泛应用的算法是基于邻域的方法,而基于邻域的方法主要包含下面两种算法:
- 基于用户的协同过滤算法.这种算法给用户推荐和他们兴趣相似的其他用户喜欢的物品.
- 基于物品的协同过滤算法.这种算法给用户推荐和他们之前喜欢的物品相似的物品.
基于用户的协同过滤方法
- 找到和目标用户兴趣相似的用户集合,关键在于计算两个用户的兴趣相似度
- 找到这个集合中用户喜欢的,且目标用户没有听说过的物品推荐给目标用户
这种方法更加社会化,反映了用户所在的小型用户群体中物品的热门度.
基于物品的协同过滤方法
- 计算物品间的相似度
- 根据物品的相似度和用户的历史行为给用户生成推荐列表
这种方法更加个性化,反映了用户自己的兴趣传承,而与其他用户无关.
新闻应用中的协同过滤
在新闻的应用中,用户的兴趣不是特别细化,绝大多数都是喜欢看热门的新闻.
即使是个性化,也是比较粗粒度的,不如有些用户喜欢体育新闻,有些喜欢社会新闻,而特别细粒度的个性化一般是不存在的.比方说,很少有用户只看某个话题的新闻,主要是因为这个话题不可能保证每天都有新的消息,而这个用户确实天天需要看新闻的.因此,个性化新闻推荐更加强调抓住新闻热点,热门程度和时效性是个性化新闻推荐的重点,而个性化对于这两点略显次要.因此,UserCF可以给用户推荐和他有相似爱好的一群其他用户今天都在看的新闻,这样在抓住热点和时效性的同事,保证了一定程度的个性化.这是Digg在新闻推荐中使用UserCF的最重要原因.
UserCF适合用于新闻推荐的另一个原因是从技术角度考量的.因为作为一种物品,新闻的更新非常快速,每时每刻都有新的内容出现,而ItemCF需要维护一张物品相关度的表,如果物品更新很快,那么这张表也需要很快更新,这在技术上很难实现.绝大多数物品相关度表都只能做到一天更新一次,这在新闻领域是不可以接收的.而UserCF是需要用户相似性表,虽然UserCF对于新用户也需要更新相似度表,但在新闻网站中,物品的更新速度远远快于新用户的加入速度,而且对于新用户,完全可以给他推荐最热门的新闻,因此UserCF显得是利大于弊.
UserCF需要维护一个用户相似度矩阵,而ItemCF需要维护一个物品相似度矩阵.从存储的角度来说,如果用户很多,那么维护用户兴趣的相似度矩阵需要很大空间,同理,如果物品很多,那么维护物品相似度矩阵代价较大.
在早期的研究中,大部分研究人员都是让少量的用户对大量的物品进行评价,然后研究用户兴趣的模式.那么,对于他们来说,因为用户很少,计算用户兴趣相似度也是最快最简单的方法.但是实际互联网中,用户数目往往非常庞大,而在图书,电子商务网站中,物品的数目则是比较少的.因此,物品的相似度对于用户的兴趣一般比较稳定,因此使用ItemCF是比较好的选择.当然,新闻网站是个例外,在新闻应用中,物品的相似度变化很快,物品数目庞大,相反兴趣则相对固定(都是喜欢看热门的),所以新闻网站的个性化推荐使用UserCF算法的更多.
冷启动
冷启动基本分为三种:
用户冷启动: 主要解决如何给新用户做个性化推荐的问题.当新用户到来时,没有他们的行为数据,所以无法根据他们的历史行为预测其兴趣,从而无法借此做个性化推荐.
物品冷启动: 主要解决将新的物品推荐给可能对他感兴趣的用户这一问题.
系统冷启动: 主要解决如何在一个新开发的网站上设计推荐系统(无用户,无行为,只有少量物品).
解决方案:
- 提供非个性化方案: 比如首先使用热门排行榜,后续再进行切换.
- 利用用户注册时提供的基本个人信息
- 要求用户在登录时对一些物品进行反馈,收集用户的兴趣信息
- 对于新加入的物品,可以利用内容信息,将他们推荐给喜欢过和他们相似的物品的用户
- 系统冷启动时,引入专家知识,通过一定的高效方式迅速建立起物品的相关度
一般架构
A: 负责从数据库或缓存中拿到用户的行为数据,通过分析不同的行为,生成当前用户的特征向量,进行输出
B: 负责将用户的特征向量通过特征-物品相关矩阵,转化为初始推荐列表
C: 负责对初始推荐列表进行过滤排名等处理,生成最终推荐列表
实时推荐系统
聚类技术和实时协同过滤算法
在算法上，一般采用EM（Expectation-Maximization）、K-means、吉布斯（Gibbs Sampling）、模糊聚类等聚类技术提高推荐速度。因为使用聚类技术可以大大缩小用户或项目的最近邻居搜索范围，从而提高推荐的实时性，如表9-1所示。
在算法上,一般采用EM(Expectation-Maximizatio),K-means,吉布斯(Gibbs Sampling),模糊聚类等聚类技术提高推荐速度.因为使用聚类技术可以大大缩小用户或项目的最近邻居搜索范围,从而提高推荐的实时性.
聚类技术比较:
| 算法 | 概念 | 缺点 |
|---|---|---|
| EM | 最大期望算法,估计用户或物品属于某一类的概率 | 每个用户或物品属于两个不同的用户分类或物品分类,EM算法就不再适用 |
| K-means | 主要思想是以空间中K个点为中心进行聚类,对最靠近他们的对象进行归类.通过迭代的方法,逐次更新各聚类中心的值,直至得到最好的聚类结果 | 聚类数目K的值需要事先给定,而且不同的应用中K值是不同的,难于选取.另外初始聚类中心是随机选取的,对于同一组数据,可能因为初始聚类的中心不同而产生不同的聚类结果.有些类型的数据,比如全是1和0组成的二进制数组,如果要对这种二进制数组进行聚类,K-means不合适,因为如果采用欧氏距离,很难定义和计算他们的聚类中心点,这时可以采用Jaccard相似度和ROCK等层次聚类算法 |
| 吉布斯采样 | 与EM算法类似,不同的是吉布斯采样方法基于贝叶斯模型,计算可以离线进行 | 算法复杂度较大,聚类过程比较耗时 |
| 模糊聚类 | 利用模糊等价关系将给定的对象分为一些等价类,并由此得到与关系对应的模糊相似矩阵,该模糊相似矩阵满足传递性.根据相似矩阵求出其传递关系的闭包,然后在传递关系的闭包上实现分类,计算可以离线进行 | 可能性划分的收敛速度慢,当数据离散程度大,即数据灰度大,预测精度越差,需要对历史数据的平滑处理 |
基于Spark的方式
在架构上,第一种是使用Spark吧模型计算放在内存中,加快模型计算速度,Hadoop中作业的中间输出结果是放到硬盘的HDFS中,而Spark是直接保存在内存中,因此Spark能更好的适用于数据挖掘与机器学习等需要迭代的模型计算.
MapReduce和Spark的Shuffle过程对比:
| MapReduce | Spark | |
|---|---|---|
| collect | 在内存中构造了一块数据结构y用于Map输出的的缓冲 | 直接把输出写到磁盘文件上 |
| sort | Map输出的数据有排序 | Map输出的数据没有排序 |
| merge | 对磁盘上的多个spill文件最后进行合并成一个输出文件 | 在Map端没有merge过程,在输出的时候直接是对应一个Reduce的数据写入到一个文件中,这些文件同时存在并发写,最后不需要合并成一个 |
| copy框架 | Jetty | Netty或直接Socket流 |
| 对于本节点上的文件 | 仍然是通过网络框架拖取数据 | 不通过网络框架,对于在本节点上的Map输出文件采用本地读取的方式 |
| copy过来的数据存放的位置 | 先放到内存,内存放不下时写到磁盘 | 一种方式全部放在内存,另一种方式先放在内存 |
| merge sort | 最后会对磁盘文件和内存中的数据进行合并排序 | 对于采用另一种方式时也会有合并排序的过程 |
基于Kiji框架的方式
第二种是使用Kiji,它是一种用来构建大数据应用和实时推荐系统的开源框架,本质上是对HBase上层的一个封装,用Avro来承载对象初始化的数据,使得用户能更容易的用HBase管理结构化数据,使得用户姓名,地址等基础信息和点击购买等动态信息都能存储到一行,在传统数据库中,往往需要建立多张表,在计算的时候需要关联多张表,影响实时性.
Kiji和HBase的映射关系:
| 项 | Kiji | HBase |
|---|---|---|
| Entity相关 | Entity | 相同键的值都属于同一行 |
| Entity相关 | EntityID | 行键(row key) |
| Column相关 | locality:family:key | Family:qualifier |
| Column相关 | locality | Famlily |
| Column相关 | Family:key | Qualifier |
| Schema相关 | Table Layout | Hbase上的KijiMetaTable,如kiji.default.meta |
| Schema相关 | Cell Sehema | Avro Schema |
| Schema相关 | Cell Schema mapping | HBase上的Schema Table,如: kiji.default.schema-hash,kiji.default.id |
Kiji提供了一个KijiScoring模块,它可以定义数据的过期策略,如综合产品的点击次数和上次的点击事件,设置数据的过期策略吧数据刷新到KijiScoring服务器中,并且根据自定义的规则,决定是否需要重新计算得分.如用户有上千万浏览记录,一次的行为不会影响对少总体得分,不需要重新计算,但如果用户仅有几次浏览记录,一次的行为,可能就要重新训练模型.Kiji也提供了一个Kiji模型库,使得改进的模型部署到生产环境时不用停掉应用程序,让开发者可以轻松更新其底层的模型.
基于Storm的方式
最后一种基于Storm的实时推荐系统.在实时推荐上,算法本身不能设计的太复杂,并且很多网站的数据库是TB,PB级别的,实时读写大表比较耗时.可以把算法分成离线部分和实时部分,利用Hadoop离线任务尽量吧查询数据库比较多的,可以预先计算的模型先训练好,或者把计算的中间数据先计算好,比如,线性分类器的参数,聚类算法的集群位置或者协同过滤中条目的相似性矩阵,然后把少量更新的计算留给Storm实时计算,一般是具体的评分阶段.
计算过程分析:
使用HBase或HDFS存储历史的浏览和购买行为信息,用Hadoop基于UserCF的协同过滤,先把用户的相似度离线生成好,用户到商品的矩阵往往比较大,预算比价耗时,把耗时的运行先离线计算好,实时调用离线的结果进行轻量级的计算有助于提高产品的实时性.
回顾一下协同过滤算法:
首先程序获取用户和产品的历史偏好,得到用户到产品的偏好矩阵,利用Jaccard相似系数(Jaccard coefficient),向量空间余弦相似度(Cosine similarity),皮尔逊相关系数(Pearson correlation coefficient)等相似度计算方法,得到相邻的用户(UserCF)和相似商品(ItemCF).在UserCF中,基于用户历史偏好的相似度得到邻居用户,将邻居用户偏好的产品推荐给该用户;在ItemCF中,基于用户对物品的偏好向量得到相似产品,然后把这款产品推荐给喜欢相似产品的其他用户.
然后通过Kafka或Redis队列,保存前端等最新浏览等事件,在Storm的Topolog中实时读取里面的信息,同时获取缓存中用户TopN个邻居用户,把邻居用户喜欢的商品存到缓存中,前端从缓存中取出商品,根据一定测策略,组装成推荐商品列表.
推荐系统商业应用架构
总结: Hulu的推荐系统,至少在他blog中写的比较简单.更多的是对推荐系统在线部分的一种描述,离线部分我猜想也是同步分布式计算或者不同的计算方式将算法产生的数据存储进入一种介质中,共推荐系统在线部分调用.系统的整个流程是这样的,首先获取用户的行为,包括(watch、subscribe、vote),这样行为会在后台获取show-show对应的推荐数据.同时这些行为也会产生对应的topic,系统也会根据topic到后台获取topic-show对应的推荐数据.两种数据进行混合,然后经过filter,explanation,ranking这一系列过程,最后生成用户看到的推荐数据.
总结: 淘宝的推荐系统,描述了推荐引擎搭建的整体架构,包括离线的分布式计算和存储,监控,数据统计和分析,实验平台等.给我们搭建推荐引擎提供了很好的建议,整体流程大致这样.通过后台的分布式计算,将算法产生的算法结果数据存储进入一种介质,首推HBase.然后,通过一种叫做云梯的机制将算法结果推入中间层介质中,共推荐系统的在线部分调用.在线部分提供引擎和实验分流,用户的行为将存储进入Hadoop中,数据分析平台有Hive来搭建,主要用来分析和统计Hadoop中的用户行为log.
总结: Google提供了一种分层实验模型的架构.通过不同层次之间的随机分流来保证不同实验层之间的正交,从而保证不同实验层之间不会发生相互影响的情况.Google主要把这套分层实验平台用于广告推荐当中,我们的推荐引擎可以借鉴这种模式.整体流程大致为,把用户的请求分配到不同的domain中,如果是在线的domain则用同样的流程,可以不进行实验,如果用户该次请求进入的是实验的domain,则通过在随机的在不同实验层之间选择实验,为该次请求打上实验tag,然后后面的部分则根据不同的实验tag进行实验.
整体总结: 我们的推荐系统可以以Taobao的那个推荐引擎为基础,搭建整体一个推荐生态系统,包括推荐引擎,实验平台,分布式计算和存储,日志统计和分析等.在线部分,可以采用Google的分层实验平台来完成我们队不同算法效果的AB-test.而在线的流程可以借鉴Hulu的处理流程.