nakatani @ cybozu labs

Pathtraq 活用第２弾。
Pathtraq では YouTube の動画で人気のあった順(よく見られた順)に一覧ページを作ってくれます。
一方、はてなさんとこの Rimo はページ内の YouTube をさっくりつなげて見せてくれます。

というわけで組み合わせると、「みんなが見ている、人気のある動画だけまとめてさっくり見たい！」というあなたにぴったりな「 Pathtraqが贈る人気のYouTube on Rimo (毎朝自動更新)」のできあがり。

( Pathtraqが贈る人気のYouTube ・ ウィンドウいっぱいで見る ・ blog貼り付け用コードを見る )

だいたい「昨日よく見られた動画」が出てきている感じですね（ Pathtraq 側の集計単位は必ずしもそう言うわけではないんですが）。

まあ実は YouTube の人気の動画一覧や、はてブの注目の動画でも同じようなことはできちゃうんですが、Pathtraq on Rimo の方がちょうどいい雰囲気の動画が並んでいるように思います。
まあそれが母集団の違いなのか、集計単位の違いなのか、動画を埋め込んでるblogの方をブクマしてしまうんで動画そのもののカウントは出てきにくいからなのか、個人の好みなのか、単なる身びいきなのかはあんましよくわかりませんが(笑)。

パストラックは、「社会」「政治」「スポーツ」などのカテゴリごとにページのランキングを見る機能があります。

パストラックの注目・人気・定番のページ一覧で右上のセレクトボックスからカテゴリを選ぶと、そのカテゴリの一覧が表示されます。

例：

「政治」の人気ページ一覧(人気ページ＝昨日・今日あたりによく見られたページ)

http://pathtraq.com/popular?category=Politics

「スポーツ」の注目ページ一覧（注目ページ＝ここウン時間によく見られたページ)

http://pathtraq.com/popular?m=upcoming&category=Sports

「車/二輪」の人気ページ一覧

http://pathtraq.com/popular?category=Motor

「食/グルメ」の注目ページ一覧

http://pathtraq.com/popular?m=upcoming&category=Foods

ちなみに、「Pathtraq が贈る人気ページ」ウィジェットでもそのカテゴリ毎のランキング取得に対応してたりなんかします。

このカテゴリ分類は自動で行っているのですが、ようやくそろそろ語っても恥ずかしくない程度に精度も上がってきてくれたので、「Webページの自動カテゴライズ」という切り口でその裏側をざっくり紹介します。

まず Web ページの自動カテゴライズを行うには、以下の技術要素が必要になります。

• クローラー
• 本文抽出
• 分かち書き
• カテゴライズ

このうち、今回のケースでは対象となる web ページの URL についてはパストラック本体が収集してくれるので、クローラーは特別なものは必要ありませんでした（せいぜいプロキシーとかキャッシュとか細かい最適化のレベルの話）。

本文抽出については話が長くなるので別稿で。

分かち書きには MeCab を利用させていただきました。

本文が抽出できて、分かち書きまで済んでいれば、それ使って分類してくれるなんらかのフィルタの登場となります。
いくつか手法がある中で一般にはベイジアンフィルタが使われることが多いようです。今回のカテゴライズでもベイジアンを採用しました。
ベイジアンは追加学習のコストが低いので、Web ページのように変遷の大きいものについて適しているだろうという判断です。
分類精度が学習量と学習データに対して結構シビアな反応を示すので、そのあたりは結構気を使いますね（スパムか非スパムかという２値の判定ならそこまで神経質にならなくてもいいと思うんですが）。カテゴリー毎の一覧を作成するという点を考えると、分類漏れより間違って分類してしまう方がダメージが大きいので、少し過学習寄りに調整していけばなかなかうまくいくということがわかりました。
ちなみに、ベイジアンなら実装ライブラリがすでにそこそこあるので、自分で実装しなくていいというメリットもあります。

また、カテゴライズはどうしてもやっぱりある程度重い処理になりますし、また Web ページを対象とする場合は日々膨大なデータを処理できる必要が生じるので、一定のスケーラビリティを持たせる必要があります。
今回は、全体を Ruby で実装しており、本文抽出からカテゴライズまでの一連の処理を dRuby を用いて分散実行できるようにしました。
１台の仮想サーバ環境でも１日５０万件程度の処理能力があり、自動分類のようなそこそこ重い処理でこのくらいの速度が出てればいいかなあと個人的には満足してるんですが、光成さんには「 C/C++ で書かないの？」とかささやかれちゃったりします(苦笑)。

