数据库 基于 Postgres 实现一个推荐系统

hooopo · 2018年09月20日 · 最后由 hooopo 回复于 2020年07月27日 · 12540 次阅读
本帖已被管理员设置为精华贴

对于内容类网站或者 APP,搜索和推荐已经是标配。搜索相对容易,使用 Elasticsearch 简单配置一下就可以做出一个性能还不错效果也还可以的搜索引擎,然而,推荐系统的话,没有专门的团队实践起来还挺困难的。

网上推荐系统相关的理论非常多,但可用的实践却少见,要么是介绍相似度算法的 demo,要么是讲高大上架构的文章,看懂这些离真正实现一个推荐系统还差着十万八千里。本文的重点不是介绍原理,也不是探讨算法优劣,侧重点在于如何基于 Postgres 快速落地一个性能还不错的推荐系统。

准备工作

通过movielens.sql创建一个 movielens 数据库

createdb movielens
curl https://raw.githubusercontent.com/ankane/movielens.sql/master/movielens.sql | psql -d movielens

主要包含以下关系表,其中 ratings 表大概 10w 左右的数据:

\d ratings
               Table "public.ratings"
  Column  |            Type             | Modifiers
----------+-----------------------------+-----------
 id       | integer                     | not null
 user_id  | integer                     |
 movie_id | integer                     |
 rating   | integer                     |
 rated_at | timestamp without time zone |
\d movies
                      Table "public.movies"
    Column     |          Type          |        Modifiers
---------------+------------------------+-------------------------
 id            | integer                | not null
 title         | character varying(255) |
 release_date  | date                   |
\d users;
                Table "public.users"
    Column     |          Type          | Modifiers
---------------+------------------------+-----------
 id            | integer                | not null
 age           | integer                |
 gender        | character(1)           |
 occupation_id | integer                |
 zip_code      | character varying(255) |

另外还需要一个 Rails 项目:https://github.com/hooopo/movielens-rails-app

相似度算法

“推荐系统中,推荐算法分为两个门派,一个是机器学习派,另一个就是相似度门派。机器学习派是后起之秀,而相似度派则是泰山北斗,以致撑起来推荐系统的半壁江山。”

相似度的算法非常多,下面来介绍一下常用的相似度算法以及 Ruby 代码实现。

Jaccard Similarity

Jaccard 相似度,是两个集合的交集元素个数在并集中所占的比例。由于集合非常适用于布尔向量表示,所以 Jaccard 相似度简直就是为布尔值向量私人定做的,即 Jaccard 相似度非常适合做隐式反馈数据,比如收藏行为、加购物车行为、点击行为等。

def jaccard_sim(other_movie)
  # 假设评分大于等于3的为喜欢
  other_user_ids = other_movie.ratings.where("rating >= 3").pluck(:user_id)
  user_ids       = self.ratings.where("rating >= 3").pluck(:user_id)

  # 交集数量
  intersection = (other_user_ids & user_ids).count

  # 并集数量
  union        = (other_user_ids | user_ids).count

  return 0 if union.zero?
  intersection.to_f / union.to_f
end

Cosine Similarity

余弦相似度在度量文本相似度、用户相似度、物品相似度的时候都较为常用,它与向量的长度无关。

def cosine_sim(other_movie)
  other_user_ratings = other_movie.ratings.map { |r| [r.user_id, r.rating] }.to_h
  user_ratings       = self.ratings.map { |r| [r.user_id, r.rating] }.to_h

  # 有共同评价的用户
  union_user_ids = other_user_ratings.keys & user_ratings.keys
  return 0 if union_user_ids.count == 0

  u = other_user_ratings.values_at(*union_user_ids)
  v = user_ratings.values_at(*union_user_ids)

  dot_product = u.zip(v).map { |a, b| a*b }.sum

  magnitude_u = Math.sqrt(u.map { |x| x*x }.sum)
  magnitude_v = Math.sqrt(v.map { |x| x*x }.sum)

  cosine_similarity = dot_product.to_f / (magnitude_v * magnitude_u)
end

Pearson Correlation

