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

こんばんは、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

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

集合知プログラミング