预测喜欢(在简单推荐引擎的算法中)

本文概述

  • 集和方程
  • 构建推荐引擎
  • 试驾
  • 改进之处
  • 总结
推荐引擎(有时称为推荐系统)是一种工具, 可让算法开发人员预测用户在给定项目列表中可能喜欢还是不喜欢什么。推荐引擎是搜索字段的一种非常有趣的替代方法, 因为推荐引擎可以帮助用户发现他们可能不会碰到的产品或内容。这使得推荐引擎成为了网站和服务(如Facebook, YouTube, Amazon等)中很大一部分。
推荐引擎理想地以两种方式之一工作。它可以依赖于用户喜欢的商品的属性, 通过分析这些属性来确定用户还喜欢什么。或者, 它可以依赖于其他用户的喜好, 推荐引擎然后使用它们来计算用户之间的相似性指数, 并据此向他们推荐项目。也可以将这两种方法结合起来以构建更强大的推荐引擎。但是, 像所有其他与信息有关的问题一样, 必须选择一种适合所要解决问题的算法。
预测喜欢(在简单推荐引擎的算法中)

文章图片
在本教程中, 我们将引导你完成构建基于协作和内存的推荐引擎的过程。该推荐引擎将根据用户喜欢和不喜欢的东西向他们推荐电影, 并且其功能类似于前面提到的第二个示例。对于这个项目, 我们将使用基本的集合操作, 一些数学知识以及Node.js / CoffeeScript。与本教程相关的所有源代码都可以在这里找到。
集和方程 在实施基于协作式内存的推荐引擎之前, 我们必须首先了解这种系统背后的核心思想。对于此引擎, 每个项目和每个用户都不过是标识符。因此, 在生成推荐时, 我们不会考虑电影的任何其他属性(例如演员, 导演, 流派等)。两个用户之间的相似性使用-1.0到1.0之间的十进制数表示。我们将此数字称为相似性索引。最后, 将使用另一个介于-1.0和1.0之间的十进制数字来表示用户喜欢电影的可能性。现在, 我们已经使用简单的术语对这个系统周围的世界进行了建模, 我们可以释放一些优雅的数学方程式来定义这些标识符和数字之间的关系。
在我们的推荐算法中, 我们将维护许多集合。每个用户都有两套:一组用户喜欢的电影和一组用户不喜欢的电影。每部电影还将具有与之关联的两组:一组喜欢该电影的用户和一组不喜欢该电影的用户。在生成建议的阶段中, 将生成许多集合-主要是其他集合的并集或交集。我们还将按顺序排列建议列表和每个用户的相似用户。
为了计算相似性指数, 我们将使用Jaccard指数公式的变体。该公式最初称为” commun decommunauté” (由Paul Jaccard创造), 该公式将两组数据进行比较, 并产生一个介于0到1.0之间的简单十进制统计信息:
预测喜欢(在简单推荐引擎的算法中)

文章图片
该公式包括将任一组中的公共元素数除以两组中所有元素的数目(仅计数一次)。两个相同集合的Jaccard索引将始终为1, 而没有公共元素的两个集合的Jaccard索引将始终为0。现在我们知道如何比较两个集合, 让我们考虑可以用来比较两个集合的策略用户。如前所述, 从系统的角度来看, 用户是三件事:标识符, 一组喜欢的电影和一组不喜欢的电影。如果仅根据用户喜欢的电影定义用户的相似性指数, 则可以直接使用Jaccard指数公式:
预测喜欢(在简单推荐引擎的算法中)

文章图片
在这里, U1和U2是我们正在比较的两个用户, L1和L2分别是U1和U2喜欢的电影集。现在, 如果考虑一下, 喜欢同一部电影的两个用户是相似的, 那么不喜欢同一部电影的两个用户也应该相似。这是我们对等式进行一些修改的地方:
预测喜欢(在简单推荐引擎的算法中)

文章图片
现在, 我们不仅仅考虑公式分子中的常见” 喜欢” , 还添加了” 常见不喜欢” 的数量。在分母中, 我们采用用户喜欢或不喜欢的所有商品的数量。现在, 我们已经以一种独立的方式考虑了好恶, 我们还应该考虑两个用户的偏好完全相反的情况。两个用户喜欢一个电影而另一个不喜欢它的两个用户的相似性索引不应为0:
预测喜欢(在简单推荐引擎的算法中)

