2011-06-07

Amazon の Item-to-Item CF の論文を読んだメモ

今となってはかなり古い部類に入る論文ですが、レコメンデーションの基礎を改めて勉強し直すために読んだので、そのメモを残しておきます。1

Amazon.com Recommendations: Item-to-Item Collaborative Filtering


この論文が議論の対象としているのは、（Amazon.com のような）数千万ユーザ・数百万点の商品（アイテム）という大規模なデータセットに対し、リアルタイム（遅くとも 500ms 以下）、オンライン 2 で、かつ高品質な推薦を行うという問題です。Amazon はこの問題をアイテムベースの協調フィルタリングで解決しています。

ユーザベースの協調フィルタリング


協調フィルタリングの詳細については こちらの資料 に譲るとして、端的にいうと「協調フィルタリング」というのは、アクティブユーザ（推薦対象のユーザ）に類似する他のユーザを、商品購入履歴や評点情報の近さから探し出し、そのユーザが購入している商品をアクティブユーザに推薦する、というものです。

古典的な GroupLens のユーザベース協調フィルタリングでは、時間計算量の制約から、オンラインでの推薦を提供できるのは中規模（数十万ユーザ、数万点の商品程度？）のデータセットまでとなっているようです。このユーザベースの協調フィルタリングの時間計算量は、ユーザ数を m、商品数を n とすると、最悪のケースで O(mn) となります。ただし、実際のデータセットにおいては、ユーザと商品の関係が疎であることが多いので、その場合には O(m + n) の時間計算量に近くなるそうです。どちらにせよ、Amazon ほどの大規模なデータセットにおいては、O(m + n) の時間計算量でさえもオンライン・リアルタイムでの推薦を難しくする要因となり得ます。

このユーザベースの協調フィルタリングを大規模データセットに適用する場合は、時間計算量を小さくする工夫が必要になります。この論文では以下のように、データの規模を減らすことで時間計算量を小さくする手法が挙げられています。
  • ユーザをランダムサンプリングして、全体のユーザ数を減らす
  • 購入量の少ないユーザを省く（類似度計算結果の精度が低く、推薦にあまり役立たないため）
  • とてもよく購入されている/ほとんど購入されていないアイテムを省く
ほかにも、商品の集合をそのカテゴリごとに分類し、その分類された商品の集合内で推薦処理を行う方法も挙げられています。しかしながら、いずれの手法を採用するにしても、推薦の品質・精度が低下してしまう問題がつきまとってしまいます。

クラスタモデルの手法


ユーザベースの協調フィルタリングでは、リクエストの都度、ユーザ間の類似度を計算して、アクティブユーザに類似するユーザを探していました。一方でクラスタモデルでは、ユーザ集合を類似するユーザ同士であらかじめクラスタリングしておきます。このクラスタリング処理は、推薦処理とは切り離してオフラインで計算することができます。推薦処理では、このユーザのクラスタを利用し、アクティブユーザがどのクラスタに属するかを判定したのちに、そのクラスタに属する他のユーザの情報を利用して推薦が行われます。

このクラスタモデル、計算時間の観点では優れた手法ではありますが、推薦品質については決して高くはないようです。推薦品質を向上させるためにはクラスタの数を増やす必要があり、クラスタ数を増やしてしまうと、オンラインでの計算量が増えてしまう、という問題を抱えています。

Amazon.com のアイテムベース (Item-to-Item) の協調フィルタリング 3


以上のように、大規模なデータセットに対して高品質・高精度で、かつパフォーマンスのよい推薦を実現するのは難しい問題と言えます。Amazon はこの問題に対し、アイテムベースの協調フィルタリングを利用することで解決を図っています。

