纯PostgreSQL-5分钟实现推荐系统

用PostgreSQL 5分钟实现一个最简单ItemCF推荐系统

Vonng

推荐系统大家都熟悉哈,猜你喜欢,淘宝个性化什么的,前年双十一搞了个大新闻,拿了CEO特别贡献奖。

今天就来说说怎么用PostgreSQL 5分钟实现一个最简单ItemCF推荐系统,以推荐系统最喜闻乐见的movielens数据集为例。

原理

ItemCF的原理可以看项亮的《推荐系统实战》,不过还是稍微提一下吧,了解的直接跳过就好。

Item CF,全称Item Collaboration Filter,即基于物品的协同过滤,是目前业界应用最多的推荐算法。ItemCF不需要物品与用户的标签、属性,只要有用户对物品的行为日志就可以了,同时具有很好的可解释性。所以无论是亚马逊,Hulu,YouTube,balabala用的都是该算法。

ItemCF算法的核心思想是:给用户推荐那些和他们之前喜欢的物品相似的物品。

这里有两个要点:

  • 用户喜欢物品怎么表示?
  • 物品的相似度怎样表示?

用户评分表

可以通过用户评分表来判断用户对物品的喜爱程度,例如电影数据的5分制:5分表示非常喜欢,1分表示不喜欢。

用户评分表有三个核心字段:user_id, movie_id, rating,分别是用户ID,物品ID,用户对物品的评分。

怎样得到这个表呢?如果本来就是评论打分网站在做推荐系统,直接有用户对电影,音乐,小说的评分记录那是最好不过。其他的场景,比如电商,社交网络,则可以通过用户对物品的行为日志生成这张评分表。例如可以为“浏览”,“点击”,“收藏”,“购买”,点击“我不喜欢”按钮这些行为分别设一个喜好权重:0.1, 0.2, 0.3, 0.4, -100。将所有行为评分加权求和,最终得到这张用户对物品的评分表来,事就成了一半了。

物品相似度

还需要解决的一个问题是物品相似度的计算表示

假设一共有\(N\)个物品,则物品相似度数据可以表示为一个\(N \times N\)的矩阵,第\(i\)\(j\)列的值表示物品\(i\)与物品\(j\)之间的相似度。这样相似度表示的问题就解决了。

第二个问题是物品相似度矩阵的计算。

但在计算前,首先必须定义,什么是物品的相似度?

两个物品之间的相似度有很多种定义与计算方式,如果我们有物品的各种属性数据(类型,大小,价格,风格,标签)的话,就可以在属性空间定义各式各样的“距离”,来定义相似度。但ItemCF的亮点就在于,不需要物品的属性标签数据也可以计算其相似度来。其核心思想是:如果一对物品被很多人同时喜欢,则认为这一对物品更为相似。

\(N(i)\)为喜欢物品\(i\)的用户集合,\(|N(i)|\)为喜欢物品\(i\)的人数,\(|N(i) \cap N(j)|\)为同时喜欢物品\(i,j\)的人数,则物品\(i,j\)之间的相似度\(_{ij}\)可w以表示为:

\[ w_{ij} = \frac{|N(i) \cap N(j)|}{ \sqrt{ |N(i)| * |N(j)|}} \]

即:同时喜欢物品\(i,j\)的人数,除以喜爱物品\(i\)人数和喜爱物品\(j\)人数的几何平均数。

这样,就可以通过用户对物品的行为日志,导出一份物品之间的相似矩阵数据来。

推荐物品

现在有一个用户\(u\),他对物品\(j\)的评分可以通过以下公式计算:

\[ \displaystyle p_{uj} = \sum_{i \in N(u) \cap S(i, K)} w_{ji}r_{ui} \]

其中,用户\(i\)对物品\(i_1,i_2,\cdots,i_n\)的评分分别为\(r_1,r_2,…,r_n\),而物品\(i_1,i_2,\cdots,i_n\)与目标物品\(j\)的相似度分别为\(w_1,w_2,\cdots,w_n\)。以用户\(u\)评分过的物品集合作为纽带,按照评分以相似度加权求和,就可以得到用户\(u\)对物品\(j\)的评分了。

对这个预测评分\(p\)排序取TopN,就得到了用户\(u\)的推荐物品列表

实践

说了这么多废话,赶紧燥起来。

第一步:准备数据

下载Movielens数据集,开发测试的话选小规模的(100k)就可以。对于ItemCF来说,有用的数据就是用户行为日志,即文件ratings.csv地址

-- movielens 用户评分数据集
CREATE TABLE mls_ratings (
  user_id   INTEGER,
  movie_id  INTEGER,
  rating    TEXT,
  timestamp INTEGER,
  PRIMARY KEY (user_id, movie_id)
);

-- 从CSV导入数据,并将评分乘以2变为2~10的整数便于处理,将Unix时间戳转换为日期类型
COPY mls_ratings FROM '/Users/vonng/Dev/recsys/ml-latest-small/ratings.csv' DELIMITER ',' CSV HEADER;
ALTER TABLE mls_ratings
  ALTER COLUMN rating SET DATA TYPE INTEGER USING (rating :: DECIMAL * 2) :: INTEGER;
ALTER TABLE mls_ratings
  ALTER COLUMN timestamp SET DATA TYPE TIMESTAMPTZ USING to_timestamp(timestamp :: DOUBLE PRECISION);

得到的数据长这样:第一列用户ID列表,第二列电影ID列表,第三列是评分,最后是时间戳。一共十万条

movielens=# select * from mls_ratings limit 10;
 user_id | movie_id | rating |       timestamp
---------+----------+--------+------------------------
       1 |       31 |      5 | 2009-12-14 10:52:24+08
       1 |     1029 |      6 | 2009-12-14 10:52:59+08
       1 |     1061 |      6 | 2009-12-14 10:53:02+08
       1 |     1129 |      4 | 2009-12-14 10:53:05+08

第二步:计算物品相似度

物品相似度的DDL

-- 物品相似度表,这是把矩阵用<i,j,M_ij>的方式在数据库中表示。
CREATE TABLE mls_similarity (
  i INTEGER,
  j INTEGER,
  p FLOAT,
  PRIMARY KEY (i, j)
);

物品相似度是一个矩阵,虽说PostgreSQL里提供了数组,多维数组,自定义数据结构,不过这里为了方便起见还是使用了最传统的矩阵表示方法:坐标索引法\((i,j,m_{ij})\)。其中前两个元素为矩阵下标,各自表示物品的ID。最后一个元素存储了这一对物品的相似度。

物品相似度的计算

计算物品相似度,要计算两个中间数据:

  • 每个物品被用户喜欢的次数:\(|N(i)|\)
  • 每对物品共同被同一个用户喜欢的次数 \(|N(i) \cap N(j)|\)

如果是用编程语言,那自然可以一趟(One-Pass)解决两个问题。不过SQL就要稍微麻烦点了,好处是不用操心撑爆内存的问题。

这里可以使用PostgreSQL的With子句功能,计算两个临时结果供后续使用,一条SQL就搞定相似矩阵计算:

-- 计算物品相似度矩阵: 3m 53s
WITH mls_occur AS ( -- 中间表:计算每个电影被用户看过的次数
    SELECT
      movie_id,     -- 电影ID: i
      count(*) AS n -- 看过电影i的人数: |N(i)|
    FROM mls_ratings
    GROUP BY movie_id
),
    mls_common AS ( -- 中间表:计算每对电影被用户同时看过的次数
      SELECT
        a.movie_id AS i, -- 电影ID: i
        b.movie_id AS j, -- 电影ID: j
        count(*)   AS n  -- 同时看过电影i和j的人数: |N(i) ∩ N(j)|
      FROM mls_ratings a INNER JOIN mls_ratings b ON a.user_id = b.user_id
      GROUP BY i, j
  )
INSERT INTO mls_similarity
  SELECT
    i,
    j,
    n / sqrt(n1 * n2) AS p  -- 距离公式
  FROM
    mls_common c,
    LATERAL (SELECT n AS n1 FROM mls_occur WHERE movie_id = i) n1,
    LATERAL (SELECT n AS n2 FROM mls_occur WHERE movie_id = j) n2;

物品相似度表大概长这样:

movielens=# SELECT * FROM mls_similarity LIMIT 10;
   i    | j |         p
