Pure PostgreSQL实现推荐系统

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
上一篇:file_fdw妙用无穷——从数据库读取系统信息


下一篇:Jquery中使用定时器setInterval和setTimeout