専門知識の仕入れ方

oxy
エンジニア

2011-09-18 11:08:25

吉田です.
今日は,普段どのようにして専門知識を仕入れているかについて書いてみようと思います.特に自分が得意でない分野を知りたいと思った時に,どうするかに注目したいと思います.自分の専門の場合は,いくらでも時間を注ぐことが出来るので,世界中のリソースを全て探し当てて勉強すれば良いのですが,ちょっと興味が有るぐらいではそこまでやる時間は取れません.なので出来るだけ効率的に分かった気になるのが目標です.

線形識別器でカーネルトリックを使う方法

preferred

2011-09-05 16:01:47

WEB+DB PRESS Vol.64に「作って学ぶ日本語入力」という特集記事を書かせていただきました。徳永です。全国の書店で発売中ですので、ぜひみなさんお買い求めください。(宣伝)

さて今回は、線形識別器でカーネルを使うのと同じ効果を得るための手法を紹介したいと思います。

続きを読む »

最近傍探索2011

岡野原 大輔

2011-08-05 19:25:57

こんにちは、二台目のmbaを買うのをためらっている岡野原です。

アイテム集合に対し、与えられたアイテムと似ているアイテムを求める、という近傍探索問題は古典的な問題でありながら、現在でも多くの改善がされています。特に言語情報、画像情報、行動履歴情報、生物情報、購買情報などありとあらゆるデータが高次元中の点として表現されるようになってきており、こうしたデータの最近傍探索は広い分野で応用範囲がある技術になっています。

アイテムが低次元(例えば2, 3次元)の場合はkd木や最近だとwavelet木を使う方法がありますが、今回扱うケースは各アイテムが高次元(数百万次元)中の点であったり、アイテム間の距離のみが定義されている場合(カーネル関数など)です。アイテム数は数万から数億ぐらいを想定しています。

最近傍探索問題はいくつかありますが、例えばk近傍グラフ構築問題では、

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、全てのアイテムxにそれぞれについて、それらから最も近いk個のアイテム(k近傍リスト)、kNN(x)を求めよ」

となり、近傍列挙問題では

「アイテム集合X = x1, x2, …, xnと、それらのアイテム間の距離が与えられた時、距離がt以下のアイテムペアを全て列挙せよ」

といった形になります。

この問題に対する自明で最も単純な方法は、全てのアイテムについて、他のアイテム全ての距離を計算し、最小k個を求める方法です。この場合、距離計算はn^2/2回行う必要があり、アイテム数が数百〜数千ぐらいまでしかスケールしません。

この問題に対しては、アイテム一つずつ近傍探索するのではなく、全てのアイテムの近傍探索をまとめて解くことで、高速に求めることが出来る方法がいくつか存在します。今回はそのなかでも実用的で新しいアイディアに基づいているものをいくつか紹介します。

Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measures

PDF
W. Dong, M. Charikar, and K. Li, WWW 2011

なぜ誰も思いつかなかったのか(ルーターのMST決定とかで見たような)というほど単純なアイディアで近傍探索を高速に求めるアルゴリズムです。
このアルゴリズムの基本アイディアは、「近傍の近傍は近傍になりやすい」ということです。それぞれのアイテムが自分の現状の近傍リストを持ち、近傍の近傍に今のリストに入っているアイテムより近いものがないかを調べて、近傍リストを逐次的に改善していきます。

各アイテムxについて、そのk個の近傍アイテムをB[x]で表すことにします。逆に、アイテムxを近傍だとしているアイテムの集合をR[x]とします。B[x]は常にk個なのに対し、R[x]はk個とは限らないことに注意してください。また、B[x]とR[x]の和集合をU[x]とします。

はじめに、各アイテムxについて、B[x]をX中のランダムなk個で適当に決めます。次に、各点xについて、その近傍の近傍、つまり、U[x]の中から一つアイテムyを選び、さらにU[y]の中の各アイテムzについて、それが自分の今持っている近傍リスト中のアイテムより近いかどうかをチェックし、近ければ近傍リストを更新します。これを収束するまで繰り返します。

