转载

推荐系统，第 2 部分: 开源引擎简介

本系列的第 1 部分分析了推荐系统使用的一些核心方法和具体算法。本部分首先介绍一个推荐引擎的上下文。然后介绍一些构建推荐系统的开源解决方案。您将看到如何使用 Ruby 开发一个简单的集群应用程序并将它应用到第 1 部分中的示例数据中。然后将试验两个开源引擎，它们实现类似的算法但使用完全不同的方法。最后将概述开源领域中的其他推荐系统、机器学习和数据挖掘解决方案。

推荐引擎会处理一组服务用户的行为相关数据。在大部分情况下，该服务是一个网站，向一群用户公开各个商品并跟踪用户与这些商品相关的行为（比如查看、购买和评分）。这类数据形成了一个推荐引擎的基础需求，该引擎使用基于用户或基于商品的协作式过滤。

图 1 演示了一个推荐系统的简单生态系统。该生态系统包含：

一小群用户
一个服务
在该服务中区分用户行为（购买、查看等）的能力
一个计算和存储各个推荐要素的推荐引擎

图 1. 一个简单的推荐生态系统

接下来，我将介绍一个使用 Ruby 的简单集群实现。该实现根据用户的行为将类似用户分组到一起。

基于用户的协作式过滤集群

回想一下，第 1 部分分析了在一个包含 4 个用户的简单人群中执行基于用户的协作式过滤。要在一个人群中进行推荐，首先必须根据这些用户的行为对他们进行分类。第一个示例介绍如何使用一个简单的集群算法 k -means 来对用户进行分类。

从第 1 部分中我们已知道， k -means 将各个项目分区到 k 个集群中，最初随机地分区。然后为每个集群计算一个重心作为其成员的函数。然后检查每一项与集群重心之间的距离。如果发现一项更靠近另一个集群，会将它移到该集群中。每次检查所有项目的距离时都会重新计算重心。在一次迭代期间没有项目移动时，算法结束工作。

图 2 显示了 4 个阅读博客的用户示例数据集。

图 2. 用户博客阅读行为的示例数据

清单 1 给出了一个 Cluster 类的 Ruby 实现，它表示一个用于 k -means 算法的集群。

清单 1. 使用 Ruby 编写的 Cluster 类

class Cluster    # Initialize the class instance   def initialize     @people = Array.new     @vcentroid = Hash.new( "0" )   end    # Add a feature vector to the cluster   def add( person )     @people.push( person )   end    # Remove a feature vector from the cluster   def remove( person )     @people.delete( person )   end    # Return the cluster centroid   def get_people     return @people   end    # Calculate the centroid vector from the cluster members   def calculate_centroid      # Clear the centroid vector     @vcentroid.clear     tcentroid = Hash.new( "0" )      # Iterate through each feature vector     @people.each do |person|        # Sum the feature vectors in this cluster       person.each do |key,value|         tcentroid[key] = tcentroid.delete(key).to_i + value.to_i       end      end      # Compute the average for the centroid     tcentroid.each do |key,value|       @vcentroid[key] = value.to_f / @people.length     end    end    # Calculate the geometric distance   def calculate_gd( person )      gd = 0.0      person.each do |key,value|       gd += (@vcentroid[key].to_f-value.to_f) * (@vcentroid[key].to_f-value.to_f)     end      gd = Math.sqrt(gd)      return gd    end  end

Cluster 类以数组形式包含集群的成员，集群的重心作为一个哈希值（博客名称作为键，查看的文章作为值）。 initialize 方法创建了该数组和哈希值。

可用 3 个方法管理集群的成员：

add 方法向集群添加一个 person 。
remove 方法删除一个 person 。
get_people 方法提取该数组，以对它进行迭代。

可用两个方法管理集群。 calculate_centroid 方法根据集群当前的成员来更新集群的均值。 calculate_gd 方法返回集群重心与一个所传递的 person 对象之间的欧几里德距离。

