はじめに

こんにちは！

askenで機械学習エンジニアとして働いているyuma（shoku_pan）です。

前回、以下の記事を書きました。

tech.asken.inc

あすけんで100点をとるために、線形計画問題を使って食事の組み合わせを考えました。確かに、「100点をとる」という目標は達成することができたのですが、以下の課題も浮き彫りになりました（詳細は前回記事の「まとめ」を参照ください）。

①朝昼晩に分けて考える
②妥当な組み合わせを考える
③手に入れやすいものに絞る

①は3食に分けて前回の方法を使うとよさそうですが、②と③はどうでしょうか。

②は「一緒に食されることが多い食事の組み合わせを考える」、③は「ユーザーの食事の履歴に基づいた食事の組み合わせを考える」といった対応が考えられます。

この考えのもと、今回は推薦（レコメンド）の手法を使って課題①②に取り組みました。

アソシエーション分析

アソシエーション分析は、昔から広く一般的に使われている推薦の一手法です。

ECサイトにおいては、ユーザーの購買履歴から「商品Aを購入するとき、商品Bも同時に購入されることが多い」といった法則性を見つけるのに使われます。あすけんに当てはめると、「食品Aと食品Bは一緒に食されることが多い」といった法則性を見つけることになります。

具体例で考えてみましょう。

	食品A	食品B	食品C
ユーザー1	○	○
ユーザー2	○	○
ユーザー3			○
ユーザー4	○	○	○

各ユーザーごとに、どの食品を食したかのデータが与えられています。

ここで、 $U$ をユーザー全体の集合、 $A, B, C$ をそれぞれの食品を食したユーザーの集合として

$\displaystyle \begin{align} U &= \{1, 2, 3, 4\}\\ A &= \{1, 2, 4\}\\ B &= \{1, 2, 4\}\\ C &= \{3, 4\} \end{align}$

と定義します。このとき、集合の大きさ（要素数）は

$\displaystyle \begin{align} |U| = 4, |A| = 3, |B| = 3, |C| = 2 \end{align}$

となります。

それでは以下で、アソシエーション分析で必要な3つの指標「支持度」「確信度」「リフト」について説明します。

支持度（Support）

支持度（Support） $S$ は、以下のように表すことができます。

$\displaystyle S(X) = \frac{|X|}{|U|}, ~~~S(X, Y) = \frac{|X \cap Y|}{|U|}$

上記の例では

$\displaystyle \begin{align} S(A) = \frac{3}{4} = 0.75, ~~~ S(A, B) = \frac{|A \cap B|}{|U|} = \frac{3}{4} = 0.75 \end{align}$

同様にして、 $S(B, C) = 0.25, S(C, A) = 0.25$ などとなります。

全体に対してどれだけ（同時に）食されているかを測る指標であり、最も基本的な指標かと思います。多くの人が食すメジャーな食品は、人気度順として推薦することが考えられます。

信頼度（Confidence）

次に、食品Xを食したユーザーが食品Yを食した場合の信頼度（Confidence） $C$ は、以下のように表すことができます。

$\displaystyle C(Y|X) = \frac{|X \cap Y|}{|X|}$

ここで、 $X$ を条件部（antecedents）、 $Y$ を帰結部（consequents）といいます。

上記の例では

$\displaystyle \begin{align} C(B|A) &= \frac{|A \cap B|}{|A|} = \frac{3}{3} = 1 \end{align}$

同様にして、 $C(C|B) = 0.33, C(A|C) = 0.5$ などとなります。

支持度との違いは、まず全体に対してではなく、特定の食品を食したユーザーに対する割合ということです。全体的に見てそこまで多くなくても、特定の食品との組み合わせにフォーカスすると多く食されているものもあります。たとえば、バターは全体に占める割合が少なかったとしても、パンを食したユーザーに絞るとその割合は高くなると考えられます。これにより、食品ごとに推薦するものを変える、ということが考えられます。

また、支持度には方向性があり、一般に $C(Y|X) \ne C(X|Y)$ となることに注意が必要です。上記の例では $C(A|C)=0.5, C(C|A)=0.33$ でこれらは一致しません。具体的には、パンを食べた人のうちコーヒーを飲んだ人の割合と、コーヒーを飲んだ人のうちパンを食べた人の割合は異なる、といったものになります。そのため、パンを食べた人にコーヒーを勧めることはあっても、コーヒーを飲んだ人にパンを勧めるのは適切ではない、といったケースがありうることに注意が必要です。

