Python でレコメンデーションを実装する

今年の後半くらいから、めっきり更新頻度が低下していますが、ひさしぶりの更新です。

[前回](http://qiita.com/ynakayama/items/07072060c99edf37f22d)の記事は 3 ヶ月以上前だわ、ストック数の多かった記事があらかた 1 年以上前と表示されるわ、 Qiita の記法 (≒ Markdown) を忘れかけてるわ、いろいろ悲惨です......。

今回は協調フィルタリング (レコメンデーション) を Python で書いてみようという話です。

と、言っても今年の一月に [Ruby で書いたという記事](http://qiita.com/ynakayama/items/ceb3f6408231ea3d230c)がありますので、こちらも併せて参照してください。

## 元データ

[前の記事](http://qiita.com/ynakayama/items/ceb3f6408231ea3d230c)と同じデータを利用します。

ある会社 A 社の社内食堂でランチをした人にここ 10 日間ほどの感想を 5.0 を満点として採点してもらいました。

それぞれのメニューに対する評点は次の通りでした。なお一度も食べなかったメニューは -- となっています。

|名前|カレー|ラーメン|チャーハン|寿司|牛丼|うどん|
|:--|:--|:--|:--|:--|:--|:--|
|山田さん|2.5|3.5|3.0|3.5|2.5|3.0|
|田中さん|3.0|3.5|1.5|5.0|3.0|3.5|
|佐藤さん|2.5|3.0|--|3.5|--|4.0|
|中村さん|--|3.5|3.0|4.0|2.5|4.5|
|川村さん|3.0|4.0|2.0|3.0|2.0|3.0|
|鈴木さん|3.0|4.0|--|5.0|3.5|3.0|
|下林さん|--|4.5|--|4.0|1.0|--|

みな味の好みがバラバラで、同じメニューでも人によって採点が高かったり低かったりしているようです。

## 元データの作成

まずは Python で扱える形でデータを用意し recommendation_data.py とします。

```py3
dataset = {
    '山田': {'カレー': 2.5,
           'ラーメン': 3.5,
           'チャーハン': 3.0,
           '寿司': 3.5,
           '牛丼': 2.5,
           'うどん': 3.0},
    '田中': {'カレー': 3.0,
           'ラーメン': 3.5,
           'チャーハン': 1.5,
           '寿司': 5.0,
           'うどん': 3.0,
           '牛丼': 3.5},
    '佐藤': {'カレー': 2.5,
           'ラーメン': 3.0,
           '寿司': 3.5,
           'うどん': 4.0},
    '中村': {'ラーメン': 3.5,
           'チャーハン': 3.0,
           'うどん': 4.5,
           '寿司': 4.0,
           '牛丼': 2.5},
    '川村': {'カレー': 3.0,
           'ラーメン': 4.0,
           'チャーハン': 2.0,
           '寿司': 3.0,
           'うどん': 3.0,
           '牛丼': 2.0},
    '鈴木': {'カレー': 3.0,
           'ラーメン': 4.0,
           'うどん': 3.0,
           '寿司': 5.0,
           '牛丼': 3.5},
    '下林': {'ラーメン': 4.5,
           '牛丼': 1.0,
           '寿司': 4.0}}
```

## データのハンドリング

上の recommendation_data.py からデータを読み出して Python で表示してみます。

```py3
from recommendation_data import dataset
from math import sqrt

print(("山田さんのカレーの評価 : {}".format(
    dataset['山田']['カレー'])))
print(("山田さんのうどんの評価 : {}\n".format(
    dataset['山田']['うどん'])))
print(("佐藤さんのカレーの評価: {}".format(
    dataset['佐藤']['カレー'])))
print(("佐藤さんのうどんの評価: {}\n".format(
    dataset['佐藤']['うどん'])))

print("鈴木さんのレーティング: {}\n".format((dataset['鈴木'])))

#=> 山田さんのカレーの評価 : 2.5
#=> 山田さんのうどんの評価 : 3.0

#=> 佐藤さんのカレーの評価: 2.5
#=> 佐藤さんのうどんの評価: 4.0

#=> 鈴木さんのレーティング: {'寿司': 5.0, 'うどん': 3.0, 'カレー': 3.0, '牛丼': 3.5, 'ラーメン': 4.0}
```

## 協調フィルタリングの実装

類似性尺度にはいろいろあります。以下はユークリッド距離を求めるコードです。

```py3
def similarity_score(person1, person2):
    # 戻り値は person1 と person2 のユークリッド距離

    both_viewed = {}  # 双方に共通のアイテムを取得

    for item in dataset[person1]:
        if item in dataset[person2]:
            both_viewed[item] = 1

    # 共通のアイテムを持っていなければ 0 を返す
    if len(both_viewed) == 0:
        return 0

    # ユークリッド距離の計算
    sum_of_eclidean_distance = []

    for item in dataset[person1]:
        if item in dataset[person2]:
            sum_of_eclidean_distance.append(
                pow(dataset[person1][item] - dataset[person2][item], 2))
    total_of_eclidean_distance = sum(sum_of_eclidean_distance)

    return 1 / (1 + sqrt(total_of_eclidean_distance))

print("山田さんと鈴木さんの類似度 (ユークリッド距離)",
      similarity_score('山田', '鈴木'))

#=> 山田さんと鈴木さんの類似度 (ユークリッド距離) 0.3405424265831667
```

以下はピアソン相関係数を求めるコードです。データが正規化されていないような状況でユークリッド距離よりも良い結果を得られることが多いとされています。

```py3
def pearson_correlation(person1, person2):

    # 両方のアイテムを取得
    both_rated = {}
    for item in dataset[person1]:
        if item in dataset[person2]:
            both_rated[item] = 1

    number_of_ratings = len(both_rated)

    # 共通のアイテムがあるかチェック、無ければ 0 を返す
    if number_of_ratings == 0:
        return 0

    # 各ユーザーごとのすべての好みを追加
    person1_preferences_sum = sum(
        [dataset[person1][item] for item in both_rated])
    person2_preferences_sum = sum(
        [dataset[person2][item] for item in both_rated])

    # 各ユーザーの好みの値の二乗を計算
    person1_square_preferences_sum = sum(
        [pow(dataset[person1][item], 2) for item in both_rated])
    person2_square_preferences_sum = sum(
        [pow(dataset[person2][item], 2) for item in both_rated])

    # アイテムごとのユーザー同士のレーティングを算出して合計
    product_sum_of_both_users = sum(
        [dataset[person1][item] * dataset[person2][item] for item in both_rated])

    # ピアソンスコアの計算
    numerator_value = product_sum_of_both_users - \
        (person1_preferences_sum * person2_preferences_sum / number_of_ratings)
    denominator_value = sqrt((person1_square_preferences_sum - pow(person1_preferences_sum, 2) / number_of_ratings) * (
        person2_square_preferences_sum - pow(person2_preferences_sum, 2) / number_of_ratings))
    if denominator_value == 0:
        return 0
    else:
        r = numerator_value / denominator_value
        return r

print("山田さんと田中さんの類似度 (ピアソン相関係数)",
      (pearson_correlation('山田', '田中')))

#=> 山田さんと田中さんの類似度 (ピアソン相関係数) 0.39605901719066977
```

## 類似度を算出する

山田さんに食の好みが似ている人トップ 3 を求めます。

```py3
def most_similar_users(person, number_of_users):
    # 似たユーザーとその類似度を返す
    scores = [(pearson_correlation(person, other_person), other_person)
              for other_person in dataset if other_person != person]

    # 最高の類似度の人物が最初になるようにソートする
    scores.sort()
    scores.reverse()
    return scores[0:number_of_users]

print("山田さんに似た人ベスト 3",
      most_similar_users('山田', 3))

#=> 山田さんに似た人ベスト 3 [(0.9912407071619299, '下林'), (0.7470178808339965, '鈴木'), (0.5940885257860044, '川村')]
```

## おすすめのメニューを探す

最後に、下林さんにおすすめのメニューを推薦してみます。

```py3
def user_reommendations(person):

    # 他のユーザーの加重平均によるランキングから推薦を求める
    totals = {}
    simSums = {}
    for other in dataset:
        # 自分自身は比較しない
        if other == person:
            continue
        sim = pearson_correlation(person, other)

        # ゼロ以下のスコアは無視する
        if sim <= 0:
            continue
        for item in dataset[other]:

            # まだ所持していないアイテムのスコア
            if item not in dataset[person] or dataset[person][item] == 0:

                # Similrity * スコア
                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 list(totals.items())]
    rankings.sort()
    rankings.reverse()
    # 推薦アイテムを返す
    recommendataions_list = [
        recommend_item for score, recommend_item in rankings]
    return recommendataions_list

print("下林さんにおすすめのメニュー",
      user_reommendations('下林'))
#=> 下林さんにおすすめのメニュー ['うどん', 'カレー', 'チャーハン']
```

## さいごに

今回の記事のソースコードは[こちら](https://github.com/ynakayama/sandbox/blob/master/python/machine-learning/recommendation/collaborative_filter.py)です。

協調フィルタリングには大きく分けてアイテムベース、ユーザーベースという方法があります。具体的なコードを含めた解説としては「[集合知プログラミング](https://www.oreilly.co.jp/books/9784873113647/)」の第二章を読むと良いでしょう。今回の記事もこれにならっています。

推薦システムのアルゴリズムについて体系的に知りたい場合は、神嶌敏弘氏の執筆した[人工知能学会誌](http://ci.nii.ac.jp/ncid/AN10067140)の以下の論文が個人的にはわかりやすくてオススメです。

```
神嶌 敏弘: 推薦システムのアルゴリズム (1), 人工知能学会誌, vol.22, no.6, pp.826-837, 2007.
神嶌 敏弘: 推薦システムのアルゴリズム (2), 人工知能学会誌, vol.23, no.1, pp.89-103, 2008.
神嶌 敏弘: 推薦システムのアルゴリズム (3), 人工知能学会誌, vol.23, no.2, pp.248-263, 2008.
```

論文なんか読む環境が無いよという人は、著者サイトの[推薦システムの解説資料](http://www.kamishima.net/jp/kaisetsu/)がほとんど同じ内容なのでこれを参照すると良いかと思います。

今回の記事を執筆するにあたり、上記論文と[集合知プログラミング](https://www.oreilly.co.jp/books/9784873113647/)と以下の記事を参考にしています。
collaborative filtering recommendation engine implementation in python
http://dataaspirant.com/2015/05/25/collaborative-filtering-recommendation-engine-implementation-in-python/