この方法は近傍リストを逐次的、Greedyに更新していくので、kNNの最急降下法という説明が論文ではなされています。

基本的なアイディアはここまでなのですが、改良ポイントが四点あります。

一つ目がlocal joinです。先程のような更新方法をとる場合、近傍の近傍でループを回すとメモリアクセスに局所性がありません。例えば、a – b で aとbが近傍ということを表すと、先ほどは a – b – cの関係にある時、aを固定してループを回して、cがaの近傍に入るかというのをチェックしています。local joinでは bを固定して、bの近傍二つa, cをとってきて、それらがそれぞれ自分の近傍リストを更新できるかどうかをチェックするようにします。こうすることによって、計算量自体はかわりませんが、メモリアクセスの局所性が増し(各アイテムの近傍リストを二重ループするだけ)、高速化することができます。

二つ目がincremental searchです。近傍リストは後半になってくると収束して殆ど更新されなくなってきます。そこで、近傍リストに新しく入ったかどうかを各アイテム毎にフラグとして持っておき、local joinで調べるときには少なくとも片方が新しく入った場合だけチェックをするようにします。

三つ目がsamplingです。local joinの時に実際に全部をチェックするのではなく、適当にサンプルしたものだけをチェックするようにします。次回のサンプリングでは前回サンプリングされなかったものを選ぶようになります。近いのであれば、どれかの近傍には入っているので、全部調べるのは冗長という考えにもとづいています。

四つ目はEarly Terminationです。収束してきたら、近傍リストの改善は少なくなってくるので、適当なところでやめてしまいます。

実験では画像データや言語データなどいくつか試していますが大体傾向は同じです。iteration回数はどの場合でも4,〜5回程度で収束し、その時の再現率が9割前後(本当の近傍のうち9割程度見つかる)、データ数nに対する計算量は 多くのデータでO(n^1.14)です。
このアルゴリズムでは逐次的に近傍リストを更新していくのでアイテムの追加や削除、更新についても効率的にサポートできそうです。

結果で気になるのはデータの種類や量によらず計算量のオーダーが常に同じ(小数点第2位まであう)だということです。近傍グラフの性質がスモールネットワークのように一定以上の量になると法則が現れてくるのでしょうか。

今後の改善の余地があるとすれば、理論的な解析をするのと、更新にランダム性をいれたりMCMCのような枠組みをいれることで局所最適ではなく大域最適な結果が見つかるようにできるかということです。

Scaling Up All Pairs Similarity Search

pdf
R. J. Bayardo, Y. Ma, and R. Srikant, WWW 2007

次に紹介する方法は各アイテムが疎で高次元な特徴ベクトルの場合に向けての方法です。先程の方法では結果は近似でしたが、今回の方法は正確な結果を返します。
話を簡単にするために距離がcos類似度(高ければ高いほどよい)の場合であり、各特徴ベクトルのL2ノルムが1に正規化されているとします。また、cos類似度が閾値tを超えたものだけを見つけたいとします。
#そうでない場合については論文を参照してください。

このような特徴ベクトルが疎で、内積ベースで距離を計算する場合にまず考えられることは、情報検索のように各特徴毎に、それが発火したデータと、特徴値を保存した転置ファイルを構築し、それを利用して内積を計算する方法です。しかし、この転置ファイルを利用する方法には問題が三つあります。
一つ目は、そのまま計算してしまうと(x, y)と(y, x)の二つの類似度の計算をしてしまうという問題、二つ目は全部のデータを読み込んで、それに対して転置ファイルを構築した後でしか結果を出せないという問題、三つ目は転置ファイル自身が元のデータと同じサイズだけ必要で作業領域量が大きいことです。これらを解決していきます。

まず最初の改善では、初めに転置ファイルを作るのではなく、データを順番に調べていって、その時に一緒に転置ファイルも作っていく方法です。データをx1, x2, …, xk-1までみていった時、ここまでのデータに対する転置ファイルを構築します。そして、xkを調べるときには(x1, xk), (x2, xk), …, (xk-1, xk)の類似度が閾値より大きかどうかをチェックします。これにより、対称部分の計算の重複がなくなりますし、また、データ全体を読み込まなくても結果を返すことができます。

