推荐系统-关键模块
  • Jul 15, 2019
  • 13 minutes read

日志和数据

推荐系统离不开数据，主要是来自日志。关于采集数据，按照用途分类有三种：

  1. 报表统计
  2. 数据分析
  3. 机器学习

数据采集

推荐系统收集日志，有：日志的数据模型、收集哪些日志，用什么工具收集，收集的日志怎么存储四个部分。

数据模型

数据模型就是把数据归类，不同的数据应用，数据模型略有不同。

数据模型帮助梳理日志、归类存储，以方便在使用时获取。针对推荐系统，除了Relation数据外，其他都是必须的数据。

矩阵 行 列 数据类型 说明
人、属性矩阵 用户ID 属性 User Profile 用户属性数据
物、属性矩阵 物品ID 属性 Item Profile 物品属性数据
人、人矩阵 用户ID 用户ID Relation 关系数据，并不是每个产品都有，社交网络有社交关系
人、物矩阵 用户ID 物品ID Event 事件数据，用户发生的所有行为和动作，比如曝光、浏览、点积、收藏、购买

数据在哪

数据的产生主要来自两种：

  1. 业务运转必须要存储的记录，如用户注册资料，主要来自业务数据库，通常都是结构化存储，如MySQL
  2. 用户使用产品时顺便记录下来的，这叫做埋点，按照技术手段分：
    1. SDK埋点：嵌入第三方统计的SDK到自己的APP或者网站，复杂度高，一旦埋点有错，需要更新客户端版本
    2. 可视化埋点： 在SDK基础上，埋点工作通过可视化配置的方式完成。业界有开源方案可参考，如：Mixpanel。不能收集到非界面数据
    3. 无埋点：不是不埋点收集数据，而是尽可能多自动收集所有数据集，但是使用方按照自己的需求去使用部分数据 按照收集数据的位置分为前端埋点和后端埋点，一个是在前端请求点击时记录，一个是服务器端收到请求时打印一条业务日志。

对于推荐系统，所需要的数据基本上都可以从后端收集，采集成本较低，但是有两个要求：要求所有的时间都需要和后端交互，要求所有的业务响应都要有日志记录。后端收集业务日志好处：

  1. 实时性：可以做到实时采集。
  2. 可及时更新：不需要重新发布客户端版本
  3. 开发简单，不需要单独维护一套SDK

元素有哪些

后端收集时间数据需要业务服务器打印日志，大致需要包含以下几类元素：

  1. 用户ID：唯一标示用户身份
  2. 物品ID：唯一标示物品
  3. 事件名称：每一个行为一个名字
  4. 事件发生时间： 时间非常重要
  5. 事件发生时的设备信息和地理位置信息等等
  6. 从什么事件而来
  7. 从什么页面而来
  8. 事件发生时用户的相关属性
  9. 事件发生时物品的相关属性

把日志记录现象成一个Live快照，内容越丰富就越能还原当时的场景。

怎么收集

典型数据采集架构

最左边是数据源，有两部分，一个是来自非常稳定的网络服务器日志，由Nginx或者Apache产生。

业务服务器，这类服务器会处理具体场景的具体业务，甚至推荐系统本身也是一个业务服务器。这类服务器有各自不同的日志记录方式，例如Java是Log4j，Python是Logging等，还有RPC服务。这些业务服务器通常分布在多台机器上，需要由产生的Flume汇总。

Kafka是一个分布式消息队列，按照Topic组织队列，订阅消费模式，可以横向水平扩展，非常适合作为日志清洗计算层和日志收集之间的缓冲区。

在Kafka后端一般是一个流计算框架，上面有不同的计算任务去消费Kafka的数据Topic，流计算框架实时地处理完收集到的数据，会送完分布式的文件系统中永久存储，一般是HDFS。

日志的时间属性非常重要。因为HDFS中存储日志时，为了后续抽取方便快捷，一般要把日志按照日期分区。

质量检验

关注数据质量，大致需要关注下面几个内容：

  1. 是否完整？事件数据至少要有用户ID、物品ID、事件名称三元素才算完整，才有意义
  2. 是否一致？
  3. 是否正确？
  4. 是否及时？

数据分析关心数据的维度，推荐系统更加关注事件。

矩阵 算法应用
人、属性矩阵 内容推荐、模型融合
物、属性数据 内容推荐、模型融合
人、人矩阵 协同过滤、矩阵分解
人、物矩阵 协同过滤、矩阵痕迹、深度学习、模型融合

