集合知プログラミング読み始めました

こんばんは、south37です。最近、O'Reillyの「集合知プログラミング」を読み始めました。

まだ本当に読み始めなんですが、なかなか面白いです。最初に取り上げられていたのは、「推薦」のお話でした。

推薦

「推薦」の方法として、「協調フィルタリング」というものがあります。ざっくり言うと、「自分と似た趣味・趣向を持つユーザが好むものは、自分も好む可能性が高い」という考え方に基づいた推薦方法です。その実現の第一歩として、まずは自分と似た嗜好を持つユーザーを見つける必要があります。

自分と似たユーザーを見つける

類似性を見積もる方法として、最も単純なのはユークリッド距離によるスコア付けです。この方法では、項目ごとに興味・感心度合いをパラメータとして割り振って、それを多次元空間における点とみなした時に、点同士がどれだけ近いかで趣向の類似度を測ります。

今回は、ユークリッド距離によるスコア付けを試してみる事にします。

自分と似た嗜好(はてブ)を持つはてなユーザーを探す

題材は、はてなブックマークの類似度です。自分は興味を持ったサイトをはてなブックマークしていて、他のユーザーもきっと同じような使い方をしていると思います。よって、他のユーザがどれだけ自分と似たような嗜好を持つかは、ブクマするサイトの類似度で判断出来るはずです。

ユークリッド距離としては、単純にサイト一つ一つを変数とした多次元空間における距離を考える事にします。要は、ブクマしてれば1ポイント、してなければ0ポイントをそのサイトに与える事にして、そのポイントの与え方が近い人を捜す事になります。

とりあえずは、近い人で試す

とりあえず、自分がはてなでお気に入りにしてるユーザと、リレーブログを一緒にやってる他の6人について、データを集めてみる事にします。データははてなのフィードAPIで適当に集めて、ユーザ毎にyamlファイルとして保存します。

データ収集

スクリプトを書きました。

require 'mechanize'

def proc_user(user, of = 0)
  agent = Mechanize.new
  agent.get "http://b.hatena.ne.jp/#{user}/atomfeed?of=#{of}"

  links = agent.page.search('entry').search('link[rel="related"]').map { |link| link['href'] }
  File.open("#{user}.yaml", 'a') do |f|
    links.each { |link| f.write "- #{link}\n" }
  end

  proc_user(user, of + 20) if links.size == 20 # 一度に取得されるlinkは、デフォルト20
rescue => e
  puts "[ERROR]: #{e.message}"
end

proc_userメソッドにはてなユーザ名渡して実行すると、はてなユーザ名.yamlファイルにそのユーザがブクマしたサイトのurlのリストが保存されます。別にリンクだけ保存する必要は無いうえ、テキストファイルでは無くDBとかでも良いですが、一番楽そうだったのでこうしてます。

次に、自分のお気に入りユーザのリストを取得して、そのユーザごとにporc_userを実行してみます。

def proc_favorite_users_of(user)
  agent = Mechanize.new
  agent.get "http://b.hatena.ne.jp/#{user}/favorite"

  agent.page.search('.sidebar-users').search('a').each do |user_l|
    proc_user user_l['href'][1..-2]
  end
end

proc_favorite_users_of 'south37' # south37のお気に入りしてるユーザ達に対して、proc_user実行

このブログが属しているブロググループ「焼き肉ブログ」のユーザに対してもproc_userを実行しようとしましたが、誰もはてなブックマーク使ってませんでした...orz

比較

次に、比較用のメソッドを書きます。ユーザ二人を受け取って、その類似度をユークリッド距離の逆数として算出します。逆数にするのは、数字が大きい程近い事にするためです。サイト毎に1ポイントか0ポイントしか割り振られないため、単純にかぶってるサイトの数とかぶって無いサイトの数が分かれば良いはずです。よって、concatしてからuniqして、その減少量とか考えれば良い事になります。

require 'yaml'

def euclid(user, other)
  user_links  = YAML.load(File.read "#{user}.yaml").uniq
  other_links = YAML.load(File.read "#{other}.yaml").uniq

  total_links = user_links.concat(other_links)
  total_num = total_links.size
  same_num  = total_num - total_links.uniq.size
  diff_num  = total_num - 2 * same_num

  1.0 / (1 + diff_num ** 0.5)
end

とりあえずこれで実行してみます。

Dir.glob('./*.yaml') do |f|
  file_name = File.basename(f)
  next if file_name == 'south37.yaml'
  other = file_name.split('.').first
  p "south37 vs #{sprintf("%-11.11s", other)} #{euclid('south37', other)}"
