2017-12-08

word2vecでitem2vecを実装して映画を推薦する

Python Recommender system

自然言語処理 Advent Calendar 2017 - Qiita 8日目の投稿となります。

qiita.com

前回の投稿ではword2vecを推薦に応用したitem2vecを紹介しました。
今回は、gensimのword2vecを使ってitem2vecの実装を行い、映画を推薦するシステムを作ります。

ohke.hateblo.jp

MovieLens

学習に用いるデータセットとして、かの有名なMovieLensを採用します。

MovieLensは、ミネソタ大学のGroupLensプロジェクトの一環で収集されているデータセットです。
映画のユーザ評価値、各映画のカテゴリやタグなどのメタ情報など、質・量ともに充実しており、推薦システムの評価によく用いられています。

https://movielens.org/

今回は扱いやすさを優先して、MovieLens 100K Datasetを使います(今なお収集・更新され続けているデータセットですので、最新版では2,000万を超える評価値が収録されています)。

ユーザ数: 943
- 20以上の評価をしているユーザが対象
タイトル数: 1,682
評価数: 100,000(1〜5の5段階評価)
- 1997/9/19〜1998/4/22の7ヶ月間の収集データ

以下よりダウンロードして、今回作成するPythonファイルと同じディレクトリに解凍します。

https://grouplens.org/datasets/movielens/

次に評価値をDataFrameにロードしておきます。

import numpy as np
import pandas as pd


# 評価値を持つファイルはu.data
ratings = pd.read_csv('ml-100k/u.data', delimiter='\t', header=None).iloc[:, :3]
ratings.rename(columns={0: 'user_id', 1: 'item_id', 2: 'rating'}, inplace=True)

print('ratings.shape: {}'.format(ratings.shape))
# ratings.shape: (100000, 3)

ratings.head()

ユーザID、アイテムID、評価値のシンプルなテーブルとなります。

f:id:ohke:20171203153153p:plain

各アイテムの映画タイトルもDataFrame(items)にロードしておきます(推薦結果の確認のために使います)。

import codecs


# pd.read_csvで読み込もうとすると文字コードエラーになるため、
# codecs.openでエラーを無視してファイルを読み込んだ後にDataFrameにする
with codecs.open('ml-100k/u.item', 'r', 'utf-8', errors='ignore') as f:
    items = pd.read_table(f, delimiter='|', header=None).ix[:, 0:1]
    items.rename(columns={0: 'item_id', 1: 'item_title'}, inplace=True)
    items.set_index('item_id', inplace=True)
    
items.head()

こちらもアイテムID(インデックス)と映画タイトルからなる、シンプルなテーブルとなります。

f:id:ohke:20171203161217p:plain

分布を概観しておきます。

評価しているアイテム(左の図)、評価しているユーザ(真ん中の図)にそれぞれ偏りがあり、一部のアイテム・ユーザの評価が極端に多くなっています。
また評価値は4が一番多く、1や2などの低い評価は少ないことがわかります。

f:id:ohke:20171203161304p:plain

item2vecの実装

本題です。

前回紹介したitem2vecの論文では、アプリの購入明細やユーザごとの再生ログをそれぞれ文章としてとらえて、ベクトル化していました。

MovieLensを使った今回の取り組みでは「word2vecで言うところの"単語"を"アイテムID"、"文章(単語列)"を"ユーザごとに高評価したアイテムIDリストの文字列"に置き換え(ここではコンテキストと呼ぶことにします)、skip-gram negative sampling(SGNS)でベクトル化して、類似度の高いアイテムを推薦する」方針で実装していきます。

各コンテキストは"61 33 160 20 202 ..."のような文字列になります
平均値を上回る評価をしたアイテムに限定して、下回るアイテムについてはコンテキストから除外します
- 評価が甘いユーザ、辛いユーザが混在しているため、平均値はユーザごとに計算します

文字列に変換するので、既存のword2vecの実装をそのまま利用できます。
今回はgensimを使います(gensimのword2vecを使った例は、Word2Vecで京都観光に関するブログ記事の単語をベクトル化する - け日記も参考にしてみてください)。

具体的な実装に入ります。

gensimのword2vecは、決まったフォーマット(1行1文章で、各文章内の単語はスペースで区切られている)のファイルを入力として受け取る必要があります。
そのため、まずはratingsからコンテキストを作り、このフォーマットでファイル(ml100k.txt)に出力します。