清单 2 显示了一个 k -means 的 Ruby 实现，它处理图 2中的示例数据。

清单 2. 实现基本的 k -means 算法

def kmeans    # Sample user hashes   marc = { 'linux' => '13', 'oss' => '10', 'cloud' => '6',            'java' => '0', 'agile' => '0' }   megan = { 'linux' => '3', 'oss' => '0', 'cloud' => '1',             'java' => '6', 'agile' => '7' }   elise = { 'linux' => '11', 'oss' => '0', 'cloud' => '9',             'java' => '0', 'agile' => '1' }   jill = { 'linux' => '0', 'oss' => '3', 'cloud' => '0',            'java' => '9', 'agile' => '8' }    # Define our two clusters and initialize them with two users   cluster1 = Cluster.new   cluster1.add(marc)   cluster1.add(megan)    cluster2 = Cluster.new   cluster2.add(elise)   cluster2.add(jill)    changed = true    # Repeat until no further membership changes occur   while changed do      changed = false      # Recalculate each cluster's centroid (mean)     cluster1.calculate_centroid     cluster2.calculate_centroid      # Get the membership of each cluster     people1 = cluster1.get_people     people2 = cluster2.get_people      # Check members of cluster 1 against the cluster centroids     puts "Checking cluster 1"     people1.each do |person|       if cluster2.calculate_gd(person) < cluster1.calculate_gd(person) then         puts "Feature vector moved from cluster 1 to cluster 2"         cluster1.remove(person)         cluster2.add(person)         changed = true       end     end      # Check members of cluster 2 against the cluster centroids     puts "Checking cluster 2"     people2.each do |person|       if cluster1.calculate_gd(person) < cluster2.calculate_gd(person) then         puts "Feature vector moved from cluster 2 to cluster 1"         cluster2.remove(person)         cluster1.add(person)         changed = true       end     end    end    puts    puts "Cluster 1 contains"   people = cluster1.get_people   people.each do |person|     person.each do |key,value| print "#{key}=#{value} " end     puts   end   puts    puts "Cluster 2 contains"   people = cluster2.get_people   people.each do |person|     person.each do |key,value| print "#{key}=#{value} " end     puts   end   puts  end

清单 2 首先向集群添加示例数据。接下来，它计算每个集群的重心（作为其成员的均值），然后检查每个成员与两个集群之间的距离。如果成员距离它当前集群的重心更远，则会从原始集群中删除它并将其添加到另一个集群中。检查所有成员后，会重新计算重心并再次检查成员。未出现进一步的变化时，算法完成工作。

要将示例用户分组到 k = 2 个集群中，可调用 kmeans 方法，如清单 3 中的控制台会话所示。

清单 3. 运行简单的 k -means 实现

$ ruby kmeans.rb Checking cluster 1 Feature vector moved from cluster 1 to cluster 2 Checking cluster 2 Feature vector moved from cluster 2 to cluster 1 Checking cluster 1 Checking cluster 2  Cluster 1 contains cloud=6 java=0 linux=13 oss=10 agile=0  cloud=9 java=0 linux=11 oss=0 agile=1   Cluster 2 contains cloud=0 java=9 linux=0 oss=3 agile=8  cloud=1 java=6 linux=3 oss=0 agile=7   $

该算法已成功地将 Marc 和 Elise 分组到集群 1 中，将 Megan 和 Jill 分组到集群 2 中。完成集群分配后，推荐引擎可使用一个集群成员之间的差异来形成推荐。

这种自助方法不是构建推荐功能的唯一选择。接下来，我将深入分析两个开源推荐引擎，并简短描述其他一些可用的开源解决方案。

回页首

SUGGEST 和 Top-N 推荐

SUGGEST 是一个 Top-N 推荐引擎，实现为一个库。SUGGEST（它由明尼苏达大学的 George Karypis 开发）使用多个协作式过滤算法，实现基于用户和基于项目的协作式过滤。可在初始化一个特定的数据集时指定该算法。

