Pythonで簡単な協調フィルタリングを実装するためのノート



##この記事について

Pythonで `協調フィルタリング` のアルゴリズムを簡単に書いてみる
協調フィルタリングはいわゆる「これを見ている人はこれも見ています」の仕組みのアレである。

ここで扱っているのは非常に簡単なアルゴリズムなので、実際に何かの用途にそのまま使えるようなものではないが、協調フィルタリングアルゴリズムのHow to Workを簡単に理解するには役立つだろう。

この記事のコードを実際に書いてみれば、**「これを見ている人はこれも見ています」**のロジックはコンセプト自体はそれほど難解ではないということが理解いただけると思う。


## 協調フィルタリングを勉強するのに有用なサイト

なお、この記事で扱っているコードは[このサイト](http://dataaspirant.com/2015/05/25/collaborative-filtering-recommendation-engine-implementation-in-python/)を参考にしている。
英語を読むのに抵抗がない諸氏はオリジナルのサイトを読んでも良いだろう。

その他、レコメンドシステムのコンセプトを勉強するのに有用なサイトを幾つか列挙する
特にCourseraの講義はオススメである

- [Coursera "intro to recommender systems"](https://www.coursera.org/learn/recommender-systems/lecture/bWRen/introduction-to-recommender-systems)
- [kamishima.net 推薦システムのアルゴリズム](http://www.kamishima.net/archive/recsysdoc.pdf)
- [gihyo.co.jp 情報推薦システムの基本](http://gihyo.jp/dev/serial/01/information-recommendation-system)
- [slide share 協調フィルタリングを利用した推薦システム構築](http://www.slideshare.net/masayuki1986/recommendation-ml)


##協調フィルタリングの基本的なコンセプト
あるユーザAに対して、オススメの映画をレコメンドするアルゴリズムを考えよう。
この時アルゴリズムで行われることは単純化すると下記のようになる

```
step① そのユーザと他のユーザの **類似度** を計算する
↓
step② 他のユーザが見た映画のうち、ユーザAがまだ見てない映画の集合を抽出する
↓
step③ それらの映画群のうち、おすすめ度が高い映画のリストを返す。
       この選定の際に、類似度が高いユーザが見た映画ほど重みが高くなるようにする
```


## 準備

#### 必要なパッケージのインストール

```py:package.py
from math import sort
```

#### データの用意
ここで使うデータには、何人かの映画好きが見た映画とそのレビュー（得点）の結果が辞書形式で入っている。

```py:dataset.py
dataset={
 'Lisa Rose': {
 'Lady in the Water': 2.5, 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'Superman Returns': 3.5,'You, Me and Dupree': 2.5, 'The Night Listener': 3.0
  },
 'Gene Seymour': {
 'Lady in the Water': 3.0, 'Snakes on a Plane': 3.5, 'Just My Luck': 1.5, 'Superman Returns': 5.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 3.5
  },
 'Michael Phillips': {
 'Lady in the Water': 2.5, 'Snakes on a Plane': 3.0, 'Superman Returns': 3.5, 'The Night Listener': 4.0
  },
 'Claudia Puig': {
 'Snakes on a Plane': 3.5, 'Just My Luck': 3.0, 'The Night Listener': 4.5, 'Superman Returns': 4.0, 'You, Me and Dupree': 2.5
  },
 'Mick LaSalle': {
 'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'Just My Luck': 2.0, 'Superman Returns': 3.0, 'The Night Listener': 3.0, 'You, Me and Dupree': 2.0
  },
 'Jack Matthews': {
 'Lady in the Water': 3.0, 'Snakes on a Plane': 4.0, 'The Night Listener': 3.0, 'Superman Returns': 5.0, 'You, Me and Dupree': 3.5
  },
 'Toby': {
 'Snakes on a Plane':4.5, 'You, Me and Dupree':1.0, 'Superman Returns':4.0
  }
}
```

## ユーザ同士の「類似度の計算」
協調フィルタリングでは、まず「ユーザ間の類似度」を計算する。
ここでアルゴリズムの設計上ポイントとなるのは、**どのようにして「あるユーザ同士が似ている、もしくは似ていない」**と定義するかだ。

これには設計者の思惑によって無数に定義が考えられるが、
ここでは、「ユーザ同士が同じ映画に対して近い点数の評価を与えているほど」「類似度が高い」と定義して話をすすめる

この場合、`ユーザ(person1, person2)`間の類似度を計算する関数を下記にように実装できる

```py:similarity.py
def get_similairty(person1, person2):
  
  ## 両者とも見た映画の集合を取る
  set_person1 = set(dataset[person1].keys())
  set_person2 = set(dataset[person2].keys())
  set_both = set_person1.intersection(set_person2)
  
  if len(set_both)==0: #共通でみた映画がない場合は類似度を0とする
    return 0
  
  list_destance = []
  
  for item in set_both:
    # 同じ映画のレビュー点の差の2乗を計算
    # この数値が大きいほど「気が合わない」=「似ていない」と定義できる 
    distance = pow(dataset[person1][item]-dataset[person2][item], 2) 
    list_destance.append(distance)
  
  return 1/(1+sqrt(sum(list_destance))) #各映画の気の合わなさの合計の逆比的な指標を返す
```

ここでは、下記の数字を類似度として定義している
類似度 = ```1/(1+sqrt(sum(list_destance)))```...(1)

`sum(list_destance)`はレビュー点数空間でのユーザ同士の距離の2乗であることに注意。
この距離が大きいほど `似ていない`ということを表すので、(1)は`似ている`度合いを表すことになる。距離が`0の場合`類似度は1になり、距離が極端に大きい場合類似度は0に近づく。


```
get_similairty('Lisa Rose','Jack Matthews')
0.3405424265831667
```


## レコメンド関数を実装する

レコメンド設計及び実装上の思想はコメントで書いている

```py:recomend.py
def get_recommend(person, top_N):
  
  totals = {} ; simSums = {} #推薦度スコアを入れるための箱を作っておく
  
  # 自分以外のユーザのリストを取得してFor文を回す
  # -> 各人との類似度、及び各人からの（まだ本人が見てない）映画の推薦スコアを計算するため
  list_others = dataset.keys() ; list_others.remove(person)

  for other in list_others:
    # 本人がまだ見たことが無い映画の集合を取得
    set_other = set(dataset[other]); set_person = set(dataset[person])
    set_new_movie = set_other.difference(set_person)

    # あるユーザと本人の類似度を計算(simは0~1の数字)
    sim = get_similairty(person, other)
    
    # (本人がまだ見たことがない)映画のリストでFor分を回す
    for item in set_new_movie:

      # "類似度 x レビュー点数" を推薦度のスコアとして、全ユーザで積算する
      totals.setdefault(item,0)
      totals[item] += dataset[other][item]*sim 

      # またユーザの類似度の積算値をとっておき、これで上記のスコアを除する
      simSums.setdefault(item,0)
      simSums[item] += sim

  rankings = [(total/simSums[item],item) for item,total in totals.items()]
  rankings.sort()
  rankings.reverse()

  return [i[1] for i in rankings][:top_N]
```

## 結果

```
get_recommend('Toby',2)

['The Night Listener', 'Lady in the Water']
```