皮尔逊相关度,实际上也是一种余弦相似度,不过先对向量做了中心化,向量 p 和 q 各自减去向量的均值后,再计算余弦相似度。皮尔逊相关度和修正后的余弦相似度很像,但其实是有差别的,主要区别是均值的定义不同。

def pearson_sim(other_movie)
  other_user_ratings = other_movie.ratings.map { |r| [r.user_id, r.rating] }.to_h
  user_ratings       = self.ratings.map { |r| [r.user_id, r.rating] }.to_h

  # 有共同评价的用户
  union_user_ids = other_user_ratings.keys & user_ratings.keys
  n = union_user_ids.count
  return 0 if n == 0

  u = other_user_ratings.values_at(*union_user_ids)
  v = user_ratings.values_at(*union_user_ids)

  sum_u = u.sum
  sum_v = v.sum 

  sum_u_sq = u.map { |x| x*x }.sum 
  sum_v_sq = v.map { |x| x*x }.sum

  prod_sum = u.zip(v).map { |x, y| x*y }.sum
  num = prod_sum - ((sum_u * sum_v) / n.to_f)
  den = Math.sqrt((sum_u_sq - (sum_u * sum_u) / n.to_f) * (sum_v_sq - (sum_v * sum_v) / n.to_f))
  return 0 if den == 0
  [num / den, 1].min
end

最后,做下演示:

movie = Movie.first
movie.recommendation_movies(limit: 10, using: :jaccard_sim)

基于 Postgres 的推荐系统

上面代码的目的是为了学习三种算法的实现,所以没有复用,也没有性能方面的优化。纯 Ruby 来做推荐基本不靠谱,所以我们来试一下基于 Posgres 和 Jaccard 相似度来实现一个推荐系统。

首先上面 Ruby 代码里假设 rating 大于 3 就是喜欢,这并不十分准确,有些人评分可能非常严格,他只打 1-3 分,那么对于他来说,其实 3 分就算喜欢了。

为了应对这种情况,我们用用户均值来推断他是否喜欢一部电影。另外我们要便于以后计算方便,把计算结果先缓存到 movies 的 like_user_ids 字段上。

# 增加缓存字段like_user_ids,存储喜欢这部电影的用户ID
def change
  add_column :movies, :like_user_ids, :integer, :array => true, :default => '{}'
end

# 使用PG内置扩展intarray:https://www.postgresql.org/docs/current/static/intarray.html
# 对intarray的求交集操作可以利用gin or gist索引
def change
  enable_extension :intarray
end

def change
  execute <<-SQL
    CREATE INDEX like_user_ids_idx_2 ON movies USING gin(like_user_ids gin__int_ops);
  SQL
end

第一次,批量初始化 like_user_ids 字段,单条记录更新可以实时计算出来填充进去。

WITH avg_rating_per_user AS ( 
  SELECT movie_id, 
         user_id, 
         rating,
         AVG(rating) OVER (PARTITION BY user_id) AS avg_rating 
    FROM ratings
),
rating_per_movie AS (
  SELECT movie_id, 
         array_agg(user_id) AS like_user_ids
    FROM avg_rating_per_user
   WHERE rating > avg_rating 
GROUP BY movie_id
)

UPDATE movies AS m 
   SET like_user_ids = r.like_user_ids
  FROM rating_per_movie AS r
 WHERE r.movie_id = m.id;

实时查询方案

def recommend_by_sql(limit: 10)
  Movie.find_by_sql(<<~SQL)
      SELECT array_length(m.like_user_ids & movies.like_user_ids, 1) / array_length(m.like_user_ids | movies.like_user_ids, 1)::float AS score,
             m.* 
        FROM movies 
             INNER JOIN movies AS m ON m.id != #{self.id} 
       WHERE movies.id = #{self.id}  
    ORDER BY 1 DESC 
       LIMIT #{limit}
  SQL
end

由于排序字段是一个动态计算值,所以这个语句无法利用索引,效率由 movies 表大小决定,但其实比 Ruby 版的已经快很多了。

预计算相似度方案

基于相似度的推荐算法的目标就是产生一个 Item-Item 或 User-User 的相似度矩阵。用关系型数据库的表示方法为:

