ソーシャルブックマークのレコメンドシステム作成のまねごとと、レコメンドシステム検証方法の考察を行った。以下はレポートである。誇張が入り交じってるがご容赦いただけると幸い。

近年、ソーシャルブックマークの利用者が増えている。それに伴い公開されているブックマークのデータも増え、集合知を活用出来る環境が整っている。

その一つの方法としてはレコメンドシステムが挙げられる。しかし現状のレコメンドシステムは、利用者が満足できるほどの性能を持ち合わせていないように思える。

そこで、ソーシャルブックマークにおける新たなリコメンド手法を提案すると共に、その評価を行いたい。

Windows XP SP3にインストールしたVMWare Player上のDebian etchを開発環境とした。そして、Railsフレームワークを使い開発を行った。

ここではlivedoorから提供されている研究用データセットを使用する。これはlivedoor クリップというソーシャルブックマークの実データをCSV形式で纏めた物である。今回はこれをMySQLデータベースに格納して処理を行った。

格納したデータはまず扱いやすくするため、下図のように正規化及びメタデータの付加を行った。

まず始めに、何回もクエリに使われるカラムにインデックスを張った。このとき、出来るだけUNIQUEを使うことにより処理速度を向上した。

しかし、200万以上のブックマークデータそれぞれに対して、SELECTを2 + タグの価数回、INSERTもしくはUPDATEを3 + タグの個数 * 2回行うので処理量が膨大になってしまい、1日以上変換にかかってしまった。

処理時間を短縮できる鍵は無いかと探していたところ、どうやらディスクIOに時間がかかっているようだった。よってClipsテーブルを MEMORYテーブルにしようとしたが、固定長のレコードフォーマットしか使用出来ないためメモリに入りきらなかった。そこで、VSuite Ramdiskというソフトを使いメモリ上にディスクを構築し、そこに全てのテーブルデータを移行した。そして更に、このシステムにおけるテーブルは基本 的に更新されない、つまりトランザクション処理を行う必要がないので、ストレージエンジンをInnnoDBからMyISAMに変更した。また、MySQL のメモリに関する設定を弄り、チューニングを行った。こうして処理を行ったところ、処理時間を半分ほどにまで縮めることが出来た。

しかしそれでも遅いので、全てのブックマークについて変換することはやめ、これから行うレコメンド処理の特性を使い時間の短縮を図ることにし た。今回のレコメンドでは、利用者が事前にリコメンドして欲しいタグを指定する。よって、事前にレコメンド処理に必要とされる利用者をタグから割り出し、 その利用者のみについてテーブルの変換を行うことにした。これにより大幅に処理時間を短縮することが出来た。最終的に処理時間は当初の四分の一以下、六時 間まで縮まった。

定量的なレコメンドシステムの評価方法について考えた。ここではレコメンドシステムを、所謂バックテスト方式によって評価したい。

各人のブックマークを時系列にプロットすると以下のようになる。

ここである一つのタイムポイントを取り、そこを境に過去の情報と未来の情報に分ける。ここで、Aに対してのレコメンドを評価したいとすると、 まず過去の情報からAにレコメンドするブックマークを生成する。そして、Aの未来のブックマークに、レコメンドしたブックマークがいくつ含まれているかが レコメンドシステムの評価となる。つまり、利用者がこの先ブックマークするブックマークをレコメンドすることが出来るとき、そのレコメンドシステムは優れ ているとする。

自分と各人において、各々のタグと使用頻度における相関を取り、相関が高い人を抽出する。その人と自分がよく使っているタグの中で、同じブッ クマークがよくあるタグを探す。そのタグで自分がブックマークしていないが、その人がブックマークしているブックマークをレコメンドすることにしたが、処 理に時間がかかってしまい実用的とは言えなかった。livedoorで使われているレコメンドシステムでは、処理をバッチで行っていたので、リアルタイムで処理を行うというのは元から諦めた方が良いのかもしれない。それにしても時間がかかりすぎるので、次の様に処理を変更した。

自分が登録しているあるタグについてのレコメンドを受けたいとする。そのとき、各人のそのタグにブックマークされているサイトと、自分がその タグにてブックマークしているサイトを比較して一致度を調べる。一致度が高い人がブックマークしているサイトで、自分がブックマークしていないサイトをリ コメンドする。ここの実験ではそのタグを「イラスト」とした。

通常タグは各個人ごとに付けられる。タグ名も然り。よって、同じ分類を意図したタグでも、表記揺れなどによってタグ名が異なる場合が出てくる。このシステムではその修正を図った。

しかし、適切なシソーラスが見つからなかった。よって、「イラスト」の類義語として「絵」、「illust」、 「illustration」、「picture」を採用し、下位語として「漫画」、「マンガ」、「まんが」「comic」、「同人」、「dojin」、 「doujin」を採用した。ここでの、類義語、下位語は一律して「イラスト」と同じ語として扱う。

当初Graphvizを使う予定だったが、もっとインタラクティブなグラフを作成したかったのでGraph Gear（無 向グラフをFlashで表示出来るライブラリ）を使用してグラフを表示した。しかし、これはグラフを放射状にしか表示出来なかったので、非常に見にくく なってしまった。よって、Graphvizを使い再度グラフを作成した。全てを楕円で表示したときは分かりにくかったが、色を付けたりすることによって分かりやすくなった。以下は指定したユーザへのイラストタグに限定したリコメンドである。UIDと書いてあるノードはユーザ、そこからリンクされているノードはタグ、そしてタグからリンクされている数字のノードはURLである。以下の場合、赤いノードはUID:1のみ、青いノードはUID:5344のみ、紫のノードは両方のユーザが登録しているURLを表す。この場合はUID:1に青いノードがレコ面倒される。

Graphviz on Railsを参考にしてRailsへのグラフ実装を行った。user_idとタグ（現在は決めうち）を入力することにより、リコメンド結果とリコメンド結果をグラフ表示したものが返ってくるように設定した。

こうして作成したが、タグを限定してレコメンドするとユーザ同士の重複するブックマークが少なくなってしまい、適切にレコメンドが行えなかった。

また検証方法だが、URLが指す実体というのは不変ではない。URL先のページが削除され、以後ブックマークされないといった事態が存在するとご指摘を頂いた。ある時点でのページの有無も考慮に入れたバックテストを行うことも必要だと考えた。