Amazon のアイテムベース協調フィルタリングの一番の特徴は「アイテム間の類似度行列をオフラインで計算して、推薦に備えておく」ことです。アイテム間の類似度行列の計算は、最悪のケースで O(n^2 * m)、疎なデータセットでも O(nm) の時間計算量となりますが、オフラインで計算するのであればこの計算量は許容できる範囲になるのではないでしょうか。また、よく購入されている商品を購入したユーザをサンプリングしてアイテム間の類似度行列を計算することで、品質・精度の低下を小さくしつつ、時間計算量を削減できるようです。

推薦処理では、このアイテム間の類似度行列を利用します。その推薦処理の時間計算量は、ユーザ数や商品総数に依存せず、アクティブユーザの購入商品数、評点情報数にのみ依存します。そのため、大規模データセットであっても、オンラインでの推薦処理で充分な性能が出せるようになる、とのことです。

また、このアイテムベースの協調フィルタリングは、アクティブユーザの購入済みの商品が 2,3 個程度と僅かな状況であっても、質の良い推薦が実現できます（ユーザーベースの協調フィルタリングでは、類似するユーザーを探すためにそれなりの数の購入商品数を必要とするので、2,3 個程度の商品数では十分な推薦が実現できません）。

まとめ


大規模データセットに対して推薦をする場合、高いパフォーマンスと推薦品質・精度の両立は簡単ではありません。Amazon.com は、アイテムベースの協調フィルタリングを採用することで推薦品質・精度の問題を解決し、またその協調フィルタリングで利用するアイテム間類似度行列をオフライン計算することでパフォーマンスの問題を解決しています。

感想など


普段扱っているデータの規模が大きくても数十万ユーザ、数万アイテム数だというのに、この程度でヒイヒイ言っている自分が情けなくなりますね… 規模の大きいデータにもっと慣れねば！

1：個人的な解釈が多分に含まれているので、この記事を参考にすることがもしあれば、一度原文と照らし合わせてみることをお勧めします。
2：推薦すべき商品を事前に計算して準備しておくのではなく、リクエストが来たところで初めて推薦する商品を算出する方式。論文の記述から察するに、ショッピングカート内の商品から推薦する場合などにも利用されているらしい。
3：アクティブユーザに類似するユーザを探すのではなく、あるアイテムに類似する別のアイテムを探すタイプの協調フィルタリングを、ここでは「アイテムベースの協調フィルタリング」と呼んでいます。
by @komiya_atsushi2:222 comments

2011-02-19

Trie が提供すべき操作について検討してみる

nokuno さんの記事「オープンソースのTrieライブラリまとめ」あたりを参考に、まず既存の Trie ライブラリ群がどのような API を提供しているのかを調査し、その上でこれから Trie を実装する場合に、どのような操作・API を提供すべきかを検討した結果のメモです。

