2008-10-05

Slope One Predictors for Online Rating-Based Collaborative Filteringを読んだメモ1 (http://d.hatena.ne.jp/ytakano/20081002/1222970856)の続きで，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.のメモです

slope oneは英語版のWikipediaにも多少載っていますが，英語が読めるなら，元の論文を参照した方がよいでしょう．(http://en.wikipedia.org/wiki/Slope_One)

slope oneでは，ユーザがつけたアイテム間の評価の平均偏差から，あるアイテムの評価値を予測します．いま，下記のような評価があったとします．

	A	B
user1	3	4
user2	4

ここでは，user2は，まだ，アイテムBに評価を下していません．しかし，user1がアイテムAに3，アイテムBに4の評価をつけており，その差は1であるので，user2はアイテムBに評価5をつけるであろうと予測できます．slope oneではこのようにして，ユーザがつけたアイテム間の評価を利用して，予測を行います．

ここで，あるアイテムjとiの平均偏差を以下のように定義します．
$\mathrm{div}_{j, i} = \sum_{u \in \mathbf{U}_{j, i}} \frac{R_{u, j} - R_{u, i}}{|\mathbf{U}_{j, i}|}$
ただし， $\mathbf{U}_{j, i}$ をアイテムjとi両方に評価を下したユーザの集合， $R_{u, i}$ をユーザuのアイテムiに対する評価とします．

こうすると，あるユーザuのアイテムjに対する評価は以下のようにして求まります．
$\mathbf{P}(\mathbf{R}_{u, j}) = \frac{1}{|\mathbf{R}_u|} \sum_{i \in \mathbf{R}_u} (\mathrm{dev}_{j, i} + u_i)$

ちなみに，上記の式はユーザuがアイテムjに評価を下していない場合，以下の式と等価になります．
$\mathbf{P}(\mathbf{R}_{u, j}) = \bar{u} + \frac{1}{|\mathbf{R}_u|} \sum_{i \in \mathbf{R}_u} \mathrm{dev}_{j, i}$

以上がなんの修飾も付かないslope one方式の説明でした．しかしながら，実際問題として，1ユーザにしか評価を下されていないアイテムと，1000ユーザに評価を下されたアイテムでは，その重みは違ってくると考えられます．そこで，weighted slope oneでは，普通のslope oneに，評価したユーザの数を重みとして掛け合わせます．weighted slope oneの予測関数は以下のようになります．
$\mathbf{P}^{\mathrm{w}} (\mathbf{R}_{u, j}) = \frac{\sum_{i \in \mathbf{R}_u} (\mathrm{dev}_{j, i} + u_i)|\mathbf{U}_{i, j}|}{|\mathbf{U}_{i, j}|}$

ここで少し，評価というモノを考えてみます．例えば，user1がアイテムAを悪い，アイテムBを良いと評価したとします．これまで説明したslope oneのアルゴリズムでは，これらを区別することなく予測していました．しかしながら，良い評価を下されたアイテムBから推測して，悪い評価を下されたアイテムAを推薦してしまうことも考えられます．これをさけるために，bi-polar slope oneでは，良い評価と悪い評価のアイテムを別々に区別して，予測を行います．

まず，bi-polar slope oneでは，良い評価と悪い評価に分けた平均偏差を求めます．良い評価，すなわち評価が平均得点より上であるアイテムの平均偏差の式は以下となります．
$\mathrm{dev}^{\mathrm{like}}_{j, i} = \sum_{u \in \mathbf{U}^{\mathrm{like}}_{j, i}} \frac{R_{u, j} - R_{u, i}}{\left|\mathbf{U}^{\mathrm{like}}_{j, i}\right|}$
ただし， $\mathbf{U}^{\mathrm{like}}_{j, i} = \{u \in \mathbf{U} | i, j \in R_u, R_{u, i} > \bar{R_u}, R_{u, j} > \bar{R_u}\}$ となります．
悪い評価の平均偏差である $\mathrm{dev}^{\mathrm{dislike}}_{j, i}$ も定義されますが，likeの場合と不等号が逆なだけなので詳細は省きます．

bi-polar slope oneでは上記の，良い評価と悪い評価に分けて求めた平均偏差を用いて予測を行います．その予測関数は以下のようになります．
$\mathbf{P}^{\mathrm{bp}} (R_{u, j}) = \frac{\sum_{i \in R^{\mathrm{like}}_{u}} \mathrm{dev}^{\mathrm{like}}_{j, i} \left|\mathbf{U}^{\mathrm{like}}_{j, i}\right| + \sum_{i \in R^{\mathrm{dislike}}_{u}} \mathrm{dev}^{\mathrm{dislike}}_{j, i} \left|\mathbf{U}^{\mathrm{dislike}}_{j, i}\right|}{\sum_{i \in R^{\mathrm{like}}_{u}} \left|\mathbf{U}^{\mathrm{like}}_{j, i}\right| + \sum_{i \in R^{\mathrm{dislike}}_{u}} \left|\mathbf{U}^{\mathrm{dislike}}_{j, i}\right|}$

正確さは，bi-polar slope one, weighted slope one, slope oneの順によくなり，全てのslope oneはitem basedよりも良くなったそうです．

これをpythonで実装してみると，以下のようになります．

#!/usr/bin/env python

# this program implements slope one predictors
#
# 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.

# slope one scheme
class slopeone:
    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 _avedev(self):
        self._dev = {}
        
        num = len(self._items)
        for i in range(num):
            for j in range(i + 1, num):
                item1 = self._items[i]
                item2 = self._items[j]

                r = 0.0
                n = 0
                for k in range(len(self._users)):
                    user = self._users[k]
                    if user.has_key(item1) and user.has_key(item2):
                        r += user[item2] - user[item1]
                        n += 1

                if n > 0:
                    r /= float(n)

                self._dev[(item1, item2)] = (r, n)
                self._dev[(item2, item1)] = (-r, n)

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

        if len(user) == 0:
            return 0

        r = 0.0
        for key in user.keys():
            dev = self._dev[(key, item)][0]
            r += dev + user[key]

        return r / len(user)

    def _doFirst(self, user):
        pass

    def recommends(self, user):
        self._doFirst(user)

        self._ave()
        self._avedev()

        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


# wheighted slope one scheme
class wslopeone(slopeone):
    def _predict(self, user, item):
        if user.has_key(item):
            return user[item]

        if len(user) == 0:
            return 0

        r1 = 0.0
        r2 = 0.0
        for key in user.keys():
            dev, n = self._dev[(key, item)]
            r1 += (dev + user[key]) * n
            r2 += n

        try:
            return r1 / r2
        except:
            return 0

# bi-polar slope one scheme
class bpslopeone(slopeone):
    def __init__(self, users, items):
        self._users = users
        self._items = items

    def _avedev2(self, item1, item2, cmpf):
        r = 0.0
        n = 0
        for i in range(len(self._users)):
            user = self._users[i]
            if (user.has_key(item1) and user.has_key(item2) and
                cmpf(user[item1], self._ave[i]) > 0 and
                cmpf(user[item2], self._ave[i]) > 0):
                r += user[item2] - user[item1]
                n += 1

        if n > 0:
            r /= float(n)

        return r, n

    def _avedev(self):
        self._devLike = {}
        self._devDislike = {}
        
        num = len(self._items)
        for i in range(num):
            for j in range(i + 1, num):
                item1 = self._items[i]
                item2 = self._items[j]

                r1, n1 = self._avedev2(item1, item2, lambda x, y: cmp(x, y))
                r2, n2 = self._avedev2(item1, item2, lambda x, y: cmp(y, x))

                self._devLike[(item1, item2)] = (r1, n1)
                self._devLike[(item2, item1)] = (-r1, n1)
                self._devDislike[(item1, item2)] = (r2, n2)
                self._devDislike[(item2, item1)] = (-r2, n2)

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

        if len(user) == 0:
            return 0

        r1 = 0.0
        n1 = 0.0
        r2 = 0.0
        n2 = 0.0
        for key in user.keys():
            if user[key] > self._uave:
                dev, n = self._devLike[(key, item)]
                r1 += (dev + user[key]) * n
                n1 += n
            else:
                dev, n = self._devDislike[(key, item)]
                r2 += (dev + user[key]) * n
                n2 += n

        try:
            return (r1 + r2) / (n1 + n2)
        except:
            return 0

    def _doFirst(self, user):
        self._uave = sum(user.values()) / float(len(user))


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']

s = slopeone(users, items)
print s.recommends(users[3])

ws = wslopeone(users, items)
print ws.recommends(users[3])

bps = bpslopeone(users, items)
print bps.recommends(users[3])

# output is
# [('D', 4.166666666666667), ('C', 2.0), ('A', 1.8333333333333333)]
# [('D', 4.25), ('C', 2.0), ('A', 1.8333333333333333)]
# [('D', 5.0), ('A', 0.0), ('C', 0)]

データが少ない状況だと，bi-polar slope oneはイマイチのようです．

NO!と言えるようになりたい

Slope One Predictors in Python