« Announce: The Transfer of Mylingual.net | Main

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: パストラックにおいては、事前計算のみではなくリクエストベースで注目度を計算して表示したりもしていました

TrackBack

TrackBack URL for this entry:
http://bb.lekumo.jp/t/trackback/404050/25394671

Listed below are links to weblogs that reference アクセスログからアテンション(注目情報)をデータマイニングする手法について:

Comments

>しかし実際は後者の方が、より重要ではないでしょうか。
>ですので実際には、パストラックでは、累乗の指数を機能ごとに調整することで、この問題に対応していました。

そういうときは偏差値を使うのがいいと思いますよ。

When visiting blogs. i always look for a very nice content like yours “   

Very good blog you've got here.

Thanks a large amount for this, I am greatful for that the information

Post a comment