「集合知プログラミング」del.icio.usのリンクを推薦するシステムを作るのサンプルコードを試してみました。

「集合知プログラミング」では、インターネットを通じて集合知のモトとなるデータを集め、取り扱う方法が説明されています。

その２章「推薦を行う」にて「del.icio.usのリンクを推薦するシステム」の説明があります。delicious（デリーシャス）とは、ソーシャルブックマークサイトです。簡単に言えば、お気に入りのサイトを公開して共有するサービスです。

del.icio.us
https://delicious.com/

沢山の人が、お気に入りのブックマークを登録しています。登録されているブックマークを分析して、ある人と同じ嗜好を持つ人を探しだすプログラムを作ります。さらに、その人が好みそうなリンクを推薦するシステムを作ります。



「集合知プログラミング」では、Pythonのコードでの説明がされています。この「del.icio.usのリンクを推薦するシステム」では、Pythonのモジュール「pydelicious」を使います。

検証は、Mac OS X 10.7.5のPython 2.7.1で行います。
「pydelicious」のバージョンは、「pydelicious-0.6」を使用します。

下記のソースは、del.icio.usのデータセットを作る処理本体の　deliciousrec.py　の内容です。

書籍の記載のままでは、動作しない箇所があります。1行目「import time」の記載不足、8行目「for p2 in get_urlposts(p1['href']):」24行目「url=post['href']」は、del.icio.usのAPIの仕様変更により、「for p2 in get_urlposts(p1['url']):」「url=post['url']」への修正が必要です。

import time
from pydelicious import get_popular,get_userposts,get_urlposts

def initializeUserDict(tag,count=5):
 user_dict={}

 for p1 in get_popular(tag=tag)[0:count]:
  for p2 in get_urlposts(p1['url']):
   user=p2['user']
   user_dict[user]={}
 return user_dict

def fillItems(user_dict):
 all_items={}
 for user in user_dict:
  for i in range(3):
   try:
    posts=get_userposts(user)
    break
   except:
    print "Failed user "+user+", retrying"
    time.sleep(4)
  for post in posts:
   url=post['url']
   user_dict[user][url]=1.0
   all_items[url]=1

 for ratings in user_dict.values():
  for item in all_items:
   if item not in ratings:
    ratings[item]=0.0

あと、推薦をするプログラム　recommendations.py　が必要です。

from math import sqrt

# Returns a distance-based similarity score for person1 and person2
def sim_distance(prefs,person1,person2):
  # Get the list of shared_items
  si={}
  for item in prefs[person1]: 
    if item in prefs[person2]: si[item]=1

  # if they have no ratings in common, return 0
  if len(si)==0: return 0

  # Add up the squares of all the differences
  sum_of_squares=sum([pow(prefs[person1][item]-prefs[person2][item],2) 
                      for item in prefs[person1] if item in prefs[person2]])

  return 1/(1+sum_of_squares)

# Returns the Pearson correlation coefficient for p1 and p2
def sim_pearson(prefs,p1,p2):
  # Get the list of mutually rated items
  si={}
  for item in prefs[p1]: 
    if item in prefs[p2]: si[item]=1

  # if they are no ratings in common, return 0
  if len(si)==0: return 0

  # Sum calculations
  n=len(si)
  
  # Sums of all the preferences
  sum1=sum([prefs[p1][it] for it in si])
  sum2=sum([prefs[p2][it] for it in si])
  
  # Sums of the squares
  sum1Sq=sum([pow(prefs[p1][it],2) for it in si])
  sum2Sq=sum([pow(prefs[p2][it],2) for it in si]) 
  
  # Sum of the products
  pSum=sum([prefs[p1][it]*prefs[p2][it] for it in si])
  
  # Calculate r (Pearson score)
  num=pSum-(sum1*sum2/n)
  den=sqrt((sum1Sq-pow(sum1,2)/n)*(sum2Sq-pow(sum2,2)/n))
  if den==0: return 0

  r=num/den

  return r

# Returns the best matches for person from the prefs dictionary. 
# Number of results and similarity function are optional params.
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]