实时推荐

推荐系统是利用已经存在的用户和物品之间的连接去预测其他连接，连接是有时间属性的，因此，实时推荐非常重要。

实时推荐的三个层次：

  1. 第一层，“给的及时”，指服务的实时响应
  2. 第二层，“用的及时”，指特征的实时更新，刚刚购买了一个商品，立即更新到用户历史行为中，参与到下一次协同过滤推荐结果的召回中，过一会，首页推荐做出相应变化，这一层次的操作影响范围只是当前用户
  3. 第三层，“改的及时”，指模型的实时更新，刚刚购买了一个商品，实时地去更新这个商品和所有该用户购买的其他商品之间的相似度，因为这些商品对应的共同购买用户数增加了，商品相似度就是一种推荐模型，所以它的改变影响的是全局推荐

构建第三层次的推荐系统

架构概览

一个处在第三层次的推荐系统，需要满足下面三个条件：

  1. 数据实时进来
  2. 数据实时计算
  3. 结果实时更新

第三层次实时推荐系统基本架构

实时数据

实时流数据的接入，需要一个实时的消息队列，开源解决方案Kafka已经很成熟。

Kafka生产者消费模型

Kafka以生产者消费者的模式吞吐数据，这些数据以主题的方式组织在一起，每一个主题的数据会被分为多块，消费者各自去消费，互不影响，Kafka也不会因为某个消费者消费了而删除数据。

每一个消费者各自保存状态信息：所消费数据在Kafka某个主题某个分块下的偏移位置。

一个生产者可以看做一个数据源，生产者决定数据源放进哪个主题中，也可以通过一些算法决定数据如果落进哪个分块里。

Kafka的核心思想是：往某个主题写数据，以及从某个主题读取数据。

流计算

整个实时推荐建立在流计算平台上，常见的流计算平台有Twitter开源的Storm，Yahoo开源的S4，还有Spark中的Streaming。推荐Storm，最新的流计算框架FLink表现强劲，高吞吐低延迟也值得尝试。

Storm有以下几个元素：

  1. Spout：喷嘴，水龙头，接入一个数据流，然后以喷嘴的形式把数据喷洒出去
  2. Bolt： 螺栓，两端可以接入数据流
  3. Tuple：元组，流在水管中的水
  4. Topology，拓扑结构，前面三个一起组成了一个有向无环图

水管由Storm提供，只需要编写水龙头和螺栓即可。

Storm中要运行实时推荐系统的所有计算和统计任务，有：

  1. 清洗数据
  2. 合并用户的历史行为
  3. 重新更新物品相似度
  4. 在线更新机器学习模型
  5. 更新推荐结果

效率提升

在协同过滤中，物品之间的相似度计算，可以利用剪枝、加窗、采样、缓存四个方法提升计算效率。

剪枝

两个物品之间的相似度范围为[0,1]，因此将两个物品之间的相似度看成一个随机变量，这个随机变量有一个期望值，根据Hoeffding不等式，针对有界的随机变量，经过一定的更新次数之后，就可以确定一个置信区间，即可以说明两个物品是否相似,而且如果此时的相似度小于设定阈值，就可以斩钉截铁地说：这两个物品不相似，即在N+1次的更新时就不需要再计算这两个物品的相似度了。

Hoeffding不等式：随机变量的真实期望值不会超过x+e的概率为1-delta，其中e的值是：

$$ \epsilon = \sqrt{\frac{\ln{\frac{1}{\delta }}}{2n}} $$

公式中： x是历次更新得到的相似度平均值，n是更新过的次数。确定了delta和epsilon之后，就知道更新多少次之后就可以确定两个物品之间的相似度关系，可以不再进行计算。

假如，delta=0.05，则：

与真实相似度误差 epsilon 最少更新次数
0.1 150
0.05 600
0.01 14979
加窗

用户兴趣衰减，潜在的意思是比较久远的用户历史行为数据所起的作用应该小一些。通过设定一个时间窗口，时间窗口内的历史行为数据参与实时计算，窗口外的不再参与实时计算，有两种窗口方法：

  1. 最近K次会话。用户如果反复来访问产品，每次访问是一次会话，那么实时计算时只保留最近K次会话信息
  2. 最近K条行为记录，不管访问多少次，只保留最近K条历史行为事件，参与到实时推荐中