end
# >> "south37 vs a666666    : 0.03081818865084289"
# >> "south37 vs amachang   : 0.015521413111784664"
# >> "south37 vs mizchi     : 0.008304596529085169"
# >> "south37 vs mrkn       : 0.010594157602211253"
# >> "south37 vs naoya      : 0.008752925493532536"
# >> "south37 vs nitro_idiot: 0.018603215944083363"
# >> "south37 vs tagomoris  : 0.015135647044646766"

最後にコメントで書いてあるのが実行結果です。

感想

これ見るとa666666さんとは趣向が割と近くて、mizchiさんとは遠い様にみえます。

が、実は実態は違ってきます。それを示す為に、それぞれのユーザと一致したブクマの数、そしてそれぞれのユーザの総ブクマ数を示してみます。

# >> "south37: 50 vs a666666    : 939   same: 0"
# >> "south37: 50 vs amachang   : 3973  same: 0"
# >> "south37: 50 vs mizchi     : 14220 same: 5"
# >> "south37: 50 vs mrkn       : 8674  same: 1"
# >> "south37: 50 vs naoya      : 12779 same: 2"
# >> "south37: 50 vs nitro_idiot: 2733  same: 0"
# >> "south37: 50 vs tagomoris  : 4186  same: 1"

south37が僕で、ブクマ数は50、その隣にそれぞれのユーザのブクマ数と、そのユーザと一致したブクマ数が示してあります。mizchiさんとは5つ一致しているので、実は絶対的な数ではトップだという事が分かります。

では、何故ユークリッド距離を用いた方法では、実態とはかけ離れた結果となってしまったのでしょうか？

ざっくり言うと、ブクマしたサイトがかぶる事なんてほとんど無い為、ブクマ数が多いユーザとは「多くのサイトに対して違う判断を下した」事になるからです。結果的に、ブクマ数が多いユーザほど小さなスコアが出ています。

実は、今回の手法ではあるサイトに対して誰かがブクマをしていない時、そのサイトを見てすらいない可能性があるにも関わらず、「サイトに興味が無かったのでブクマしなかった」と解釈して解析を行っています。その為、極端にブクマ数が多いユーザと比較を行う時は、ブクマ数が少ない側のユーザはその多くのサイトを見てすらいない可能性が高いのに、「多くのサイトをブクマする価値無しと判断した」と考えてしまう為に、類似度が低く出てしまいます。

アプローチの仕方が適切ではありませんでした。

改善

パッと思いついた方法としては、ブクマしたサイトをタグやカテゴリで集計して、その分布度合いで類似度を見るというものが考えられます。総ブクマ数の違いは、「ピアソン相関」と呼ばれる手法を用いれば吸収出来るはずです。

これも、近々試してみたいですね!!

追記

Jaccard係数なるものを知りました。二つの集合に対し、ORの数でANDの数を割ったもののようです。 今回のケースだと良い指標となる気がしたので、試してみます。

以下、実行結果です。

# >> "south37: 50 vs a666666    : 939   and: 0.0 jaccard: 0.0"
# >> "south37: 50 vs amachang   : 3973  and: 0.0 jaccard: 0.0"
# >> "south37: 50 vs mizchi     : 14220 and: 5.0 jaccard: 0.0003505082369435682"
# >> "south37: 50 vs mrkn       : 8674  and: 1.0 jaccard: 0.00011463945890175398"
# >> "south37: 50 vs naoya      : 12779 and: 2.0 jaccard: 0.00015592110392141577"
# >> "south37: 50 vs nitro_idiot: 2733  and: 0.0 jaccard: 0.0"
# >> "south37: 50 vs tagomoris  : 4186  and: 1.0 jaccard: 0.0002361275088547816"

ブクマ数が多いユーザとはORの数が多くなりがちであるものの、ANDの数が多ければそれがちゃんと影響してくる為、悪く無い結果だと思いますね!!

さらに、勝手にnaoyaさんとそれ以外の人との比較もしてみました。

# >> "naoya: 12779 vs a666666    : 939   and: 57  jaccard: 0.004172461752433936"
# >> "naoya: 12779 vs amachang   : 3973  and: 78  jaccard: 0.004677941705649514"
# >> "naoya: 12779 vs mizchi     : 14220 and: 377 jaccard: 0.014161220043572984"
# >> "naoya: 12779 vs mrkn       : 8674  and: 182 jaccard: 0.008556250293827276"
# >> "naoya: 12779 vs nitro_idiot: 2733  and: 110 jaccard: 0.007141929619529931"
# >> "naoya: 12779 vs south37    : 50    and: 2   jaccard: 0.00015592110392141577"
# >> "naoya: 12779 vs tagomoris  : 4186  and: 131 jaccard: 0.007781870024949507"

これくらいブクマ数が多い人だと、ちゃんとそれっぽい結果になりますね。特に、相手のブクマ数が変な影響を与えてなさそうなのが、とても良い感じです。

集合知プログラミング

集合知プログラミング