二つ目の改善では、転置ファイルを全て作らずに関係しそうなところだけを作る方法です。特徴毎に発火数に大きな偏りがあることをうまく利用し、転置ファイルには珍しい特徴だけが含まれるようにします。アイテムxについての転置ファイルを構築する際には、xの発火している特徴を、転置ファイル中でのエントリ数が多いものから順番に調べるようにします。次に値bに現在みてきた特徴と、他のアイテム全てのうち特徴値が一番大きいものを計算したときの内積を保存します。そして、閾値がtの時 b < tの間は転置ファイルに登録せず、元のデータに登録しておき、b >= t になった時から転置ファイルに登録するようにします。

これらの改良により、転置ファイルは、実際に閾値tを超える可能性がある場合のみ転置ファイルに入るようにあります。そして、転置ファイルにひっかかって類似度を計算するときには、転置ファイルによって計算された分にくわえ、残されたアイテムからの類似度計算部分を調べます。転置ファイルのエントリ数が大きいものから小さいものに順に調べているので、大部分の転置ファイルをつくらずにすむようになり、使用容量の大幅な削減と計算時間の削減が達成できます。

三つ目の改善では、データを、それが持つ特徴値の最大値が大きい順番に並び替えます。そして、転置ファイルを作る時と、それを利用して閾値がtを超えるものを調べる両方の時に枝刈りを行います。これにより、転置ファイルが作る量と、実際に候補が出る量の両方が大幅に減らすことができます。

またこの他にも、特徴ベクトルがbit列である場合や、距離がcos類似度ではない場合向けの最適化も紹介しています。

これらの最適化を適用することで何も最適化を施さない場合と比べて数倍から数十倍、他の手法(例えばLSHを使う場合)などと比べても数倍の高速化が達成できたと報告しています。

その他

この他にも、注目すべきトピックがいくつかありますので要点だけ述べておきます。

“Hashing with Graphs

W. Liu et. al, ICML 2011 pdf

アイテムの集合からアンカーポイントと呼ばれる少数の点を選んだ後に、各アイテムをそれから一番近いk個のアンカーポイントが張るsimplex上で表します。そして、アイテムaとアイテムbの間の近さを、aから関係する各アンカーポイント、そしてそれらのアンカーポイントからbへの近さをあわせて測るようにします。このように作られた行列はいくつも良い性質があって、例えば隣接情報は非常に疎に表せることができますし、またグラフラプラシアンなどを高速に求められるという特徴があります。この論文では、グラフラプラシアンを使った符号化に注目していましたが、アンカーグラフの方はいろいろな用途に使えそうです。

詳しく知りたい方はbeamさんによる解説や、nokunoさんによる解説をどうぞ

Kernel-based similarity search in massive graph databases with wavelet trees

Y. Tabei, K. Tsuda, SDM 2011 pdf

k個以上の共通要素を持つアイテムを求める問題をwavelet木を使うことで高速に求めています。wavelet木を利用することで、アイテム数に依存せず共通要素を調べることができます。
これまではほぼ全探索しかできなかったgraph向けの近傍探索を非常に大規模にこなすことができるようになっています。

田部井さんによる解説もどうぞ。

ユニークなクラウドソーシング・プロジェクト

祢次金 佑
エンジニア

2011-07-11 11:51:03

こんな暑い日はTDSに行きたい祢次金です。

機械には難しい大量のタスクを不特定多数の人間に依頼できる、クラウドソーシング。有名どころはAmazonのMechanical Turk(以下、Mturk)かと思いますが、最近では機械学習や自然言語処理の研究で、学習データへのアノテーションタスクに活用されることもあるそうです。

機械学習とは関係ありませんが、先日見たTEDのプレゼンテーションの中に、クラウドソーシングを利用した面白いプロジェクトがありましたので紹介したいと思います。

このプレゼンテーションは現在Google Creative Labに所属するAaron Koblin氏によるものです。プレゼン中の、クラウドソーシングが絡むプロジェクトから幾つかピックアップします。

