Matrix Factrization(MF)と協調フィルタリングについて

## 概要
強調フィルタリングにおいて次元削除を行うことで、より良い推薦を行おうという手法です。
勉強も兼ねてまとめました。
他のQiitaの記事[Matrix Factorizationとは](https://qiita.com/ysekky/items/c81ff24da0390a74fc6c)と[Matrix Factorizationとレコメンドと私](https://qiita.com/michi_wkwk/items/52660778ad6a900965ee)を参考に作成しています。

## 協調フィルタリング
まず簡単に協調フィルタリングについて説明します。
協調フィルタリングは、ユーザの嗜好データを用いてレコメンドする方法です。
例）本の趣味が似ている知り合いに、面白かった本を教えてもらう。


__手順__
実際に処理を行う際の手順は以下のようになります。
1. ユーザの嗜好データを取得する
2. 嗜好データに基づき、ユーザ間の類似度を算出
3. ターゲットのユーザに対して、似ているユーザを抽出
4. 似ているユーザが購入している商品をレコメンド

__具体例__
次に具体的な例を示してみます。
あるサービスで4人のユーザが４つのアイテムに対して１〜５の５段階評価をしたときの評価値を
以下のようなベクトルで表します。ただし、0は未評価のデータを示します。
また、各ユーザにおいて１つ目の要素が$item_1$の評価であり、同じ次元の要素は同じアイテムに対する評価を表します。

```math
\vec{user_1} = (3,5,0,0)^T \\
\vec{user_2} = (5,0,1,4)^T \\
\vec{user_3} = (5,5,1,5)^T \\
\vec{user_4} = (4,3,3,2)^T \\
```
次に、各ユーザのベクトル同士がどれだけ似ているかを、今回はコサイン類似度を用いて調べます。
コサイン類似度は次の式で表されます。

```math
cos(\vec{p},\vec{q}) = \frac{\vec{p} \cdot \vec{q}}{|\vec{p}||\vec{q}|}
```

それでは、pythonのscipyパッケージを用いて、$user_1$と最も似ているユーザを実際に調べていきます。

```python
>>> from scipy.spatial.distance import cosine
>>> import numpy as np
>>> user1 = np.array([3,5,0,0])
>>> user2 = np.array([5,0,1,4])
>>> user3 = np.array([5,5,1,5])
>>> user4 = np.array([4,3,3,2])
>>> cosine(user1,user2)
0.6030579069812776
>>> cosine(user1,user3)
0.21311052463536628
>>> cosine(user1,user4)
0.24883990649921273
```
ここで、scipy.spatial.distance.cosineは距離を返す関数になっているので、
[1-類似度]の値を返していることに注意してください。
そのため、値が小さいほど類似度が大きいということになるので、
$user_1$は$user_3$と最も似ていることがわかります。
したがって、$user_3$が最高の5と評価しているがまだ$user_1$は評価していない$item_4$を
推薦すればいいのではないかという結論を導き出すことができます。

## なぜ次元削除をする必要があるのか
先ほど例で示したデータの場合はうまくいっているように見えます。
しかし、実際のサービスにおいてアイテム数は何万、何十万とあり、高次元なデータとなってしまいます。
機械学習は、高次元データをうまく扱えない（__次元の呪い__）という問題を抱えるため、
高次元データの特徴をできるだけ保持したままデータを低次元データに変換する必要があります。

## Matrix Factorizationとは？
$m$人のユーザと$n$個のアイテムが存在する場合について考えます。
先ほどの例では、各ユーザは$n$次元ベクトルで表現されますが、これを$k$次元$(0 < k < m)$に次元削除して変換することを目標とします。
つまり、評価値を表す$m \times n$の行列Rを、ユーザ要素を表す$k \times m$の行列Pとアイテム要素を表す$k \times n$の行列$Q$に分解し、近似を行います。

```math
R \simeq P^TQ
```

ここで、ユーザ$u$が評価したアイテム$i$の評価値$\hat{r_{ui}}$は$\hat{r_{ui}} = \vec{p_u}^T\vec{q_i}$として表すことができます。
Matrix Factorizationでは、評価値$\hat{r_{ui}}$を既知の評価値から学習することで最適な近似を行います。

まず、次の式を満たすP、Qを訓練データから求めます。

```math
min_{P,Q} \sum_{(u,i) \in R} (r_{ui} - \hat{r_{ui}})^2 + \lambda(||\vec{p_u}|| ^2+||\vec{q_i}||^2)
```
次に上の式を最適化するために、以下の更新式を用います。

```math
\begin{align}
e_{ui} &= r_{ui} - \hat{r_{ui}} \\
p_{u,k} &= p_{u,k} + \gamma \cdot(e_{ui}\cdot p_{u,k} - \lambda \cdot p_{u,k}) \\
q_{i,k} &= q_{i,k} + \gamma \cdot(e_{ui}\cdot q_{i,k} - \lambda \cdot q_{i,k})
\end{align}
```
## Matrix Factorizationを用いる利点
次元削減をする方法としては、SVD（Singular Value Decomposiitiion）と呼ばれる手法が広く知られており、
情報検索などの分野で活用されています。
ここで、SVDでは0という情報を保存しながら次元削減を行います。
しかし、推薦システムの場合、一般的に0は未評価を表す値であるため、推薦の最適化にはあまり有効ではない形で変換されてしまいます。
そのため、値があるところのみで最適化していくMatrix Factorizationが推薦システムには最も有効であるとされています。

## まとめ
Matrix Factrizationという言葉をよく見かけるため今回まとめてみました。
推薦の分野も面白そうだと少し感じました。

## 参考
- https://qiita.com/ysekky/items/c81ff24da0390a74fc6c
- https://qiita.com/michi_wkwk/items/52660778ad6a900965ee
- Koren, Yehuda, Robert Bell, and Chris Volinsky. "Matrix factorization techniques for recommender systems." Computer 42.8 (2009): 30-37.
- https://www.slideshare.net/hoxo_m/ss-53305070