クローリング検索エンジンの第一歩となるWebページを収集するクローラを作る。昔は、クローラというプログラムがWebサーバを渡り歩いてデータを収集し、本部のサーバへデータを送るというイメージを持っていたのだがこれは全く違う。実際は、本部からURLへアクセスしてデータをダウンロードするだけ。実体がサーバを渡り歩くプログラムはモバイルエージェントと言ってクローラとは目的が異なる。urllib2を用いるとWebページを簡単にダウンロードして収集できる。Soupを使うとダウンロードしたHTMLを簡単にパースできる。リンクを表すaタグだけを集めたり、タグ内のhref属性のリンク先だけを集めたりできる。Googleなんかだとクローラを並列に動かして非常に大規模に収集しているらしい。この本では、起点となるページからリンクを次々にたどり、幅優先探索でWebページを収集している。効率的に収集する方法なんかは研究がある。インデキシング収集したWebページは、インデックスという索引をつけてデータベースに保存する。(単語を含むURL、単語の位置)という転置インデックスを作るらしいが、この本ではテーブルの自己結合でやってる(遅くない?)。章末エクササイズにもあるが、ブール検索をしたいときは転置索引の方が楽かも。この本では、pysqlite2というのを使っているがPython2.5にはない?かわりにsqlite3モジュールを使った。データベースへの接続がsqlite3.connect()になるだけであとは同じ。英語のストップワードリストは、SMARTシステムのがここにある。ストップワードとは、索引語として登録しないつまらない(笑)単語のこと。日本語はどうやるんだろ。形態素解析して、助詞とか助動詞は除くくらいはわかるけど、名詞のストップワードリストとかあるのかな?単語をそのままインデックスに格納するのではなく、語幹だけ格納するステミングを施した方がよい。Porterアルゴリズムの実装がここにある。検索クエリに指定したキーワードをすべて含むURLをインデックスから探し出す。この本ではAND検索しか実装してない。OR検索やNOT検索はエクササイズ!テーブルの自己結合でやってるから遅いかも。ランキング探し出したURLをランキングして重要なものから並べて検索結果として提示する。検索のランキング問題と推薦のランキング問題って関係ありそうだけどどうなんだろ。内容ベースの順位付けでは、単語の出現頻度、ドキュメント内での単語位置、指定したクエリの単語間の距離などをもとにURLを重みづけている。重みが高い方が高ランク!いろいろランキング方法を組み合わせることもできるが、どれがよいかいまいちわからなかった。Brinが発明したPageRankはWebページのランキングアルゴリズムの一種。Pageを掛けてるみたいでネーミングがCool!コンテンツ内容ではなく、ページ間の参照関係をもとにランキングする。多くの良質なページからリンクされているページは、やはり良質なページであるという仮定に基づく。コンテンツベースランキングからPageRankへの移り変わりは、コンテンツベース推薦がうまくいかなくて、協調フィルタリングが支配的になったのと似ている。PageRank的なアイデアをもとにした協調フィルタリングも考えられるかも。Winogradの研究室だったんだ。PageRank徹底解説を読んでおくとわかりやすい。この本では、初期値から繰り返し計算する方法でPageRankを求めているが、一般的にはページ間遷移行列の固有値分解問題に帰着させるらしい。Retrievalがよさげ。ただで読めるってのもあるけど(笑)Googleを支える技術も面白そう。大規模システムは別の難しさがあるんだなぁと思う。»プロフィールid:aidiary人工知能とその関連分野に興味があります。Blog|ブログを報告する。