続きを読む »

FCRC 2011参加報告

oxy
エンジニア

2011-06-18 08:16:31

吉田です。
先日、アメリカのサンノゼで開催されたFCRC (Federated Computing Research Conference)に参加してきましたので、その様子について報告したいと思います。
写真は最終日に遊びに行ったスタンフォード大学の門です。奥に見える(見えない?)建物まで歩かないとキャンパスに辿り着きません。アメリカの広さを感じます。
続きを読む »

MapReduce以外の分散処理基盤BSP, Piccolo, Sparkの紹介

preferred

2011-06-17 14:32:34

どうも,実は今年から開発チームにjoinしていた中川です.可愛い犬の写真がなかったので,可愛いマスコットの画像を貼っておきます.

最近MapReduceとかその実装であるHadoopとかをよく聞くようになりました.これはつまり,それだけ大量のデータをなんとか処理したいという要望があるからだと思います.しかし当たり前ですが,MapReduceは銀の弾丸ではありません.

ということで,最近気になっているMapReduceとは違ったアプローチを取っている分散処理基盤について,社内のTechTalkで話した内容を簡単にまとめて紹介したいと思います. 続きを読む »

多項式フィッティングのワナ

preferred

2011-06-15 20:12:45

Meow

今回は新しい試みとして、かわいい柴犬の画像によっていろいろなことをごまかすことにチャレンジしています。なお、画像はflickrからCCライセンスのものをお借りしております。画像をクリックするともっと大きいのが見れるよ。

続きを読む »

最近のtrieの話(xbwなど)

岡野原 大輔

2011-05-20 19:24:32

岡野原です。
ブログの更新がとまっていましたが、また少しずつ更新してきたいと思います。
今回はtrie(トライ)の最近の話をしたいと思います。
trieはキー集合を扱うためのデータ構造の一種です。例えば、単語集合からなる辞書であったり、クロールしたURL情報を扱ったり、最近だと、KVS(Key Value Store)のようにキーを介してデータを保存、読み込みをしたりと様々な場面で利用されます。
trieは図にあるように、木構造で各枝に文字が付随しており、根から葉へのパス上に付随する文字をつなげた文字が各キーに対応します。
同じようにキー集合を格納するデータ構造としてハッシュを利用する方法があります。キーからハッシュ値を計算し、その場所に文字列へのポインタを格納しておくデータ構造です。ハッシュを利用した場合とtrieを利用した場合の一番の大きな違いは、trieの場合だと、ある文字列から始まるキーを全て列挙する、いわゆる接頭辞探索ができることです。例えば”te”で始まる文字列を網羅的に調べることができます。木をたどって、”te”の下にある葉を全て列挙するだけです。hashはこの操作を効率的に行うことはできません。同様に辞書式順序でxよりも大きく、yよりも小さいキーを全て列挙するといったこともtrieは効率的に実現できますが、hashだとできません。
trieの大きな問題点として、木構造を格納する必要があり作業領域量が大きいという問題がありました。そのまま木構造を素直にポインタベースで実装してしまうと、元のキー集合に対しその数倍の作業領域量を必要とする場合も少なくありません。
この問題は簡潔木を利用することで解決できます。このアイディアを実装したものがtx, uxなどです。私もお世話になっているGoogle IMEもtxのクローンであるrxを利用することで大規模辞書を効率的に管理しています。
木構造を圧縮すると、元のキーをそのまま格納するよりも小さく格納できるようになり、データ圧縮としても利用することができます。trieでは文字列の先頭部分(接頭辞、prefixと呼びます)を一つのパスとして表現することができるためです。しかも、通常のデータ圧縮とは違って、データ全体を復元しなくてもあるキーのみを復元するということができます。
簡潔木を利用したtrieについての情報は既にある程度広まってきているので、今回は簡潔木を利用しないtrieの最新情報についていくつか紹介します。

XBWを利用したtrie

