一个简单的推荐系统 - 协作网络库

引言

您是否觉得像Amazon.com之类的网站的“购买了此商品的用户也购买了这些商品”功能很有用？您是否希望为您的电子商务网站添加此功能以增加交叉销售机会？也许您只是对向浏览您网站的访问者推荐页面感兴趣。无论您想推荐或交叉销售的具体商品类型是什么，技术都可以是相同的。有很多算法可以用来实现推荐系统。在本文中，我将基于一个直接的图结构和简单的算法来描述其中一个实现。

借助本文的内容和可下载的源代码，您将能够将一个简单的推荐算法注入到您的网站中。

本文结构如下

• 背景信息（对推荐系统理论的快速解释）
• 库概述
• 如何使用库
• 实现细节
• 闭幕词
• 参考文献

背景

推荐系统是大型电子商务网站的生命线。潜在客户会根据他们表现出的喜好获得高度相关的产品推荐；从而增加购买的可能性。购买了一件或多件商品的客户会获得类似商品的推荐，增加了交叉销售的可能性。而回头客则通过基于他们先前购买记录的推荐质量得到留存。总的来说，任何推荐系统的目标都是向用户呈现一组高度相关的商品。

推荐算法通常有两种类型。一种基于当前活跃用户与先前用户之间的相似性。相似性通常是使用有关每个用户表现出兴趣（或购买）的商品的信息计算的。另一种类型基于当前用户选择的商品与其他商品的相似性。通常分别称为基于用户的协同过滤和基于物品的协同过滤，这些算法在收集的数据和形成的数据项之间的关联方面有所不同。

这两种类型的系统都可以进一步归类为基于内存或基于模型的协同过滤器。基于内存的方法依赖于在请求推荐时将所有观察数据库保存在内存中。然后，通过搜索表现出相似行为的邻居，并将这些邻居的偏好组合成一组排名靠前的商品来满足请求。基于模型的系统依赖于离线构建模型（通常通过机器学习算法），然后使用学习到的模型来对用户进行分类并推荐相关商品。

本文介绍的协同网络库是一个简单的以物品为中心、基于内存的协同过滤算法。它不是一种概率方法，并且完全基于对物品对之间观察到的关联；因此，它不处理未观察到的物品或特征。这意味着，如果用户选择了一个之前没有被任何用户选择过的物品，那么系统将无法产生推荐。要使一个物品成为推荐的一部分，它必须已经被一个或多个之前的用户与其他物品关联过。

库概述

基于内存的协同过滤器有两个主要方面。第一个涉及更新用户与您的产品或网站页面交互的内存表示。第二个是获取推荐。本文介绍的协同网络库在这方面没有不同。这两个步骤都通过一个单独的类来实现。您的代码与库的主要交互将通过`Platypus.Collaborator`命名空间中的`ItemGraphSingleton`类进行。通过调用`void AddLink(string strSource, string strTarget)`方法来更新基于物品的图，其中`strSource`是先前查看的产品，`strTarget`是新请求/查看/选择的物品。

对于协同网络库，收集的内存数据基于物品的查看或购买顺序。为了捕捉有意义的关联，用户必须查看或购买不止一件物品。但是，为了减轻此要求，您始终可以为所有关联提供一个虚拟的起点。例如，如果用户访问您的网站并查看或购买了一件名为“foo product”的商品，您可以创建一个虚拟物品（例如，“home”）与购买的商品之间的链接。这允许库从任何用户会话的开始推荐物品。

通过`Item[] NextItems(string strItem, int nTopN)`方法获取推荐。它返回一个最多包含`nTopN`个Item对象的数组，按降序排序。这些是实例方法，因此必须通过静态`ItemGraphSingleton.GetInstance()`方法访问。这是库的两个主要操作。

