協調フィルタリング とは

協調フィルタリング には様々なやり方があるが、
一般的には大人数の集団の中からレコメンド対象と好みが似た集団を見つけ出し、
その集団の行動リストの中から適切な行動を推薦するというものである。

嗜好データ

嗜好データを構造化するにはいろいろな方法があるが、
簡単にするには商品を購入したを1、していない0にしたり、
見た映画には1から5の評価を付けさせ、見ていない映画には0にしたりするなどがある。

ECサイト		映画
商品を購入した	1	映画を見た	1.0 – 5.0
商品を購入していない	0	映画を見ていない	0

人とその人の映画の評価（１．０－５．０の範囲）をpythonのディクショナリでハードコーディングしたものは
このようになる。 これを利用するには以下の様なコードを書けば良い。

#!/usr/bin/python

from database import critics

# Read evaluation
print critics['Lisa Rose']['Lady in the Water']

# Set value
critics['Toby']['Snakes on a Plane'] = 5.0
print critics['Toby']

---

嗜好の似ている集団を検索する

リコメンド対象とそれ以外の人がどれだけ似ているかを調べるためには類似性スコアを算出するとよい。
このスコアを算出するには様々な方法がある。
ここでは、以下の２つの方法を説明する。

• ユークリッド距離
• ピアソン相関

ユークリッド距離

お互いに同じ２つの映画（ターミネーターとスターウォーズ）を見て評価をしている場合、
以下のように２次元グラフ上にプロットしてその距離を計算する方法である。
この距離が短いほうが２人の好みが似ていると考える。

３つ以上ある場合はz,wなど変数を増やして同様の計算式を使用すればよい。 先ほどのデータを利用して任意の２人の評価者の好みを計算するプログラムは以下のようになる。

#!/usr/bin/python

from database import critics
from math import sqrt

#
# Calculate similarity between person1, person2
# using euclid distance
#
def sim_distance(prefs, person1, person2):
    # Get the list item evaluated by twosome
    items = [1 for item in prefs[person1] if item in prefs[person2]]

    # Nothing items
    if len(items) == 0: return 0

    # Calculate euclid distance
    distance = sum([pow(prefs[person1][item]-prefs[person2][item],2)
        for item in prefs[person1] if item in prefs[person2]])

    return 1.0/(1.0 + distance)

# main
if __name__ == '__main__':
    print sim_distance(critics, 'Lisa Rose', 'Gene Seymour')

ピアソン相関

ユークリッド距離はデータの大きさが整理されていないときにはうまく動作しない。
例えば、人同士の類似性スコアを計算しようとしてその人達の身長と年齢をデータとして比べようとすると、
身長のほうが年齢よりも値が大きくなるため身長の差が年齢の差よりも結果に大きな影響を与えてしまう。 ピアソン相関係数を用いるとその問題はなくなる。
ピアソン相関では２つのデータ群の関係性を見る。
片一方のデータ群が変化した時にもう一方のデータ群も同じように変化をするならば相関が高い、すなわち類似していると見るのである。

これを計算するには次のように考える。
データの変化をよく表す直線と平均の差とデータと平均の差の割合を計算すると。
図で言うと、緑色の線がデータの変化を良く表す直線と平均の差で、
青色の線がデータと平均の差である。
ちなみに、各データは映画の評価、x,y軸が評価者になる。

各データが青色の直線（データの変化をよく表す直線）上に乗っていれば、
両方の評価者の評価は近く、直線よりも遠ければ評価も遠いことが感覚的にわかるだろう。 各データが青色の直線上に乗っているとは、
２つの差の割合を計算することで計算できる。書くデータが直線上に完全に乗っていれば、
両方の差の値は同じになるはずであるから、1となる。
完全に離れてしまえば0となる。

２つの差の割合であるから以下の計算式で計算できる。
回帰直線の部分を計算して計算式に代入することで以下の計算式の右端の式が得られる。
回帰直線の導き方は話題が異なるので省略する。
ソースコードは以下のようになる。

#!/usr/bin/python

from database import critics
from math import sqrt

#
# Calculate pearson correlation between p1 and p2
#
def sim_pearson(prefs,p1,p2):
    # Get item list
    items = {}
    for item in prefs[p1]:
        if item in prefs[p2]:
            items[item]=1
    n = len(items)

    # return 0 when items are nothing
    if n == 0: return 0

    # calculate p's variance
    ave1 = sum([prefs[p1][it] for it in items])/float(n)
    var1 = sqrt(sum([pow(prefs[p1][it]-ave1,2) for it in items]))

    ave2 = sum([prefs[p2][it] for it in items])/float(n)
    var2 = sqrt(sum([pow(prefs[p2][it]-ave1,2) for it in items]))

    # calculate covariance
    cov = sum([(prefs[p1][it]-ave1)*(prefs[p2][it]-ave2) for it in items])

    # calculate similarity
    if var1*var2 == 0: return 0
    return cov/(var1*var2)

