November 11, 2010

アクセスログからアテンション(注目情報)をデータマイニングする手法について

多数のユーザーの行動記録からアテンション情報(注目されているデータが何か)をデータマイニングしたいというのは、大量のデータを扱っているウェブサイトにおいては自然と出てくる要求です。そこで、先月末にサービスを終了したサービス「パストラック」において使用していた、アクセスログから注目度(人気度)の高いウェブページや人名等のキーワードを抽出するためのアルゴリズムを紹介しておきたいと思います

たとえばはてなブックマークのような、ユーザーの能動的な行為(「ブックマークする」という作業)から注目情報を抽出するのは決して難しいことではありません。それは、直近の一定期間内のブックマーク数=注目度、という前提が上手に機能するからです。現に、はてなブックマークの人気エントリーは、最近24時間程度の期間内にブックマークしたユーザー数の多い URL を降順で並べているように見受けられます。

しかし、アクセスログからアテンション情報をマイニングする場合に、直近の一定期間内のヒット数を使うことはできません。単純にそうしてしまうと、例えばパストラックの場合は Yahoo! JAPANGoogle のトップページが常に注目情報のトップに表示されることになってしまいます。これは、ウェブの構造のハブとなっているページは常に大量のアクセスを集めているためです。

単純な回避策としては、たとえば過去24時間以内に初めてアクセスされた情報についてのみ、そのヒット数によってランキングする、という方法もあります。しかし、この手を使ってしまうと、たとえば昔から存在する URL へのアクセスが急増した場合注1に取りこぼしが発生してしまうことになります。また、「人気のキーワード」のような機能を実現することまできません注2

そこで、パストラックでは、運動エネルギーのアナロジーを用いた指数を使って注目度のランキングを行っていました。具体的には以下の式のとおりです。

注目度指数 = 単位時間内のヒット数 × (単位時間内のヒット数/長期間のヒット数)2

単位時間は、「注目」データのマイニング機能については最近6時間、「人気」データのマイニングについては最近24時間とし、除数である「長期間のヒット数」については、時間帯や曜日による揺れを省く目的から、約7日間としました。

そして、「注目」あるいは「人気」のウェブページ (URL) を表示する場合は、アクセスが記録されたウェブページについて、この注目度指数でソートした結果を降順で表示。キーワードによる「注目」あるいは「人気」情報の検索については、TF/IDFのスコアに対して注目度指数を乗算した値による降順ソート結果を表示していました。

また、「人気のキーワード」機能については、過去1日以内に一定以上のヒット数を記録したウェブページを形態素解析し、各単語(あるいは人名)について注目度指数によるランキングを行い、上位の8ワードを選択することで、話題になっている事象や人名を抽出していました。

と書くと、かっこいいのですが、上の式には1点問題がありました。それは、運動エネルギーのアナロジーにおいて本来は別の値を使うべき質量と速度の項の両方に、単位時間内のヒット数を使っている点です。このままだと、例えば、毎日1000ヒットを記録するウェブページの注目度指数 (24時間) は約 143 になる一方、今日初めて登場し、いきなり100ヒットを記録したウェブページの指数は 100 になり、前者の方が注目度が高いということになってしまいます。しかし実際は後者の方が、より重要ではないでしょうか。

ですので実際には、パストラックでは、累乗の指数を機能ごとに調整することで、この問題に対応していました。具体的には、ウェブページの抽出においては指数を 4 に、「人気のキーワード」機能では指数を 3 にしていました。

以上が、パストラックにおいて使用していたアテンション情報のマイニングアルゴリズムです。私はデータマイニングについては全くの門外漢ですので、きっとより良い方法があるのだろうとは思います。ただ、この式は簡便・高速注3でパラメータが少ないため調整も簡単ですし、パストラックでは十分満足する結果が得られていましたので、他のサービスにおいても使える可能性は高いと思います。ご参考まで。

注1: 参考:スラッシュドット効果
注2: キーワードや人名は、以前から存在するものが、ある時期急激にアクセスされるようになるため
注3: パストラックにおいては、事前計算のみではなくリクエストベースで注目度を計算して表示したりもしていました

October 27, 2010

Announce: The Transfer of Mylingual.net