[1] “Structuring labeld trees for optimal succinctness, and beyond”, P. Ferragina, and et. al. FOCS 2005
[2] “Succinct Dictionary Matching With No Slowdown”, D. Belazzougui, CPM 2010
[3] “Faster Compressed Dictionary Matching”, W. K. Hon, and et. al. SPIRE 2010

ラベル付木に対する簡潔データ構造であるxbwは[1]により最初に紹介されました。その後[2], [3]の論文で、さらにxbwはシンプルになり高速化されています。

xbwについて簡単に説明します。

ノードから根に向かって辿った時の文字列をつなげた文字を、そのノードのreverse prefix pathと呼ぶことにします。次に全ノードをreverse prefix pathの辞書式順序でソートします。複数のノードが同じreverse prefix pathを持つ場合がありますが(trieの場合は無いが)、その時は木中の幅優先探索の順序順で順番を決定するとします。最後に各ノードの子に付随する文字をその順に格納します。これがxbwです。先ほどのtrieの場合の例を以下の図に示します。列reverse prefix pathは各ノードから根に向かうパスであり、末尾は特殊文字$がつけてあります。この$は他のどの文字よりも小さいとします。列childrenにそれぞれのノードに対応する子に付随する文字を格納します。ここで#とあるのはそこが終端ノードであることを示しています。この#は他のどの文字よりも大きいとします。children内部での順序は関係ありませんので集合で表すことにします。例えばchildren[1] = {t, i, w}, children[3] = {a, n}です。

結論を先に言うと、このchildrenの列だけを使って先程のtrieを完全に表現することができます(reverse prefix pathはいらない)。

実際に節点をchildrenの情報だけを使って辿ってみましょう。

rank(i, c)をchildren[1…i-1]中に含まれる文字cの出現数と定義します。また、C(c)を全てのchildren中で”c”より小さい文字の出現個数とします。例えばこの図の例ですとですとC(a)=0, C(e)=2, C(i)=4…となります。
まず、図中の根のノードに着目してみます。先程の表では、i=1となります。ここからラベル”t”を辿った場合、次に行くべきノードのreverse prefix pathは”t$”です。このノードは”t”で始まるreverse prefix pathを持つノードの中では最小のはずです。よって”t$”を持つノードはC(t)+1 = 10となります。

では、次にこのノードからラベル”e”を辿るとすると、その節点は”et$”をreverse prefix pathとして持つはずです。”e”で始まるreverse prefix pathを持つノードの数は、children[1…9]の中で”e”を持っている数に一致します。なので、”et$”に対応するノードの番号はC(e)+rank(10, e)+1=3となります。

このように、現在iの位置にいる時に文字cを辿った先のノード番号は

C(c)+rank(i, c)+1

として求められます。C(i, c)+1は文字”c”から始まるreverse prefix pathを持つノードが始まる添字番号であり、rank(i, c)はその中での順番です。

既にお気づきの方も多いと思いますが、これはBWT (Burrows Wheeler Transform, BlockSorting) におけるLF-mappingと同じ考えです。bwt(block sorting)は一本鎖のパスからなる木に対するxbwであり、xbwはbwtの自然な拡張になっています。

さて、このchildrenのテーブルをどのように効率的に格納し、rankを高速に求められるかが問題です。BWTの場合はここが文字列になっていたため、wavelet treeを利用することができました。今回は各位置に複数の文字が存在します。[1]では、ビットベクターと組み合わせることによって、集合を文字列にしてしまい、文字列に対するrank操作の問題に還元しました。[2], [3]では、各文字ごとに、転置ファイルのようにその位置に文字cが出現したかどうかをbit vectorで記録し、bit vectorに対するrank操作としてこれを実現します。どちらも、trieに対するk次経験エントロピーに漸近するサイズで格納できるということが示されています。

さらに、[3]では、このxbwを利用してAC法が実現できることが示されています。

木を潰したtrie

