没有合适的资源?快使用搜索试试~ 我知道了~
18.传统推荐算法1
需积分: 0 0 下载量 160 浏览量
2022-08-03
12:51:05
上传
评论
收藏 8.13MB PDF 举报
温馨提示
试读
97页
1. 在 1992 年的论文 《Using Collaborative Filtering to Weave An Information 2. 下图给出了 T
资源详情
资源评论
资源推荐
2022/4/27 13_classic_rec_system
huaxiaozhuan.com/深度学习/chapters/12_classic_rec_system.html 1/97
推荐系统-传统算法
一、Tapestry[1992]
1. 在 1992 年的论文 《Using Collaborative Filtering to Weave An Information
Tapestry》 中,论文提出了一个基于协同过滤 collaborative filtering 的电子邮件过滤系
统。
Tapestry 是 Xerox Palo Alto 研究中心开发的实验邮件系统,其动机来自于电子邮件的日益
使用,导致用户被大量的邮件所淹没。
处理大量电邮的一种方法是提供邮件列表,这使得每个用户只能订阅他们感兴趣的那些列表。但
是,特定用户感兴趣的文档集合很少能够完整的映射到现有的列表。
更好的解决方式是为每个用户指定一个 filter 过滤器,该过滤器将扫描所有的列表,然后在所
有列表中选择用户感兴趣的文档。
目前已经有一些邮件系统支持基于文档内容的过滤。 Tapestry 系统可以在基于内容的过滤之
外,通过引入人们的行为来执行更有效的过滤,这种过滤被称作协同过滤 collaborative
filtering 。
协同过滤通过记录人们对于他/她所阅读文档的反应 reaction 来协同从而帮助彼此进行过滤,这
种反应可能是文档特别有趣(或者特别无趣)。这些反应(通常也被称作注解 annotation )可
以由其它过滤器访问。
2. 下图给出了 Tapestry 的整体架构:
Indexer :从电子邮件、 Netnews 等外部来源读取文档,并将其添加到 Document Store
中。 Indexer 负责将文档解析为一组索引字段从而方便在 query 中使用。
Document store :为所有 Tapestry 文档提供长期存储,该存储仅支持追加。它还在存
储的文档上维护索引,以便可以有效地执行对文档数据库的 query 。
Annotation store :为文档关联的注解提供长期存储,该存储也只支持追加。
Filterer :重复对文档集合运行用户指定的一组 query ,那些与 query 匹配的文档将被返
回。
Little box :将特定用户感兴趣的文档排队。每个用户都有一个 little box ,它里面的
文件由过滤器填充,并由用户的文件阅读器消费。
Remailer :通过电子邮件定期的将 little box 的内容发送给用户。
Appraiser :对用户的文档进行个性化分类(如用户的 little box 中的文档)。该功能
可以自动地对文档进行优先级排序和分类。
Reader~Browser :提供用于访问 Tapestry 服务的用户界面,如添加/删除/编辑过滤器、
检索新文档、显示文档等。
2022/4/27 13_classic_rec_system
huaxiaozhuan.com/深度学习/chapters/12_classic_rec_system.html 2/97
3. 在 Tapestry 系统中,用户需要显式指定协同的用户以及该用户的行为构建协同过滤器。在后续
的演变过程中,协同过滤已经改进了这种方式,无需用户手动指定即可实现协同过滤。
二、GroupLens[1994]
1. 在 1994 年的论文 《GroupLens: An Open Architecture for Collaborative Filtering
of Netnews》 进一步的发扬了这种 UserBased 协同过滤的思想。
GroupLens 是一个采用协同过滤的网络新闻过滤系统,它设计了一种机制来帮助用户筛选他/她
感兴趣的新闻。 GroupLens 基于一个朴素的思想:用户在过去的兴趣会延续到将来。
GroupLens 利用了用户对文章的评分:
首先计算不同用户的评分序列之间的相关性,从而得到用户兴趣之间的相似性。
然后根据相似用户的评分来预测当前用户对于新文章的评分。
2. 给定评分矩阵:
其中 表示用户 对于文章 的评分,该评分可能是已知的,也可能是未知的(因为用户尚未阅
读该文章)。当用户评分未知时,我们将其填充为
GroupLens 首先计算用户兴趣之间的相似性。给定用户 和 ,定义他们共同评分的文章集合
为:
然后计算用户 在这些共同评分文章上的均值、方差、以及协方差:
2022/4/27 13_classic_rec_system
huaxiaozhuan.com/深度学习/chapters/12_classic_rec_system.html 3/97
则用户 和 的兴趣相似性由二者评分集合的相关系数 correlation coefficient 定义为:
3. 当预测用户 在未阅读文章 上的评分时,我们首先找出在 上存在评分的用户集合 :
然后我们基于用户 和集合 中用户的相似性来预测:
评分 不仅受到用户 对文章 的偏好的影响,还受到用户 整体打分的影响。如,有的用
户倾向于都打高分,有的用户倾向于都打低分。因此这里通过 来剔除整体性偏好的影
响,得到文章 的偏好。
三、ItemBased CF[2001]
1. 世界上信息量的增长速度远远超过我们处理信息的能力。我们都有体会:被每年出版的海量的新
书、期刊文章和会议纪要所淹没的感觉。技术大大降低了发布 publishing 和分发
distributing 信息的障碍。现在是时候创造新的技术,从而可以帮助我们从所有可用信息中找
到最有价值的信息。
此类最有前途的技术之一是协同过滤 collaborative filtering 。协同过滤的工作原理是建立
用户对 item 的偏好数据库。对于一个新用户,假设叫做 Neo ,我们从数据库中匹配邻居,这些
邻居是历史上与 Neo 有相似品味 taste 的其它用户。然后我们将邻居喜欢的 item 推荐给
Neo ,因为 Neo 可能也会喜欢这些 item 。协同过滤在研究和实践中都非常成功,在信息过滤应
用和电商应用中都非常成功。然而,协同过滤推荐系统有两个基本挑战仍然未能克服:
可扩展性 scalability :这些算法能够实时搜索数以万计的潜在邻居,但是现代系统需要搜
索数千万个潜在邻居。由于整体计算复杂度为 ,其中 为用户数量、 为平均
每个用户评分的 item 数量,因此随着用户规模的增加其计算复杂度难以忍受。
此外,现有算法对于拥有大量历史行为的单个用户 individual user 也存在性能问题。例
如,某些用户可能在成千上万个 item 上有过行为,那么这批用户会拖慢每秒可以搜索的相
似用户的数量(因为计算用户之间的相似度的计算复杂度为 , 为用户评分的 item
数量),从而进一步降低了可扩展性。
推荐质量 quality :用户需要他们可以信任的推荐,从而帮助他们找到感兴趣的 item 。对
于质量较差的推荐,用户一般都是“用脚投票”,直接拒绝使用该推荐系统。
某种程度上这两个挑战是相互冲突的:算法花在搜索邻居上的时间越少,它的可扩展性就越强、推
荐质量也就越差。出于这个原因,同时处理这两个挑战很重要,这样的解决方案既有效又实用。
论文 《Item-Based Collaborative Filtering Recommendation Algorithms》 提出了
Item-Based CF 来同时解决这两个挑战。
传统的协同过滤算法的瓶颈是在大量用户中搜索邻居,而 Item-Based 算法通过首先探索 item
之间的关系、而不是用户之间的关系来避免这个瓶颈。通过查找用户喜欢 item 相似的其它 item
来获取对用户的推荐。 由于 item 之间的关系是相对静态 static 的, Item-Based 算法可以
减少在线计算的数量,同时保持与 User-Based 算法相同的推荐质量。
2022/4/27 13_classic_rec_system
huaxiaozhuan.com/深度学习/chapters/12_classic_rec_system.html 4/97
论文主要贡献:
分析 Item-Based 的预测算法,并识别 identification 实现其子任务的不同方法。
形式化 item 相似度的预计算模型 pre-computed model ,从而提高 Item-Based 推荐的
在线可扩展性。
几种不同的 Item-Based 算法与经典的 User-Based 算法(最近邻)的实验效果比较。
2. 相关工作:这里我们简要介绍一些与协同过滤、推荐系统、数据挖掘、以及个性化相关的研究文
献。
Tapestry 是基于协同过滤的推荐系统的最早实现之一。该系统依赖于来自紧密社区
close-knit community (如办公室工作组)的人们的显式意见 explicit opinion ,其
中每个用户都了解其它用户。但是大型社区的推荐系统不能依赖于每个用户都了解其它用
户。
后来,人们开发了几个基于评级 ratings-based 的自动推荐系统。
GroupLens 研究系统为 Usenet 新闻和电影提供了匿名协同过滤解决方案。
Ringo 和 Video Recommender 是分别生成音乐推荐和电影推荐的 email-based 系
统和 web-based 系统。
ACM 的通讯特刊 《Recommender Systems》 介绍了许多不同的推荐系统。
其他技术也已经应用于推荐系统,包括贝叶斯网络、聚类 clustering 、以及 Horting 。
贝叶斯网络创建一个基于训练集的模型,每个节点都有一个决策树,边代表用户信息。
该模型可以在几个小时或者几天内离线构建。生成的模型非常小,速度非常快,并且基
本上与最近邻方法一样准确。
贝叶斯网络被证明可能适用于用户偏好缓慢变化(相对于构建模型所需的时间)的环
境,但是不适用于必须快速或频繁更新用户偏好模型的环境。
聚类技术通过识别似乎具有相似偏好的用户组 user group 来工作。一旦创建了簇
cluster ,就可以通过对该簇中其它用户的意见进行平均来对单个用户进行预测。
某些聚类技术将每个用户划分到多个 cluster ,然后预测时按照跨 cluster 取加权
平均值,权重是参与这个 cluster 的程度。
聚类技术通常比其它方法产生较少个性化的推荐,并且在某些情况下聚类的准确性比最
近邻算法更差。然而,一旦聚类完成,性能就会非常好,因为必须分析的组的数量要小
得多。
聚类技术也可以作为 first step 来应用,用于在最近邻算法中缩小候选集、或者在
多个推荐引擎之间分配最近邻计算。虽然将用户划分为 clusters 可能会损害
cluster 边缘附近用户的准确性或推荐,但是 pre-clustering 可能是准确性和吞
吐量之间的一个值得的 trade-off 。
Horting 是一种 graph-based 技术,其中节点是用户、节点之间的边表示两个用户
之间的相似程度。预测是通过游走到附近节点,然后结合附近用户的意见来产生的。
Horting 和最近邻不同,因为它探索了 graph 上的高阶关系而最近邻仅探索 graph
上的一阶关系(直接关系),从而探索最近邻算法中没有考虑的信息传递。在一项使用
人工合成数据的研究中, Horting 产生了比最近邻更好的预测算法。
《Recommender Systems in E-Commerce》 展示了电商中使用的推荐系统的详细分类和
示例,以及它们如何提供一对一的个性化,同时可以捕获客户忠诚度 loyalty 。
尽管这些系统在过去取得了成功,但是它们的广泛使用暴露了它们的一些局限性,例如数据集的稀
疏性问题、与高维相关的问题等。
推荐系统中的稀疏性问题已经在
2022/4/27 13_classic_rec_system
huaxiaozhuan.com/深度学习/chapters/12_classic_rec_system.html 5/97
《Using Filtering Agents to Improve Prediction Quality in the GroupLens
Research Collaborative Filtering System》 和 《Combining Collaborative
Filtering With Personal Agents for Better Recommendations》 中得到解决。
推荐系统中与高维相关的问题已经在 《Learning Collaborative Information
Filters》 中讨论过,在 《Application of Dimensionality Reduction in
Recommender System -- A Case Study》 中已经研究了应用降维技术解决这些问题。
我们的工作探索了 Item-Based 推荐算法(一类新的推荐算法)能够在多大程度上解决这些问
题。
3.1 模型
3.1.1 CF-Based 推荐系统
1. 推荐系统主要解决以下问题:通过为给定用户生成预测的可能性得分、或者 top-N 的推荐 item
列表,从而帮助用户找到他们想在电商网站上购买的 item 。
可以使用不同的方法进行 item 推荐,例如基于用户的人口统计 demographics 、热门 item 、
或者用户历史购买习惯。协同过滤 Collaborative Filtering: CF 是迄今为止最成功的推荐
技术。基于 CF 的算法的基本思想是:根据其他志趣相投用户的意见提供 item 推荐或预测。用
户的意见可以显式 explicitly 地从用户那里获取,也可以通过一些隐式 implicit 的手段获
取。
2. 协同过滤处理 Overview :协同过滤算法的目标是根据用户历史偏好、或者其他志趣相投用户的
意见,为目标用户推荐新 item 或者预测某个 item 的效用 utility 。
在典型的 CF 场景中,有一个 个用户的列表 、以及一个包含 个
item 的列表 。每个用户 都有一个 item 列表 ,对该列表中的每个
item ,用户 已经表达了他/她的意见 opinion 。 意见可以由用户显式给出(如位于某个数字
区间的评级分数 rating score ),也可以通过分析日志从购买记录中隐式地获取。注意,
,并且 可能是空集。
给定目标用户 ,协同过滤算法的任务是为 找到一个 item 偏好 item likeliness 。
这种偏好有两种形式:
预测:预测用户 对于 item 的评分 。
推荐:为用户 推荐他/她可能最喜欢的由 个 item 组成的列表 。注意,推荐列
表必须位于目标用户尚未购买的 item 上,即 。这被称作 Top-N 推荐。
下图给出了协同过滤任务的示意图。 CF 算法将整个 个 user-item 数据表示为一个评分
矩阵 ,矩阵中的每一个元素 表示第 个 user 在第 个 item 上的评分。每个评分在一定
范围之内(如 1~5 ),也可以为 0 ,表示用户尚未对该 item 评分。
协同过滤算法可以分为两类:
memory-based 基于内存的(也称作 user-based )协同过滤:利用整个评分矩阵来生成预
测。
剩余96页未读,继续阅读
普通网友
- 粉丝: 16
- 资源: 319
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0