情報の分類・推薦アルゴリズムとクロール問題

Web

ゴールデンウィークが終わって*1 ネット世界に戻ってきたところ、Gunosy 騒動 とやらで賑わっていました。クロール問題（どうやって効率的に対象となる URL をクロールするか）は私自身も苦労している部分なので、何か書いてみます。

情報の推薦（レコメンデーション）や分類（カテゴライズ、ランキング、等々）を行う Web サービスを作成・運営する場合、大雑把に分けると以下の 2 つのフェーズが存在します。

  1. Web 上から対象となる情報（主に URL）を収集する
  2. 収集した情報を何らかのアルゴリズムに従って分類・推薦する

今回のお話の結論を先に書いてしまうと、「アルゴリズムやコンセプトの検討段階では 2. のフェーズ（情報の分類・推薦）を非常に重要視するが、実際に Web サービスが出来あがって運用する段階になると、むしろ 1. のフェーズ（情報の収集）に苦心する事が多い」と言うものです。

SoGap の分類アルゴリズム

例えば、私が個人的に運営している Web サービスの一つに SoGap と言うものがありまして、何をやっているのかと言うと、「はてなブックマーク数、Twitter のツイート数、Facebook の「いいね！」数の 「ギャップ」を利用して、それぞれのソーシャルサービス内で尖っている話題を見つけるための Web サービス」と言うものです。

この Web サービスの分類アルゴリズムの概要は SoGap - SNS 間での話題性の「ギャップ」を利用したカテゴライズ&ランキング と言う記事に記載しているのですが、大したアルゴリズムではないので実コードをそのまま載せてしまうと、以下になります。

# dataset は、以下になります（数字は適当）
# dataset = { :twitter => 100, :hatena => 20, :facebook => 50 }
# base に :twitter, :hatena, :facebook を指定するとその値をベースに計算
# @alpha = 10 (パラメータ)
def calculate(dataset, base = nil)
    return 0.0 if (dataset == nil || dataset.size == 0)
    return 0.0 if (base != nil && !dataset.has_key?(base))
    return 0.0 if (dataset.values.max < @alpha)
    
    if (base != nil)
        source = dataset[base]
        v = dataset.reject { |key, value| key == base }.values
    else
        v = dataset.values.sort { |x, y| y <=> x }
        source = v.shift
    end
    
    compared   = v.push(@alpha).max
    quotient   = source / compared.to_f
    difference = [source - compared, 0.0].max
    return quotient + Math.sqrt(difference.to_f)
end

さて。ここまで、コンセプトと具体的なアルゴリズムを考え、サンプルデータに対して適用した結果もまずまずと分かったまではいいのですが、実際の運用を考える段階になるとどうやって母集団となる情報を収集（クロール）しよう？と言う問題を考えなければならなくなります。

クロールと RSS フィードとはてなブックマーク

「Twitter と Facebook とはてなブックマークで話題になっている情報 (URL) を収集する」と言う課題を考えるにあたって、最も簡単にかつ確実に実現できるものは「はてなブックマーク」となります。

はてなブックマークは非常に細かい粒度で RSS フィードを提供しており、例えば、http://b.hatena.ne.jp/entrylist?mode=rss&sort=eid と言う RSS フィードからは、直近 30 件の「1 つでもブックマークの付いた URL」を取得する事ができます。話題になっている情報のみを取得したいと言うのであれば、http://b.hatena.ne.jp/entrylist?mode=rss&sort=hot&threshold=10 のように、threshold の値を適当に調整すれば、それに相当する URL のみを取得する事も可能です。

このように、はてなブックマークに関して言えば、自分にとって必要な条件になるような RSS フィードを定期的に取得していけば、（はてなブックマークで）話題になっている全ての URL を簡単に取得する事ができます。

しかし、他の 2 つの Web サービス（Twitter、および Facebook）に関しては、そう言ったものは提供されていないので、何とか自力で取得する方法を検討しなければなりません。例えば Twitter については、Twitter Streaming API を用いる事によって全ての呟きを取得する事ができるので原理的にはそこから URL を抽出すれば良いのですが、実際問題としては、呟きの量が非常に膨大な事や API の制限等の問題もあって効率的に取得するのはなかなか大変な作業となります。Facebook に関しては……どうずればいいんでしょうね。

こう言った事情もあり、Web サービス開始直後（クロール技術が成熟していない段階）においては、母集団となる情報（URL 群）に占めるはてなブックマークの割合が高くなりがちです。SoGap も現在でこそ、母集団に占めるはてなブックマークの割合は 30%〜40% 程度ですが、かなり最近まで、その多くをはてなブックマークに頼っていました。

アルゴリズムの評価と実際に運用する事との間の壁

私は学術的な研究分野から離れて久しいので、実際にどう言った形でこの類の提案手法（アルゴリズム）の評価が行われるのかはっきりとは分からないのですが、自分の経験上では、「予め用意したサンプルデータに対して提案手法（および比較対象となる手法）を適用し、有用性を確かめる」と言う評価手順が多いように思います。つまり、（情報の推薦や分類のような）研究の評価段階においては「どうやって提案手法を適用する対象となる情報（母集団）を収集（クロール）するか」と言う課題については、あまり深く検討されていない可能性があります。

一方で、実際に Web サービスを運用する段階になると、主眼を置いて研究しているアルゴリズム以外の部分に関しても方法を検討する必要があります。この「それ以外の部分」を軽視すると「アルゴリズムの評価段階では良かったんだけど、実際に運用し始めてみるとイマイチ」と言う結果にも繋がってしまい、ここに「アルゴリズムの評価」と「実際の運用」との間に壁が存在します。

だからと言って「アルゴリズム自体に価値がないのか」と問われると決してそんな事はありません。ただ、今回の騒動を見て「ユーザは最終的なアウトプットのみで評価する（最悪、アルゴリズム自体に意味がないかのような主張をし始める）」ので、自分の Web サービスの「強み」はどこで「今後の課題」は何かをうまく切り分けられる説明ができるように準備しておく事も必要なのだろうなぁと思いました。

Related Pages

*1:書きかけで放っておいたら、1週間位過ぎてしまいました……