Item based collaborative filtering - NO!と言えるようになりたい

D. Lemire and A. Maclachlan, "Slope One Predictors for Online Rating-Based Collaborative Filtering", In SIAM Data Mining (SDM'05), Newport Beach, California, April 21-23, 2005.を読んだメモです．

この論文では，よりよいrecommendationアルゴリズムとして"slope one"という方式を提案していますが，その方式の説明は次回行うことにして，今回はrelated workで挙げられていた，B. Sarwar, G. Karypis, J. Konstan and J. Riedl, "Item-based collaborative filtering recommendation algorithms," in Proceedings of the Tenth International Conference on the World Wide Web (WWW 10), pp. 285-295, 2001.の手法について説明します．(http://www10.org/cdrom/papers/519/)

item-basedのrecommendationは，オライリーから出ている"Programing Collective Inteligence"にも載っていますが，こちらの方が多少厳密です．ちなみにこの本は最近，日本語版が発売されたらしいです．

item-basedの方式では，アイテム間の相関係数を計算し，その相関係数を元にrecommendを行います．例えば，あるアイテムAとBの取得したポイントは以下のようになったとします．

	A	B
user1	4	3
user2	5	3
user3	3	2

このとき，相関係数は
$\frac{\sum_{u \in \bf{U}} (R_{u, i} - \bar{R_u}) (R_{u, j} - \bar{R_u})}{\sqrt{\sum_{u \in \bf{U}} (R_{u, i} - \bar{R_u})^2} \sqrt{\sum_{u \in \bf{U}}(R_{u, j} - \bar{R_u})^2}}$
となります，ここで $\bf{U}$ はユーザの集合で， $R_{u,i}$ はユーザuがアイテムiに下した評価です．この例の場合，相関係数は-1.0となります．ピアソンの相関係数と似ていますが，平均値が，アイテムの平均ではなく，ユーザの平均であるという点において違いがあります．

さらに，Aを独立変数，Bを従属変数として，回帰直線をもとめます．回帰直線とは，
$y = ax + b$
で表されるような一次式であり，近似直線でもあります．ここで，回帰係数a, bは最小二乗法により求めることが出来て，
$a = \frac{\sum_{u \in \bf{U}} (R_{u, A} - \bar{A})(R_{u, B} - \bar{B})}{\sum_{u \in \bf{U}} (R_{u, A} - \bar{A})^2}$
$b = \bar{B} - a \bar{A}$
となります．上の例の場合，回帰係数はa = 0.5, b = 0.66となります．

今，別のuser4がAに対して，評価3をつけたとします．このとき，user4がBに対して，どのような評価を下すかを，item-basedの方法で予測してみると．
$\frac{|-1.0| \times (3 \times 0.5 + 0.66)}{|-1.0|} = 2.166$
となり，user4はBに対して，評価2.166をつけるであろうと予測できます．

item-basedでは，このようにして，相関係数と回帰分析を用いて，ユーザの評価を予測します．ユーザuのアイテムiに対する評価の予測値は以下の式で求められます．
$P(R_{u, i}) = \frac{\sum_{j \in R_u} |\mathrm{sim}_{i, j}| (\alpha_{i, j} R_{u, j} + \beta_{i, j})}{\sum_{j \in R_u} |\mathrm{sim}_{i, j}|}$
ここで，iは予測するアイテム， $\mathrm{sim}_{i, j}$ は上記で説明したとおり，アイテムiとjの相関係数を表します．また， $\alpha_{i, j}$ と $\beta_{i, j}$ は，アイテムjの評価を独立変数，iの評価を従属変数としたときの回帰係数です．

あとは，ユーザuが評価していないアイテムに関して評価値の予測を行い，予測値の高いモノをrecommendすれば，recommendationができます．

これをPythonで書いてみたら，以下のようになります．

#!/usr/bin/env python

# this program implements item based recommender system
#
# B. Sarwar, G. Karypis, J. Konstan and J. Riedl,
# "Item-based collaborative filtering recommendation algorithms," in
# Proceedings of the Tenth International Conference on the World Wide Web
# (WWW 10), pp. 285-295, 2001.
import math

def regress(data):
    xm = 0.0
    ym = 0.0
    sx2 = 0.0
    sxy = 0.0
    i = 0

    for x, y in data:
        i += 1
        x -= xm
        xm += x / i
        sx2 += (i - 1) * x * x / i
        y -= ym
        ym += y / i
        sxy += (i - 1) * x * y / i

    try:
        a = sxy / sx2
    except:
        a = 1.0

    return a, ym - a * xm


class recommender:
    def __init__(self, users, items):
        self._users = users
        self._items = items

    def _ave(self):
        self._ave = {}
        for i in range(len(self._users)):
            user = self._users[i]
            self._ave[i] = sum(user.values()) / float(len(user))

    def _corr(self):
        self._correlations = {}
        self._regressions = {}
        ave = {}

        num = len(self._items)
        for i in range(num):
            for j in range(i + 1, num):
                item1 = self._items[i]
                item2 = self._items[j]

                if item1 > item2:
                    tmp = item1
                    item1 = item2
                    item2 = tmp

                r1 = 0.0
                r2 = 0.0
                r3 = 0.0
                for i in range(len(self._users)):
                    user = self._users[i]
                    if user.has_key(item1) and user.has_key(item2):
                        r1 += ((user[item1] - self._ave[i]) *
                               (user[item2] - self._ave[i]))

                        tmp = user[item1] - self._ave[i]
                        r2 += tmp * tmp

                        tmp = user[item2] - self._ave[i]
                        r3 += tmp * tmp

                try:
                    p = r1 / (math.sqrt(r2) * math.sqrt(r3))
                except:
                    p = 0.0

                self._correlations[(item1, item2)] = p

    def _reg(self):
        num = len(self._items)
        for i in range(num):
            for j in range(num):
                if i != j:
                    item1 = self._items[i]
                    item2 = self._items[j]
                    data = [(x[item1], x[item2]) for x in self._users
                            if x.has_key(item1) and x.has_key(item2)]
                    a, b = regress(data)
                    self._regressions[(item1, item2)] = (a, b)


    def _predict(self, user, item):
        if user.has_key(item):
            return user[item]

        denomi = sum([abs(self._correlations[k])
                      for k in self._correlations.keys()
                      if ((k[0] == item and user.has_key(k[1])) or
                          (k[1] == item and user.has_key(k[0])))])

        numerator = 0.0
        for k in self._correlations.keys():
            if ((k[0] == item and user.has_key(k[1])) or
                (k[1] == item and user.has_key(k[0]))):
                if k[0] == item:
                    uitem = k[1]
                    key = (k[1], k[0])
                else:
                    uitem = k[0]
                    key = k

                p = (user[uitem] * self._regressions[key][0] +
                     self._regressions[key][1]) * abs(self._correlations[k])
                numerator += p
        try:
            return numerator / denomi
        except:
            return 0.0

    def recommends(self, user):
        self._ave()
        self._corr()
        self._reg()

        items = [item for item in self._items if not user.has_key(item)]

        result = []
        for item in items:
            p = self._predict(user, item)
            result.append((item, p))

        result.sort(lambda x, y: cmp(y[1], x[1]))
        return result

users = [{'A': 4, 'B': 5, 'C': 2, 'D': 4,         'F': 5}, # user 0
         {'A': 2,         'C': 3, 'D': 4, 'E': 3        }, # user 1
         {'A': 1, 'B': 4,         'D': 5, 'E': 3, 'F': 4}, # user 2
         {        'B': 5,                 'E': 2, 'F': 4}, # user 3
         {        'B': 3, 'C': 1, 'D': 3,         'F': 3}] # user 4

items = ['A', 'B', 'C', 'D', 'E', 'F']

r = recommender(users, items)
print r.recommends(users[3])

# output is
# [('A', 4.0), ('D', 3.5), ('C', 2.0)]

ちなみに，回帰係数は1パスで求めることができるそうで，回帰係数を求める部分は下記URLから拝借しました．

Algorithms with Python番外編：統計学の基礎知識 [3] (http://www.geocities.jp/m_hiroi/light/pystat03.html)

その2(http://d.hatena.ne.jp/ytakano/20081005/1223201692)