検索とランキング

作者: Toby Segaran,當山仁健,鴨澤眞夫
出版社/メーカー: オライリージャパン
発売日: 2008/07/25
メディア: 大型本
購入: 91人クリック: 2,220回
この商品を含むブログ (277件) を見る

4章の検索とランキングを読んだ。pythonを使ってシンプルな検索エンジンを作ってるけどけっこう感動した。この本すごいよ。技術メモと感想。

1. クローリング

検索エンジンの第一歩となるWebページを収集するクローラを作る。昔は、クローラというプログラムがWebサーバを渡り歩いてデータを収集し、本部のサーバへデータを送るというイメージを持っていたのだがこれは全く違う。実際は、本部からURLへアクセスしてデータをダウンロードするだけ。実体がサーバを渡り歩くプログラムはモバイルエージェントと言ってクローラとは目的が異なる。

urllib2を用いるとWebページを簡単にダウンロードして収集できる。
Beautiful Soupを使うとダウンロードしたHTMLを簡単にパースできる。たとえば、リンクを表すaタグだけを集めたり、タグ内のhref属性のリンク先だけを集めたりできる。
Googleなんかだとクローラを並列に動かして非常に大規模に収集しているらしい。
この本では、起点となるページからリンクを次々にたどり、幅優先探索でWebページを収集している。もっと効率的に収集する方法なんかは研究がある。

2. インデキシング

収集したWebページは、インデックスという索引をつけてデータベースに保存する。一般的には

単語 → (単語を含むURL、単語の位置）

という転置インデックスを作るらしいが、この本ではテーブルの自己結合でやってる（遅くない？）。章末エクササイズにもあるが、ブール検索をしたいときは転置索引の方が楽かも。

この本では、pysqlite2というのを使っているがPython2.5にはない？かわりにsqlite3モジュールを使った。データベースへの接続がsqlite3.connect()になるだけであとは同じ。

英語のストップワードリストは、SMARTシステムのがここにある。ストップワードとは、索引語として登録しないつまらない（笑）単語のこと。日本語はどうやるんだろ。形態素解析して、助詞とか助動詞は除くくらいはわかるけど、名詞のストップワードリストとかあるのかな？

単語をそのままインデックスに格納するのではなく、語幹だけ格納するステミングを施した方がよい。Porterアルゴリズムの実装がここにある。Pythonによる実装もあり！（後で使い方まとめる）

3. 検索

クエリに指定したキーワードをすべて含むURLをインデックスから探し出す。

この本ではAND検索しか実装してない。OR検索やNOT検索はエクササイズ！
テーブルの自己結合でやってるから遅いかも。転置インデックスを使ったら速くなる？

4. ランキング

探し出したURLをランキングして重要なものから並べて検索結果として提示する。検索のランキング問題と推薦のランキング問題って関係ありそうだけどどうなんだろ。

内容ベースの順位付けでは、単語の出現頻度、ドキュメント内での単語位置、指定したクエリの単語間の距離などをもとにURLを重みづけている。重みが高い方が高ランク！
いろいろランキング方法を組み合わせることもできるが、どれがよいかいまいちわからなかった。NTCIRなどの評価セットでどれがよいか評価する？
Googleの創業者L. PageとS. Brinが発明したPageRankはWebページのランキングアルゴリズムの一種。L. PageとWeb Pageを掛けてるみたいでネーミングがCool！
コンテンツ内容ではなく、ページ間の参照関係をもとにランキングする。多くの良質なページからリンクされているページは、やはり良質なページであるという仮定に基づく。
コンテンツベースランキングからPageRankへの移り変わりは、コンテンツベース推薦がうまくいかなくて、協調フィルタリングが支配的になったのと似ている。PageRank的なアイデアをもとにした協調フィルタリングも考えられるかも。
PageRankの原論文は、L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank Citation Ranking: Bringing Order to the Web, 1998。2人はTerry Winogradの研究室だったんだ。初めて知った。
上の論文を読む前にGoogleの秘密 - PageRank徹底解説を読んでおくとわかりやすい。
この本では、初期値から繰り返し計算する方法でPageRankを求めているが、一般的にはページ間遷移行列の固有値分解問題に帰着させるらしい。でも巨大な行列の固有値分解なんてできるのかな？
情報検索に関する教科書は、Introduction to Information Retrievalがよさげ。ただで読めるってのもあるけど（笑）
Googleを支える技術も面白そう。大規模システムは別の難しさがあるんだなぁと思う。