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，就得到了推荐物品列表
实践
说了这么多废话，赶紧燥起来。
第一步：准备数据
对于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
