BigQueryでサッと試す推薦アルゴリズム - Re:ゼロから始めるML生活

この記事は（1人で）基礎から学ぶ推薦システム Advent Calendar 2022の10日目の記事です。

前回までで、推薦システムを考える上でのさわりの部分は確認できたと思うので、ちょっとずつ実務っぽい話にシフトしていこうと思います。

実務で難しい推薦アルゴリズムを実装する前に、「チューニングとかはおいておいて、だいたいどれくらい効果が出るのかサッと試したい」という場面があったりします。腰を据えてしっかりアルゴリズムを調整するならPythonでGPUを使って一つずつ実験をして…といった試行を繰り返すことになるかと思いますが、「安い！早い！うまい！」みたいなのが求められる状況では、Pythonを使うよりお手軽にサッと実装できると嬉しかったりします。

ということで、今回はSQLで推薦アルゴリズムを書いて、BQの計算能力でぶん殴るやりかたをやってみたいと思います。

問題設計
- Dataset
- rating
- train / testの分割
- 評価指標
  - recall
  - ndcg
アルゴリズム
SQL書きたくないってなったら...
参考文献
感想

問題設計

まずはどういう問題設定にするか考えてみます。

全体像としてはこんな感じでやっていこうと思います。

Dataset

今回はBigQueryだけですべての処理が完結するので、一般公開データセットを使って実装していこうと思います。

LookerのtheLook eCommerceデータセットを使ったら、どれくらいの性能が出るかは確認できそうでした。あくまで疑似データですが、実データなんて一般人は手に入れられないので（本当か？）今回はこれを使って雰囲気だけつかめれば良しとします。

データセットの構造はこのような形になっています。

bigquery-public-data
- thelook_ecommerce
  - distribution_centers
  - events
  - inventory_items
  - order_items
  - orders
  - products
  - users

rating

データセットに関して詳細な説明があるわけでも無いので、データ見ながら適当に評価値の定義を決めていきたいと思います。

bigquery-public-data.thelook_ecommerce.eventsを見る限り、与えられてるユーザーの行動はだいたいこんなもんらしいです。

event	解釈（自分の勝手な解釈です）
home	ホームにアクセス
department	売り場へアクセス
product	商品ページにアクセス
cart	カートに入れる
cancel	商品をキャンセルする
purchase	商品を購入

上の条件から、下記のようにratingを決めたいと思います。

状況	rating
購入（キャンセルしていない）	1
product pageにアクセスし、購入していない	0
それ以外	null

train / testの分割

今回は、例としてinput期間のログを使用しておすすめ商品のメールを送る状況を考えます。そして、おすすめメールを送った後に実際にその商品が購入されるかを実際に評価していきたいと思います。

この記事を執筆時点で、2022/01 - 2022/11のデータが使用できたので、

学習に使用するデータ: 2022/01 - 2022/10
評価に使用するデータ: 2022/11

としたいと思います。お手元のデータで置き換えて実装する際にはリークしないように適切にsplitしていただければ問題ないと思います。

評価指標

recall

推定したratingが高い順にユーザーにおすすめしていくとすると、

pred : ユーザー毎のrating上位k件を1, それ以外を0
test : ユーザー毎に実際に購入されたら1, それ以外を0

として、recallによって分類精度を測定することで実行できそうです。クエリで書くとこんな感じです。