通过一组用户项交易将数据提供给 SUGGEST。在本文的示例中，数据表示每个用户已阅读的博客。在一种更准确的模型中，您要提供各个历史事务，比如具体的文章阅读行为。在本例中，我会保持它尽可能简单，继续使用现有的数据集（4 个用户，5 篇博客）。

SUGGEST 公开一个简单的 API。在 C 编程语言中，仅需 3 个函数即可构建一个推荐引擎：

SUGGEST_Init 加载历史事务，定义特定的推荐算法，以及初始化推荐实例。
SUGGEST_TopN 根据所传递的示例数据计算一个推荐内容。
SUGGEST_Clean 释放 SUGGEST_Init 创建的推荐引擎实例。

第 4 个函数 SUGGEST_EstimateAlpha 为基于概率的算法定义最优的 alpha 值（如果使用该算法）。

清单 4 提供了一个使用 SUGGEST 的简单推荐实现。

清单 4. 使用 SUGGEST 推荐引擎的（使用 C 编写的）示例应用程序

#include <stdio.h> #include "suggest.h" int nusers = 4; #define MARC   0 #define MEGAN   1 #define ELISE   2 #define JILL   3 int nitems = 20;   // Marc  Megan  Elise  Jill #define LINUX1   0  //  1   0   1  0 #define LINUX2   1  //  1   0   0  1 #define LINUX3   2  //  1   0   1  0 #define LINUX4   3  //  1   1   1  0 #define OSS1   4  //  1   1   0  1 #define OSS2   5  //  0   0   1  1 #define OSS3   6  //  1   0   1  0 #define CLOUD1   7  //  0   1   1  0 #define CLOUD2   8  //  1   1   1  1 #define CLOUD3   9  //  0   0   0  1 #define CLOUD4   10 //  1   0   1  1 #define CLOUD5   11 //  0   0   0  0 #define JAVA1   12 //  0   1   0  1 #define JAVA2   13 //  0   1   0  0 #define JAVA3   14 //  1   1   0  1 #define JAVA4   15 //  0   1   1  1 #define JAVA5   16 //  0   0   0  1 #define AGILE1   17 //  0   1   0  1 #define AGILE2   18 //  0   1   0  0 #define AGILE3   19 //  0   0   1  1 #define NTRANS   40 // Historical transactions of users and items. int userid[NTRANS] =    { MARC , MARC , MARC , MARC , MARC , MARC , MARC , MARC , MARC,  MEGAN, MEGAN, MEGAN, MEGAN, MEGAN, MEGAN, MEGAN, MEGAN, MEGAN, MEGAN,   ELISE, ELISE, ELISE, ELISE, ELISE, ELISE, ELISE, ELISE, ELISE,   JILL, JILL, JILL, JILL, JILL, JILL, JILL, JILL, JILL, JILL, JILL, JILL,    }; int itemid[NTRANS] =   { /* Marc Blog Reads */  LINUX1, LINUX2, LINUX3, LINUX4, OSS1, OSS3, CLOUD2, CLOUD4, JAVA3,  /* Megan Blog Reads */  LINUX4, OSS1, CLOUD1, CLOUD2, JAVA1, JAVA2, JAVA3, JAVA4, AGILE1, AGILE2,  /* Elise Blog Reads */  LINUX1, LINUX3, LINUX4, OSS2, OSS3, CLOUD1, CLOUD2, JAVA4, AGILE3,  /* Jill Blog Reads */  LINUX2, OSS1, OSS2, CLOUD2, CLOUD3, CLOUD4, JAVA1, JAVA3, JAVA4, JAVA5, AGILE1, AGILE2   }; int main() {   int *rcmd_handle;   int behavior[7]={LINUX1, LINUX2, LINUX4, OSS1, OSS2, CLOUD1, CLOUD3 };   int recommendation[2];   int result, i;   rcmd_handle = SUGGEST_Init( nusers, nitems, NTRANS, userid, itemid,          3, 2, 0.0 );   result = SUGGEST_TopN( rcmd_handle, 7, behavior, 2, recommendation );   if (result) {  printf("Recommendations (%d) are %d and %d/n", result,    recommendation[0], recommendation[1]);   } else printf("No recommendation made./n");   SUGGEST_Clean( rcmd_handle );   return 0; }