if __name__ == '__main__':
    print sim_pearson(critics, 'Lisa Rose', 'Gene Seymour')

嗜好の似た評価者によるアイテムの推薦

最も似た嗜好を持つ評価者を特定し、
その人が高い評価を与えている映画を推薦するのが最も簡単な方法であるが、
その人がリコメンド対象が好きな映画を見ていないために精度の高い推薦ができない可能性がある。 それを解決するために嗜好の近さを重みとして、それを評価値に掛けた値を合計することで精度を高めることができる。
ソースコードにすると以下のようになる。

#!/usr/bin/python

from database import critics
from pearson import sim_pearson
from euclid import sim_distance

#
# Calculate weighed mean, and recommend
#
def getRecommendations(prefs,person,similarity=sim_pearson):
    totals = {}
    simSums = {}
    for other in prefs:
        if other == person: continue
        sim = similarity(prefs, person, other)

        # ignore similarity is less than 0
        if sim <= 0: continue

        for item in prefs[other]:
            if item not in prefs[person] or prefs[person][item] == 0:
                totals.setdefault(item,0)
                totals[item] += prefs[other][item] * sim
                # similarity
                simSums.setdefault(item,0)
                simSums[item] += sim

    # make normalized list
    rankings = [(total/simSums[item],item) for item,total in totals.items()]

    rankings.sort()
    rankings.reverse()
    return rankings

if __name__ == '__main__':
    print getRecommendations(critics, 'Toby')

最後の方でtotal/simSums[item]とあるが、
これはたくさんの評価者に見られている映画の評価値が高くなってしまうという問題を防ぐために正規化をしている。

似ているアイテムを出す

criticsのキーと値を入れ替えると、
どの映画が誰に評価されているかというデータになる。
この状態で今までやってきた関数を動かすと、アイテム同士の近さを見ることができる。
criticsを入れ替えてアイテム同士の近さを出力するプログラムを書いてみる。
すると以下のようになる。

#!/usr/bin/python

from database import critics
from pearson import sim_pearson
from euclid import sim_distance

#
# Transform key and value
#
def transformPrefs(prefs):
    result = {}
    for person in prefs:
        for item in prefs[person]:
            result.setdefault(item,{})
            result[item][person]=prefs[person][item]

    return result

#
# Make ranking
#
def topMatches(prefs,person,n=5,similarity=sim_pearson):
    scores=[(similarity(prefs,person,other),other) for other in prefs if other!=person]
    scores.sort()
    scores.reverse()
    return scores[0:n]

if __name__ == '__main__':
    movies = transformPrefs(critics)
    print topMatches(movies, 'Superman Returns')

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

これまでのユーザベースの推薦とは異なり、
ここではアイテムベースのフィルタリングについて説明する。
アイテムベースのフィルタリングでは、
アイテム同士の類似度は人同士の類似度ほど頻繁に変化しないという性質を利用して、
計算の頻度を下げ精度を上げることができる。 アイテムベースフィルタリングを使用するには以下のような手順で計算すればよい。

1. アイテム同士の類似度を値として持つデータセットを作成する（ユーザが増えて安定してきたら計算回数を減らすことができる）
2. リコメンド対象が評価したアイテムリストを作成する
3. 似ているアイテムを探し、類似度で重み付けする

これをプログラムで実現すると以下のようになる。

#!/usr/bin/python

from database import critics
from itemsim import transformPrefs,topMatches
from euclid import sim_distance

#
# calculate similarity between item and item
#
def calculateSimilarItems(prefs,n=10):
    result = {}

    itemPrefs = transformPrefs(prefs)
    c = 0
    for item in itemPrefs:
        c += 1
        if c % 100 == 0: print "%d / %d" % (c,len(itemPrefs))
        scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
        result[item]=scores
    return result

#
# Recommend on a item bases
#
def getRecommendedItems(prefs, itemMatch, user):
    userRatings = prefs[user]
    scores = {}
    totalSim = {}

    for (item,rating) in userRatings.items():
        for (similarity,item2) in itemMatch[item]:
            if item2 in userRatings: continue

            scores.setdefault(item2,0)
            scores[item2] += similarity*rating

            totalSim.setdefault(item2,0)
            totalSim[item2] += similarity

    rankings = [(score/totalSim[item],item) for item,score in scores.items()]
    rankings.sort()
    rankings.reverse()
    return rankings

if __name__ == '__main__':
    itemsim = calculateSimilarItems(critics)
    print getRecommendedItems(critics,itemsim,'Toby')

アイテムベースのフィルタリングは、一般的に、疎なデータセットに対して
ユーザベースフィルタリングより性能が優れていることが知られている。

リファレンス

この記事は以下の本を元に知人に解説するために説明の仕方を変えて記述したものである。
なお、１章と２章は公開されている。 集合知プログラミング1,2章

【楽天ブックスならいつでも送料無料】集合知プログラミング [ トビ-・セガラン ] 価格：3,672円（税込、送料込）