文章图片
那是一个长公式!但是, 我保证, 这很简单。与我们以前的公式相似, 只是分子上的差别很小。现在, 我们从两个用户的共同喜欢和不喜欢次数中减去两个用户发生冲突的喜欢和不喜欢次数。这导致相似性指数公式的值范围介于-1.0和1.0之间。品味相同的两个用户的相似性指数为1.0, 而电影中品味完全冲突的两个用户的相似性指数为-1.0。
现在, 我们知道了如何根据两个用户在电影中的口味来对其进行比较, 在开始实现自制推荐引擎算法之前, 我们必须探索一个公式:
预测喜欢(在简单推荐引擎的算法中)

文章图片
【预测喜欢(在简单推荐引擎的算法中)】让我们分解一下这个方程式。我们所说的P(U, M)是用户U喜欢电影M的可能性。ZL和ZD是用户U与喜欢或不喜欢电影M的所有用户的相似性指数之和。 | ML | + | MD |代表喜欢或不喜欢电影M的用户总数。结果P(U, M)产生一个介于-1.0和1.0之间的数字。
就是这样。在下一部分中, 我们可以使用这些公式来开始实现基于内存的协作式推荐引擎。
构建推荐引擎 我们将把这个推荐引擎构建为一个非常简单的Node.js应用程序。前端上的工作也很少, 主要是一些HTML页面和表单(我们将使用Bootstrap使页面看起来整洁)。在服务器端, 我们将使用CoffeeScript。该应用程序将具有一些GET和POST路由。即使我们在应用程序中拥有用户的概念, 我们也将没有任何详尽的注册/登录机制。为了保持持久性, 我们将使用NPM提供的Bourne软件包, 该软件包使应用程序能够将数据存储在纯JSON文件中, 并对它们执行基本的数据库查询。我们将使用Express.js简化路由和处理程序的管理过程。
此时, 如果你不熟悉Node.js开发, 则可能需要克隆GitHub存储库, 以便更轻松地学习本教程。与其他任何Node.js项目一样, 我们将从创建package.json文件并安装该项目所需的一组依赖程序包开始。如果你正在使用克隆的存储库, 则package.json文件应该已经存在, 从那里安装依赖项将要求你执行” $ npm install” 。这将安装package.json文件中列出的所有软件包。
我们需要此项目的Node.js软件包是:
  • 异步的
  • 伯恩
  • 咖啡脚本
  • 表现
  • 下划线
通过将所有相关方法分为四个单独的CoffeeScript类, 我们将构建推荐引擎, 每个类将存储在” lib / engine” 下:Engine, Rater, Similars和Recommendations。类引擎将负责为推荐引擎提供简单的API, 并将其他三个类绑定在一起。评分者将负责跟踪喜欢和不喜欢(作为评分者类的两个单独实例)。相似和建议将分别负责确定和跟踪相似用户和推荐项目。
追踪喜欢和不喜欢
首先让我们从评估者课程开始。这是一个简单的例子:
class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

如本教程前面所述, 我们将有一个Rater实例来点赞, 而有另一个Rater实例来点赞。为了记录用户喜欢某件商品, 我们会将其传递给” Rater#add()” 。同样, 要删除评分, 我们会将其传递给” Rater#remove()” 。
由于我们将Bourne用作无服务器数据库解决方案, 因此我们会将这些等级存储在名为” ./db-#{@kind}.json” 的文件中, 其中种类为” 喜欢” 或” 不喜欢” 。我们将在Rater实例的构造函数中打开数据库:
constructor: (@engine, @kind) -> @db = new Bourne "./db-#{@kind}.json"

这使得添加评分记录就像在” Rater#add()” 方法中调用Bourne数据库方法一样简单:
@db.insert user: user, item: item, (err) =>