さらに、支持度は特定の食品に対する割合を表すため、食されることが少ないレアな食品に対しても支持度は高くなります。極端な例としては、全データ中1度しか食されなかった食品A・Bの組み合わせは、支持度が1になります。そのため、次に食品A（もしくはB）を食した人に最もオススメすべきものは食品B（もしくはA）となります。これが適切かどうかの判断は難しいですが、レアな食品に対する推薦は注意を要する、もしくは推薦の対象から除外するといった検討が必要かもしれません。

リフト値（Lift）

最後に、食品Xを食したユーザーが食品Yを食した場合のリフト値（Lift） $L$ は、以下のように表すことができます。

$\displaystyle \begin{align} L(Y|X) &= \frac{|X \cap Y| / |X|}{|Y| / |U|}\\ &= \frac{S(X, Y)}{S(X)S(Y)} \tag{1}\\\\ &=\frac{C(Y|X)}{S(Y)} \tag{2}\\ \end{align}$

上記の例では

$\displaystyle \begin{align} L(B|A) &= \frac{C(B|A)}{S(B)} = \frac{1}{3/4} = 1.33\\ \end{align}$

同様にして、 $L(C|B) = 0.66, L(A|C) = 0.66$ などとなります。

リフト値の意味について考えてみます。

式(1)を見ると分母・分子ともに支持度で、分母は積の形になっています。これは、食品XとYの相関を表しており、一方が食されたときに他方がどれだけ食されやすいかを表していると言えます。

また、式(2)を見ると分母が支持度、分子が信頼度となっています。これは、単に無条件で食品Yを食す割合に対して、食品Xの後に食品Yを食す割合がどれほどか、を表しています。言い換えると、食品Xの後に食品Yを推薦することで、推薦しない場合に比べてどれほど増加（あるいは減少）するか、つまりどれだけ持ち上がる（Liftする）かを表していると言えます。そのため、リフト値が1以下の場合には推薦してもしなくても変わらない、1を超える場合には推薦することに意味がある、と考えることができます。

実際には、支持度や信頼度に着目しつつリフト値が高いものを推薦していくことになると思いますが、今回は簡単のためリフト値のみに着目してアソシエーション分析を行ってみます。

アソシエーション分析の実装にあたっては、以下のコードを参考にしました。

github.com

あすけんのデータを一部サンプリングしてアソシエーション分析を計算した結果は以下です（一部加工）。

antecedents, consequents, lift
['きゅうり(1本)'],  ['レタス(1枚)' 'トマト'], 2.528171
['ご飯(白米180g)'],  ['ご飯(白米・小盛り150g)'], 2.129423
['レタス(1枚)'],  ['プチトマト'], 1.965760
['ブロッコリー(ゆで30g)'], ['プチトマト'], 1.873148
['キムチ'], ['納豆'], 1.810700

リフト値の高い順に表示しています。食事の順序は今回は気にしなくてよさそうですが、条件部、帰結部の順に表示しています。

結果からわかることは、

野菜の組み合わせが多く見られるようです🥦
ご飯🍚に対してご飯🍚をオススメするのは…おかわり？
レタスは1枚単位でレコメンド？

ということでしょうか。

なかでも、キムチと納豆の組み合わせは納得感があるのではないでしょうか？豆腐とあわせると、暑くて食欲が低下しがちな夏でもサッパリ頂けそうですね。

行列分解

次に行列分解について説明します。

アソシエーション分析のとき同様、ユーザーと食品のデータが与えられているとします。ただし、今回は各ユーザーが各食品を食した回数を要素とする、ユーザー数 $n$ 、食品数 $m$ の行列 $R\in \mathbb{R}^{n\times m}$ であるとします。

さて、この行列を次のようにおもむろに分解することを考えます。 $Q^{T}$ は行列 $Q$ の転置を表します。

$\displaystyle R \simeq PQ^{T}$

$\displaystyle \begin{align} P = \left( \begin{array}{c} p_1 \\ p_2 \\ \vdots\\ p_n \\ \end{array} \right) ,~~~ Q = \left( \begin{array}{c} q_1 \\ q_2 \\ \vdots\\ q_m \\ \end{array} \right) ,~~~ p, q \in \mathbb{R}^k \end{align}$