除了更新图和检索推荐的主要任务之外，还必须将图持久化到持久化媒体，因为所有更新都在内存中。这可以通过多种方式实现。例如，我们可以将图持久化到SQL Server数据库或磁盘。当前实现（1.0版）支持使用.NET二进制序列化机制持久化到磁盘。为此，提供了实用类`ItemGraphSerializer`。该类有两个重载的序列化和反序列化方法。有关此类的更多详细信息将在下一节提供，但在此处足以说明，可以定期调用这些方法以将图的最新状态持久化到磁盘文件。

如何使用库

现在我们已经涵盖了通用部分，让我们深入探讨具体细节。在本节中，我将向您展示如何在最小侵入性的方式下将协同网络库集成到您的网站中。

让我们从初始化代码开始。在网站的上下文中，您可能希望在应用程序启动代码中加载先前序列化的图版本。这可以在`Global.Application_Start`方法中完成，如下所示：

using Platypus.Collaborator;
using System.IO;
...

   SerializationResult sr;

   fileName = Server.MapPath(@"\collab_graph.graph");

   if( File.Exists( fileName ) )
   {
      sr = Platypus.Collaborator.ItemGraphSerializer.Deserialize(fileName);

      if( !sr.Succeeded  )
      {
        // warning, not necessarily an error

        // log sr.ErrorMessage

      }
   }

相应地，可以在应用程序结束事件中将图序列化到磁盘：

using Platypus.Collaborator;
using System.IO;
...
protected void Application_End(Object sender, EventArgs e)
{
   fileName = Server.MapPath(@"\collab_graph.graph");

   Platypus.Collaborator.ItemGraphSerializer.Serialize( fileName );
}

有了这些代码，每次应用程序关闭时，图都会序列化到磁盘，并在启动时反序列化。当然，您可以决定不同的序列化计划；例如，在每个会话结束时。

序列化完成后，我们可以继续介绍库中最有趣的部分——获取推荐和更新图。在库概述部分，我简要介绍了此过程中涉及的两个方法。在您的应用程序中使用这两个方法很简单。`AddLink(string strSource, string strTarget)`方法接受两个参数，一个源项目和一个目标项目。源项目是当前用户先前选择的项目。目标项目是用户刚刚请求的项目。通过使用这两个参数调用此方法，我们指示图库更新从项目`strSource`到项目`strTarget`的有向关联，或者在之前未观察到关联的情况下创建它。这暗示您正在维护当前用户的会话信息，这是电子商务网站中的常见做法。然而，您维护着当前用户的状态，需要识别物品选择的顺序。

在典型场景中，您将通过某种服务器端事件处理程序响应用户选择项目的操作。在这样的处理程序中，更新图和获取推荐的操作可以合并。假设您正在使用`DataGrid`显示推荐的项目，并且用户之前的选择存储在会话中。以下代码演示了如何使用`AddLink()`方法并获取一组推荐：

protected void UpdateGraphAndRecommendNextItems(string strPrev,string strNext )
  {
     //

     //  Update the graph

     //       

     ItemGraphSingleton.GetInstance().AddLink( strPrev, strNext );

     //

     // Get a recommendation of at most 5 items

     //

     Item[] items = ItemGraphSingleton.GetInstance().NextItems(strNext , 5 );

     //

     // Bind the recommended items to the DataGrid that displays them.

     //

     dgRecommendedItems.DataSource = items;
     dgRecommendedItems.DataBind();
   }

就是这样。

实现细节

到目前为止，我为您提供了协同过滤的广泛概述和一个简单实现的鸟瞰图。在本节中，我将深入探讨库的内部工作原理以及我关于如何使用它的假设。

首先，让我们看看库的静态结构。以下UML图描绘了库中类之间的关系。

首先要注意的是`ItemGraph`和`ItemGraphSingleton`类。单例类是`ItemGraph`类的一个简单包装器。它强制在您的应用程序域中存在单个`ItemGraph`实例。如果您愿意，可以实例化一个`ItemGraph`对象并自行管理其生命周期。提供单例是为了方便。

一旦泛型概念被整合到.NET框架中（今年即将推出的2.0版本），通过使用类型为`ItemGraph[1]`的泛型单例模板，可以改进此设计。

