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

问题导读:
1.简单的推荐生态系统是怎么样的？
2.常见的推荐算法有哪些?
3.怎么用restful服务构建推荐系统？


上一篇：

推荐系统，第 1 部分: 方法和算法简介
http://www.aboutyun.com/thread-16745-1-1.html




本系列 第 1 部分 介绍了构造推荐引擎的基本方法和算法。最后一部分将探索构建推荐系统的一些开源解决方案并演示其中两种解决方案的使用。作者还将展示如何使用 Ruby 开发一个简单的集群应用程序并将它应用到示例数据中。

本系列的 第 1 部分 分析了推荐系统使用的一些核心方法和具体算法。本部分首先介绍一个推荐引擎的上下文。然后介绍一些构建推荐系统的开源解决方案。您将看到如何使用 Ruby 开发一个简单的集群应用程序并将它应用到

第 1 部分 中的示例数据中。然后将试验两个开源引擎，它们实现类似的算法但使用完全不同的方法。最后将概述开源领域中的其他推荐系统、机器学习和数据挖掘解决方案。
推荐引擎会处理一组服务用户的行为相关数据。在大部分情况下，该服务是一个网站，向一群用户公开各个商品并跟踪用户与这些商品相关的行为（比如查看、购买和评分）。这类数据形成了一个推荐引擎的基础需求，该引擎

使用基于用户或基于商品的协作式过滤。
图 1 演示了一个推荐系统的简单生态系统。该生态系统包含：
（1）一小群用户
（2）一个服务
（3）在该服务中区分用户行为（购买、查看等）的能力
（4）一个计算和存储各个推荐要素的推荐引擎
图 1. 一个简单的推荐生态系统

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

基于用户的协作式过滤集群
回想一下，第 1 部分 分析了在一个包含 4 个用户的简单人群中执行基于用户的协作式过滤。要在一个人群中进行推荐，首先必须根据这些用户的行为对他们进行分类。第一个示例介绍如何使用一个简单的集群算法 k-means 来对用户进行分类。
从 第 1 部分 中我们已知道，k-means 将各个项目分区到 k 个集群中，最初随机地分区。然后为每个集群计算一个 重心 作为其成员的函数。然后检查每一项与集群重心之间的距离。如果发现一项更靠近另一个集群，会将它移到该集群中。每次检查所有项目的距离时都会重新计算重心。在一次迭代期间没有项目移动时，算法结束工作。
图 2 显示了 4 个阅读博客的用户示例数据集。
图 2. 用户博客阅读行为的示例数据

清单 1 给出了一个 Cluster 类的 Ruby 实现，它表示一个用于 k-means 算法的集群。
清单 1. 使用 Ruby 编写的 Cluster 类
[mw_shl_code=ruby,true]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[/mw_shl_code]

Cluster 类以数组形式包含集群的成员，集群的重心作为一个哈希值（博客名称作为键，查看的文章作为值）。initialize 方法创建了该数组和哈希值。
可用 3 个方法管理集群的成员：
add 方法向集群添加一个 person。
remove 方法删除一个 person。
get_people 方法提取该数组，以对它进行迭代。
可用两个方法管理集群。calculate_centroid 方法根据集群当前的成员来更新集群的均值。calculate_gd 方法返回集群重心与一个所传递的 person 对象之间的欧几里德距离。
清单 2 显示了一个 k-means 的 Ruby 实现，它处理 图 2 中的示例数据。
清单 2. 实现基本的 k-means 算法
[mw_shl_code=ruby,true]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[/mw_shl_code]

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

。检查所有成员后，会重新计算重心并再次检查成员。未出现进一步的变化时，算法完成工作。
要将示例用户分组到 k = 2 个集群中，可调用 kmeans 方法，如清单 3 中的控制台会话所示。
清单 3. 运行简单的 k-means 实现
[mw_shl_code=applescript,true]$ 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

$[/mw_shl_code]

该算法已成功地将 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 编写的）示例应用程序
[mw_shl_code=bash,true]#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;
}[/mw_shl_code]

清单 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 推荐引擎
[mw_shl_code=applescript,true]$ ./topn
Recommendations (2) are 2 and 8
$[/mw_shl_code]

在本例中，该引擎推荐特定的读者可能喜欢 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 函数
[mw_shl_code=ruby,true]#!/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[/mw_shl_code]
如 清单 6 中所示，除了 REST 命名空间和命令，您还定义了：
apikey（使用来自 easyrec 网站的示例密钥）
tenantid
对推荐感兴趣的用户 ID
您还指定对 ITEM 类型感兴趣，以允许所有推荐的产品。定义统一资源标识符 (URI) 后，使用 Ruby 的 Net:HTTP 客户端 API 发送请求，然后返回响应并存储它。解析此响应，然后在每个返回的项目上对它进行迭代。
清单 7 演示了在 Interactive Ruby Shell (IRB) 中为特定用户使用 recommend_for_user() 函数。在本例中，推荐内容包含了根据该用户的偏好得出的音乐选择。
清单 7. 使用 easyrec 创建推荐内容
[mw_shl_code=applescript,true]irb(main):027:0> recommend_for_user( "24EH1723322222A3" )
Request for recommendations for user 24EH1723322222A3
Beastie Boys - Intergalactic
Gorillaz - Clint Eastwood
irb(main):028:0>[/mw_shl_code]
清单 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&#174; 中需要 Mono 支持）。

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


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

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

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



结束语
随着 Web 的规模不断扩大，个性化趋势的加剧继续推动着推荐引擎领域内不断出现新的算法和丰富多样的解决方案。采用多种编程语言的广泛项目 — 从用于开发协作式过滤算法的环境到用于算法评估的框架，一直到全功能的解决方案 — 在开源领域中常常可以看到。