BETA

【論文読み】Adaptive Focused Crawling

投稿日:2019-10-04
最終更新:2019-10-04

画像

内容

Abstract

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

アントコロニー最適化は

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

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

アルゴリズム

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

$t$サイクル目では、

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

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

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

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

メリット

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

感想

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

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

競プロなどをします。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう