Pure PostgreSQL实现推荐系统

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

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

原理

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

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

这里有两个Point：用户喜欢物品怎么表示？物品之间的相似度怎样表示？

用户评分表

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

这个表怎么来呢？如果本来就是个评论打分网站，直接有用户对电影，音乐，小说的评分记录，那是最好不过。对于其他的场景，比如电商，社交网络，则可以通过行为日志生成这张评分表。例如，浏览，点击，收藏，购买，点击“我不喜欢”按钮，可以分别设一个喜好权重：0.1, 0.2, 0.3, 0.4, -100。然后最终计算出每个用户对每个物品的评分来。事就成了一半了。

物品相似度

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

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

然后就是物品相似度矩阵的计算了，在此之前必须要做的一件事，就是定义什么是相似度？

两个物品之间的相似度有很多种定义与计算方式，如果我们知道物品的各种属性的话，就可以方便的根据各种“距离”来定义相似度。但ItemCF有一种更简单的定义方法，令N(i)为喜欢物品i的用户集合：

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

即：同时喜欢物品i和物品j的人数，除以喜爱物品i人数和喜爱物品j人数的几何平均数。

可以简单的认为，只要用户给电影打分超过某一阈值，就是喜爱该电影。

推荐物品

现在有一个用户u，他对物品$i_1,i_2,…,i_n$的评分分别为$w_1,w_2,…,w_n$，则按照该评分权重累积所有物品的相似度，就可以得到用户对所有物品的评分了。

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

排序取TopN，就得到了推荐物品列表

实践

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

第一步：准备数据

下载数据集，开发测试的话选小规模的(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列表，第三列是评分，最后是时间戳。一共100k条

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
       1 |     1172 |      8 | 2009-12-14 10:53:25+08
       1 |     1263 |      4 | 2009-12-14 10:52:31+08
       1 |     1287 |      4 | 2009-12-14 10:53:07+08
       1 |     1293 |      4 | 2009-12-14 10:52:28+08
       1 |     1339 |      7 | 2009-12-14 10:52:05+08
       1 |     1343 |      4 | 2009-12-14 10:52:11+08

第二步：计算物品相似度

中间结果表：

计算物品相似度，要计算两个中间数据：

• 每个物品被用户喜欢的次数：N(i)
• 每对物品共同被同一个用户喜欢的次数 N(i)∩N(j)

如果是用编程语言，那可以一次性解决两个问题，不过SQL就要稍微麻烦点了，先创建两张中间临时表。

-- 中间表1：每个电影被用户看过的次数：N(i)
CREATE TABLE mls_occur (
  movie_id INTEGER PRIMARY KEY,
  n        INTEGER
);

-- 这个好算的很，按照movie_id聚合一下就知道每个电影被多少用户看过了:47ms
INSERT INTO mls_occur
  SELECT movie_id, count(*) AS n FROM mls_ratings GROUP BY movie_id;


-- 中间表2：同时看过电影i和j的人数： N(i)∩N(j)
CREATE TABLE mls_common (
  i INTEGER,
  j INTEGER,
  n INTEGER,
  PRIMARY KEY (i, j)
);

-- 计算物品共现矩阵，这个比较慢。大表自己Join自己比较省事：2m 23s
INSERT INTO mls_common
  SELECT
    a.movie_id AS i,
    b.movie_id AS j,
    count(*)   AS n
  FROM mls_ratings a INNER JOIN mls_ratings b ON a.user_id = b.user_id GROUP BY i, j;

物品相似度表

有了中间结果，就可以应用距离公式，计算最终的物品相似度啦

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

-- 计算物品相似度矩阵：1m 24s
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;

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

第三步：进行推荐！

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

SELECT
  j               AS movie_id,
  sum(rating * p) AS score
FROM
  (SELECT
      movie_id,
      rating
    FROM mls_ratings
    WHERE user_id = 10
  ) seed
  LEFT OUTER JOIN 
  mls_similarity b ON seed.movie_id = b.i
WHERE i != j GROUP BY j ORDER BY score DESC LIMIT 100;

首先取用户评过分的电影作为种子集合，Join物品相似度表。按权重算出所有出现物品的预测评分并依此排序取TOP10，就得到推荐结果啦！大概长这样

 movie_id |      score
----------+------------------
     1270 | 121.487735902517
     1196 | 118.399962228869
     1198 | 117.518394778743
     1036 | 116.841317175111
     1240 | 116.432450924524
     1214 | 116.146138947698
     1580 | 116.015331936539
     2797 | 115.144083402858
     1265 | 114.959033115913
     1291 | 114.934944010088

包装一下，把它变成一个存储过程

CREATE OR REPLACE FUNCTION get_recommendation(userid INTEGER)
  RETURNS JSONB AS 
$$

BEGIN
  RETURN (SELECT jsonb_agg(movie_id)
          FROM (
                 SELECT
                   j               AS movie_id,
                   sum(rating * p) AS score
                 FROM
                   (SELECT
                      movie_id,
                      rating
                    FROM mls_ratings
                    WHERE user_id = userid) seed
                   LEFT OUTER JOIN mls_similarity b
                     ON seed.movie_id = b.i
                 WHERE i != j
                 GROUP BY j
                 ORDER BY score DESC
                 LIMIT 100) res);
END

$$
 LANGUAGE plpgsql STABLE;

SELECT get_recommendation(11);

用起来更方便啦

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

是的，就是这么简单……。

还能再给力点吗

就算这样，还是有些蛋疼，比如说计算相似度矩阵的时候，竟然花了一两分钟，才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