预测喜欢：在一个简单的推荐引擎的算法里面

推荐引擎（有时称为推荐系统）是一种工具，可让算法开发人员在给定项目列表中预测用户可能喜欢或不喜欢什么。 推荐引擎是搜索字段的一个非常有趣的替代品，因为推荐引擎可以帮助用户发现他们可能不会遇到的产品或内容。 这使得推荐引擎成为 Facebook、YouTube、亚马逊等网站和服务的重要组成部分。

推荐引擎以两种方式之一理想地工作。 它可以依赖于用户喜欢的项目的属性，对其进行分析以确定用户可能还喜欢什么； 或者，它可以依赖其他用户的好恶，然后推荐引擎使用它来计算用户之间的相似度指数，并相应地向他们推荐项目。 也可以结合这两种方法来构建一个更强大的推荐引擎。 但是，与所有其他与信息相关的问题一样，选择适合所解决问题的算法至关重要。

在本教程中，我们将引导您完成构建基于内存的协作推荐引擎的过程。 该推荐引擎将根据用户喜欢和不喜欢的内容向用户推荐电影，其功能类似于前面提到的第二个示例。 对于这个项目，我们将使用基本的集合操作、一些数学知识和 Node.js/CoffeeScript。 与本教程相关的所有源代码都可以在这里找到。

集合和方程

在实现基于协同记忆的推荐引擎之前，我们首先要了解这样一个系统背后的核心思想。 对于这个引擎，每个项目和每个用户都只是标识符。 因此，在生成推荐时，我们不会考虑电影的任何其他属性（例如，演员、导演、流派等）。 两个用户之间的相似度使用介于 -1.0 和 1.0 之间的十进制数表示。 我们将这个数字称为相似度指数。 最后，用户喜欢一部电影的可能性将使用另一个介于 -1.0 和 1.0 之间的十进制数来表示。 现在我们已经使用简单的术语对这个系统周围的世界进行了建模，我们可以释放一些优雅的数学方程来定义这些标识符和数字之间的关系。

在我们的推荐算法中，我们会维护一些集合。 每个用户将有两组：一组用户喜欢的电影，一组用户不喜欢的电影。 每部电影还将有两个与之关联的集合：一组喜欢这部电影的用户，以及一组不喜欢这部电影的用户。 在生成推荐的阶段，将产生许多集合——主要是其他集合的并集或交集。 我们还将为每个用户提供有序的建议和相似用户列表。

为了计算相似度指数，我们将使用 Jaccard 指数公式的变体。 该公式最初被称为“coefficient de communaute”（由 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 和 Suggestions。 类 Engine 将负责为推荐引擎提供一个简单的 API，并将其他三个类绑定在一起。 评分者将负责跟踪喜欢和不喜欢（作为评分者类的两个独立实例）。 Similars 和 Suggestions 将分别负责为用户确定和跟踪相似用户和推荐项目。

跟踪喜欢和不喜欢

让我们首先从我们的评估者类开始。 这是一个简单的：

 class Rater constructor: (@engine, @kind) -> add: (user, item, done) -> remove: (user, item, done) -> itemsByUser: (user, done) -> usersByItem: (item, done) ->

如本教程前面所述，我们将有一个 Rater 实例用于表示喜欢，另一个用于表示不喜欢。 为了记录用户喜欢某个项目，我们会将它们传递给“Rater#add()”。 同样，要删除评级，我们会将它们传递给“Rater#remove()”。

由于我们使用 Bourne 作为无服务器数据库解决方案，我们会将这些评分存储在名为“./db-#{@kind}.json”的文件中，其中 kind 是“likes”或“dislikes”。 我们将在 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 ], done remove: (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()”这个类将涉及到他们的名字所暗示的 - 分别查找用户评分的项目和对项目进行评分的用户。 例如，当使用kind = “likes”实例化 Rater 时，“Rater#itemsByUser()” 将找到用户评分的所有项目。

寻找相似用户

继续我们的下一堂课：Similars。 这个类将帮助我们计算和跟踪用户之间的相似度指数。 如前所述，计算两个用户之间的相似性涉及分析他们喜欢和不喜欢的项目集。 为此，我们将依靠 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 指数公式的一个变体。

生成推荐

我们的下一节课，建议，是所有预测发生的地方。 与 Similars 类一样，我们依赖另一个名为“./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.similarity done 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”文件从包中导出引擎：

 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 err res.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, done dislikes: (done) => e.dislikes.itemsByUser query.user, done suggestions: (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请求以记录用户的好恶的地方。 如有必要，两条路线都会通过首先删除任何冲突的评级来添加评级。 例如，用户喜欢他们以前不喜欢的东西会导致处理程序首先删除“不喜欢”评级。 如果需要，这些路线还允许用户“不喜欢”或“不喜欢”一个项目。

最后，“/refresh”路由允许用户按需重新生成他们的推荐集。 虽然，只要用户对项目进行任何评级，此操作就会自动执行。

试驾

如果您尝试按照本文从头开始实现此应用程序，则需要先执行最后一步，然后才能对其进行测试。 您需要在“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，是建立在类似的基本思想之上的。

与大多数其他涉及大量数据的计算机科学问题一样，获得正确的推荐很大程度上取决于选择正确的算法和要处理的内容的适当属性。 我希望这篇文章能让您了解在使用协作式基于内存的推荐引擎时会发生什么。