与删除它们类似(” db.delete” 而不是” db.insert” )。但是, 在添加或删除某些内容之前, 必须确保该内容在数据库中尚不存在。理想情况下, 使用真实的数据库, 我们可以将其作为单个操作完成。对于Bourne, 我们必须先进行手动检查。并且, 一旦完成插入或删除操作, 我们需要确保重新计算该用户的相似性指标, 然后生成一组新建议。 ” Rater#add()” 和” Rater#remove()” 方法如下所示:
add: (user, item, done) -> @db.find user: user, item: item, (err, res) => if res.length > 0 return done()@db.insert user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], doneremove: (user, item, done) -> @db.delete user: user, item: item, (err) => async.series [ (done) => @engine.similars.update user, done (done) => @engine.suggestions.update user, done ], done

为简便起见, 我们将跳过检查错误的部分。这在文章中可能是合理的事情, 但不是忽略真实代码中错误的借口。
此类的其他两个方法” Rater#itemsByUser()” 和” Rater#usersByItem()” 将涉及其名称所隐含的含义-分别查找由用户评价的项目和对项目进行评价的用户。例如, 当Rater用kind =” likes” 实例化时, ” Rater#itemsByUser()” 将找到用户已评分的所有项目。
寻找相似用户
继续我们的下一堂课:相似。此类将帮助我们计算并跟踪用户之间的相似性指数。如前所述, 计算两个用户之间的相似度涉及分析他们喜欢和不喜欢的项目集。为此, 我们将依靠Rater实例获取相关项的集合, 然后使用相似性指标公式为某些用户对确定相似性指标。
预测喜欢(在简单推荐引擎的算法中)

文章图片
就像我们上一个类Rater一样, 我们将所有内容都放入一个名为” ./db-similars.json” 的Bourne数据库中, 该数据库将在Rater的构造函数中打开。该类将具有” Similars#byUser()” 方法, 该方法使我们可以通过简单的数据库查找来查找与给定用户相似的用户:
@db.findOne user: user, (err, {others}) =>

但是, 此类中最重要的方法是” Similars#update()” , 它通过获取一个用户并计算一个相似的其他用户的列表, 并将该列表及其相似性索引存储在数据库中来工作。首先查找用户的喜好:
async.auto userLikes: (done) => @engine.likes.itemsByUser user, done userDislikes: (done) => @engine.dislikes.itemsByUser user, done , (err, {userLikes, userDislikes}) => items = _.flatten([userLikes, userDislikes])

