Trust-Based Recommendation Systems: an Axiomatic Approachを読んだメモ
WWW 2008(http://www2008.org/)で発表された論文である，"Trust-Based Recommendation Systems: an Axiomatic Approach"を読んだメモです．この論文は公理に基づいて，Recommendationシステムの解析をしようというモノですが，いまいち分からなかったので，詳細は省きます^^; ですが，この論文中で紹介されていた，Personalizing PageRankが面白かったので，メモっておきます．
普通のPageRankでは，ネットワーク（有向グラフ）の繋がり全てを再帰的に走査し，どのノードが重要かをランクづけます．しかしながら，Personalizing PageRankでは，あるノードにとって，他のノードはどれぐらい重要かと言うことを，ランダムウォークを用いて求めます．
- ノードuを出発ノードとする
- uから出ているリンクを，ランダムに一つ選ぶ
- そのリンク先のノード（n1）に遷移する
- 確率αで，ノードn1に止まる
- 確率1-αで，同じように，ノードn1から出ているリンクを一つ選び，リンク先のノード（n2）に遷移する
- ただし，ノードn1がリンクを持たなかったら，出発ノード（u）に戻る
- 以上の操作を再帰的に繰り返す
以上の操作を行ったとき，ノードに止まる確率が，出発ノードuからみたランクとなります．
例えば，ある物事を友人に尋ねたとき，その友人が知っていれば，そこでメデタク終わりになりますが，その友人が知らない場合，その友人の友人を紹介してもらうかもしれません．その紹介された人が知っていれば，やはりそこで終わりですが，知らない場合，またその友人の友人の友人を紹介してもらうかもしれません．しかしながら，ある時，もう紹介する人が居ない，つまり外向きのリンクを持たないという場合があります．そのときは，もう一度自分の友人，始めに訪ねた友人以外から尋ね直すでしょう．すなわち，このPersonalizing PageRankはこのような動きをシミュレートしているといえます．
このPersonalizing PageRankを，mixi上の繋がりから求めるプログラムをPythonで作成してみました．
# -*- coding: utf-8 -*- import urllib, re, sys import time import traceback # json-py (json parser) # http://sourceforge.net/projects/json-py/ import json # BeautifulSoup (html parser) # http://www.crummy.com/software/BeautifulSoup/ from BeautifulSoup import BeautifulSoup class mixiOpener(urllib.FancyURLopener): def login(self, email, password): LOGIN_URL = "http://mixi.jp/login.pl" params = urllib.urlencode({ "email": email, "password": password, "next_url": "home.pl"}) r = self.open(LOGIN_URL, params) cookie = [] for c in r.headers.getheaders("Set-Cookie"): m = re.match("(.+=.+);.*", c) if m: cookie.append(m.groups()[0]) self.addheader("Cookie", ";".join(cookie)) self.addheader("User-Agent", "Mozilla/4.0 (compatible; MSIE 7.0; Windows NT 5.1)") r = self.open("http://mixi.jp/check.pl?n=home.pl") self.count = 0 return r.read() def getFriends(self, id, page): friend_url = "http://mixi.jp/list_friend.pl" params = urllib.urlencode({ "id" : id, "page": page}) sys.stderr.write('get %s, id = %d, page = %d\n' % (friend_url, id, page)) t = 5 p = re.compile(u'安定してサイトの運営をおこなう為') while True: r = self.open(friend_url, params) html = r.read() html = unicode(html, 'euc-jp', 'ignore') if len(p.findall(html)) == 0: break else: sys.stderr.write('sleep %s seconds\n' % (t)) sys.stderr.flush() time.sleep(t) t *= 2 return html def getFriendsSimple(self): friend_url = "http://mixi.jp/list_friend_simple.pl" sys.stderr.write('get %s\n' % (friend_url)) t = 5 p = re.compile(u'安定してサイトの運営をおこなう為') while True: r = self.open(friend_url) html = r.read() html = unicode(html, 'euc-jp', 'ignore') if len(p.findall(html)) == 0: break else: sys.stderr.write('sleep %s seconds\n' % (t)) sys.stderr.flush() time.sleep(t) t *= 2 return html class mixiRank: FRIENDS_LOG = 'friends.json' def __init__(self, mail, passwd): self.minProb = 0.001 self.mixi = mixiOpener() self.mixi.login(mail, passwd) fd = None try: fd = open(mixiRank.FRIENDS_LOG, 'r') self.nodes, self.id2name = json.read(fd.read()) except: self.nodes = {} self.id2name = {} if fd != None: fd.close() def getFriends(self, id): if self.nodes.has_key(id): return self.nodes[id] else: friends = self.getFriendsByMixi(id) self.nodes[id] = [f[0] for f in friends] for f in friends: self.id2name[f[0]] = f[1] return self.nodes[id] def getFriendsByMixi(self, id, page = 1): html = '' try: html = self.mixi.getFriends(id, page) soup1 = BeautifulSoup(html) div = soup1('div', {'class': 'pageList02'}) soup2 = BeautifulSoup(str(div[0])) a = soup2('a') if len(a) > 0: next = int(str(a[-1]).split('&')[0].split('=')[2]) else: next = 1 friends = [(int(friend.get('href').split('=')[1]), friend.get('title').encode('utf-8')) for friend in soup1('a', {'class': 'iconTitle'})] except: p1 = re.compile(u'ユーザは既に退会したか') leave = p1.findall(html) p2 = re.compile(u'マイミクシィの人数が1000人を超えて') limit = p2.findall(html) if len(leave) > 0 or len(limit) > 0: next = 1 friends = [] else: # id is login id html = self.mixi.getFriendsSimple() soup1 = BeautifulSoup(html) # TODO: get next page next = 1 wrapper = soup1('div', {'class': 'wrapper'}) p1 = re.compile('id.*?class') p2 = re.compile('<p>.*?\(') friends = [(int(p1.findall(str(div))[0][4:-7]), p2.findall(str(div))[0][3:-1]) for div in wrapper] if next > page: return friends + self.getFriendsByMixi(id, next) return friends def randomWalk(self, origin, prob, rank = 1.0, children = None): if children == None: children = self.getFriends(origin) p1 = rank * prob / len(children) p2 = rank / len(children) - p1 for n in children: if n == origin: r1 = 0 r2 = rank / len(children) else: r1 = p1 r2 = p2 self.result.setdefault(n, 0) self.result[n] += r1 friends = self.getFriends(n) num = len(friends) if num > 0 and r2 > self.minProb: self.randomWalk(origin, prob, r2, friends) elif num == 0 and r2 > self.minProb: self.randomWalk(origin, prob, r2, self.nodes[origin]) def getRank(self, id, p = 0.5): self.result = {} self.randomWalk(id, p) fd = None try: fd = open(mixiRank.FRIENDS_LOG, 'w') fd.write(json.write([self.nodes, self.id2name])) except: pass if fd != None: fd.close() return self.result if __name__ == '__main__': rank = mixiRank('mail@address.co.jp', 'passwd') result = rank.getRank(10000) for k in sorted(result, key = result.__getitem__, reverse = True): print k, rank.id2name[k], result[k]
mixiRankクラスのコンストラクタにログイン用のアドレス，パスワードをわたし，mixiRank.getRank()を，出発ノードとなるidの番号を渡して呼び出せば，結果が帰ってきます．結果は辞書であり，{id: rank}という形式となっています．ニックネームは，mixiRank.id2name[id]とすると得られます．
このプログラムの問題点は，ログイン用アカウントのマイミクが多い場合に，全員分のマイミクを取得できない可能性があることです．何故出来ないかというと，自分のマイミクがそんなに多くないため，マイミクが多い場合にどのようなhtmlが吐き出されるか確認できなかったからです．
htmlの解析にBeautifulSoupを利用しているので，動作させるには，BeautifulSoup.pyを同じディレクトリに置いておく必要があります．また，一度取得したマイミクリストは，json形式で保存するため，json.pyも必要となります．無ければ，保存できません．
なお，アルゴリズムを素直に実装すると，閉路をもつようなグラフの場合，自分自身にも止まってしまう可能性があるので，このプログラムでは，そのような場合はスルーするようにしてあります．
追記：json.pyでは，キーが文字列以外だとエラーが出るので，該当箇所（214-215行目）をコメントアウトする必要があります