Thank you for using Mylingual.net, an automatic, user-based translation (localization) service of web-based application UI.  As of Oct. 29 2010, the service will be transferred from Cybozu Labs, Inc. to Kazuho Oku (the developer of the service, it's me).

  • All the translation data (including editing history, etc.) will be transferred.
  • The browser extensions and userscripts will continue to work as it does today.
  • The translators are requested to re-create their account after the transfer.
  • After the transfer, the translators will be requested to log-in to the new system using Twitter but the integration might not be completed as on Oct. 29.
  • After the transfer, announces and discussions will be posted to the website of Mylingual or to my personal weblog: Kazuho's Blog.

I am sorry to bother the users of the service (especially the translators).  Thank you for your cooperation.

Japanize / Mylingual サービス移管のおしらせ

直前のお知らせになり恐縮ですが、2010年10月29日より Japanize および Mylingual の両サービスを、弊社サイボウズ・ラボ株式会社より、サービスの開発者である私、奥一穂個人へ移管いたします。

  • 蓄積された翻訳データ(編集履歴等含む)は、全て移管されます。
  • 拡張機能や Userscript 等を通して翻訳機能をご利用の皆様におかれましては、何も作業していただく必要はございません。現在と同様に翻訳機能をご利用いただくことが可能です。
  • Japanize または Mylingual でアカウントを作成し、翻訳作業にご協力いただいている方々におかれましては、サービス移管後に再度アカウント作成をお願いいたします。お手数をおかけし恐縮ですが、個人情報の取り扱いに関しては慎重を期すため、再度ご登録をお願いすることにいたしました。ご理解のほど、よろしくお願いいたします。
  • 移管後のアカウント作成につきましては Twitter 連携で行うことを予定しておりますが、10月29日の段階では間に合わないかもしれません。数日間翻訳作業ができない状況になるかもしれませんが、ご容赦いただければ幸いに存じます。
  • 移管後のアナウンス等につきましては、サービスのウェブサイトおよび、奥の個人ブログ (Kazuho's Weblog) でご案内させていただきます。

以上、両サービスの翻訳にご協力いただいている方々には特にお手間をおかけし申し訳ないのですが、ご理解、ご協力のほど、よろしくお願い申し上げます。

XSSに強いウェブサイトを作る – テンプレートエンジンの選定基準とスニペットの生成手法 (第1回神泉セキュリティ勉強会発表資料)

発表資料は以下のとおり。春山様はじめECナビの皆様、ありがとうございました。

October 21, 2010

Compressing URLs in your Webapp, for size and speed

Last year I had a chance to talk about the internals of our service: Pathtraq at Percona Performance Conference (slides), in which I described the methods we use to compress the URLs in our database to below 40% of the original size, however had not released the source code since then.  I am sorry for the delay, but have finally uploaded the code to github.com/kazuho/url_compress.

It is generally considered difficult to achieve high ratio for compressing short texts.  This is due to the fact that most compression algorithms are adaptive, i.e., short texts reach their end before the compressors learn how to encode them efficiently.

Our approach uses an algorithm known as "static PPM (prediction by partial matching)", that uses a pre-built table for compressing tables.

By using static PPM it is possible to achieve high compression ratio against hostnames or domains (e.g. "www" or "com") or English words that occasionally appear in paths or query parameters (e.g. "search").  And even in case of compressing unknown words in URLs the method works fairly well by utilizing the lower-order probability prediction tables for syllable-level compression.

The repository includes the source code of the compressor / decompressor (the core of the compressor; an optimized range coder using SSE, based on the work by Daisuke Okanohara, is actually git submoduleed from github.com/kazuho/rangecoder), Perl scripts for building compression tables, a small URL corpus for building and evaluating compression tables, and source code of a MySQL plugin that can be used to compress / decompress URLs using SQL.

By following the instructions in the README you will be able to build the compressor that compresses the URLs in the corpus to 30.5% in average, and use it in your MySQL database to store URLs more efficiently.  And one more thing, the benefit is not only for space efficiency.  Since the compressor is designed so that prefix search can be performed without actually decompressing them, in some cases your query becomes faster if you store the URLs in compressed form :-)