\d item_item_matrix
      Table "public.item_item_matrix"
  Column   |       Type       |  Modifiers
-----------+------------------+-------------
 u_id      | integer          |
 v_id      | integer          |
 sim_score | double precision | default 0.0
Indexes:
    "index_item_item_matrix_on_u_id_and_v_id" UNIQUE, btree (u_id, v_id)
    "index_item_item_matrix_on_u_id_and_sim_score_and_v_id" btree (u_id, sim_score, v_id)

假设 movies 表的数量是 N,这个矩阵的条目数最大情况是 N*N,但实际并不需要全部 Item 之间的相似度都计算一遍:

  • 相同 ID 的 Item 相似度一定是 1,不需要计算和存储
  • 相似度为 0 的并不需要存储
  • 通过设置一个阈值 score,过滤掉相似度很小的,比如 score 小于 0.2 的就丢弃
  • 通过设置一个阈值 limit,过滤掉相关度排在后面的部分,比如一个 Item 最多存储相关度最高的 10 个 Item

经过上面的步骤,相关度矩阵的存储可以优化到 10*N 左右,即 10w 个电影的话,相似度矩阵里只需要存储 100w 条记录。

def recommend_by_matrix(limit: 10)
    Movie.find_by_sql(<<~SQL)
      SELECT m.*, matrix.sim_score
        FROM item_item_matrix AS matrix
             INNER JOIN movies AS m ON m.id = matrix.v_id
       WHERE matrix.u_id = #{self.id}
    ORDER BY matrix.sim_score DESC
       LIMIT #{limit}
    SQL
  end

如果 sim_score 已经预先计算好,这个查询直接可以 index only,记录条数再多也是非常快的。不管是 TopN 推荐还是评分预测,只要相似度矩阵计算好了,之后的事情易如反掌。

下面就来预计算相似度。

WITH matrix AS (
  SELECT u.id AS u_id, 
         v.id as v_id, 
         array_length(v.like_user_ids & u.like_user_ids, 1) / array_length(u.like_user_ids | v.like_user_ids, 1)::float AS sim_score 
    FROM movies AS u, 
         movies AS v 
   WHERE u.id > v.id AND v.like_user_ids && u.like_user_ids
), matrix_trim AS (
  SELECT u_id, v_id, sim_score FROM (
    SELECT u_id,
           v_id,
           sim_score,
           row_number() OVER (partition by u_id ORDER BY sim_score desc) AS row_num
      FROM matrix 
     WHERE sim_score > 0.01    /* 过滤掉相似度太小的值 */
  ) AS tmp WHERE row_num <= 10 /* 取最相近的10条记录 */
)

INSERT INTO item_item_matrix 
(
  SELECT u_id, v_id, sim_score FROM matrix_trim 
  UNION 
  /* u_id, v_id只需要计算一次,但存储两份,为了查询方便高效 */
  SELECT v_id AS u_id, u_id AS v_id, sim_score FROM matrix_trim
) 
ON CONFLICT (u_id, v_id) DO UPDATE SET sim_score = excluded.sim_score;

增量更新和离线处理

上面已经把相似度矩阵初始化完毕,对于新增数据,我们只需要把发生变化的数据重新计算一遍插入到 item item matrix 表里,这个代价非常小,可以 bulk,也可以离线。对于数量大的系统,初始化步骤也是可以分步批量插入的。由于基于 Postgres,对于超大量数据的情况,也可以平滑迁移到 greemplum 和 citus 或 redshift 这种可以并行查询计算的存储。

另外,也有一些基于 postgres 的推荐扩展,不过版本都不是很新:

Rei 将本帖设为了精华贴。 09月20日 18:05

很棒的文章

看不太懂但很赞

拿 rdbms 做?spark ml 要不要了解下?ALS 要不要了解下?

炮哥威武👍

hooopo 回复

👍 小项目 Postgres 应该是完全够用的

不过我觉得你说的有点问题,拿京东类比是非常有误导性的。

SKU 只是库存,类比到例子中的 Movie,这个量不会很大,但是用户评分这个行为会超级大。

类比到通用的推荐概念,user behavior item,SKU 只是反应了 item 数,ItemCF 的基础逻辑就是 Item 不会很多,但是 User 可能会超级多,User 的操作 behavior 也会超级多。