# ユーザIDをキーが、コンテキストが値
item_buckets = {}

for user_id in ratings['user_id'].unique():
    # ユーザごとに、評価が平均値以上のアイテムIDを抽出して' 'で連結する
    average = np.average(ratings[ratings['user_id'] == user_id]['rating'])
    user_ratings = ratings[(ratings['user_id'] == user_id) & (ratings['rating'] >= average)]
    item_buckets[user_id] = ' '.join(user_ratings['item_id'].astype('str'))

print('item_buckets[1]: {}'.format(item_buckets[1]))
# item_buckets[1]: 61 33 160 20 202 171 265 47 222 253 113 227 90 64 228 121 114 132 134 98 186 221 84 60 177 174 82 56 80 229 235 6 206 76 72 185 96 258 81 212 151 51 175 107 209 108 12 14 44 163 210 184 157 150 183 248 208 128 242 193 236 250 91 129 241 267 86 196 39 230 23 224 65 190 100 154 214 161 170 9 246 22 187 135 68 146 176 166 89 249 269 32 270 133 239 194 256 93 234 1 197 173 75 268 144 119 181 257 109 182 223 46 169 162 66 77 199 57 50 192 178 87 238 156 106 115 137 127 16 79 45 48 25 251 195 168 123 191 203 55 42 7 43 165 198 124 95 58 216 204 3 207 19 18 59 15 111 52 88 13 28 172 152

# ml100k.txtファイルに書き出す
with open('ml100k.txt', 'w') as f:
    f.write('\n'.join(item_buckets.values()))

次に、word2vecのモデルを構築しますが、いくつか考慮すべきことがあります。

skip-gramか、cbowか
- item2vecの論文に則って、skip-gramを使います
単語ベクトルのサイズ
- gensimのデフォルトは100次元ですが、データサイズも大きくなく、まずは今回の取り組みの勝ち目を検証したいので、大きめの300次元に設定します
ウィンドウサイズ
- コンテキスト内の全てのアイテムを周辺単語に含めて計算したいので、巨大な値を設定しておきます
ネガティブサンプリングか、階層的ソフトマックスか
- こちらもitem2vecの論文に則って、ネガティブサンプリングを使います
- ネガティブサンプリングする単語数は、学習結果にどう影響をあたえるのかが予測できなかったので、ここではデフォルトの5にしました

以上を引数として渡して、モデルを構築します。

from gensim.models import word2vec


sentences = word2vec.LineSentence('ml100k.txt')

# word2vecのモデルを構築
#     sg: 1ならskip-gram(cbowではなく)
#     size: 単語ベクトルの次元数
#     window: ウィンドウサイズ(今回は1行に含まれる全ての単語を対象とするため大きな値を設定)
#     hs: 0ならネガティブサンプリング(1なら階層的ソフトマックス)
#     negative: ネガティブサンプリングする単語数(結果への影響が予測できなかったのでデフォルトの5に設定)
#     seed: 乱数シード(結果を安定させたいので固定値を設定)
model = word2vec.Word2Vec(sentences, sg=1, size=300, window=100000, hs=0, negative=5, seed=0)

評価

最後に学習結果を評価していきます。

まずはあまりメジャーどころではない映画3本で試してみます。

Boys on the Side (1995)
- どちらかというと女性主体のヒューマンドラマが並んでおり、良いラインナップかと思います
Akira (1988)
- 1番目にGhost in the Shell(攻殻機動隊)が入っており、SFアニメ好きが反映された結果になってます
Anne Frank Remembered (1995)
- こちらも伝記や歴史にまつわる映画が並んでおり、納得できます。

# 「アイテムID : 映画タイトル : 類似度」を順番に表示する
def print_similar_titles(tuples):
    for t in tuples:
        print('{} : {} : {}'.format(t[0], items.ix[int(t[0])]['item_title'], t[1]))


# Boys on the Side (1995)
print_similar_titles(model.wv.most_similar(positive='723', topn=5))
# 155 : Dirty Dancing (1987) : 0.9308373332023621
# 1086 : It's My Party (1995) : 0.9249939918518066
# 1160 : Love! Valour! Compassion! (1997) : 0.9087437391281128
# 731 : Corrina, Corrina (1994) : 0.9083319902420044
# 958 : To Live (Huozhe) (1994) : 0.9018335938453674