$P \in \mathbb{R}^{n\times k}, Q\in \mathbb{R}^{m\times k}$ はそれぞれユーザーの行列と食品の行列を表します。

さらに、ユーザー $u$ は $p_u$ 、食品 $i$ は $q_i$ で表され、それぞれ $k$ コの要素で特徴付けられたベクトルになっています¹。このように行列分解することが出来れば、もとの行列 $R$ の $(u, i)$ 成分 $r_{ui}$ を $p, q$ の積として

$\displaystyle r_{ui} \simeq p_u q_i^{T}$

と計算できることになり、この値が近いほど行列分解がうまくいっていることになります。

行列分解の方法はいくつかありますが、以下では暗黙的評価値に対する行列分解について見ていきます。

IMF（Implicit Matrix Factorization）

IMF（Implicit Matrix Factorization）は、暗黙的評価値に対する行列分解の手法です。

評価値には明示的評価値と暗黙的評価値が存在します。明示的評価値とは、レビューにおける☆5などのようにユーザーが明示的に評価したものであり、暗黙的評価値とは商品詳細ページのクリックや動画の視聴などといったユーザーの行動履歴になります。明示的評価値は評価の精度が高い一方で、ユーザーに評価してもらう必要があるので収集できるデータが少なくなります。一方、暗黙的評価値は評価の精度が低い一方で、ユーザーに明示的に評価してもらう必要がなく、大量のデータを取得することができます。あすけんでは、各ユーザーの各食品に対する明示的な評価は存在しませんが、その登録数をもって暗黙的評価値とすることを考えてみます。

ここで、ユーザー $u$ が食品 $i$ を食した回数（食事登録数）を $r_{ui}$ とすると、ユーザーの食品に対する暗黙的評価値は、以下のように考えることができます。

まず、「1度でも食していれば好意を持っているだろう」という仮説から、二値変数 $\bar{r}_{ui}$ を定義します。

$\displaystyle \bar{r}_{ui} = \begin{cases}1~ (r_{ui}>0)\\0 ~(r_{ui}=0)\end{cases}$

さらに、「食す回数が多いほど好意の度合いが高いだろう」という仮説から、二値変数に対する信頼度 $c_{ui}$ を定義します。

$\displaystyle c_{ui} = 1 + \alpha r_{ui} ~~~(\alpha \gt 0)$

1度も食していない場合には信頼度は0、食す回数が増えるほど信頼度は大きくなります。

暗黙的評価値の行列分解では、以下の最適化問題を解くことになります。

$\displaystyle \min_{p,q}\sum_{u}^{n}\sum_{i}^{m}c_{ui} (\bar{r}_{ui}-p_{u}q_{i}^{T} )^2 + \lambda \Bigl( \sum_{u} ||p_{u}||^{2} + \sum_{i}||q_{i}||^{2}\Bigr)$

ここで、 $||p_u||^2, ||q_i||^2$ はそれぞれノルムの2乗、 $\lambda$ 項は過学習を防ぐための正則化項になります。大雑把には、二値変数を要素に持つ評価値行列を再現するユーザーと食品のベクトル $p, q$ を探す、ただし信頼度を加味する、といったイメージでしょうか。

IMFの実装にあたっては、以下のコードを参考にしました。

github.com

あすけんのデータを一部サンプリングしてIMFを行った結果は以下です。推薦したメニューと実際にユーザーが食したメニューを表示しています（一部加工）。

user_id: xxxx

=====推薦したメニュー=====
ご飯(白米200g)
味噌汁(わかめと豆腐)
ミックス野菜サラダ
レタス(1枚)
きゅうりの浅漬け

=====実際に食したメニュー=====
ご飯(白米200g)
アジのみりん干し
味噌汁(お好み具材セレクト可能)
ほうれん草のナムル

結果からわかることは、

ご飯(白米200g)が一致しています🍚
味噌汁は、細かい違いを別にすれば一致しています
レタスは1枚単位でレコメンド？

といったことでしょうか。

今回は簡単のため割愛しましたが、実際には ${\rm Precision}@K$ や ${\rm Recall}@K$ といったランキング評価指標を用いて精度を評価します。また1ユーザーだけでなく、複数のユーザーに対するレコメンド結果の精度を ${\rm MAP}@K$ などの指標で評価することになります。