采样

当推荐系统遇到热门的物品或者异常活跃的用户，或者有时候就只是突然一个热点爆发了，会在短时间内产生大量的数据，除了前面的剪枝方法，还可以对这种短时间大量出现的数据采样，有均匀采样，加权采样等。

合并计算

在进行相似度计算时，如果突然大量涌入行为数据，可以不必每一个用户行为时间都去更新相似度信息，而是可以在数据流的上游做一定的合并，等合并若干事件数据后，再送入下游去更新相似度和推荐结果。

缓存

提高实时推荐系统的效率，甚至不只是推荐系统，在任何互联网应用的后端，缓存都还是提高效率必不可少的部分。可以对高频访问的物品或者用户增加缓存，考虑包括：

  1. 活跃用户的历史行为数据
  2. 热门物品的特征数据
  3. 热门物品的相似物品列表

缓存系统一般采用Memcached或者Redis集群。缓存的数据一致性难以保证，需要注意。

实时更新的推荐结果同步到推荐服务所依赖的线上数据库，这个线上数据库还要定期被线下离线批量的推荐结果所替代，这样一来，实时推荐和离线批量之间就形成了互为补充的作用，这个模式也就是大数据架构常见的Lambda架构。

并不是每一种推荐算法都适合做实时推荐，或者没有必要。Bandit算法天然就适合在线实时进行，通过与用户之间反复互动更新推荐。

数据驱动和实验平台

数据驱动的重点是做对比实验，或者叫ABTest，通过对比，让模型、策略、设计等不同创意和智慧结晶新陈代谢，不断迭代更新。

互联网实验，需要三个要素：

  1. 流量：流量就是用户的访问，也是实验的样本来源
  2. 参数：参数就是各种组合
  3. 结果：实验的全过程都要有日志记录

在实验之初，设计人员需要考虑下面这些问题：

  1. 实验的起止时间
  2. 实验的流量大小
  3. 流量的分配方式
  4. 流量的分配条件
  5. 流量如何无偏置

重叠实验架构

所谓重叠实验，就是一个流量从进入产品服务，到最后返回结果呈现给用户，中间设置了好几个检查站，每个检查站都在测试某些东西，这样同时做多组实验就是重叠实验。

重叠实验最大的问题是怎么避免流量偏置，需要引入三个概念：

  1. 域：是流量的一个大的划分，最上层的流量进来时首先是划分域
  2. 层：是系统参数的一个子集，一层实验是对一个参数子集的测试
  3. 桶：实验组和对照组就在这些桶中

层和域可以互相嵌套，多层实验能做到重叠而不带来流量偏置，分层示意图如下：

关于分层实验，需要注意：

  • 关于分桶时，不是只对Cookie或者UUID散列取模，而是加上了层ID，是为了让层和层之间分桶相互独立。
  • Cookie或者UUID散列成整数时，考虑用均匀的散列算法，如MD5
  • 取模要一致，为了用户体验，虽然是分桶实验，但是同一个用户在同一个位置每次感受不一致，会有损用户体验

Google的重叠实验架构还有一个特殊的实验层，叫做发布层，优先于所有其他的实验层，它拥有全部流量，这个层中的实验，通常是已经通过ABTest准备全量发布的了。

流量分配方式：

  1. 用户身份ID
  2. Cookie+层ID取模
  3. 完全随机
  4. 用户ID+层ID取模
  5. Cookie+日期取模

Google的整个实验平台示意图如下；

统计效果

实验得到的流量不够，可以说实验的结论没有统计意义，也就浪费了这些流量，而实验在已经具有统计意义之后，如果还占用流量做测试，则也是在浪费流量。Google使用下面的公式确定实验规模：

$$ N >= 10.5 (\fran{s}{\theta})^2 $$

公式中： 1. s是实验指标的标准差 2. theta是希望检测的敏感度，比如想检测到2%的CTR变化

上面这个公式计算出来的实验规模，表示以90%的概率相信结果的显著性，也就是有90%的统计功效。

对比实验的弊端

ABTest的弊端如下：

  1. 落入实验组的流量，在实验期间，可能要冒着一定的风险得到不好的用户体验，在实验结束之前，这部分流量以100%的概率面对这个不确定性
  2. 要得到较高统计功效的话，就需要较长时间的测试，如果急于得到结果全面上线来说有点不能接收
  3. 下线的实验组如果不被人想起，就不会再有机会得到测试