with toy_data as (
  -- こんな感じのデータを用意する
  select
    user_id,
    row_number() over(partition by user_id order by pred_y desc) as offset,
    pred_y,
    true_y,
  from 
    unnest([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) as user_id with offset as user_id_offset,
    unnest([1, 1, 1, 1, 1, 0, 0, 0, 0, 0]) as pred_y with offset as pred_offset,
    unnest([1, 0, 0, 1, 1, 0, 0, 1, 0, 1]) as true_y with offset as true_offset
  where true 
  and user_id_offset = pred_offset
  and pred_offset = true_offset
),
summary as (
  -- こんな感じで記述すると計算できるはず(@k=5)
  select
    user_id,
    sum(if(offset <= 5 and true_y = 1, 1, 0)) as pred_y_cnt,
    sum(if(true_y = 1, 1, 0)) as true_y_cnt
  from toy_data
  group by user_id
)
select 
  pred_y_cnt / true_y_cnt as recall_at_5
from summary

ndcg

SQLでndcgを計算する際にはこちらのようになるかと思います。

github.com

with 
my_table as (
  -- こんな感じのデータを用意する
  select
    user_id,
    row_number() over(partition by user_id order by pred_y desc) as predicted_rank,
    row_number() over(partition by user_id order by true_y desc) as optimal_rank,
    pred_y,
    true_y as rel,
  from 
    unnest([1, 1, 1, 1, 1, 1, 1, 1, 1, 1]) as user_id with offset as user_id_offset,
    unnest([10, 9, 8, 7, 6, 5, 4, 3, 2, 1]) as pred_y with offset as pred_offset,
    unnest([3, 3, 3, 3, 3, 0, 0, 0, 0, 5]) as true_y with offset as true_offset
  where true 
  and user_id_offset = pred_offset
  and pred_offset = true_offset
),
ndcg_base as (
  select
    user_id, 
    sum(
      case 
        when predicted_rank = 1 then rel
        when predicted_rank between 2 and 5 then rel / log(predicted_rank, 2)
        else 0
      end
    ) as dcg, 
    sum(
      case 
        when optimal_rank=1 then rel
        when optimal_rank between 2 and 5 then rel / log(optimal_rank, 2)
        else 0
      end
    ) as idcg, 
  from my_table
  group by user_id 
)
select 
  avg(DCG/IDCG) as NDCG  
from ndcg_base
group by user_id

評価関数がわかったので、推薦によって出力するテーブルのカラムとしては、

user_id
predicted_rank
optimal_rank
pred_y (大きいほうが優先)
true_y (大きいほうが優先)

があれば十分そうなことがわかりました。

アルゴリズム

準備が終わったので、本題に入っていこうと思います。

Most popular

まずは簡単な推薦から考えていきます。「みんなに人気な商品はこの人もほしいだろう」という予想で推薦するのがMost popular推薦です。

今回は実装もシンプルに、購入回数が多いアイテムを全ユーザーに対して一律におすすめするという実装にしてみます。

アソシエーションルール

いわゆる「この商品はこちらの商品と一緒に買われています」みたいなバスケット分析ってやつです。 Support、Confidence、Liftの3つの指標を用いて、関連アイテムを推定していきます。

詳しくはこちらがわかりやすいです。

qiita.com

上の記事では、セッションごとに同時に購入されたアイテムをグループとして扱っていますが、こちらではユーザーごとに購入したアイテムをグループとして扱うことにします。

とりあえず、商品の”購入”のeventのみを使用して実装してみます。

こちら「うまくいくかな？」と思ったんですが、おすすめできたレコード（(user_id, product_id)のペア）が1700レコードほどで、おすすめが少なすぎる結果になってしまいました。 原因としては、アソシエーションルールは同じバスケット（今回は同じユーザー）で購入されるものがある程度多ければそこそこ機能するんですが、今回はデータがスパース過ぎて関連性を算出できなくなったためと考えられます。

そこで、商品の購入だけでなく商品ページの閲覧も集計対象に含めて実装してみます。このとき、

自分が購入 - 関連したアイテムが購入
自分が購入 - 関連したアイテムがクリック、自分がクリック - 関連したアイテムが購入
自分がクリック - 関連したアイテムがクリック

の優先度でおすすめすることとします。

まだまだ十分におすすめしきれてはいないですが、これで評価してみます。

協調フィルタリング

「このユーザーに似たユーザーは、こんな商品も買っています」みたいな推薦です。これくらいまでは頑張ればSQLで書けたりします。

今回はユーザーベースの協調フィルタリングを行うことものとし、協調フィルタリングの理屈に関してはこの前紹介したのでそちらをご参照いただければと思います。

www.nogawanogawa.com

今回実装の都合上、

クリックだけしたアイテムのratingを0.1と設定
ユーザー毎のratingの平均は取得せず、一律0として計算している

という条件をいれていますが、やんわりとした目で見てもらえればと思います。

結果まとめ

だいたいどんなもん出るのか、確認してみたいと思います。

アルゴリズム	ndcg@10	recall@10
Most popular	0.0000464	0.000147
アソシエーションルール	0.0176	0.0363
協調フィルタリング	0.0285	0.0385

補足として、アソシエーションルールと協調フィルタリングに関しては、おすすめできるアイテムが10件に満たないユーザーが発生しますが、そのユーザーについては評価対象外として、その上でndcg, recallのユーザー平均を算出しています。

人工データセットを使用している以上データの生成過程に強く依存している気がしますが、一応 Most popular < アソシエーションルール <協調フィルタリングという結果になったので値に違和感は無いですね。

SQL書きたくないってなったら...

まあこんな感じで書けるには書けるんですが、「実際やるのはめんどくさいし…」みたいなケースもあると思います。

そんなときはBQMLを使って実装するのが安心かもしれないですね（実はこれが一番楽かもしれないです）

参考文献

下記の文献を参考にさせていただきました。

推薦システム実践入門 ―仕事で使える導入ガイド

作者:風間正弘,飯塚洸二郎,松村優也
オライリージャパン

Amazon

推薦システム: 統計的機械学習の理論と実践

作者:Agarwal,Deepak K.,Chen,Bee‐Chung
共立出版

Amazon

感想

「そもそもBQ使ってるんだったらBigQueryML使えよ」ってツッコミが入りそうですね。笑

大体どれくらいうまくいきそうか
どれくらいのスコアが出れば良いのか

みたいなベースライン決めには、これくらい試せば大丈夫な気がした（あくまで気がしただけですが）ので、この辺を試してみてはいかがでしょうか？個人的には「安い！早い！うまい！」みたいなので良ければ、これくらいの実装をやっておけば良さそうかな？と思ってます。まあ、それでもPythonで書いたほうがいくらか楽な気はしますが。笑