机器学习系列(17)_Yelper推荐系统

个人博客

原文地址：yelper recommendation system
原文翻译与校对：@酒酒 && @寒小阳
时间：2016年10月。
出处：http://blog.csdn.net/han_xiaoyang/article/details/52778321
声明：版权所有，转载请联系作者并注明出

1. 我们为什么需要推荐系统？

“推荐”可是个当红话题。Netflix愿意用百万美金召求最佳的电影推荐算法，Facebook也为了登陆时的推荐服务开发了上百个项目，遑论现在市场上各式各样的应用都需要个性化服务。

“从互联网中提取信息犹如用消防栓饮水”（Mitchell Kapor）。如今的信息量早已过载，要依据如此嘈杂的信息做出正确决定显然是艰难的。这也是为什么推荐系统日渐流行，尤其在像Netflix, Amazon, Echo,和Facebook这类需要个性化服务的产品。 在大数据时代，实时推荐可能是新的趋势，因为：

• 实时推荐使得用户和服务商都能得到及时的信息反馈
• 这将大大加速产品和公司的升级
• 这也使得实时分析成为可能

2. “Yelper”是什么？

根据2016年的"Yelp Challenge"数据来看，“Yelper”能够做到：

• 按照城市划分商业数据来进行更周到的推荐服务
• 用Spark的MLlib实现协同过滤
• 用D3和其他图像工具实现以用户为主导的可视化商业分析
• 用Scala中Spark GraphX做用户-商业关系图分析
• 用Spark Streaming和Apache Kafka模拟实时的用户请求处理
• 给用户推荐高评服务时的谷歌地图展示

Yelper实现的背后展示了一个事实：
知道机器学习背后的工作原理已经不能满足现在的需求了，数据科学家们需要对即将到来的新挑战做好准备：在大数据时代对大规模的流数据的挖掘分析。

Yelper的GitHub主页：https://github.com/sundeepblue/yelper_recommendation_system

PPT展示

3. 搭建Yelper的主要模块

Yelper主要由5部分构成，如下图所示。这张图展示了Yepler从接受请求到处理的大致流程。

3.1 数据预处理

Yelper的数据主要基于Yelp Challenge 2016 Dataset, 其中包括了：

• 2.7M的评论和来自687K个用户关于86K商户的649K条建议
• 566K个商业服务特征，例如营业时间，停车信息，周边环境等
• 共包括有4.2M种关系（edge）的关于687K用户的社交网络。
• 对86K商户信息的不断汇总更新
• 和公司及其服务相关的200,000张图片

Yelper系统主要依赖于687K用户和86K商户的数据。而对它们的预处理主要包括两步（Python 代码）：

• 将顾客和商业服务的ASCII编码字符串格式的ID信息转为整数索引
• 把商业服务的数据按9个城市划分（按城市划分数据结构示例）：us-charlotte, us-lasvegas, us-madison, us-phoenix, us-pittsburgh, us-urbana-champaign, canada-montreal, germany-karlsruhe, uk-edinburgh

在Yelper系统中，M为百万单位，所有的商业ID在[0，1M]范围中，而由于顾客数量远多于这个数，顾客ID在[10M,+∞]范围内。这样的话以10M为单位我们可以将顾客信息和商业信息联系起来。总的来说，将字符串换为整数索引有这些好处：

• 便于使用Spark GraphX，因为它要求所有的节点和边都具有整数ID
• 用D3 Javascript可视化时能更方便地编写和查错
• 在以CSV或者JSON文件导出时文件大小会大大减小，使得加载和操作都更快捷
• 可以根据数字大小范围就能确认是顾客ID还是商业ID

而将商业数据以城市划分也大有好处：

• 可以根据城市特色建立不同的推荐模型
• 划分后，每个城市的数据量都比原数据小了很多，可以更快地进行模型训练
• 按城市来调整模型和参数更加灵活
• 可以根据现有城市模型向新城市推广，毕竟这个世界上有成千上万的城市
• 而就像每个人都是不同的，每个城市也都各具特色，用一个模型概括所有城市显然是不科学的

