ECサイトを作っていると販売促進のため商品詳細ページにおすすめ商品を埋め込みたくなります。
ここではユーザーが購入した商品の履歴を用いた協調フィルタリングでおすすめ商品を出力しましょう。

環境

PostgreSQL9.6

テーブル定義

簡単化のため各テーブルはIDのみを持っています。

# ユーザーテーブル
create table users( id int primary key not null );

# 商品テーブル
create table products( id int primary key not null );

# 購入履歴テーブル
create table user_products( product_id int not null, user_id int not null, primary key (product_id, user_id) );
create index index_user_id_product_id_on_user_products on user_products (user_id, product_id);

協調フィルタリングのクエリ

各商品の購入履歴を特徴量ベクトルと考え、特徴量ベクトル間のコサイン類似度を求めます。
つまり、"閲覧しているページの商品を購入した他のユーザーの他の購入商品は閲覧中のユーザも欲しいはずだ"、です。

コサイン類似度の詳しい説明は https://en.wikipedia.org/wiki/Cosine_similarity をご覧ください。

で、下が完成したクエリです。

select *
from (
  select
    b.id,
    (select count(*)
     from user_products c join user_products d using(user_id)
     where c.product_id = 0 and d.product_id = b.id) /
    sqrt((select count(*) from user_products where product_id = 0)) /
    sqrt((select count(*) from user_products where product_id = b.id)) as similarity
  from (
    select product_id as id from user_products group by product_id
  ) b -- for (ERROR:  division by zero)
  where b.id != 0
  group by b.id
) e
order by similarity desc
limit 10;

購入履歴を500件いれてexplainした結果は下の通り

                                                              QUERY PLAN                                                                                                     
---------------------------------------------------------------------------------------------------------------------------------------                                      
 Limit  (cost=2684.92..2684.94 rows=10 width=12)
   ->  Sort  (cost=2684.92..2685.42 rows=200 width=12)
         Sort Key: (((((SubPlan 1))::double precision / sqrt(($1)::double precision)) / sqrt(((SubPlan 3))::double precision))) DESC                                         
         ->  Group  (cost=4.64..2678.59 rows=200 width=12)
               Group Key: user_products.product_id
               InitPlan 2 (returns $1)
                 ->  Aggregate  (cost=4.36..4.37 rows=1 width=8)
                       ->  Index Only Scan using user_products_pkey on user_products user_products_1  (cost=0.28..4.35 rows=4 width=0)                                       
                             Index Cond: (product_id = 0)
               ->  Group  (cost=0.28..52.03 rows=456 width=4)
                     Group Key: user_products.product_id
                     ->  Index Only Scan using user_products_pkey on user_products  (cost=0.28..49.07 rows=1184 width=4)                                                     
                           Filter: (product_id <> 0)
               SubPlan 1
                 ->  Aggregate  (cost=8.71..8.72 rows=1 width=8)
                       ->  Merge Join  (cost=0.56..8.71 rows=1 width=0)
                             Merge Cond: (c.user_id = d.user_id)
                             ->  Index Only Scan using user_products_pkey on user_products c  (cost=0.28..4.35 rows=4 width=4)                                               
                                   Index Cond: (product_id = 0)
                             ->  Index Only Scan using user_products_pkey on user_products d  (cost=0.28..4.33 rows=3 width=4)
                                   Index Cond: (product_id = user_products.product_id)
               SubPlan 3
                 ->  Aggregate  (cost=4.34..4.35 rows=1 width=8)
                       ->  Index Only Scan using user_products_pkey on user_products user_products_2  (cost=0.28..4.33 rows=3 width=0)
                             Index Cond: (product_id = user_products.product_id)

すべてのデータを抽出しないとソートできないので遅そうですね。計算したコサイン類似度を保持するテーブル作ってインデックス作成してもよいのですが、商品数の2乗で類似度データが増えるので、大規模データでは現実的では無いです。

次やりたいこと

購入履歴数が多くなると計算が遅くなる可能性大なので、https://research.preferred.jp/2011/02/minhash/ で紹介されている高速な計算方法を実装したいです。
この方法は購入履歴がない場合には何もおすすめできません。つまり、登録されたばかりの新商品にはおすすめができないということです(コールドスタート問題といいます)。購入履歴以外の特徴量を混ぜることで、ある適度解決できそうなので他の方法も混ぜたいです。