# Akira (1988)
print_similar_titles(model.wv.most_similar(positive='206', topn=10)) 
# 1240 : Ghost in the Shell (Kokaku kidotai) (1995) : 0.8688986301422119
# 55 : Professional, The (1994) : 0.8473154306411743
# 184 : Army of Darkness (1993) : 0.8467724323272705
# 154 : Monty Python's Life of Brian (1979) : 0.8439988493919373
# 91 : Nightmare Before Christmas, The (1993) : 0.8403595089912415

# Anne Frank Remembered (1995)
print_similar_titles(model.wv.most_similar(positive='1084', topn=5))
# 1120 : I'm Not Rappaport (1996) : 0.8835359215736389
# 1117 : Surviving Picasso (1996) : 0.8799570798873901
# 740 : Jane Eyre (1996) : 0.8373265862464905
# 295 : Breakdown (1997) : 0.8226629495620728
# 676 : Crucible, The (1996) : 0.8197730183601379

一方で、メジャーで癖のない映画になると、映画のストーリーやジャンルと関係なく、同じくメジャーどころの映画が並びます。「話題の映画を見たい」というミーハーの欲求にこたえたラインナップですが、内容の嗜好といったものが反映されていません。

# Toy Story (1995)
print_similar_titles(model.wv.most_similar(positive='1', topn=5))
# 222 : Star Trek: First Contact (1996) : 0.8651309609413147
# 50 : Star Wars (1977) : 0.8567565679550171
# 151 : Willy Wonka and the Chocolate Factory (1971) : 0.8447127342224121
# 405 : Mission: Impossible (1996) : 0.8326137065887451
# 257 : Men in Black (1997) : 0.8289622068405151

# Jurassic Park (1993)
print_similar_titles(model.wv.most_similar(positive=['82'], topn=5))
# 161 : Top Gun (1986) : 0.9202654361724854
# 380 : Star Trek: Generations (1994) : 0.8908969163894653
# 210 : Indiana Jones and the Last Crusade (1989) : 0.8803819417953491
# 403 : Batman (1989) : 0.880357027053833
# 79 : Fugitive, The (1993) : 0.8706289529800415

word2vecでベクトル化されていますので、足し算引き算も可能です。 The RockとBad Boysを足すと、やはりアクション映画が多くなる傾向にあります。

# 117: Rock, The (1996), 27: Bad Boys (1995)
print_similar_titles(model.wv.most_similar(positive=['117', '27'], topn=5))
# 1016 : Con Air (1997) : 0.8946918249130249
# 597 : Eraser (1996) : 0.8450523614883423
# 147 : Long Kiss Goodnight, The (1996) : 0.833519458770752
# 273 : Heat (1995) : 0.8113495707511902
# 685 : Executive Decision (1996) : 0.8015687465667725

おわりに

word2vecでitem2vecを実装し、MovieLensのデータで推薦システムを作り、大雑把にいくつか映画を推薦させて傾向を見てみました。

2017-12-02

論文メモ: Item2Vec: Neural Item Embedding for Collaborative Filtering

NLP Recommender system 論文メモ

word2vecをリコメンデーションに応用した論文"Item2Vec: Neural Item Embedding for Collaborative Filtering"を読みましたので、そのメモとなります。

[1603.04259] Item2Vec: Neural Item Embedding for Collaborative Filtering

1. INTRODUCTION AND RELATED WORK

SGNS(skip-gram negative sampling, word2vec)をアイテムベースの協調フィルタリングに応用する。

それをitem2vecと名付け、SVDと比較して優位性を示す。

2. SKIP-GRAM WITH NEGATIVE SAMPLING

SGNSについて概観する(初出はこちらの論文)。

前処理まで完了した文章(単語列の形式で、例えばI have a pen.なら[I, have, a, pen])を ${(w_i)^K_{i-1}}$ 、文章内で現れる全単語を ${W={w_i}^W_{i=1}}$ とすると、skip-gramは以下の目的関数の最大化を目指して、確率的勾配降下法で学習する。

$\frac{1}{K} \sum^K_{i=1} \sum_{-c \le j \le c, j \ne 0} \log p(w_{i+j} \mid w_i)$

cはウィンドウサイズで、前後c単語(周辺単語と呼ぶ)を考慮する。
${p(w_j | w_i)}$ は、対象の単語 ${w_i}$ と周辺単語 ${w_{i+j}}$ の共起確率を表すソフトマックス関数です。