3.2低秩矩阵分解 （Low-Rank matrix factorization）

我们希望做出高相关的推荐，而现有的推荐系统主要使用2种算法：

• 以协同过滤为基础的关联推荐算法，例如low-rank matrix factorization，SVD等
• 以内容为基础的推荐（content-based recommendation）

这两种方法各具优劣，我们先简明扼要地说一下第一种算法。如果有时间的话，将第二种算法整合进系统也不难。

我们用Spark MLlib来训练ALS-based协同过滤模型（Python 代码戳这里）。以下是大致的步骤：

• 用Spark加载数据文件F，F记录了不同城市的用户-商业服务-星级评分的元祖数据。（Las Vegas的样本元祖数据）
• 将F里的数据分为三组：60%为训练集，20%为测试集，20%为验证集。
• 设置矩阵的秩作为备选参数值（rank values），比如4，8，12，用交叉验证方法调参找出最佳的参数，调参标准是最小化RMSE（Residual Mean Squared Error）值
• 用选取的参数建模
• 将模型输出到对应城市的目录下（Las Vegas训练模型样本）

最后一步输出，最好将模型固化到硬盘或云盘里，这样便于后来的压缩、传输和缓存。

3.3 动态网络的可视化

Yelper尤其对于分析用户-商业服务的相互作用，从而对城市得以有更深的思考感兴趣。为什么？因为我们认为：

• 总的来说，一个城市拥有更多的商业机会，这个城市发展的潜能就更大；
• 而更多的用户（居民，游客，人口等）可以刺激城市开发更多的商业服务来满足用户的需求

如下是建立城市为单位的用户-商业服务关系网络步骤：

• 用Spark GraphX提取图中的connected components（Scala 代码戳这里）
• 用Python生成动态的用户-商业服务关系网络图（Python代码戳这里）以生成Javascript JS文件（js 示例代码戳这里），用js文件做D3可视化（HTML代码戳这里）

下图是Madison(US)城市的示例。图中每个节点代表用户（绿色）或商业服务（蓝色）。如果一个用户对一个服务进行过评分，就会对应生成一条从用户（u）出发到商业服务(b)的边（edge）连接这两个节点，即边u-->b。Madison有超过10K条边，遗憾的是D3.js处理不了这么大的图，所以我们随机选取了一小部分在Chrome里展示。

从这个关系网络里我们能发现什么？至少我们可以得到用户和商业服务的拓扑关系。图中边（红色）的密度从某种意义上反映了一个城市里用户对其所有的商业服务的评级。如果每个城市都能生成一个这样的关系网络，我们会发现每个城市的图都是不同的。这样单从这个关系图里就能进一步提取城市更深的信息，例如图形的in/out degree，聚合程度，page rank分析，min cut，社区发现等。

3.4 利用谷歌地图API的前端服务

Yelper有一个服务器让用户可以收到推荐。这个服务器需要用到：

• Spark
• Flask
• cherrypy
• Python paste

Yelper的前端具有以下特点：

• 用户可以搜索任何他们感兴趣的关键字（不仅仅是餐馆）（Python 代码戳这里）
• 推荐的服务能够在谷歌地图中展示出来（Javascript 地图代码戳这里）
• 用户可以修改城市名和希望得到的推荐数目
• RESTful API可以让用户在URL上修改城市/前K项推荐/关键字

下图是用户与Yelper的互动展示。ID为“10081786”的用户提出了Charlotte城市里关键字为“restaurants”，“book store”,"library"和“ice cream”的推荐请求，Yelper返回了“topK”条推荐结果，并且用谷歌地图API展示了地点信息。

3.5 模拟处理实时请求

假设有成千甚至成百万的用户想要得到不同城市的推荐，处理这么多请求是很具挑战性的，因为：