清单 4首先给出了历史数据的定义，它在两个数组（ users 和 items ）中定义。这两个数组在一定程度上是相关的，因为 user [index] 定义了用户项事务 ( users[0] 购买了 items[0] 等）。出于简单性和可读性，这些数组按用户项的顺序定义。

SUGGEST 解决方案的使用包含在清单 4中简短的 main 函数中。这里，首先使用示例用户和项目数据初始化您的推荐系统（这些数据一起表示一组项目上的多个用户事务）。将 user 和 items 数组传递到 SUGGEST_Init 中，以及它们的限制和可能的值（用户和项目标识符）。同样地，为推荐指定一个基于项目的 Top-N 推荐算法（基于用户的 Top-N 和基于余弦的相似性函数）和近邻的大小。接下来，在您的 “篮子” 中填入项目来计算推荐请求，调用 SUGGEST_TopN 来请求推荐内容。最后，释放与推荐系统相关的资源并退出。注意，在这个示例中，该网站提供了涵盖 5 个主题的 20 篇文章，以及 4 个用户的历史数据。

示例 SUGGEST 推荐系统的执行如清单 5 中的控制台会话所示。

清单 5. 使用示例数据运行 SUGGEST 推荐引擎

$ ./topn Recommendations (2) are 2 and 8 $

在本例中，该引擎推荐特定的读者可能喜欢 LINUX3 和 CLOUD2。这些推荐内容是合理的，考虑了用户以前的行为和该用户的查看频率。注意，调用 SUGGEST_TopN 的结果是推荐数组中的推荐数量。

SUGGEST 是 Top-N 协作式过滤算法的一个简单但有效的实现。

回页首

RESTful Web 服务和 easyrec

easyrec 开源推荐引擎采用了一种新颖的方法来构建推荐服务。（easyrec 由 Research Studios Austria 在 Austrian Federal Ministry of Science and Research 的资助下开发和维护。）

easyrec 公开了一个具象状态传输 (REST) 接口，从而可将它与开发人员的语言选择完全分开。此方法增强了开发人员将服务与最终用户应用程序集成的能力，并且改进了服务的可伸缩性。

easyrec API 公开了丰富的 RESTful 接口，涵盖一个推荐系统所需的所有可能操作，包括物品购买、查看和评分。这些操作记录在 easyrec 数据库中。推荐通过一组特定的接口提供，比如 “与一个给定物品相关的物品”、“其他用户也查看了这些物品”、“针对一个给定用户的具体建议” 和 “其他用户也已购买”。这些基础推荐操作涵盖了许多预测场景中最常见的情形。easyrec API 支持使用 XML 和 JSON 进行响应。

现在我将展示一个使用 easyrec 为给定用户请求推荐的示例。该 easyrec 解决方案以一个包的形式提供，您可将它集成到自己的设置中，但也有一个演示服务器可用于测试。接下来，您将使用此服务器和 easyrec 的测试数据来请求推荐。

您可使用清单 6 中的简单 Ruby 脚本为指定用户请求推荐。在 easyrec 数据库中预定义了用户和一个物品列表。清单 6 定义了一个 Ruby 函数来与远程 Web 服务交互。此函数构建了一个表示 easyrec 请求的 URL。（在本例中，所请求命令是 recommendationsforuser 。）

清单 6. 与 easyrec 交互来获得推荐的 Ruby 函数

#!/usr/bin/ruby  require 'rubygems' require 'json' require 'net/http'  def recommend_for_user( userid )    puts "Request for recommendations for user #{userid}"    apikey = "3d66b20f7cbf176bf182946a15a5378e"    request = "http://intralife.researchstudio.at:8080" +             "/api/1.0/json/recommendationsforuser?" +             "apikey=#{apikey}&" +             "tenantid=EASYREC_DEMO&" +             "userid=#{userid}&" +             "requesteditemtype=ITEM"    resp = Net::HTTP.get_response(URI.parse(request))    parsed = JSON.parse(resp.body)    parsed2 = parsed['recommendeditems']    parsed2['item'].each do |item|     puts item['description']   end  end

如清单 6中所示，除了 REST 命名空间和命令，您还定义了：

apikey （使用来自 easyrec 网站的示例密钥）
tenantid
对推荐感兴趣的用户 ID

您还指定对 ITEM 类型感兴趣，以允许所有推荐的产品。定义统一资源标识符 (URI) 后，使用 Ruby 的 Net:HTTP 客户端 API 发送请求，然后返回响应并存储它。解析此响应，然后在每个返回的项目上对它进行迭代。

清单 7 演示了在 Interactive Ruby Shell (IRB) 中为特定用户使用 recommend_for_user() 函数。在本例中，推荐内容包含了根据该用户的偏好得出的音乐选择。

清单 7. 使用 easyrec 创建推荐内容

irb(main):027:0> recommend_for_user( "24EH1723322222A3" ) Request for recommendations for user 24EH1723322222A3 Beastie Boys - Intergalactic Gorillaz - Clint Eastwood irb(main):028:0>

清单 7 演示了 easyrec 提供的接口的简单性，该接口可使用任何支持 HTTP 客户端和 JSON 或 XML 解析器的语言来实现。

回页首

其他开源产品

其他一些推荐解决方案或解决方案元素也是开源的。本节分析一下其中一些产品。（参见参考资料了解这些产品和其他选项。）

LensKit

LensKit（来自明尼苏达大学）是一个用于构建推荐系统的框架，常常用在协作式过滤的研究中。LensKit 的目的是带来一个容易理解和访问，用于集成到 Web 应用程序中的高质量实现。

Crab

Crab 推荐引擎框架是为 Python 构建的，使用了 Python 生态系统的一些科学计算方面，比如 NumPy 和 SciPy。Crab 实现基于用户和基于项目的协作式过滤。该项目计划在未来实现 Slope One 和 Singular Value Decomposition 算法，最终使用 REST API。

MyMediaLite

MyMediaLite 是多个用于开发推荐引擎的推荐系统算法的轻量库。MyMediaLite 根据用户项目评分反馈来实现评分预测和商品预测。该库使用 C# 实现，在 Microsoft .NET 平台上运行（在 Linux® 中需要 Mono 支持）。

Waffles

Waffles 是由杨百翰大学的 Mike Gashler 使用 C++ 开发的一个机器学习工具包。Waffles 构造了一组基于 CLI 的工具。这些工具实现了机器学习的细粒度任务，包括推荐，进而支持在比 API 集成所需的更高级别上编写机器学习任务脚本。通过包含可用任务的大量参数，Waffles 支持针对手头的任务对操作进行调优。

Duine

Duine 是一个来自挪威 Telematica Instituut 的用于预测引擎开发的软件库。Duine 使用 Java™ 语言实现协作式过滤技术，以及信息过滤。这个框架的最后一次提交是在 2009 年，所以该项目现在可能已停止。

Recommenderlab

Recommenderlab 是一个针对 R 环境的协作式过滤扩展。Recommenderlab 提供了一个用于研究和开发推荐系统的一般基础架构。Recommenderlab 环境既简化了算法开发和评估工作，又简化了多个算法之间的比较工作。

其他产品

开源领域还有很多其他产品可用作构建和评估算法的开发环境。Shogun 机器学习工具箱专注于大规模内核方法（比如 Support Vector Machine [SVM]），以及其他一些方法和模型。Milk 是一个针对 Python 的机器学习工具包，专注于监督分类方法（SVM、k-NN 等）。最后，Weka 提供了用 Java 编程语言编写的数据挖掘软件。

回页首