`ItemGraph`类的一个重要方面是，由于其实例在多个会话之间共享，因此其操作必须是线程安全的。为此，您将看到`void AddLink()`方法同步了更新图内部结构的过程。在内部，图表示为邻接列表[3]。`ItemGraph`对象包含通过`AddLink()`方法添加的`Item`对象集合。当遇到新项目时，它们会被添加到此集合中。该集合是强类型的，并且基于`System.Collections.CollectionBase`类。那么它到底是如何成为一个图的呢？每个`Item`对象都包含一个`DirectedEdge`对象的集合。`DirectedEdge`对象具有权重，并包含对另一个`Item`的引用。顾名思义，每个`DirectedEdge`对象表示包含`Item`与`DirectedEdge`引用的`Item`（类型为`Item`的属性，名为`Target`）之间的定向链接。`Weight`属性表示这两个项目之间的关联被添加的次数。在电子商务网站的上下文中，这可以表示客户在看到源项目后又对目标项目表现出兴趣的次数。下图直观地展示了一个假设的图的实例。

在这个假设的图中，`ItemGraph`项集合中的第一个项将是`Item A`。这个`Item`对象将拥有一组指向Item `C`、`G`和`E`的`DirectedEdge`对象，权重分别为3、2和3。

当前版本有一个非常简单的推荐物品的方法。它在图中查找请求的`Item`，然后枚举其出向链接，直到达到请求的数量。一个更好的方法，尤其是在图的早期演化阶段，是实现一个深度遍历算法来找到具有请求项目数量的“最重”路径。例如，如果请求的项目只有2个出向链接，而请求数量是4，则算法将检查这2个出向链接的子项，并找到其中最重的一个。这种方法可以包括一个遍历成本，该成本根据与请求节点的分离步数来降低出向链接的权重。这个调整后的权重将代表链接中的目标与请求节点之间基于它们分离的间接关联。

库的其余与图相关的方面相当简单。粗略查看源代码将比文字更好地理解。

有必要简要描述一下序列化代码。`ItemGraphSerializer`类封装了图到文件流的填充和提取。此过程利用.NET二进制序列化机制。`ItemGraphSerializer.Serialize()`方法接受一个文件名和一个`ItemGraph`对象的引用。如果您通过`ItemGraphSingleton`类与图进行交互，那么它提供了一个公共属性`Graph`来访问其私有的`ItemGraph`实例。当调用此方法时，将使用`FileMode.Create`和`FileAccess.Write`打开一个文件流（`System.IO.FileStream`）。然后使用`BinaryFormatter`将`ItemGraph`对象序列化到此流。反序列化同样通过`FileStream`使用`BinaryFormatter`执行。`ItemGraphSerializer.Deserialize()`支持此操作。此方法接受一个`ItemGraph`变量的引用，它将文件的内容反序列化到该变量中。返回一个`SerializationResult`结构，该结构指定此过程的结果。如果遇到故障，结构体的`Succeeded`布尔成员将设置为`false`。

结束语

在本文中，我介绍了一个使用以图为中心的简单协同过滤推荐系统。它易于使用，并且无需太多精力即可集成到.NET网站中。它提供了一个基于文件的持久化模型，可以轻松修改为基于SQL Server。

该库可用于在电子商务网站中推荐产品，或帮助用户浏览网站上的相关页面或内容。它通过成对项目之间形成循环关联图的加权关系来泛化演进。

包含了一个简单的推荐算法，该算法仅返回图中与所选项目相关联或引用的项目。

前面一节暗示了对推荐算法的未来改进。此产品后续版本将包含用于输出图可视化数据的代码。要了解有关此未来增强功能的更多信息，请访问我们的网站。

参考文献

1. 《更有效的C++：提高程序和设计的35种新方法》，作者：Scott Meyers。
2. 《基于物品的协同过滤推荐算法》；Sarwar等人。
3. 《算法导论》；Cormen、Leiserson和Rivest。