针对这个问题，可以在实验平台中使用Bandit算法替代流量划分的方式，通过Bandit算法选择不同的参数组合、策略，动态实时地根据用户表现选择策略，一定程度上可以避免上述弊端。

推荐系统服务化、存储选型以及API设计

以下讲到的储存，专指近线或者在线部分所用到的数据库，并不包括离线分析时所设计的业务数据库或者日志数据库。

离线阶段产生的数据类型：

  1. 特征： 特征数据指用户画像、物品画像等，更新并不频繁
  2. 模型： 机器学习模型等，这类数据的特点是它们大都是键值对，更新比较频繁
  3. 结果： 一些推荐算法在离线阶段批量计算出推荐结果后，供最后融合时召回使用，任何一个数据都可以直接做推荐结果，如协同过滤结果。

特征数据有两种：

  1. 稀疏的： 文本类特征，用户标签类特征
  2. 稠密的： 各种隐因子模型的产出参数，Embedding向量，可以考虑使用文件存储，采用内存映射的方式，会更加高效地读取和使用

特征数据以两种形态存在：

  1. 正排：以用户ID或者物品ID作为逐渐查询，需要用列式数据库存储，如HBase，Cassandra
  2. 倒排：以特征作为主键查询，需要用KV数据库存储，如Redis，Memcached

模型数据分为两种：

  1. 机器学习模型：在模型训练阶段，如果是超大规模的参数数量，业界一般采用分布式参数服务器，中小公司采用更加灵活的PMML文件作为模型的存储方式
  2. 非机器学习模型：如相似度矩阵

最后是预先计算出来的推荐结果，或者叫做候选集，这类数据通常是ID类，召回方式是用户ID和策略算法名称。通常采用高效的KV数据库存储，如Redis。

特殊的数据存储工具：ElasticSearch，一个构建在开源搜索引擎Lucene基础上的分布式搜索引擎，也常用于日志存储和分析。但由于它良好的接口设计，扩展性和尚可的性能，也常常被用来做推荐系统的简单第一版，直接承担了存储和计算的任务。

列式数据库

列式数据库与行式数据库相对，有个列族的概念，可以对应于关系型数据库中的表，键空间的概念，对应于关系型数据库中的数据库。

列式数据库适合批量写入和批量查询，因此常常在推荐系统中被广泛使用。主要有：

  1. Cassandra：是一个去中心化的分布式数据库，在数据库的CAP理论中可以平滑权衡，读写性能要优于HBase，更适合推荐系统
  2. HBase：是一个有Master节点的分布式存储数据库，在数据库的CAP理论中是强一致性

通过行逐渐以及列名就可以访问到数据矩阵的单元格值。

键值数据库

Redis可以看成是一个网络版本的HashMap，但是它存储的值类型比较丰富，有字符串、列表、有序列表、集合、二进制位。其数据都是放在内存中的，闪电般的速度来读取。

在推荐系统中，Redis常常用于以下场景：

  1. 消息队列：List类型的存储可以满足这一需求
  2. 优先队列：比如兴趣排序后的信息流，或者相关物品，对此sorted set类型的存储可以满足这一需求
  3. 模型参数：典型的键值对类型可以满足

Redis的弊端是不太高可用，对此有一些集群解决方案。

非数据库

虚拟内存映射，称为MMAP，可以看成是一个简陋版本的数据库，其原理就是把磁盘上的文件映射到内存中，以解决数据太大不能读入内存，但又想随机读取的矛盾需求。

MMAP在推荐系统中应用：训练的词嵌入向量，或者隐因子模型，当特别大时，可以二进制存储在文件中，然后采用虚拟内存映射的方式读取。

PMML文件专门用来保存数据挖掘和部分机器学习模型参数以及决策函数的，当模型参数还不足以称之为海量时，PMML是一个很好的部署方法，可以让线上服务在做预测时并不依赖离线时的编程语言，以PMML协议保存离线训练结果就好。

API

除了存储，推荐系统作为一个服务，应该以良好的接口和上游服务之间交互。主要有两大类：数据录入和推荐服务

可以用于数据采集的埋点，或者其他数据录入，常见API如下：

本文是《推荐系统三十六式》的读书笔记，仅限个人学习，请勿用作商业用途，谢谢。

Note: Cover Picture

  • RS
    • Previous
    推荐系统-常见架构
    Next
    推荐系统-效果保证