# Gets recommendations for a person by using a weighted average
# of every other user's rankings
def getRecommendations(prefs,person,similarity=sim_pearson):
  totals={}
  simSums={}
  for other in prefs:
    # don't compare me to myself
    if other==person: continue
    sim=similarity(prefs,person,other)

    # ignore scores of zero or lower
    if sim<=0: continue
    for item in prefs[other]:
     
      # only score movies I haven't seen yet
      if item not in prefs[person] or prefs[person][item]==0:
        # Similarity * Score
        totals.setdefault(item,0)
        totals[item]+=prefs[other][item]*sim
        # Sum of similarities
        simSums.setdefault(item,0)
        simSums[item]+=sim

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

  # Return the sorted list
  rankings.sort()
  rankings.reverse()
  return rankings

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


def calculateSimilarItems(prefs,n=10):
  # Create a dictionary of items showing which other items they
  # are most similar to.
  result={}
  # Invert the preference matrix to be item-centric
  itemPrefs=transformPrefs(prefs)
  c=0
  for item in itemPrefs:
    # Status updates for large datasets
    c+=1
    if c%100==0: print "%d / %d" % (c,len(itemPrefs))
    # Find the most similar items to this one
    scores=topMatches(itemPrefs,item,n=n,similarity=sim_distance)
    result[item]=scores
  return result

def getRecommendedItems(prefs,itemMatch,user):
  userRatings=prefs[user]
  scores={}
  totalSim={}
  # Loop over items rated by this user
  for (item,rating) in userRatings.items( ):

    # Loop over items similar to this one
    for (similarity,item2) in itemMatch[item]:

      # Ignore if this user has already rated this item
      if item2 in userRatings: continue
      # Weighted sum of rating times similarity
      scores.setdefault(item2,0)
      scores[item2]+=similarity*rating
      # Sum of all the similarities
      totalSim.setdefault(item2,0)
      totalSim[item2]+=similarity

  # Divide each total score by total weighting to get an average
  rankings=[(score/totalSim[item],item) for item,score in scores.items( )]

  # Return the rankings from highest to lowest
  rankings.sort( )
  rankings.reverse( )
  return rankings

def loadMovieLens(path='/data/movielens'):
  # Get movie titles
  movies={}
  for line in open(path+'/u.item'):
    (id,title)=line.split('|')[0:2]
    movies[id]=title
  
  # Load data
  prefs={}
  for line in open(path+'/u.data'):
    (user,movieid,rating,ts)=line.split('\t')
    prefs.setdefault(user,{})
    prefs[user][movies[movieid]]=float(rating)
  return prefs

用意ができたので、Pythonのインタラクティブシェルで動作を確認します。

#必要なモジュールの読み込み
>>> import recommendations
>>> from deliciousrec import *
>>> import random

# 「design」というタグを付けているユーザーの取得
>>> delusers=initializeUserDict('design')

# 取得した各ユーザーのリンクを取得
>>> fillItems(delusers)

# 取得したユーザー達の中からランダムに1人を取得
>>> user=delusers.keys()[random.randint(0,len(delusers)-1)]

# このユーザーに似ているユーザーをリストアップ
>>> recommendations.topMatches(delusers,user)

[
(0.5344262295081967, u'thehrisworld'), 
(-0.16393442622950818, u'yaax'), 
(-0.16393442622950818, u'tchiule'), 
(-0.16393442622950818, u'sneurgaonkar'), 
(-0.16393442622950818, u'sethkontny')
]

# このユーザーが好みそうなリンクを推薦
>>> recommendations.getRecommendations(delusers,user)[0:10]

[
(1.0, u'http://www.youtube.com/watch?v=C5tOEBmBAHg'), 
(1.0, u'http://www.lifeisstory.com/'), 
(1.0, u'http://techcrunch.com/2013/09/06/what-to-do-if-you-get-a-troll-demand/'), 
(1.0, u'http://on.mash.to/1dJDvYC'), 
(0.0, u'https://www.facebook.com/sethkontny/posts/10201536626993865'), 
(0.0, u'https://communities.vmware.com/community/vmtn/vcloud-automation-center'), 
(0.0, u'http://www.yorkdispatch.com/breaking/ci_24031648/more-sleep-better-kids-but-too-much-trouble'), 
(0.0, u'http://www.wpcentral.com/geophoto-windows-phone-8-helping-you-remember-where-you-took-photo'), 
(0.0, u'http://www.wired.com/wiredscience/2013/09/wired-space-photo-of-the-day-saturn-storm-circles-planet/'), 
(0.0, u'http://www.wired.com/wiredscience/2013/09/what-exactly-is-astrovirology/')
]