あとの課題としては、今後の継続的な学習をどうしていくかというところでしょうか。
学習をも自動化する、というのは別の挑戦として楽しそうではあるんですが、ちょっとハードル高すぎるのでｗ、なんとか半自動化する方向で色々検討しているところです。

ところで、「出来合いのフィルタ」を使ってちゃんとした精度が出るのか？　という疑問を持たれる方もいるかもしれません。
でも自動カテゴライズを作ってみてよくわかったことがあって、実は学習フィルタをどうこうするよりも、本文抽出の精度の方がはるかに分類精度へのインパクトが大きいんですよね。まあ「Webページ」の分類に限った話であるのだろうとは思いますけど。
本文抽出系の話に手を染めたことのある人なら諸手で同意してくれるでしょうが、この「Web ページ」というのは極めてノイズの多い代物で、ちょっと油断するとサイドバーに「本文」より長い宣伝が書いてあったりなんてのは序の口もいいところ。メニューやフッター、関連リンク、コメント/トラックバックなどなどなどなどなどなどをきちんと取り除けているかどうかが分類精度向上の大きな鍵になります。

と、本文抽出の話にきれいに戻ってきたところで、続きは次回「Webページの本文抽出」。
一応、本文抽出のいろいろ泥臭い話とかしつつ、汎用性のある部分についてはライブラリとして公開しようかなと思ってます（まだ日本語特化のコードとか埋め込まれてしまっているので、ただいまそれを除去中）。
乞うご期待？

Webページの自動カテゴライズ の続き。
前回書いたとおり、パストラックで行っている Web ページのカテゴライズでは、Web ページの本文抽出がひとつの鍵になっています。今回はその本文抽出モジュールを公開しつつ、使っている技法をざっくり解説などしてみます。



本モジュールの利用は至極簡単。require して analyse メソッドに解析したい html を与えるだけ。文字コードは UTF-8 です。
【追記】大事なこと書き忘れ。本モジュールは Ruby1.8.5 で動作確認していますが、特別なことはしていないので、1.8.x なら動くと思います。

$KCODE="u" # 文字コードは utf-8
require 'extractcontent.rb'

# オプション値の指定
opt = {:waste_expressions => /お問い合わせ|会社概要/}
ExtractContent::set_default(opt)

html = '' # 解析対象 html 
body, title = ExtractContent::analyse(html) # 本文抽出

本文抽出時に使用するパラメータをオプション値として指定するようになっています。パラメータ値の簡単な説明はソース内に記述しています(すいません、ドキュメントが無くて)。
これらは微妙な増減で結果が大きく変わるので、waste_expressions や decay_factor, continuous_factor あたりを中心に対象とする html や処理に応じてあれこれ調節してみてください。


余談ですが、これまで大なり小なり色々なプログラムを作ってきてますが、実はライブラリの状態で公開するのはこれが初めて。正直、勝手がよくわかってません(苦笑)。
本モジュールのライセンスはひとまず BSD ライセンスとしますが、そんなわけで不都合のない範囲であれこれ変更させていただくようなこともあるかもしれません。あしからずご了承ください。


さて。
パストラックの本文抽出は大きく以下の方針で開発しています。
- 本文を抽出する、というより「本文以外を除外する」
- カテゴライズ精度の向上に寄与する方向でのチューニング。
- 実用本位。極力一般化するが、無理な範囲はプラグインでサイト別に各種ルールを記述。
プラグインでサイト別に記述する、なんてのは誰でも出来る話なので、以下で解説するのは一般的な html に対する本文抽出ロジックに関する工夫のあれこれです(公開したモジュールもちょうどその範囲)。

まず、手を付けるに当たって参考にさせていただいたのが下記記事です。ありがとうございます。

ブログの記事本文を抽出するスクリプトをつくってみた - zuzara

http://blog.zuzara.com/2006/06/06/84/

ブログの本文抽出にチャレンジ - Ceekz Logs

http://private.ceek.jp/archives/002039.html

正確にはこれらの記事を参考に奥さんが作った本文抽出モジュール(Perl版) が社内に転がっていたので、そちらを参考にさせてもらったんですが(笑)。サイボウズ・ラボはそんなところです。はい。


そんなこんなで今回のモジュールで採った方式は下記の通り。