$p(w_j \mid w_i) = \frac{\exp(u^T_i v_j)}{\sum_{k \in I_W} \exp(u^T_i v_k)}$

${u_i}$ は対象単語のベクトル、 ${v_j}$ は周辺単語のベクトル、 ${I_W}$ は全単語のインデックスを表す。単語ベクトル長(mとする)はハイパーパラメータとして設定する。

上の式では、分母で全単語との総和を計算しているため、pの計算量は出現する全ての単語数(10⁵〜10⁶)に比例して増大してしまう。

negative samplingでは、周辺外単語の計算(分母の計算)は全ての単語について計算するのではなく、ランダムにサンプリングされたN個の単語についてのみ行うことで近似する。
以下の式になる。ただし、 ${\sigma(x) = 1/(1+\exp(-x))}$ と置いている。

$p(w_j \mid w_i) = \sigma(u^T_i v_j) \prod^N_{k=1} \sigma(-u^T_i v_k)$

なお、単語の出現頻度による偏りを防ぐために、出現頻度が高い単語はサンプリングされにくいように工夫する。
単語wの出現頻度をf(w)、閾値をρとすると、以下の確率で単語wはサンプリングから外す。

$p(discard \mid w)=1-\sqrt{\frac{\rho}{f(w)}}$

参考

SGNSについては、こちらの方の記事がとても参考になります。あわせて読むと理解が捗ります。

word2vecのソースを読んでみた - Qiita

Word2Vec のニューラルネットワーク学習過程を理解する · けんごのお屋敷

3. ITEM2VEC - SGNS FOR ITEM SIMILARITY

SGNSをアイテムベース協調フィルタリングへ組み込む方法について説明する。

SGNSでは単語列からある単語とその周辺の単語から関連性を計算していた。
アイテムベースCFでは、単語をアイテム、単語列をアイテム集合(バスケット)と置き換えることでSGNSを適用する。

列から集合となったことで、SGNSでは持っていた時間・位置の近接情報については、捨てることにした。
したがって目的関数からは、ウィンドウサイズを取り払い、以下の式に変更する。

$\frac{1}{K} \sum^K_{i=1} \sum^K_{j \ne i} log p(w_{i+j} \mid w_i)$

アイテムiのベクトルを ${u_i}$ とする。アイテム間の関連度はコサイン類似度で計算する。

以降では、このプロセスやこのプロセスで得られたアイテムベクトルを総称してitem2vecと呼ぶ。

4. EXPERIMENTAL SETUP AND RESULTS

SVDを比較対象とし、データセットを使った実験と評価を行う。

SVDは以下の手順でベクトルを作る。 item2vec同様、アイテム間のコサイン類似度を計算する。

K×Kの正方行列を用意する(Kはアイテム数)
- (i, j)の要素は ${(w_i, w_j)}$ の同時出現頻度が正規化された値がセットされる
正方行列を特異値分解して、行の単語ベクトルを得る
- Sは対角行列(K×K)で、Sから重要度の高いベクトルをm個を持つ(したがって、m次元まで圧縮できる)
- Uは左特異行列(K×K)
(SVDについて正しく理解できていないので、記述が誤っているかもしれません。)

評価には2種類のデータセットを使う。

Microsoft Xbox Musicの再生ログ
- 732,000ユーザと49,000アーティストの9,000,000再生ログ
Microsoft Storeの購入ログ
- 1,706アイテム、379,000オーダー
- 「同時に購入された」という情報のみを持つ(その他のユーザの情報は使わない)

まずはMusicデータセットについて、それぞれの手法(item2vecとSVD)でジャンル分けして、精度を見る。
t-SNEで2次元に可視化した結果が下の図(原文Fig.2を引用。左がitem2vec、右がSVD)で、概ねitem2vecの方がきれいに分離していることがわかる。(SVDは図右下で混在が見られる)。

f:id:ohke:20171130142811p:plain

数字(原文TABLE 2を引用)でもitem2vecのほうが精度が高く、特に人気の低い(15人以下のユーザが再生した)アーティストでは約10%の差を付けている。これは、人気の高い(出現頻度の高い)アイテムについては間引かれやすく(p(discard | w)の式)、またnegative samplingの対象にもなりやすいので、人気の低いアイテムの影響が相対的に高くなったためである。

