【論文読み】Adaptive Focused Crawling

画像

内容

Abstract

Webサイトが増加しており、特定のキーワード・トピックに関するページを効率的に収集したい。
そこで、Ant Basedなクローラーを利用するといい。

アントコロニー最適化は

  • 動的性 よって、流動的なウェブに対応できる
  • 環境に対する近く
  • 個としてはシンプルなため、実装しやすい
  • ランダム性と軽い計算量

という面でクローラーに向いている。
また、Webの構造自体がグラフであるため、そういった意味でも嬉しい。

アルゴリズム

サイクル$cycle$回で行われる。

$t$サイクル目では、

・蟻の確率による移動
・構築したパスにフェロモンをつける

を$N$体の蟻$k$に対して行う。

蟻の確率による移動は頂点$i$から、いける頂点集合$to$に対し、
$j$にいく確率をフェロモンから計算している。

そして、それを繰り返して確率的に移動したあと
フェロモンをつけるために、移動したパスを評価して、フェロモンを添付する。
どう評価するかはぼやっとしか書いてなく、キーワード・ユーザの嗜好にあっているか?しか書いていない。

メリット

  • ウェブページは自己完結でなく、エッジのつながりによって、成り立つため、エッジに意味をフェロモンで持たす、ACOは直感的に嬉しい
  • フェロモンを使うことで必要ないページをスクレイピングする可能性が減る。
  • ユーザがクエリを変えてもACOなら対応できうr
    • 動的性なアルゴリズムフレームワークなので

感想

実際に行った形跡はないが、内容自体は分かりやすく正しい。
他の論文で実際にスクレイピングしているので正しいと言える。