記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。

  • Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。
    • prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。
    • commonPrefixSearch() ... common prefix search。Trie に格納されている文字列より、対象文字列の接頭辞にあたる文字列をすべて列挙する。結果は一括して求められる。
    • predictiveSearch() ... predictive search。Trie に格納されている文字列より、対象文字列が接頭辞となる文字列をすべて列挙する。結果は一括して求められる。
    • expandSearch() ... common prefix search + predictive search。Trie に格納されている文字列より、対象文字列を接頭辞とする文字列、または対象文字列の接頭辞にあたる文字列を列挙する。結果は一括して求められる。
  • UX ... Tx と同じく岡野原さんによるプロダクト。さらに簡潔。だいたい Tx と同じ API 構成。この命名は、"Tx" の１つ先（t -> u）を行く、という意味が込められているのかな？
    • prefixSearch() ... prefix search。
    • commonPrefixSearch() ... common prefix search。
    • predictiveSearch() ... predictive search。
  • sumire-tries ... やたさんによる、簡潔データ構造を含む各種 Trie の実装。Trie 木構造のノードレベルでの走査（traversal）ができるのが特徴。
    • TrieBase#find() ... exact match。Trie に格納されている文字列より、対象文字列に完全一致する文字列を探し出す。
    • TrieBase#follow() ... Trie・ノードの走査。指定されたノードから始まり、対象文字列に合致する Trie 上の経路（ノード）を辿る。
    • TrieBase#find_child() ... Trie・ノードの走査。あるノードより指定された文字を辿った先にある子ノードを求める。
    • TrieBase#child() ... Trie・ノードの走査。指定のノードの先にある子ノードのうち、最初の子ノードを求める。
    • TrieBase#sibling() ... Trie・ノードの走査。指定のノードの、次の兄弟ノードを求める。
    • class CompleterBase ... predictive search。Iterator パターンで、文字列を順次列挙する。
  • marisa-trie ... やたさんによる、簡潔データ構造を利用した Trie の実装。UX の手法をさらに発展させたものっぽい。
    • lookup() ... exact match。sumire-tries では find() でしたが、marisa-trie では同名メソッドは別の機能を提供しているようです。
    • find() ... common prefix search。一括して列挙する。
    • find_first()/find_last() ... prefix search。
    • find_callback() ... common prefix search。１つずつ、コールバック関数を呼び出して列挙する。
    • predict() ... predictive search。一括して列挙する。
    • predict_callback() ... predictive search。１つずつ、コールバック関数を呼び出して列挙する。
  • Darts ... MeCab 開発者の工藤さんによる Double Array Trie の実装。MeCab でも利用されています。
    • exactMatchSearch() ... exact match。
    • commonPrefixSearch() ... common prefix search。一括して列挙する。
  • Doar ... Igo/Gomoku の開発者 sile さんによる Double Array Trie の C++ 実装。
    • Searcher#search() ... exact match かな？
    • Searcher#common_prefix_search() ... common prefix search。１つずつ、コールバック関数を呼び出して列挙する。
    • Searcher#children() ... Trie・ノードの走査。子ノードを１つずつ、コールバック関数を呼び出して列挙する。
  • jada ... sile さんによる Double Array Trie の Java 実装。
    • Trie#search() ... exact match。
    • Trie#commonPrefixSearch() ... common prefix search。同メソッドを繰り返し呼び出して、１つずつ列挙する。

こんなところでしょうか。以上より「Trie を使った操作」は、
  • exact match
  • common prefix search
  • predictive search
  • prefix search
の４つが用意できるとよさそうです。少なくとも、上から３つは必須となりそうですね。

「Trie の走査を実現する走査」としては、ピックアップした実装ではあまり提供されていませんでしたが、
  • あるノードの直下の子ノードを列挙する
操作は必須となりそうです。

この結果を参考に、汎用的に使えそうな Trie の Java 実装について検討を進めてみます。
by @komiya_atsushi1:59No comments

2010-12-11

[メモ]MinGW/MSYS 環境で Kyoto Cabinet Core & Java バインディングをビルドする

本家から Windows 版がでた今となっては全く不要な記事となりましたが、せっかく書いたので残しておきます。

対象バージョン


1. 準備

Kyoto Cabinet のビルドを始める前に、依存ライブラリ regex と zlib をビルド＆インストールする必要があります。

1.1 regex のビルド・インストール

上記 URL からダウンロードした regex の tarball を展開し、展開先ディレクトリにて
$ ./configure
$ make
 を実行します。make が終わったら、スタティックな libregex.a を作るため、
$ rm libregex.a
$ ar rcs libregex.a regex.o
 とします。その後、
$ make install
を実行し、regex のビルド・インストールは完了です。

1.2 zlib のビルド・インストール

zlib の tarball を展開した先のディレクトリにて、
$ make -f win32/Makefile.gcc
とし、Windows/gcc 環境用の Makefile を用いて make します。インストールの際は以下のように、事前に INCLUDE_PATH、LIBRARY_PATH の環境変数を定義する必要があります。
$ export INCLUDE_PATH=/usr/local/include
$ export LIBRARY_PATH=/usr/local/lib
$ make -f win32/Makefile.gcc install
以上で準備は完了です。

