362
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，就得到了推薦物品列表
實踐
說了這麼多廢話，趕緊燥起來。
第一步：準備數據
對於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
最後更新：2017-04-19 11:30:40
上一篇：
【Android 】【Monkey Demons】 針對性的進行穩定性測試
下一篇： Java基礎入門（一）：Java裏麵的時間
- 阿裏雲在線教育解決方案——促進教育資源均等化，助推教育質量提升
- 策略模式
- .xin域名亮相2017雲棲大會·成都峰會（現場花絮）
- 08年的雷軍：這樣的程序員創業有戲
- android開發中使用到的一些設計者模式
- 雲棲大會進行時 雲啟資本創始合夥人黃榆镔獲評“2017人工智能領域TOP20投資人”
- Android 優化Bitmap避免 OutOfMemoryError
- 門道多：一次MaxCompute PS任務的問題排查之旅
- 驚喜與局限並存，12c Sharding內測報告搶先看！
- maven項目建立pom.xml報無法解析org.apache.maven.plugins:maven-resources-plugin:2.4.3