協調フィルタリングによるソーシャルブックマークの推薦 [実践編]

こんばんは、south37です。今回は、「協調フィルタリング」という手法で僕に最適化されたブックマークを調べてみました。まあ、前回の続きですね。

やった事

10万件のブックマークの中から、僕のブックマークした50件のサイトに最も近いサイトを調べてランキングにしました。候補とした10万件としては、「僕がブックマークしてるサイト50個」をブックマークしてるユーザが「ブックマークしてるサイト」を使いました。本当は10万件以上あったのですが、計算が全然終わらなくて件数をしぼってます...すいません...

結果発表

トップ10だけ載せておきます。

Rank Title Score
1 最強オブジェクト指向言語 JavaScript 再入門! 23.18088142475065
2 Node.js チュートリアル Node ビギナーズブック 23.004493305610232
3 JavaScriptフロントエンド開発の昨今 // Speaker Deck 22.950250300412787
4 Webサービス開発現場から / 近頃の開発のやり方 ・・・ Github と Pull Request とコードレビュー - naoyaのはてなダイアリー 22.70594401407323
5 JavaScript イディオム集 » nmi.jp 22.573218450885197
6 Vagrant - naoyaのはてなダイアリー 22.568123360119024
7 github を用いた開発フローテンプレート 22.53364189193526
8 Web API 設計のベストプラクティス集 \"Web API Design - Crafting Interfaces that Developers Love\" - フリーフォーム フリークアウト 22.52874256917394
9 今、AngularJSというフレームワークがヤバい - (゚∀゚)o彡 sasata299's blog 22.52628633504841
10 爆速でわかるjQuery.Deferred超入門 - Yahoo! JAPAN Tech Blog 22.444775813357474

所感

期待していた以上に自分の好みを反映した結果になりました。実は上のリンクのほとんどは一度目にしたことがあって、面白いと思ってたものだったので、好みをピンポイントで突いてきた事に驚いています。僕のブックマーク数が50と少なめだったので若干不安はあったのですが、50くらいあれば問題なく精度の良い推薦が出来そうですね。

使った手法

前回説明した通り、候補のブックマーク10万件の1件1件に対して、僕のブックマーク50件との類似度をuser集合のjaccad相関関数で見積もり、その後僕のブックマーク50件に対して足し合わせてスコアを算出しました。原理上、スコアの最大値は50になるはずですが、実際にはそんなに高いスコアがでる事は無く、17~19程に偏って分布している印象でした。サイトごとに結構ちゃんと差が出てて、それが精度の良いランクに繋がったのが良かったと思っています。

どうせなんでいくつか書いたスクリプトを載せておきます。

def jaccard(array1, array2)
  return 0.0 unless array1 && array2
  concat_array = array1.concat(array2)
  concat_num   = concat_array.size
  or_num       = concat_array.uniq.size
  and_num      = concat_num - or_num

  and_num / (or_num + 0.0) # floatに変換
end

def calcurate_similarity_with_south37
  south37_bookmarks = YAML.load_file 'result/south37_bookmarks_info.yaml'
  south37_urls      = south37_bookmarks.keys
  YAML.load_stream(open('result/bookmarks_info.yaml').read) do |bookmark|
    next unless bookmark
    bookmark_info = bookmark.to_a.first
    url   = bookmark_info[0]
    users = bookmark_info[1]
    next if south37_urls.include?(url)

    similarity_table = {}
    south37_bookmarks.each do |south37_url, south37_users|
      similarity_table[url] ||= {}
      similarity_table[url][south37_url] = jaccard(users, south37_users)
    end
    File.write('result/similarity_table.yaml', similarity_table.to_yaml, mode: 'a')
  end
end

def score_with_south37
  end_urls = YAML.load_file('result/end_score_with_south37.yaml') if File.exist?('result/end_score_with_south37.yaml')
  end_urls ||= []
  YAML.load_stream(open('result/similarity_table.yaml').read) do |similarity_table|
    url, similarities = similarity_table.to_a.first
    next if end_urls.include? url
    score = similarities.values.inject(:+)
    File.write('result/score_with_south37.yaml', "#{url}: #{score}\n", mode: 'a')
    File.write('result/end_score_with_south37.yaml', "- #{url}\n", mode: 'a')
  end
end

データを無理矢理yaml形式でテキストファイルとして保存していたのですが、データサイズが大きくなるといろいろ辛いものがありました...

今後は大人しくDB使っておこうと思います。特に、DataMapperがすごいって聞いたので手を出してみたいですね。

追記: 度数分布

スコアは、こんな感じで分布していました。

範囲 度数
00 - 01 99
01 - 09 0
09 - 10 1
10 - 11 0
11 - 12 2
12 - 13 10
13 - 14 37
14 - 15 71
15 - 16 146
16 - 17 472
17 - 18 1620
18 - 19 12611
19 - 20 75196
20 - 21 3048
21 - 22 396
22 - 23 24
23 - 24 2
24 - 25 0

大体ガウシアンっぽい感じですかね?グラフ化とかもまたしてみたいですね!

集合知プログラミング

集合知プログラミング