- div, td で囲まれた範囲をテキストブロックとして取り出す
- 句読点の数をそのテキストブロックのベースのスコアとする
- リンクタグ以外のテキスト長の割合をスコアに反映
- 前半のブロックほどスコアが高くなるように傾斜（ここまでが参考にさせていただいた部分)
- 特にリンクリストを判定し、除外する方向でスコアに反映
- アフィリエイトリンク、フォーム、フッタ等に特有のキーワードが含まれていれば、除外する方向でスコアに反映
- スコアの高い連続ブロックをクラスタ化し、クラスタ間でさらにスコアの比較を行う
- (裏技) Google AdSense Section Target を考慮

Web ページにはメニューとかヘッダーとかフッターとかプロフィールとか連絡先とかコメント欄とかトラックバックとか広告とか、とにかく本文以外の「ゴミ」がわんさかついているので、本文を抽出するというより「いかにゴミを取り除くか」に注力しています。
そういった「ゴミ」にはリンクが整列している場合が多いので、リンクリストを判定する方法を３通りほど用意して極力除外。
また広告はアフィリエイトの有無、コメントや検索はフォームの有無、フッターは特徴的な語句が含まれているかで判定できる可能性がある程度あるので、それらも判定。
語句を指定してしまうと当然ながら言語に依存してしまいますが、今回の目的はカテゴライズであり、そのフィルタは日本語に特化して学習しているので、パストラックのカテゴライズでは割り切って日本語の語句をびしばし指定して利用しています。


上にも書きましたように、コメントやトラックバックについても極力除外する方向で開発・チューニングしています。
これらを本文に含めるか含めないかは意見の分かれるところでしょうが、今回の目的はカテゴライズなので、それらはノイズだと判断しました(実際、コメント/トラックバックを含めてしまうと分類精度が落ちてしまうことがわかっています)。
逆に、全文検索のための本文抽出であればコメントやトラックバックも含めたいということも考えられますから、そこは本文抽出のロジックやチューニングに対してケースバイケースが求められる部分になるんじゃないかと思います。


また、評価の高いテキストブロックが連続している場合、それらをひとかたまりにして扱うようにしています。
本文に該当する部分が div や td で区切られてしまっていても(実際、写真の挿入や段組などのために区切られてしまうことが多々ある)、基本的にはそれらは連続していることを反映する形です。
これにより、本文の左右にある比較的文章量の多いテキストブロック(例えばアブストラクト付きの関連ページリンクなど)などを除外しています。


Ceekz さんの書かれていた、

- 直前のエントリと diff を取る
- RSS の description と比較する

あたりのアイデアにも興味はあったんですが、前者はコストが高く、後者は対象として非ブログの方が多いことが想定されたため費用対効果が低く、とりあえずスルー。


で、ここまででもカテゴライズを対象とした場合には実用レベルの本文抽出にたどり着けているのですが。
実は結構強力な裏技がありまして。


Google AdSense が表示する広告は、内容との関連性を高いほど広告効果も高まることが期待されるわけですが、それを支援するために セクションターゲット という仕組みがあります。
これはページ内で「強調したいテキスト」を <!-- google_ad_section_start --> ～ <!-- google_ad_section_end --> などで囲うことで、Google AdSense が表示する広告と照合する際に考慮する、というもの。
それってなんて本文？　なわけで、セクションターゲットに対応しているサイトであれば 100% に近い精度で本文が抜けます。
とりあえず目立つ範囲だけでも asahi.com, livedoor, hatena, gigazine, nikkeibp, mycom, nikkansports, sponichi, fc2.com, atwiki などなどなどなど、かなり多くのサイトが対応しており、今後も増えていくことが予想され(この本文抽出モジュールを作り始めたときはセクションターゲット使ってなかったはずなのに、現在は使っているというサイトがいくつか)、裏技といいつつ本文抽出やるなら見逃せない。
本当に、お金の力は偉大やのう。


ちゃんと母集団を決めて統計をとったりまではしていないのであくまで感覚的な数字ですが、オプション値をチューニングして使えば、ニュース系のサイトの記事ページなら 95%～99% 程度は期待したとおりの本文が抽出できています。
ブログはやはり千差万別なため少し厳しいのですが、それでも 90% は超えているかと。
一方で、一覧系のページ(特にポータルトップ)はもともと本文と言える部分がないに等しく、それを「本文無し」と判定してくれれば御の字なのですが、やはりどうしてもゴミっぽいところを誤って抽出してしまうことはある程度発生してしまっています。そのあたりはまだ課題ですね～。