アイテムベース協調フィルタリングに今更挑戦してみた

自分の知識の整理もかねて今更ながら協調フィルタリングについてまとめます。
基本的には自分用勉強ノートみたいな感じですが、

> 「レコメンドやってみたいけどどういう風に始めればよいかわからない」
> 「個々の概念はわかるけど全体を繋げるとどんな感じになるのかわからない」

という方向けにも書いてます（これは自己紹介でもあります）。
なるべく内容が正確であるよう心がけますが、もし誤り・誤解を招く表現がございましたらコメントにてご指摘頂けると助かります。

## おしながき
1. 今回用いるデータセット - MovieLens 100k
2. レコメンドシステムのアプローチ／協調フィルタリングとは
3. データの整形
4. 類似度の計算
5. スコアの算出~レコメンドしてみた
6. レコメンドの精度を評価 - Precisionを用いて
7. 参考資料

なお今回用いているコードは[こちらのColaboratory](https://drive.google.com/open?id=1LFSFD44J45Pn2QAsps7nz7PJnUoY87o6)にて確認することができます。

## 1. 今回用いるデータセット - MovieLens 100k
### 1.1 概要
今回使用するMovieLensデータセットは推薦システムの開発やベンチマークのために作られた映画のレビューのためのデータセットです。
一言にMovieLensと言ってもいくつか種類があり、例えば以下のようなものが配布されています。
  1. MovieLens 100k Dataset
  2. MovieLens 1M Dataset
  3. MovieLens 20M Dataset
それぞれリリース年月・データ収集の期間が異なっており、今回使用するMovieLens 100k Datasetでは1997年9月から1998年4月までのデータが使われています。
MovieLensへのリンクは[こちら](https://grouplens.org/datasets/movielens/)です

### 1.2 データの取り込み
ml-100k.zipを解凍すると色々なファイルが入っています。
ここでは各ユーザのそれぞれのアイテムに対する評価10万件が入っているu.dataを用いて中身を確認してみます。
なお今回はColaboratory上で動くようサイトから直接取得しています。

```python
import numpy as np
import pandas as pd
from tqdm import tqdm
from sklearn.metrics.pairwise import pairwise_distances

# 今回はサイトから直接データを引っ張ってきている
data_org = pd.read_csv(
   'http://files.grouplens.org/datasets/movielens/ml-100k/u.data', names=["user_id", "item_id", "rating", "timestamp"], sep="\t")
data_org.head()
```
中身は以下の通りです。

|  | user_id | item_id | rating | timestamp |
|--:|--:|--:|--:|--:|
| 0 | 186 | 302 | 3 | 891717742 |
| 1 | 22 | 377 | 1 | 878887116 |
| 2 | 244 | 51 | 2 | 880606923 |
| 3 | 166 | 346 | 1 | 886397596 |
| 4 | 298 | 474 | 4 | 884182806 |

見ての通り一回のレビューにつき1レコード入るような形をしています。
具体的な内容を箇条書きすると以下のようになります。

- 943ユーザによる1682アイテムに対するレビュー   
  （\* 全員が全てのアイテムをレビューしたわけではない）
- 全部で10万件のレビューがあり、各ユーザは最低20本評価している
- 評価値は{1,2,3,4,5}の5つ
- レコードの順番はランダム


## 2. レコメンドシステムのアプローチ／協調フィルタリングとは
### 2.1 レコメンドシステムいろいろ
[1]によるとレコメンドシステムには大きく分けて以下のような類型があると言われています。

> 1. 協調型
> 2. 内容ベース型
> 3. 知識ベース型

今回扱う協調フィルタリングはこのうち協調型に属する手法となっています（みたままじゃん、って感じですが）。

### 2.2 アイテムベース協調フィルタリングとは
そもそも協調フィルタリングの基本的なアイデアは「あるユーザAとユーザBの趣味嗜好が似ている場合、ユーザAは将来ユーザBと似たような行動をとるだろう（逆も然り）」という点にあります。
<b>「ユーザが暗黙的にお互いに協調する」</b>ことから協調フィルタリングと呼ばれると言われています[1][^1]。

協調フィルタリングにも以下のような2つの類型があります。

> 1. ユーザベース協調フィルタリング　…　ユーザ同士の類似度を元にレコメンドを行う
> 2. アイテムベース協調フィルタリング　…　アイテム同士の類似度を元にレコメンドを行う

ユーザベース協調フィルタリングでは「ユーザAは未評価アイテムIに対して、当該ユーザと似たような嗜好をしている他ユーザと同じような評価をするだろう」という仮定に基づいています。
つまりユーザAと似ている（＝類似度の高い）ユーザの未評価アイテムIへの評価点を元にユーザAの評価点を予測する、というアプローチになります。

一方今回用いるアイテムベース協調フィルタリングでは「アイテム同士の類似度とあるユーザAの過去に評価したアイテムの評価点を用いて未評価アイテムIの評価点を予測する」というアプローチになります。
[1]によるとこちらの手法の方がよりオフライン処理しやすく、かつ計算速度という面で優れていることからより使われるようです。

以下文字数を少し減らすため「アイテムベースCF」と表記します。

### 2.3 アイテムベースCFでやりたいこと

今回のタスクを改めて確認すると「ユーザAの未評価アイテムのうちテストデータで評価する（≒新たに視聴する、と想定）アイテムを予測する」ということでした。
これを踏まえて今回アイテムベースCFで何をやりたいか整理すると以下のようになります。

> 1. アイテム同士の類似度を出す
> 2. あるユーザの未評価アイテムの予測評価点を出す
> 3. 予測評価点の高いアイテムのうちk点推薦し、そのレコメンドがどれだけ正確か評価する

先の項では類似度の話しかしていませんでしたが、実際にレコメンドするアイテムを決定するためには予測評価点（スコア）を算出する必要があります。
またレコメンドするアイテム点数はある程度自由に決めることができますが、今回はk=10で評価していきたいと思います。

次の項以降具体的な話に入っていきます。

## 3. データの整形
### データの取り込み
精度の評価が必要なためデータを学習用とテスト用に分ける必要があります。
MovieLensの場合はご丁寧に最初から学習用とテスト用のデータが分かれています。親切です。
今回はその中でもua.baseとua_testを使います。早速取り込みます。

```python
# ユーザ×評価値のデータ
u_data_train = pd.read_csv(
   '../data/org/ua.base', names=["user_id", "item_id", "rating", "timestamp"], sep="\t")
u_data_test = pd.read_csv(
   '../data/org/ua.test', names=["user_id", "item_id", "rating", "timestamp"], sep="\t")
```

ua.testの件数は9430件で、これはちょうどユーザ数×10件という数に当たります。つまりテストデータでは全てのユーザが10件評価をしている状態になっています[^2]。

### 3.2 データの整形
次にアイテム同士の類似度を計算できるようこの取り込んだ学習データをitem_id × user_idの行列に直していきます。

```python
# ここの変換にちょっと時間がかかっているので修正の余地あり

# item_id x user_idの行列に変換する
item_list = u_data_org.sort_values('item_id').item_id.unique()
user_list = u_data_org.user_id.unique()
rating_matrix_item = np.zeros([len(item_list), len(user_list)])

for item_id in tqdm(range(1, len(item_list))):
    user_list_item = u_data_train[u_data_train['item_id'] == item_id].sort_values('user_id').user_id.unique()
    for user_id in user_list_item:
        try:
            user_rate = u_data_train[(u_data_train['item_id'] == item_id) & (u_data_train['user_id'] == user_id)].loc[:, 'rating']
        except:
            user_rate = 0
        rating_matrix_item[item_id-1, user_id-1] = user_rate
````

この結果以下のような行列を得られます。

```
array([[5., 4., 0., ..., 5., 0., 0.],
       [3., 0., 0., ..., 0., 0., 5.],
       [4., 0., 0., ..., 0., 0., 0.],
       ...,
       [0., 0., 0., ..., 0., 0., 0.],
       [0., 0., 0., ..., 0., 0., 0.],
       [0., 0., 0., ..., 0., 0., 0.]])
```

また最後の予測評価値の計算のところで使用する二つの行列もここで作成しておきます。

```python
# item x userの評価したかどうか{0, 1}がわかる行列作成
rating_matrix_calc = rating_matrix_item.copy()
rating_matrix_calc[rating_matrix_calc != 0] = 1

# 評価していないアイテムに1が立つ行列を作成。後で使う
rating_matrix_train = np.abs(rating_matrix_calc - 1)
```

## 4. 類似度の計算
データの整形も終えたところでいよいよアイテム同士の類似度を計算していきます。
類似度の計算方法には色々ありますが、その中でも今回はコサイン類似度とjaccard指数を用いた計算方法を紹介します。

### 4.1 コサイン類似度
コサイン類似度には「普通のコサイン類似度」と「調整コサイン類似度」の2種類があります。
まず普通のコサイン類似度の出しかたを確認します。

```math
sim_{cosine}(\vec{a}, \vec{b}) = \frac{\vec{a} \cdot \vec{b}}{|\vec{a}|\,\times\, |\vec{b}| }
```

簡単に言えば二つのベクトル$\vec{a}$と$\vec{b}$がどれだけ似ているか、という話です。
ただしレコメンドに置いては評価点少し修正した調整コサイン類似度が用いられるようです。
アイテム$i$とアイテム$j$の調整コサイン類似度は以下のように表されます。

```math
sim_{ajusted\_cosine}(i,j) = \frac{\sum_{u \in U_i \cap U_j} (r_{ui} - \bar{r_u}) \cdot (r_{uj} - \bar{r_u})}{\sqrt{\sum_{u \in U_i \cap U_j}(r_{ui} - \bar{r_u})^2} \cdot \sqrt{\sum_{u \in U_i \cap U_j}(r_{uj} - \bar{r_u})^2}}
```

ここで$r_{u,i}$はユーザ$u$のアイテム$i$に対する評価点、$\bar{r_u}$はユーザ$u$の全アイテムの評価点の平均とします。
アイテム$i$とアイテム$j$の類似度は両方のアイテムを評価したユーザたちの評価点を用いて計算されます。
今回用いるpairwise_distancesでは調整コサイン類似度で計算しています[^3]。

### 4.2 jaccard指数
jaccard指数は集合Aと集合Bがどれだけ似ているかを表します。
具体的には集合AとBの和集合のうち共通部分がどれだけあるかで表されます。
式では以下のように表されます

```math
sim_{jaccard}(a,b) = \frac{A \cap B}{A \cup B}
```

### 4.3 類似度の計算
scikit-learnにあるpairwise_distancesを用いて類似度行列を出します。
今回はコサイン類似度を用います。

```python
# おとなしくpairwise_distanceを使う

# コサイン
similarity_matrix = 1 - pairwise_distances(rating_matrix_item, metric='cosine')

# jaccard
# similarity_matrix = 1 - pairwise_distances(rating_matrix_item, metric='jaccard')

# 対角成分の値はゼロにする
np.fill_diagonal(similarity_matrix, 0)
```
ここで得られるsimilarity_matrixは以下のようになります。

```
array([[0.        , 0.40295926, 0.33326137, ..., 0.        , 0.05080415,
        0.        ],
       [0.40295926, 0.        , 0.2691851 , ..., 0.        , 0.08155909,
        0.        ],
       [0.33326137, 0.2691851 , 0.        , ..., 0.        , 0.        ,
        0.        ],
       ...,
       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
        0.        ],
       [0.05080415, 0.08155909, 0.        , ..., 0.        , 0.        ,
        0.        ],
       [0.        , 0.        , 0.        , ..., 0.        , 0.        ,
        0.        ]])
```

これで予測評価値の計算およびレコメンドする準備が整いました。
次の項ではいよいよユーザ1人に対してレコメンドをしてみたいと思います。

## 5. スコアの算出~レコメンドしてみた
### 5.1 予測評価点（スコア）の算出方法
[2]によるとアイテムベースCFのスコア（ユーザ$u$の未評価アイテム$i$に対する予測評価点$r_{u,i}$）の算出方法は以下のように示されています。

```math
r_{u, i} = \frac{\sum_{j \in Q_t(u)} sim(i, j) * r_{u, j}}{\sum_{j \in Q_t(u)} sim(i, j)}
```

簡単にいうとユーザ$u$が評価したアイテムの実際の評価点と未評価アイテムuと評価したアイテムの類似度を掛けた値の加重平均をとった形になります。
類似度が高くて評価が高い場合は高く評価し、高い評価であっても類似度が低い場合or類似度が高くても評価が低い場合は低く評価されます。

なお私がこの数式通りに実装しようとしたところ精度（Precision）が視力以下になってしまいました。
そのため今回は[3]を参考に以下の通り変更してあります。
簡単にいうと分母を取り払っています。

```math
r_{u, i} = \sum_{j \in Q_t(u)} sim(i, j) * r_{u, j}
```


### 5.2 user_id=100でレコメンドの結果確認

いよいよスコアの算出とレコメンドをします。
ここでの戦略は以下のようになります。

> 1. 類似度×評価点を算出
> 2. アイテムごとに「類似度×評価点」を合計
> 3. ユーザが既に評価したアイテムのスコアはゼロに直す
> 4. この状態でスコアの最も高いアイテム10個をレコメンド

これをコードに起こしていきます。

```python
user_id = 100
hits = 0

# 各ユーザの評価値を抜き出し「類似度×評価点」を算出
rating_matrix_user = rating_matrix_item[:, user_id - 1]
pred_rating_user = similarity_matrix * rating_matrix_user
# アイテム（行）ごとに「類似度×評価点」を合計
pred_rating_user = pred_rating_user.sum(axis=1)

# ユーザが既に評価したアイテムのスコアはゼロに直す
pred_rating_user_item = pred_rating_user * rating_matrix_train[:,user_id - 1]

#ここからレコメンドされたアイテムがどれだけあっていたかを評価していく
recommend_list = np.argsort(pred_rating_user_item)[::-1][:10] + 1
purchase_list_user = u_data_test[u_data_test.user_id == user_id].loc[:, 'item_id'].unique()
for item_id in recommend_list:
    if item_id in purchase_list_user:
        hits += 1
pre = hits / 10.0
```

上記コードの実行結果は以下の通りです。

```
print('Recommend list:', recommend_list)
print('Test Rated list:', purchase_list_user)
print('Precision:', str(pre))

> Recommend list: [302 307 750 288 332 748 331 301 245 268]
> Test Rated list: [266 268 288 302 321 340 344 354 355 750]
> Precision: 0.4
```

なんかめっちゃ当たってる…。といってもこれは個人差あるので次の項で全体の精度をみていきたいと思います。

## 6. レコメンドの精度を評価 - Precisionを用いて

ということで全体の精度評価です。
今回は指標としてPrecisionを用いています。他にもいい指標がありますが[こちらの解説](http://blog.brainpad.co.jp/entry/2017/08/25/140000)が素晴らしく僕にはいうことがない状態です。
ですので評価指標についてはそちらを参照して頂くことにし、ここでは粛々と精度の評価をしていくこととします。

```python
# 予測評価値の計算
precision_list = []
recall_list = []
user_list_test = u_data_test.sort_values('user_id').user_id.unique()

for user_id in tqdm(user_list_test):
    hits = 0
    # 各ユーザの評価値を抜き出し「類似度×評価点」を算出
    rating_matrix_user = rating_matrix_item[:, user_id - 1]
    pred_rating_user = similarity_matrix * rating_matrix_user

    # アイテム（行）ごとに「類似度×評価点」を合計
    pred_rating_user_item = pred_rating_user * rating_matrix_train[:,user_id - 1]
    
    # ユーザが既に評価したアイテムのスコアはゼロに直す
    pred_rating_user_item[np.isnan(pred_rating_user_item)] = 0
    
    #ここからレコメンドされたアイテムがどれだけあっていたかを評価していく
    recommend_list = np.argsort(pred_rating_user_item)[::-1][:10] + 1
    purchase_list_user = u_data_test[u_data_test.user_id == user_id].loc[:, 'item_id'].unique()
    if len(purchase_list_user) == 0:
        continue
    for item_id in recommend_list:
        if item_id in purchase_list_user:
            hits += 1
    pre = hits / 10.0
    precision_list.append(pre)
    
# 全体の精度検証
precision = sum(precision_list) / len(precision_list)
print('Precision:', precision)
```

最終的な精度は以下のようになりました

```
Precision: 0.1995758218451741
```

これでも正直ちょっと高い気がしますが、[3]と似たような結果になったので一旦これで終わりとします。
注釈でも述べてる通りデータの分け方変えると精度がガックリ落ちていて、そっちの方がそれっぽい結果だったので分け方に問題があったのかもしれません。

ちょっともやもやした部分が残っていしまいましたがひとまずアイテムベースCFの実装が終わりました。
今回は100kという規模だったので普通のPythonで終わりましたが、これがもっと大きくなってくるとSparkだのなんだのが必要になるんだろうなと感じました。
これの点検も必要ですが他のモデルも早く実装したいです。

ということで終わりです。

### 参考資料
[1] Dietmar Jannach, et. al, 田中克己, 角谷和俊訳, 『情報推薦システム入門 - 理論と実践-』, 共立出版, 2012
[2] Charu C. Aggrawal, <i>Recommender Systems: The Textbook</i>, Springer, 2016
[3] [fuxuemingzhu/MovieLens-Recommender (GitHub)](https://github.com/fuxuemingzhu/MovieLens-Recommender)

[^1]: もう少し細かく分けると協調型も①メモリベースCFと②モデルベースCFに分かれます。今回のアイテムベースCFはオリジナルの評価値データベースを全てメモリの中に格納し推薦を行うことからメモリベースと言われます。なお近傍点を用いているためNeigborhood-Based Collaborative Filteringとも言われます[2]。
[^2]: なおu.dataをtimestampで並び替えてtrain_test_splitすることも可能です。が、その場合精度がかなり落ちます。リークでもあるのだろうか…。
[^3]: cosine_similarityのソース[こちら](https://github.com/scikit-learn/scikit-learn/blob/7389dba/sklearn/metrics/pairwise.py#L861)とnormalizeのソース[（こちら）](https://github.com/scikit-learn/scikit-learn/blob/7389dbac82d362f296dc2746f10e43ffa1615660/sklearn/preprocessing/data.py#L1493)からそのように見受けられます。