我们还会找到所有对这些项目进行评级的用户:
async.map items, (item, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.usersByItem item, done , done , (err, others) =>

接下来, 对于其他每个用户, 我们计算相似性索引并将其全部存储在数据库中:
async.map others, (other, done) => async.auto otherLikes: (done) => @engine.likes.itemsByUser other, done otherDislikes: (done) => @engine.dislikes.itemsByUser other, done , (err, {otherLikes, otherDislikes}) => done null, user: other similarity: (_.intersection(userLikes, otherLikes).length+_.intersection(userDislikes, otherDislikes).length-_.intersection(userLikes, otherDislikes).length-_.intersection(userDislikes, otherLikes).length) / _.union(userLikes, otherLikes, userDislikes, otherDislikes).length, (err, others) => @db.insert user: user others: others , done

在上面的代码段中, 你会注意到我们在本质上与Jaccard索引公式的一种相似性表达式相同。
产生建议
我们的下一课” 建议” 是所有预测发生的地方。类似于类Likes, 我们依赖于在构造函数内部打开的另一个名为” ./db-suggestions.json” 的Bourne数据库。
预测喜欢(在简单推荐引擎的算法中)

文章图片
该类将具有” Suggestions#forUser()” 方法来查找给定用户的计算建议:
forUser: (user, done) -> @db.findOne user: user, (err, {suggestions}={suggestion: []}) -> done null, suggestions

计算这些结果的方法是” Suggestions#update()” 。该方法类似于” Similars#update()” , 将用户作为参数。该方法首先列出与给定用户相似的所有用户, 以及给定用户未评分的所有项目:
@engine.similars.byUser user, (err, others) => async.auto likes: (done) => @engine.likes.itemsByUser user, done dislikes: (done) => @engine.dislikes.itemsByUser user, done items: (done) => async.map others, (other, done) => async.map [ @engine.likes @engine.dislikes ], (rater, done) => rater.itemsByUser other.user, done , done , done , (err, {likes, dislikes, items}) => items = _.difference _.unique(_.flatten items), likes, dislikes

列出所有其他用户和未分级项目后, 我们可以开始计算新的一组建议, 方法是删除任何先前的建议集, 遍历每个项目, 然后根据可用信息计算用户喜欢它的可能性:
@db.delete user: user, (err) => async.map items, (item, done) => async.auto likers: (done) => @engine.likes.usersByItem item, done dislikers: (done) => @engine.dislikes.usersByItem item, done , (err, {likers, dislikers}) => numerator = 0 for other in _.without _.flatten([likers, dislikers]), user other = _.findWhere(others, user: other) if other? numerator += other.similaritydone null, item: item weight: numerator / _.union(likers, dislikers).length , (err, suggestions) =>

完成后, 我们将其保存回数据库:
@db.insert user: user suggestions: suggestions , done

公开库API
在Engine类内部, 我们将所有内容绑定到一个类似API的简洁结构中, 以便从外部轻松访问:
class Engine constructor: -> @likes = new Rater @, 'likes' @dislikes = new Rater @, 'dislikes' @similars = new Similars @ @suggestions = new Suggestions @

一旦我们实例化了Engine对象:
e = new Engine

我们可以轻松添加或删除喜欢和不喜欢的内容:
e.likes.add user, item, (err) -> e.dislikes.add user, item, (err) ->

我们还可以开始更新用户相似性指数和建议:
e.similars.update user, (err) -> e.suggestions.update user, (err) ->

最后, 从各自的” .coffee” 文件中导出此Engine类(以及所有其他类)很重要:
module.exports = Engine

然后, 通过创建一行” index.coffee” 文件, 从包中导出Engine:
module.exports = require './engine'

创建用户界面
为了能够在本教程中使用推荐引擎算法, 我们希望在Web上提供一个简单的用户界面。为此, 我们在” web.iced” 文件中生成一个Express应用程序并处理一些路由:
movies = require './data/movies.json'Engine = require './lib/engine' e = new Eengine app = express()app.set 'views', "#{__dirname}/views" app.set 'view engine', 'jade'app.route('/refresh') .post(({query}, res, next) -> async.series [ (done) => e.similars.update query.user, done(done) => e.suggestions.update query.user, done ], (err) => res.redirect "/?user=#{query.user}" )app.route('/like') .post(({query}, res, next) -> if query.unset is 'yes' e.likes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.dislikes.remove query.user, query.movie, (err) => e.likes.add query.user, query.movie, (err) => if err? return next errres.redirect "/?user=#{query.user}" )app.route('/dislike') .post(({query}, res, next) -> if query.unset is 'yes' e.dislikes.remove query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" else e.likes.remove query.user, query.movie, (err) => e.dislikes.add query.user, query.movie, (err) => res.redirect "/?user=#{query.user}" )app.route('/') .get(({query}, res, next) -> async.auto likes: (done) => e.likes.itemsByUser query.user, donedislikes: (done) => e.dislikes.itemsByUser query.user, donesuggestions: (done) => e.suggestions.forUser query.user, (err, suggestions) => done null, _.map _.sortBy(suggestions, (suggestion) -> -suggestion.weight), (suggestion) => _.findWhere movies, id: suggestion.item , (err, {likes, dislikes, suggestions}) => res.render 'index', movies: movies user: query.user likes: likes dislikes: dislikes suggestions: suggestions[...4] )

在应用程序中, 我们处理四个路线。索引路由” /” 是我们通过渲染Jade模板提供前端HTML的地方。生成模板需要电影列表, 当前用户的用户名, 用户的喜好以及针对用户的前四项建议。 Jade模板的源代码未包含在本文中, 但可以在GitHub存储库中找到。
” / like” 和” / dislike” 路线是我们接受POST请求以记录用户的喜欢和不喜欢的地方。如有必要, 两条路线都会先删除任何有冲突的评分来添加评分。例如, 用户喜欢他们以前不喜欢的东西, 将使处理程序首先删除” 不喜欢” 的评分。如果需要, 这些路线还允许用户” 不喜欢” 或” 不喜欢” 一件物品。
最后, ” /刷新” 路径允许用户根据需要重新生成他们的推荐集。虽然, 只要用户对项目进行任何评分, 该操作就会自动执行。
试驾 如果你尝试通过遵循本文从头开始实现此应用程序, 则需要执行最后一步才能测试它。你将需要在” data / movies.json” 处创建一个” .json” 文件, 并用一些电影数据填充该文件, 如下所示:
[ { "id": "1", "name": "Transformers: Age of Extinction", "thumb": { "url": "//upload.wikimedia.org/wikipedia/en/7/7f/Inception_ver3.jpg" } }, // … ]

你可能需要复制GitHub存储库中可用的存储库, 该存储库中预先装有一些电影名称和缩略图URL。
一旦所有源代码都准备好并连接在一起, 启动服务器进程就需要调用以下命令:
$ npm start

假设一切顺利, 你应该在终端上看到以下文本:
Listening on 5000

由于我们尚未实现任何真正的用户身份验证系统, 因此原型应用程序仅依赖在访问” http:// localhost:5000″ 之后选择的用户名。输入用户名并提交表单后, 应将你带到包含两个部分的另一个页面:” 推荐电影” 和” 所有电影” 。由于我们缺乏基于协作内存的推荐引擎(数据)中最重要的元素, 因此我们将无法向该新用户推荐任何电影。
此时, 你应该打开另一个浏览器窗口到” http:// localhost:5000″ , 然后以其他用户身份登录。作为第二用户喜欢和不喜欢一些电影。返回第一个用户的浏览器窗口, 并对一些电影进行评分。确保为两个用户都至少打几部普通电影。你应该立即开始看到建议。
改进之处 在此算法教程中, 我们构建的是原型推荐引擎。当然, 有一些方法可以改进此引擎。本节将简要介绍一些需要改进的地方, 以便大规模使用此地方。但是, 在需要可伸缩性, 稳定性和其他此类属性的情况下, 应始终求助于使用经过时间验证的良好解决方案。与本文的其余部分一样, 此处的想法是提供对推荐引擎如何工作的一些见解。除了讨论当前方法的明显缺陷(例如我们已实现的某些方法中的竞争条件)外, 将在更高级别上讨论改进。
这里一个非常明显的改进是使用真实的数据库, 而不是我们基于文件的解决方案。基于文件的解决方案在小规模的原型中可能会很好地工作, 但对于实际使用而言, 这根本不是一个合理的选择。 Redis是众多选择之一。 Redis速度很快, 并且具有特殊功能, 在处理类似集合的数据结构时非常有用。
我们可以解决的另一个问题是, 每当用户制作或更改电影评级时, 我们都会计算新推荐。与其实时进行重新计算, 不如将这些建议更新请求排队给用户, 并在后台执行它们-也许设置定时刷新间隔。
除了这些” 技术” 选择之外, 还可以做出一些战略选择来改进建议。随着项目和用户数量的增长, 生成建议的成本(在时间和系统资源方面)将越来越昂贵。通过仅选择一部分用户来生成推荐, 而不是每次都处理整个数据库, 可以使其变得更快。例如, 如果这是餐馆的推荐引擎, 则可以将相似的用户集限制为仅包含居住在同一城市或州的那些用户。
其他改进可能涉及采用混合方法, 其中基于协作过滤和基于内容的过滤生成建议。这对于电影等内容非常明确的内容尤其有用。例如, Netflix采取这种方式, 根据其他用户的活动和电影属性来推荐电影。
总结 基于内存的协作推荐引擎算法可能非常强大。我们在本文中尝试过的方法可能很原始, 但是也很简单:易于理解, 易于构建。它可能远非完美, 但推荐引擎的强大实现(例如Recommendable)是建立在类似的基本思想之上的。
像大多数其他涉及大量数据的计算机科学问题一样, 获得正确的建议也与选择正确的算法和适当的内容属性有关。我希望本文能使你了解使用协作式基于内存的推荐引擎时的情况。

    推荐阅读