--------+---+--------------------
 140267 | 1 |  0.110207753755597
   2707 | 1 |  0.180280682843137
 140174 | 1 |  0.113822078644894
   7482 | 1 | 0.0636284762975778

实际上还可以修剪修剪,比如计算时非常小的相似度干脆可以直接删掉。也可以用整个表中相似度的最大值作为单位1,进行归一化。这里都不弄了。

第三步:进行推荐!

现在假设我们为ID为10的用户推荐10部他没看过的电影,该怎么做呢?

WITH seed AS	-- 10号用户评分过的影片作为种子集合
  (SELECT movie_id,rating FROM mls_ratings WHERE user_id = 10)
SELECT
  j as movie_id,	-- 所有待预测评分的电影ID
  sum(seed.rating * p) AS score -- 预测加权分,按此字段降序排序取TopN
FROM
  seed LEFT JOIN mls_similarity s ON seed.movie_id = s.i 
  WHERE j not in (SELECT DISTINCT movie_id FROM seed) -- 去除已经看过的电影(可选)
GROUP BY j ORDER BY score DESC LIMIT 10; -- 聚合,排序,取TOP

推荐结果如下:

 movie_id |      score
----------+------------------
     1270 | 121.487735902517
     1214 | 116.146138947698
     1580 | 116.015331936539
     2797 | 115.144083402858
     1265 | 114.959033115913
      260 | 114.313571128143
     2716 | 113.087151014987
     1097 |  113.07771922959
     1387 | 112.869891345883
     2916 |  112.84326997566

可以进一步包装一下,把它变成一个存储过程get_recommendation

CREATE OR REPLACE FUNCTION get_recommendation(userid INTEGER)
  RETURNS JSONB AS $$ BEGIN
  RETURN (SELECT jsonb_agg(movie_id)
          FROM (WITH seed AS
          (SELECT movie_id,rating FROM mls_ratings WHERE user_id = userid)
                SELECT
                  j as movie_id,
                  sum(seed.rating * p) AS score
                FROM
                  seed LEFT JOIN mls_similarity s ON seed.movie_id = s.i
                WHERE j not in (SELECT DISTINCT movie_id FROM seed)
                GROUP BY j ORDER BY score DESC LIMIT 10) res);
END $$ LANGUAGE plpgsql STABLE;

这样用起来更方便啦,同时也可以在这里加入一些其他的处理逻辑:比如过滤掉禁片黄片,去除用户明确表示过不喜欢的电影,加入一些热门电影,引入一些随机惊喜,打点小广告之类的。

movielens=# SELECT get_recommendation(11) as res;
                                  res
-----------------------------------------------------------------------
 [80489, 96079, 79132, 59315, 91529, 69122, 58559, 59369, 1682, 71535]

最后写个应用把这个存储过程作为OpenAPI开放出去,事就这样成了。

关于这一步可以参考前一篇:当PostgreSQL遇上GraphQL:Postgraphql中的做法,直接由存储过程生成GraphQL API,啥都不用操心了。

What’s more

几行SQL一条龙执行下来,加上下载数据的时间,总共也就五分钟吧。一个简单的推荐系统就这样搭建起来了。

但一个真正的生产系统还需要考虑许许多多其他问题,例如,性能。

这里比如说计算相似度矩阵的时候,才100k条记录花了三四分钟,不太给力。而且这么多SQL写起来,管理起来也麻烦,有没有更好的方案?

这儿有个基于PostgreSQL源码魔改的推荐数据库:RecDB,直接用C实现了推荐系统相关的功能扩展,性能看起来杠杠地;同时还包装了SQL语法糖,一行SQL建立推荐系统!再一行SQL就开始使用啦。

-- 计算推荐所需的信息
CREATE RECOMMENDER MovieRec ON ml_ratings
USERS FROM userid
ITEMS FROM itemid
EVENTS FROM ratingval
USING ItemCosCF

-- 进行推荐!
SELECT * FROM ml_ratings R
RECOMMEND R.itemid TO R.userid ON R.ratingval USING ItemCosCF
WHERE R.userid = 1
ORDER BY R.ratingval
LIMIT 10

PostgreSQL能干的事情太多了,最先进的开源关系数据库确实不是吹的,其实真的可以试一试。

  •   Category
  • Dev