2. Kyoto Cabinet core library のビルド・インストール

g++ に渡すオプションを、以下のとおり定義します。
$ export CPPFLAGS=-D_WIN32_WINNT=0x0501
あとは、kyotocabinet の tarball 展開先ディレクトリにて、
$ ./configure
$ make
$ make check
$ make install
として、ビルド＆インストールが完了します。

3. Kyoto Cabinet Java バインディングのビルド・インストール

3.1 準備

Kyoto Cabinet Java バインディングをビルドする前に、JDK をインストールした先のディレクトリの情報を MSYS の fstab ファイルに追記する必要があります。

fstab ファイルは、(MinGW のインストールルート)\msys\1.0\etc ディレクトリに配置されています。以下は、"C:\Program Files\Java" ディレクトリに JDK をインストールした場合の追記内容の例です。
C:\Progra~1\Java\jdk1.6.0_18 /java
上記のように、JDK をインストールした先のパスの途中に空白を含むディレクトリが存在する場合、チルダ ~ を使ってそのディレクトリ名を表記する必要があるようです（ダブルクォーテーションで括っても、MSYS は認識してくれません）。

3.2 ビルド＆インストール

./configure を実行する前に、環境変数 JAVA_HOME を定義し (直し) ます。
$ export JAVA_HOME=/java
JAVA_HOME を定義したら kyotocabinet-java の tarball 展開先で
$ ./configure
とします。./configure が完了したら、出力された Makefile を一部修正します。以下のようにターゲット libjkyotocabinet.so.$(LIBVER).$(LIBREV).0 の内容に、jkyotocabinet.dll を生成するためのコマンドを追記します。
libjkyotocabinet.so.$(LIBVER).$(LIBREV).0 : $(LIBOBJFILES)
 $(CXX) $(CXXFLAGS) -shared -Wl,-soname,libjkyotocabinet.so.$(LIBVER) -o $@ \
   $(LIBOBJFILES) $(LDFLAGS) $(LIBS)
 ##### 以下の２行を追記する #####
 $(CXX) $(CXXFLAGS) -shared -Wl,--kill-at -Wl,-soname,jkyotocabinet.dll -o jkyotocabinet.dll \
   $(LIBOBJFILES) $(LDFLAGS) $(LIBS)
本来なら CPPFLAGS などの環境変数で解決したい内容なのですが、何故か kyotocabinet-java の ./configure では環境変数が反映されないようなので、やむを得ずこのような work around をしています。さて、Makefile の編集が終わったところで、
$ make
$ make check
とします。なお、make check は
make DBNAME="*" RNUM="10000" check-each
のテストの実行時にエラーになってしまうようです。この問題はまだ解消できていませんが、普通に利用する分には支障はないのかな、と思います。

後は、生成された jkyotocabinet.dll と kyotocabinet.jar を利用すれば、Windows 上でも Java から Kyoto Cabinet が使えるようになることでしょう（試していません…）。
by @komiya_atsushi2:26No comments

2010-11-21

「第8回 データマイニング＋WEB 勉強会＠東京」で発表してきました

11/14（日）に開催された「第8回 データマイニング＋WEB 勉強会＠東京」で、「協調フィルタリングにおける希薄問題の解決法 - Random walk」という題目で発表してきました。以下はその発表に使ったスライドです。

TokyoWebmining#8 協調フィルタリングにおける希薄問題の解決法 - Random walk

現在、本発表内容に関連した、もう一歩踏み込んで説明した補足資料を作成しています。11/23（火）までに作り終えられるといいなあ。

12/1 追記

補足資料を slideshare で公開しました。

【補足資料】協調フィルタリングにおける希薄問題の解決法 - Random walk
by @komiya_atsushi23:34No comments
登録: 投稿 (Atom)