pythonでアイテムベース協調フィルタリングを実装する - MovieLensを例に

協調フィルタリングのうち、最もシンプルなアイテムベース協調フィルタリングをpythonで実装してみたので、Qiitaに晒してみます。
（なにぶん初めての実装なのでもし間違っている箇所があればご指摘を mm）


推薦の題材としては、[MovieLens 100K Dataset](http://grouplens.org/datasets/movielens/100k/) を用います。詳しい解説はリンク先に譲るとして、ざっと言うと、1〜5 の rating で 映画を評価したデータです。


## 協調フィルタリングについて

協調フィルタリングは英語だと Collaborative filtering で「他人の評価を利用した口コミによる推薦システム」と言えます。


協調フィルタリングは下記のように分類することができ、アイテムベース協調フィルタリングはその中の一手法として位置付けられます。

- メモリベース法
    - 蓄積したデータを推薦時に直接用いるもの
        - ユーザベース
        - アイテムベース（★今回扱うもの）
- モデルベース法
    - 事前に調べておいたデータの規則性を用いるもの
        - クラスタモデル
        - 関数モデル
        - etc


詳しくは 神嶌先生による[推薦システム 解説・講義資料](http://www.kamishima.net/jp/kaisetsu/) を読むとよいです。この分類も上記資料を参照したものです。


## アイテムベース協調フィルタリング

協調フィルタリングは「他人の評価を利用した」推薦システムであると書きましたが、アイテムベース協調フィルタリングでは以下の2つの仮定が基となります。


仮定1： <i>Aさんが未評価のアイテム（=推薦候補）のうち、気に入る可能性が高いのはAさんが高く評価しているアイテムと類似したものだろう。</i>

仮定2： <i>アイテム同士は評価のパターンが近ければ、類似していると言えるだろう。</i>


イメージを掴むには、[協調フィルタリングを利用した推薦システム構築](http://www.slideshare.net/masayuki1986/recommendation-ml) のP36〜の解説が分かりやすいです。



数式で表現すると以下の通りです。

```math
r'_{u,y} = \frac{\sum _{j \in Y_u} {s_{y,j}r_{u,j}}}{\sum _{j \in Y_u} {\mid s_{y,j} \mid}}
```

```math
\scriptsize r'_{u,y} はユーザ u のアイテム y に関する評価予測 \\
\scriptsize S_{y,j} は アイテム y と アイテム j の類似度 \\
\scriptsize Y_{u} は ユーザ u が評価済のアイテムの集合 \\
\scriptsize r_{u,j} は ユーザ u のアイテム j に関する評価
```

分子は評価済アイテムの類似度による重み付け和で、これが仮定1に相当します。
分母は正規化です。


## STEP1: アイテムの類似度を計算する

まずは仮定2に相当するアイテムの類似度を計算する必要があります。


[python で csv, tsvデータを行列に変換する - MovieLensを例に](http://qiita.com/kotaroito/items/4cc8639864ee46524c51) で 行列 R に読み込み済みとします。

```py3
>>> print(R)
[[ 5.  3.  4. ...,  0.  0.  0.]
 [ 4.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  0.]
 ...,
 [ 5.  0.  0. ...,  0.  0.  0.]
 [ 0.  0.  0. ...,  0.  0.  0.]
 [ 0.  5.  0. ...,  0.  0.  0.]]
```

今回はコサインを用いて、アイテムの類似度を計算します。Pearson相関を利用することもあるようです。

```py3
def compute_item_similarities(R):
    # n: movie counts
    n = R.shape[1]
    sims = np.zeros((n,n))

    for i in range(n):
        for j in range(i, n):
            if i == j:
                sim = 1.0
            else:
                # R[:, i] は アイテム i に関する全ユーザの評価を並べた列ベクトル
                sim = similarity(R[:,i], R[:,j])

            sims[i][j] = sim 
            sims[j][i] = sim 

    return sims 

def similarity(item1, item2):
    # item1 と item2 のどちらも評価済であるユーザの集合
    common = np.logical_and(item1 != 0, item2 != 0)

    v1 = item1[common]
    v2 = item2[common]

    sim = 0.0
    # 共通評価者が 2以上という制約にしている
    if v1.size > 1:
        sim = 1.0 - cosine(v1, v2)

    return sim

sims = compute_item_similarities(R)
```

```py3
>>> print(sims)
[[ 1.          0.94873739  0.91329972 ...,  0.          0.          0.        ]
 [ 0.94873739  1.          0.90887971 ...,  0.          0.          0.        ]
 [ 0.91329972  0.90887971  1.         ...,  0.          0.          0.        ]
 ...,
 [ 0.          0.          0.         ...,  1.          0.          0.        ]
 [ 0.          0.          0.         ...,  0.          1.          0.        ]
 [ 0.          0.          0.         ...,  0.          0.          1.        ]]
```

## STEP2: 評価を予測する

STEP1で下記式の類似度Sは得られたので、重み付け和を求めて正規化すれば予測値を求めることができます。

```math
r'_{u,y} = \frac{\sum _{j \in Y_u} {s_{y,j}r_{u,j}}}{\sum _{j \in Y_u} {\mid s_{y,j} \mid}}
```


```py3
def predict(u, sims):
    # 未評価は0, 評価済は1となるベクトル。normalizersの計算のために。
    x = np.zeros(u.size) 
    x[u > 0] = 1

    scores      = sims.dot(u)
    normalizers = sims.dot(x)

    prediction = np.zeros(u.size)
    for i in range(u.size):
        # 分母が 0 になるケースと評価済アイテムは予測値を 0 とする
        if normalizers[i] == 0 or u[i] > 0:
            prediction[i] = 0
        else:
            prediction[i] = scores[i] / normalizers[i]

    # ユーザ u のアイテム i に対する評価の予測
    return prediction
```

確認のために、簡単な例で試してみたところ、それらしい結果が得られました。

```py3

u = np.array([5, 0, 1])
sims = np.array([ [1, 0.2, 0], [0.2, 1, 0.1], [0, 0.1, 1] ])

>> print(predict(u, sims))
[ 0.          3.66666667  0.        ]
```

## まとめ

アイテムベース協調フィルタリングを MovieLens のデータを基に実装しました。
本記事の元となった資料は以下の通りです。

  - [推薦システム 解説・講義資料](http://www.kamishima.net/jp/kaisetsu/)
  - [協調フィルタリングを利用した推薦システム構築](http://www.slideshare.net/masayuki1986/recommendation-ml)
  - [第5回　協調フィルタリング：情報推薦システムの基本｜gihyo.jp … 技術評論社](http://gihyo.jp/dev/serial/01/information-recommendation-system/0005)