• Yelper需要能稳定地处理大量来自不同客户端的用户请求（手机，iPad,笔记本等）
• 用户的请求必须得到及时的反馈
• 对于这么大量的推荐请求，Yelper不能丢失任何一条，否则将影响用户的满意度和忠实度
• 这样我们就需要一个处理这些请求的网络计算队伍
• 而同时我们需要解决用户对不同服务的要求

这也只是冰山一角，实际需要处理的问题更多，所以我们需要一个强大的推荐架构。这篇文章就不再做更细的讨论，一个简单的办法是把这些来源不同的请求看作一个不间断的信息流（non-stopping stream），用Apache Kafka将这些请求转到Kafka上，然后用Spark Streaming以fault-tolerant和scalable方式进行流处理。这样做的好处有：

• 处理流程对于任何突发情况都具有容错性
• 可以pipe不同类型的信息
• 信息可以模块化（Modulization）
• 方便处理

下图展示了我们模拟的实时大量推荐请求处理（Python 代码戳这里）。terminal左边的窗口是用Spark Streaming以频率为1.5秒处理的用户请求。注意信息以时间戳的形式显示，例如“Time: 2016-09-25 14:37:22.500000”。每个推荐结果前都有Yelper的logo。

在terminal的右边，我们用python script生成随机时间间隔的用户请求。这些请求被piped到Apache Kafka上，这样Spark Streaming就能处理这些请求了。

4.深入探究用户-商业服务关系网络

建立静态用户-商业服务关系网络可以用Python里的graph-tool包（Python 代码戳这里）（网络示例图片）。我们现在来看一看这个关系网络到底什么样子。像之前描述的，如果一个用户对一个服务做了评级，关系图里就会有一条边连接着用户和商业服务两个节点。

但是可视化这些连接并不容易。按理说图中的节点和边越多这个图就更准确。可是从可视化的角度说，这么多边和节点看起来犹如一团乱麻。所以我们用了两个简单的小技巧：在一个城市的所有边中，我们要么随机选择1%（或2%）的边，要么只选择前1%（或2%）的边。

尽管我们只用了2%，也能从这2%数据生成的网络图中挖掘到大量信息。下面来看看3个美国城市的图：Charlotte, Las Vegas, 和Pittsburgh。

4.1 Charlotte, US

我们随机选了1%的边，共3312条。大概是如下的样式：

4.2 Las Vegas, US

同样随机选择了1%的边，共11547条。大概是如下的样式：

如果我们随机抽取%2（23095条）的边呢？就变成下面这个样子了：

如果选择前23095条边的话，图会是这个样子：

4.3 Pittsburgh, US

对匹兹堡随机抽取2%的边（2230条）。

4.4 从这些关系图中我们能得到什么信息？

类似分析动态网络图，利用图计算模型和分析我们也能从静态图中得到很多有用的信息。比如说，众所周知，拉斯维加斯的经济要好于匹兹堡。从图上看，拉斯维加斯的图也是明显地有更多节点，进来每个节点的边也更多。

以下是一些可以更多思考的方向：

• 抽取图中具有高评分的边（星级>4.5）形成一个关于高质量商业服务的关系图，比较不同城市的这些图。
• 建立低星级的图（星级<2.5），看看图形分布，从分布中思考为什么它们的评分这么低。
• 在图中加入时间戳信息，比较同一城市不同时间的关系图可以告诉我们一个城市随着时间发展的情况。
• 利用network community discovery algorithm寻找潜在的新的商机。
• 按照不同服务种类建立更详细的用户-商业服务关系图。比如餐厅，图书馆等，可以深入分析不同商业模式的发展。

5.后续工作

• 更多的图分析
  
  • 用Spark GraphX Python和graph-tool包做page rank分析
  • 发现社区（community discovery）（类似Facebook的社交网络）
• 改善推荐
  
  • 加入Content-based recommendation
  • 将商业服务聚类分析
  • 用卷积神经网络从图片中提取信息