[4] “On searching compressed string collections cache-obliviously”, P. Ferragina, and. et. al. PODS 2008
もう一つ面白いtrieがFerraginaらによって提案されています。
論文にはcache-obliviouslyとありますが、注目すべきはcentroid path decompositionです。従来のtrieは遷移するノード数分だけランダムアクセスが発生しており問題になっていました。特にデータをディスクなどに格納している場合、アクセス回数が操作時間に直結するために問題になります。centroid path decompositionは元々の木を縦方向にぐしゃっとつぶします。
イメージだけでも掴んでもらうために、図を論文から借りてきました。左側の元のtrieの太い線に対応するpathをぐしゃっと一つのノードに潰します。このpathの付随するノードは、このpathの左上から順に右上まで反時計回りの順に大小関係が決まります。そのノードにはheavy pathのラベル列と、そのパスから分岐しているノードが何文字目からどのどの文字で分岐しているかの情報を記録しておきます。この情報により潰した後でも木を辿ることができます。
実際どのようにして潰すpathを決めるかについて説明します。
各ノードについて、その子の中で、最も子孫の葉の数が多い子を、そのノードのheavy childと呼びます。次に、各ノードについて、そのノードから葉までheavy childrenのみを辿っていくpathをheavy pathと呼びます。これを利用したcentroid path decompositionは次のように実行されます。まず最初に根に対応するheavy pathをたどってそのpathを一つのノードに潰します。次にそのpathから分岐して伸びている各ノードについて再帰的に同じようにheavy pathを辿って、そのpathを一つのノードに潰すというのを繰り返します。
この操作により、キーの種類数がK、文字種類数がSの時、木の高さは高々 O(log K)個になり、平均して O(log K / log S)個になります。どんなに高い木でもその順序関係を損なうことなく、木の高さを減らすことができ、アクセス回数を減らすことができます。
各節点での分岐数は増えるため、各節点での計算量は増えますが、アクセス回数が減らせることによりメリットは大きい場合が多いです。
この木に対する簡潔データ構造も論文中に提案されています。

Weak Prefix Search

[5] “Fast prefix search in little space, with applications”, D. Belazzougui, and et. al. ESA 2010
最後に紹介するのがweak prefix searchをサポートしたtrieです。
クエリ文字列pに対し、そのクエリ文字列が辞書中のどれかのキーの接頭辞である場合、そのキーの辞書中の辞書式順序の順位を返す操作をweak prefix searchと呼びます。
もし、クエリ文字列が辞書中のどれかのキーの接頭辞で無い場合、結果は保証せずランダムになります。
よって、weak prefix searchはbloom filterのようにone sided errorを許したデータ構造です。例えば、キー集合が{abc, abef, bcde}の時、abcに対しては1, abeを入力したら2、abcdeならランダムな値が返ってきます。
これまでもweak prefix searchを備えたデータ構造はString B-tree (blind  trie)などがこうした機能を有していました。
weak prefix searchは従来のtrieよりも弱い操作です(従来のtrieであれば、無い場合は無いと返すことができる)が、その分作業領域量は少なく抑えることができます。この論文では、
この問題を解くために必要なデータ構造は、従来のキーを格納するよりはるかに少ない作業領域量だけあればよいことを示しました。具体的にはキーの数がK、キーの平均長がLの時、必要な作業領域料はO(K log L)ビットになります。従来だとK Lビット だったのと比べると大きな違いです。
この論文ではz-fast trieを改良したHollow z-fast prefix trieとrange locatorを組み合わせてweak prefix searchを実現します。2-fattest numberなどいろいろ面白いアイディアを利用しています。

最後に

これまで話してきたtrieは実はいずれも動的なキーの追加・削除をサポートせず、前もって与えられたキー集合を扱っていました。
キーの追加・削除をサポートした上で、データをコンパクトに保ちつつ、高速な操作を実現するようなtrieは実現できるのか? これについてはまた紹介します。

論文輪講:Temporal Diversity in Recommender Systems

preferred

2011-04-18 18:45:06

PFIでは今年の4月から有志で論文の輪講を始めました。有名な学会の論文を毎回二人ぐらいが読んできて、資料を作って発表する、という形になっています。(ちょっと前まではTAPL輪講というものをやっていました。論文輪講が落ち着いたら、次はまた教書に戻るかもしれません。)