f:id:ohke:20171130143303p:plain

最後にMusicとStoreのそれぞれにおいて、item2vecとSVDが推薦したアイテムを比較し、いずれもitem2vecの方がより類似したアイテムを推薦していることを確認した(原文TABLE 3, TABLE 4を引用)。
特にStoreでは、「同時に購入された」という情報以外のアイテムに関する情報を捨てているにもかかわらず、類似した物が連なっていることがわかる。

f:id:ohke:20171201083136p:plain

所感

最後に私の所感をまとめます。

ドメイン情報無しで適用できる

2つ目の実験で明らかになってますが、ユーザやアイテムに関するドメイン情報を使わず、「同時に購入された」という組み合わせ情報だけで、関連度の高いアイテムが抽出できているのは注目に値するかと思います。

ドメイン情報を必要としないword2vecと協調フィルタリングの利点を、そのまま残しています。

ドメイン情報をどうやって注入するか

一方で、ビジネスに適用して高い精度を達成するためには、ドメイン情報を上手く表現して組み込む必要があるかと思います。

今回は実験のために「同時に購入された」以外の情報をばっさり落としてますが、例えばECであれば、一般的に以下のような傾向は想定されます。

ユーザAが今回購入する物は、1年前に購入した物より、先週購入した物と類似している

こうした時間的な近接性はitem2vecの目的関数にはありません。
概念的にはword2vecにあったウィンドウの考え方が近いので、それをitem2vecにも組み込めれば表現できそうです(後続の研究でこうした取り組みもあるかと予想されます)。

次の機会には実装してみたいと思います。

2017-11-26

Visual Studio Codeでシーケンス図を描く(PlantUML拡張機能)

Visual Studio Code

VSCodeでシーケンス図などのUMLを描くことができる拡張機能を紹介します。

ドキュメントに関しては、テーブル定義やAPI仕様など必要最低限のみを作成するようにしているのですが、シーケンス図は詳細設計や実装前のフローの整理ということでよく描きます。
この拡張機能を使うと、楽に作成できるようになり、Git上でも管理できるようになります。

PlantUML

PlantUMLはUML図を記述するためのドメイン特化言語です。

シーケンス図の書き方については、こちらの方の記事に詳しく記載されています。

PlantUML - シーケンス図 | プログラマーズ雑記帳

PlantUML拡張機能

VSCodeで、PlantUMLのシンタックスハイライトやプレビュー、ファイルへの出力などを行う拡張機能が開発されています。

marketplace.visualstudio.com

"PlantUML"で検索して、インストールします。

f:id:ohke:20171122084120p:plain

この拡張機能は、拡張子.puのファイルをPlantUMLファイルとして認識しますので、.puファイルにPlantUMLで記述していきます。
例えば、簡単なブログページの表示をシーケンス図をPlantUMLで表現すると、こんなコードになります。

/'
ブログのシーケンス図
- ブラウザでトップページを表示する
- JavaScriptで通知件数を表示する
'/

@startuml

actor Browser as browser
participant BlogWeb as web
participant BlogAPI as api
database BlogDB as db

activate browser

group 画面の表示
    browser -> web :トップページにランディング\nGET: ohke.hogeblog.jp
    activate web
    web -> db :トップに表示するエントリを取得
    db --> web :
    web --> browser :トップページを表示
    deactivate web
end

group 通知の表示
    browser ->> api :ユーザへの通知情報をリクエスト\nGET api.hogeblog.jp/notify/ohke
    activate api
    api -> db :ohkeへの通知を取得
    db --> api :
    api --> browser :通知情報をレスポンス\n{"count":2,"messages":[...]}
    deactivate api
    alt countが1以上
        browser -> browser :件数をアイコンの横に表示
    end
end
note right: ロードしたnotify.jsから実行

deactivate browser

@enduml

.puファイルを編集中に、Alt+Dでプレビューを表示できます。

f:id:ohke:20171123104021p:plain

完成した.puファイルは、.pngや.jpgなどの画像ファイルにエクスポートできます。

f:id:ohke:20171123110649p:plain

エクスポートした画像ファイルはoutディレクトリ以下に出力されます。

f:id:ohke:20171123110810p:plain

シーケンス図以外にも、ユースケース図やフローチャートなどもPlantUMLで記述できますので、使いでのある拡張機能かと思います。