唯物是真 @Scaled_Wurm

プログラミング(主にPython2.7)とか機械学習とか

AOJの問題を推薦――協調フィルタリングを試してみた

機械学習 競技プログラミング python

AIZU ONLINE JUDGE(AOJ)という競技プログラミングの問題を公開しているサイトがある。

screenshot
1年以上前にAOJを少しだけやっていた頃に、AOJの問題を推薦するスクリプトを書いたものの、特に公開も使用もせずに放置していたのでブログ記事にして供養(？)しておく。

AOJにはたくさんの問題があって、どれを解くべきかよくわからないので、とりあえず推薦システムを作ってみた(モチベーションがおかしい
AOJではAPIが公開されていて、各ユーザーがどの問題を解いているかなどの色々な情報が得られる

デモだけ試したい方はこちら

処理の概要

  1. AOJのAPIを使って各ユーザーがどの問題を解いているかというデータを集める。
  2. 集めたデータを元に協調フィルタリングを用いて推薦する。

データの取得

APIの結果はXMLで返される。
ほとんど問題を解いていないユーザーを除去するために、一定以上の問題数を解いているユーザーのリストを取得した。

得られたリストを元にそれぞれのユーザーが解いている問題のリストを取得する

以下にクロールした時のコードを貼っておく。
引数に与えた数値よりもユーザーの解いた問題数が少ない場合は取ってこない。
大事ないように、ユーザーごとに1、2秒のスリープを入れてからAPIを叩いている。

import xml.etree.ElementTree
import urllib2
import sys
import time
import random

argc = len(sys.argv)

if argc != 2:
    sys.exit('Error: Invalid argument')
try:
    min_user = int(sys.argv[1])
except:
    sys.exit('Error: Invalid argument')

res = urllib2.urlopen('http://judge.u-aizu.ac.jp/onlinejudge/webservice/user_list?solved_min={}'.format(min_user))
if res.code != 200:
    sys.exit('Error: Invalid response')

user_tree = xml.etree.ElementTree.fromstring(unicode(res.read(), errors = 'ignore'))

for user in user_tree.iterfind('user'):
    user_id = user.findtext('id').replace(u'\n', u'')
    print user.findtext('name').replace(u'\n', u'').encode('utf-8', errors = 'ignore')
    print user_id.encode('utf-8', errors = 'ignore')
    
    res = urllib2.urlopen('http://judge.u-aizu.ac.jp/onlinejudge/webservice/solved_record?user_id={}'.format(user_id))
    if res.code != 200:
        sys.exit('Error: Invalid response')
    
    solved_tree = xml.etree.ElementTree.fromstring(unicode(res.read(), errors = 'ignore'))
    for solved in solved_tree:
        print solved.findtext('problem_id').replace(u'\n', u'').encode('utf-8', errors = 'ignore'),
    print
    
    time.sleep(random.uniform(1, 2))

協調フィルタリング

あるユーザーに対して推薦をするときに、そのユーザーに似た別のユーザーの情報を利用して推薦を行うという手法である。
今回のタスクでは、どの問題を解いているかを元に推薦対象のユーザーと似ているユーザーを何人か求めて、得られたユーザーが共通して解いている問題の中から推薦対象のユーザーが解いていないものを推薦する。
ただし推薦対象のユーザーが解いた問題の単純な部分集合であるユーザーは似ているユーザーを選ぶときに取り除いた

協調フィルタリングの詳細を知りたい方は以下のPDFがおすすめです。

ユーザーの類似度

ユーザーごとにそれぞれの問題を解いたかどうかのベクトルを作成し、ユーザーどうしのコサイン類似度を求める。

ただし、ベクトルの要素を単純に問題を解いたかどうかの二値のベクトルにすると簡単過ぎる問題が推薦されてきてしまうという欠点がある

人気バイアス

推薦システムにはみんなに共通して人気があるアイテムを推薦しやすい傾向がある。

「村上春樹さんの著作は、日本では老若男女が読んでいる。したがって、どの本を見ても村上さんの本が推薦されてしまう事態になった。『ONE PIECE』を読んでる人にも『ハリー・ポッター』を読んでる人にも『1Q84』が推薦されてしまう」

楽天「ネット企業にとって“データを分析して活用すること”がビジネスのコア」～レコメンドの「村上春樹問題」からオープンソースを使ったデータ解析まで～ 【モバイル＆ソーシャルWEEK2012レポート】 （1/2）：MarkeZine（マーケジン）

今回のタスクの場合、みんなが共通して解いている問題＝簡単過ぎる問題を推薦してしまう

tf-idf

みんなが共通して解いている問題＝簡単過ぎる問題が推薦されるのを抑制するため、自然言語処理で単語ベクトルを使うときにtf-idfという名前で知られている方法と同様の処理を行った。

tf-idfでは単語がいくつの文書に出現したかという文書頻度を求めて、文書内での単語の相対頻度を文書頻度の対数で割っている。
なぜ文書頻度で割るかというと、多くの文書に共通して出現する単語はあまり特徴的でないことが多いからである。
今回のタスクではいくつのユーザーに出現したかというユーザー頻度を求めて、問題の相対頻度を単純にユーザー頻度そのもので割ることにした。
他にもユーザー頻度の平方根や対数など色々と試したが、ユーザー頻度そのもので割ったほうが一番面白い(過激な)結果を返したので採用した。

ソースコード

引数にユーザーIDを指定して、上に載せたスクリプトでクロールした結果を標準入力に与えて使う。
プロトタイプで適当に作っただけなのでコードは汚い。
似ているとみなすユーザー数や推薦する数などのパラメータはハードコードされてる

# -*- coding: utf-8 -*-
import xml.etree.ElementTree
import urllib2
import sys
import time
import math
import collections

uf = collections.Counter()

def freq_iuf(p):
    return 1.0 / uf[p]

freq = freq_iuf

def cos(v1, v2):
    numerator = sum([freq(c) * freq(c) for c in v1 if c in v2])
    square = lambda x: freq(x) * freq(x)
    denominator =  math.sqrt(sum(map(square, v1)) * sum(map(square, v2)))
    return float(numerator) / denominator if denominator != 0 else 0


user = {}

count = 0
for line in sys.stdin:
    line = line.strip()
    count += 1
    if count == 2:
        id = line
    if count == 3:
        problem = set(line.split())
        user[id] = problem
        for p in problem:
            uf[p] += 1
        count = 0

argc = len(sys.argv)

if argc != 2 or sys.argv[1] not in user:
    sys.exit('Error: Invalid argument')

userid = sys.argv[1]
u1 = userid
p1 = user[userid]

temp = []
for u2, p2 in user.iteritems():
    if p1.issuperset(p2):
        continue
    sim = cos(p1, p2)
    temp.append((sim, u2, p2))
temp.sort()
rec = collections.Counter()
limit = 30
for sim, u2, p2 in reversed(temp):
    if limit < 0:
        break
    limit -= 1
    for item in p2:
        if item not in p1:
            rec[item] += sim * freq(item) / len(p2)
print u'ユーザーID:', u1
print u'似ているユーザー:',
for sim, u2, p2 in reversed(temp[-5:]):
    print u2,
print
print u'推薦された問題:',
for k, v in rec.most_common(5):
    print k,
print

結果のデモ(過去にクロールした静的な結果)

データを全部JSONにしてこの記事に直接埋め込んでJavaScriptで表示しようと思ったらはてなブログの記事には長さ制限があるらしく失敗した(´・ω・｀)
しょうがないので外部に置いておいてiframeで読み込み。

とりあえず自分のアカウント(mugenen)に対して推薦した結果を貼っておく。
過去にICPC(国際大学対抗プログラミングコンテスト)の問題を解いていたので、上位5件がICPC関連の問題となっていてまあまあよい結果が得られている

解いているユーザー数で割っているので、あまり人気のない問題や難易度の高い問題が極端に優先されて出てくるので注意。

まとめ

複数人を指定してそれらのユーザーに対する推薦とかを実装したらWebアプリとして公開しようかと思っていたけど、1年以上放置していてやる気配がなかったのでブログネタにした。
推薦ユーザー数とアイテム数とが少なければ、単純に総当りするだけで簡単に推薦システムが作れる(20問以上解いているユーザーだけで数千人とかいるので全員に推薦するとそこそこ重かった)

情報推薦システム入門 -理論と実践-

情報推薦システム入門 -理論と実践-