私も先日発表をしてきたので、その資料を元にこちらの方でも論文紹介を行いたいと思います。

私が担当したのはSIGIR 2010のFiltering and Recommendationのセッションで、以下の3本の論文を紹介しました。

  • Temporal Diversity in Recommender Systems
  • Social Media Recommendation Based on People and Tags
  • A Network-Based Model for High-Dimensional Information Filtering

この3本の中から、今日は Temporal Diversity in Recommender Systems (N. Latia et al.) を紹介したいと思います。

続きを読む »

東北沖地震震災 リアルタイム情報 QuakeMeme.jp を公開しました

preferred

2011-03-23 10:55:36

iPhoneの充電池付きケースを買ったのに、ケーブルが特殊で1本しかなく、オフィスに忘れて結局充電出来てない事態に悩まされている、太田です。

はじめに

PFIでは、QuakeMeme.jpというサービスを公開致しました。「Twitter」のデータを元に、今回の東北沖地震に関する有用なURLをカテゴリ分けして収集するサービスです。

他の地震関係のサービスと比較したQuakeMemeの特徴は「情報鮮度 (リアルタイム性)」です。例として、大きな余震等が起きた時には、数分後にその余震に関する情報がQuakeMemeの上位に表示されます。

またQuakeMemeの全ての結果は機械的によって抽出されたものです。Twitter上ではデマの様な情報も多い中、割と有用な情報を優先的に抽出出来ているかと思います。

このブログエントリでは、このサービスの裏側を少し紹介したいと思います。主に、以下の3つの処理が行われています。

1) 特定のhashtagから、UserStreamAPIでTweetをクロール

まず人手で、約200個の地震関連hashtag (例: #anpi, #jishin, etc.)を収集しました。それをTwitterのUserStream APIに与えると、地震関連のテーマに絞ったツイートだけが抽出出来ます。これにはRT等も全て含まれます。現在は秒間50ツイート程度を収集しています。

このツイート情報を、弊社の開発している検索エンジンSedueに登録します。Sedueは登録後すぐに検索結果に反映出来るリアルタイム機能を持っています。これによりTwitter検索のような、秒単位で検索結果が変わる検索システムを簡単に構築出来ます。

2) カテゴリに紐づいた単語で検索

次に、人手でカテゴリ情報を整備しました。各カテゴリにはキーワードが紐づいており(例: Home, 安否情報, 原発情報)、このキーワードで検索処理を行います。

キーワードは、人手で登録します。例えば安否情報であれば”anpi|安否”, 原発情報であれば “genpatu|原発” 等のキーワードが使用されています。検索処理を行うと、指定したキーワードを含むツイートがヒットします。

実はこの段階でリアルタイム地震情報検索サービスとしてローンチを考えたのですが、ゴミ情報が多く、どれが有用な情報が分からないという問題が有りました。そこで次の方法を考えました。

3) ヒットしたツイートから、URL情報のみをカウント

最後に、検索にヒットしたツイートの中に含まれる”URL”のみを対象する事にしました。つまり検索にヒットした直近5万件のツイートに含まれるURLを抽出し、かつ登場回数でカウントを行い並び替える事を考えました。

これによって、”カテゴリに付与された単語を含むツイートと、同時に呟かれているURL”が抽出できます。現在のページはこの情報をリスト化して表示しています。

システム構成

その他、具体的なシステム構成としては、以下のような技術を使っています。

  • Twitter UserStream API (Ruby Crawler)
  • Sedueリアルタイム検索エンジン (Search Engine)
  • MySQL (RDBMS)
  • Ruby on Rails 2.3.5 (Web Framework)
  • jQuery (UI)
  • Amazon EC2 (インフラ: c1.medium * 2台)

ソースコード

このサービスのソースコードはgithubにて公開しています。

まとめ

勢いで数日で作ったサービスなので至らない所が有りますが、徐々に改善を行って行きたいと思いますので引き続きよろしくお願いします。

データとしては、Twitter以外にもmixiボイスやamebaなう等も、集めたいです (APIが有れば)。後は、フィードやガラケー/スマホ対応をしたい所。