Hbase、Hive 这种面向大数据存储或数据仓库通常意义上面向的数据量都会在 TB 以上的情景。Postgres 单表在几亿时,已经比较吃力了。

总价下我的观点:

  1. 京东的体量不可能是用 Postgres 来解决类似问题的,这里面最大的量不是 Item,而是 Behavior
  2. 对于小项目(比如数据量在 10T 以下,每日产生数据大概几千万条)可以通过 Postgres 时序数据库timescaledb来存储;对于更大的项目,还是老老实实研究 Hadoop 这一套,毕竟入门难度偏高,在一个相对较小的数据量时入门会更容易,也利于自己打磨
  3. Spark 主要是解决分布式计算,Hbase、Hive、Elasticsearch 等都提供了 Spark RDD 支持。用 Spark 分布式更容易些,自己写一套分布式算法相对还是更困难的。

所以,如果是 Demo,我觉得可以直接用 Postgres 来玩儿,如果是企业级,假设你的数据量很小,推荐是无意义的。如果数据量很大。还是乖乖研究 Hadoop 吧。

xuxiangyang 回复
  1. Postgres 是一个生态系统,并不单单是 Postgres 数据库,数据库领域和 Map Reduce 匹配的概念是 MPP,上面其实提到过,Greenplum、Citus、Redshift、postgres x 都是可以无缝切换的,包括你上面提到的 timescaledb,其实只是 postgres 的一个扩展而已。从 SQL 的角度,其实上面方案是可以迁移到 Hive 的,如果你认为 Hive 比 Postgres 快。
  2. 数据量多大和推荐系统关系其实并不大,海量日志当然可以占很大空间,而实际对业务产生价值的部分并不多,这一般是先 ETL 提取出有价值的数据。
  3. Map Reduce 是大数据处理的一个解决方案,并不是唯一方案。
  4. SQL 是一个通用接口,现在有哪个大数据工具不支持 SQL 的吗,elasticsearch?kalfka?spark?
  5. 任何技术决策都是基于你当前的状况,如果你公司不差钱,当然招一个数据团队来做那当然是很棒啦。如果你是一个小型创业公司,正巧有员工可以用一天时间用 SQL 搭建一个推荐系统,那么不是更好么...

我之前在 keep 也是花了一两天时间做了一个类似的推荐系统,纯用 spark-sql 和 hive,写了几十行 sql 就完事了 然后就被开了.....之后听产品说上线了之后效果还行,提升了 30% 多的点击吧 不过我那个纯粹是基于标签染色的,还是比较简单的

赞,刚好项目上用到,先研究参考一下炮哥的思路。已打赏~

reducm 回复

也可以试试 PredictionIO:https://predictionio.apache.org/start/

hooopo 回复

写的很好,感谢分享,最后这一句不是很懂

这个代价非常小,可以 bulk,也可以离线

bulk 和离线具体是什么意思呢?

@ceclinux-github

就是批量处理和离线处理。

最简单的就是实时处理,有变化就实时计算一次相关的分数矩阵,这样并发情况会消耗太多资源。批量处理就是说,架构上,对于增量数据可以做成延时和定时的,比如新增变化的 item 数量达到 10000 才把新增的相似度矩阵更新,或每天批量跑一次新增的数据。

离线处理是指,如果数据量再大,计算资源成为瓶颈,架构上可以把计算相似度矩阵的工作和主业务抽出来,使用独立的数据库,再通过微服务的方式给主业务。

楼主为啥不用 MySQL 呢?

posee 回复

因为 mysql 不好用啊

hooopo 回复

Postgre 不是很小众么?

posee 回复

......... 😅

現在 Postgre 才是最火

ksec 回复

因为 Oracle 收购 MySQL 后,MySQL 就不行了么?

posee 回复

mysql 是一直不行啊 mysql8 相当于 pg8 的水平吧 不过现在 pg 都出 11 了…

hooopo 回复

mysql 现在成非主流了?

👍 已支持

gakki 回复

感谢 🙏

需要 登录 后方可回复, 如果你还没有账号请 注册新账号