特集Webダイナミクス

Web更新モニタリング
5
山田 誠二

国立情報学研究所

seiji@nii.ac.jp

Webで最新情報をチェック

Web更新モニタリング
代表的なWeb更新モニタリングシステム

インターネットの普及に伴い，今や多くの個人や組織が自分の Web ページを持つに至るほど一般に普及した

Web 更新モニタリングの基本機能である，Web ページ

Web だが，その最も役に立つ特長の 1 つとして，Web ペの情報の更新をチェックし，その更新部分を検出するこージが頻繁に更新されることによる「情報の新鮮さ」がとは，基本的にはプログラムで実現できるため，これま挙げられる．株価，為替レート，ニュース，新聞，天気で Web 更新モニタリングのアプリケーションがいくつ予報など数え上げればきりがないほど，時々刻々と更新か開発されてきた．まずは，これまでの Web 更新モニされ最新の情報を提供してくれる Web サイトが多く存

タリングを理解するために，現在広く使われているシス在する．確かにこれらの Web ページで提供される最新テムとして，電子メールで更新を通知するフリーウェア

情報は，ユーザにとって非常に役に立つものであるが，である ChangeDetect と商用アプリケーションである

最新情報がアップロードされればできるだけ早くそれをWebSpector を紹介する．
2）

知る必要があるため，ユーザは常時それらの Web ペー

ChangeDetect は，NetMind から発展したアプリケージをモニタリングしなければならない．しかし，2，3ションであり，サーバが一括して Web ページの更新をの Web ページならまだしも，監視すべき Web ページがモニタ，管理する．ChangeDetect は，ユーザが更新を多くなると，とてもいちいちチェックをすることはでき通知して欲しい URL と通知メールを送る宛先のメールない．そのため，せっかくの最新情報を見逃してしまうアドレスをサーバに登録する．この登録は，図 -1 のよ経験をされた方も少なくないであろう．このような Webうなインタフェースで行われる．そして，サーバは登録ページの監視を「Web 更新モニタリング」と呼ぶ．

された URL の Web ページをモニタして，更新があるとWeb 更新モニタリングは，Web での情報収集にとってメールでユーザに通知する．モニタリングの対象として非常に重要な問題であり，これまでもいくつもの Web

いるのは，基本的に 1 つの Web ページであり，複数の更新モニタリングシステムが研究開発されてきた．本稿

Web ページを登録することはできるが，Web サイト全体

では，これまでの代表的なシステムの紹介，そこでの問をモニタすることはできない．また，フレームを使った題点と先端的な Web 更新モニタリングの研究例，そしページや動的にコンテンツを生成するページには対応して今後の課題について説明していく．ていない．
また，ChangeDetect は，意味のない更新通知を避ける工夫がされている．たとえば，ユーザ登録（有料）により拡張される機能により，更新中に含まれるべきキーワードの設定が可能で，複数のキーワードを AND, OR,フレーズで設定できる．設定後は，その条件を満たす更IPSJ Magazine Vol.44 No.7 July 2003

−1−713

特集

Webダイナミクス

図 -1 ChangeDetect のインタフェース 2）

図 -2 WebSpector のインタフェース 5）

新のみが通知される．

する．また，図 -2 のようなインタフェースが提供されメールによる更新通知メールの一部を以下に示す．こており，これを通して，モニタリングしたい URL の登録，の通知メールから分かるように，単に更新された URL更新されたページの URL のリスト表示，そしてそのリを知らせてくれるだけであり，更新された個所の提示等

ストの URL をクリックすることにより，ブラウザでそはできない．のページを表示するなどの機能がある．
さらに，WebSpector では，更新のモニタリングをいつ行うかのスケジュールを設定可能で，また，更新されThe ChangeDetect monitor has determined that

た部分のハイライト表示，ユーザが指定したキーワード

the following web page has changed:
http://research.nii.ac.jp/~seiji/index-e.htmlのハイライト表示などにより，可視性を向上させている．
さらに，検出すべき更新の条件として，差分のサイズのWebSpector ™

5）も，ユーザが登録した URL の Web ペ

しきい値を指定して，それ以上の大きさの更新があったージをモニタリングする．基本的には，クライアントア場合のみ通知させることができる．

プリケーションがユーザの PC に常駐して，モニタリングを行う．更新が検出された場合は，e メールで通知を

714

44 巻 7 号

情報処理2003 年 7 月−2−

5Web更新モニタリング

Webページ差分の抽出

問題点

Web 更新モニタリングには，Web ページが更新されたか否かを判定し，また更新された部分を抽出する技術が必要である．ここでは，Web 更新モニタリングにおいて，ここまで，Web モニタリングシステムとその機能を見Web ページ間の差分の検出に広く使われている技術であてきたが，実際に利用してみるといくつが不満な点がある最長共通部分系列 LCS とそれを拡張した HCS についることに気付く．その代表的なものを以下に挙げる．て説明する．
LCS は，直観的には，2 つの記号列間の最大共通部分• モニタリングが，Web ページ単位でしかできない：

系列を意味するが，より厳密な定義を次に示す．記号系

Web サイト全体をモニタリングしたいことも多いが，列  1 2… p に対し，非連続であってもよいが，順序それが可能なシステムはほとんどない．モニタリング

関係を保持している系列i1i2il (i1i2…il) をの対象となるページが多いこと，不要な更新を取り除く部分系列と呼ぶ．そして，2 つの記号系列 ， において，必要があることなどが，Web サイト単位のモニタリン

 が ， 両方の部分系列であるとき， を ， の共通部

グを難しくしている．

分系列とする．2 つの記号系列 ， における最長共通部• ユーザが自分の必要な更新を十分に指定できない：あ分系列 LCS（Longest Common Subsequence）とは，，る特定の更新があったときだけ通知して欲しいことが間の最も長い共通部分系列を意味する．

よくある．それに対して，更新が含むキーワードを設

2 つの Web ページの差分を抽出する場合は，まずそれ定することで対応しているシステムがほどんどであらの Web ページファイルを HTML パーザにかけて，タる．しかし，キーワードだけの条件では，数値の変動グ構造を構文解析し，2 つの記号系列を生成する．このに対する条件，予測できないキーワードを含む更新の構文解析では，基本的には，対応するタグに挟まれたプ条件など，さまざまな記述できない更新の条件が残る．

レーンテキストが 1 つの記号と見なされて，記号系列が• クライアント間の連携がない：すべてのクライアント生成される．ただし，表（<table> タグ）やリスト（<ul>,が 1 つのサーバで走っており，またクライアントは独<ol>, <li> タグ）などは，直観的な解釈に合うように特別立に動作している．本来なら，すでにモニタリングさの処理がされ，行やアイテムが 1 つの記号として抽出されている Web ページなどを共有することが望ましい．

れる．そして，得られた 2 つの記号系列から LCS を抽出する．古いページと LCS の差分が削除された部分であ

これらの問題に対し，研究システムレベルのものも含り，新しいページと LCS の差分が追加された部分となる．

むが，解決法を模索している先進的な Web 更新モニタ

また，削除された部分と追加された部分の対応をとるこリングシステムを次章で紹介していく．とで，古いページのどこが新しいページのどこに更新されたかを説明できる．なお，この LCS の検出は，UNIX先進的なWeb更新モニタリングの diff コマンドで使われている．diff では，行を単位とした記号系列において LCS を抽出し，LCS 以外を差分として取り出す．後述する WebBeholder では，この LCS

サイト全体の更新モニタリング
1）ChangeDetector は，Web ページ単位ではなく Web サを基にして，更新部分の検出を実現している．
HCS（Heaviest Common Subsequence）は，LCS を拡イト単位で更新モニタリングを行えるシステムである．

張したもので，マッチした記号とその位置に基づいた重Web サイト単位で更新をモニタすることにより，組織内みを導入し，その重みが最大になるように拡張された共のグループの再構成や生産ラインの終了などの通常では通部分系列である．近似的なマッチングや行の長さを考見 つ け に く い 変 化 を 効 果 的 に 検 出 で き る．

慮することができる．代表的な差分エンジンである

ChangeDetector は，さまざまな機械学習の技術を基盤

3）

TopBlend では，HTML ファイルを構文解析して，HCSにしている．知的クローリングにより，膨大なサイト全に基づく差分を抽出することで，より精度の高い更新部

体から効率的に関連する Web ページを収集し，集まっ分の特定を実現している．

たページから分類学習によりトピックに依存した更新抽出を行い，エンティティ抽出により，意味的にフィルタリングされた更新抽出が可能になっている．プロトタイ
プシステムで，毎週 2,000 以上のサイトをモニタリング
IPSJ Magazine Vol.44 No.7 July 2003

−3−715

特集

Webダイナミクス

図 -3ChangeDetector の更新通知 1）

れ，後は抽出された更新が，電子メールや Web ブラウ可能である．
ChangeDetector は，まず Web サイトの Web ページをザを用いてユーザに通知される．Web ブラウザによる更収集するが，1,000 ページを超える Web サイトもあるの新表示の例を図 -3 に示す．まず，上にある表に，いつ，で，サイト内すべての Web ページを収集することは難どのサイトで，何ページが更新されたかの情報が提示さしいし，ユーザはサイト内のすべての更新に興味がある

れ，その下には，Commerce One, Inc. のサイトにおけるわけではない．そこで，収集されたページを機械学習の更新の詳細がリストで表示されている

文書分類を用いて，あらかじめ設定されたクラスに分類してラベルづけを行い，ディレクトリ構造とそのラベル対話的部分更新モニタリングを基にサイトマップを自動生成する．そのサイトマップ

これまでの Web 更新モニタリングは，基本的に Webを用いて，優先的に収集すべき Web ページを記述し，ページで何らかの更新があれば通知するシステムだっクローラはそこを中心にページを収集する．文書分類にた．つまり，通知して欲しい更新の条件をシステムに知用いられるクラスは，一般的かつユーザの興味ある Webらせて，その条件を満たす更新のみ通知することは難し

ページを表現できるように，プレスリリース，コンタク

い．更新個所に含まれるキーワードを設定できるシステ

ト情報，就職情報，経営情報などの 12 のクラスが定義

ムもあるが，キーワードだけでは，たとえば，「ある企されている．

業の株価が 9,000 円を超えるか，5,000 円を下回ったらWeb ページが分類されると，XML ベースの差分検出通知」というような条件は記述しにくい．また，このよが行われる．そして，検出された変化から意味のない変うな条件を一般のユーザが直接的に正確に記述すること化を除去するフィルタリングを行う．
残った更新個所が，も容易ではない．
6）

文書分類で使われた Web ページのクラスに関連づけら

PUM は，ユーザが更新の位置と内容に関する条件づれる．このクラスにより，どのような更新かの情報が得けを対話的にできる Web 更新モニタリングシステムでられる．また，クラスを使って，通知すべき更新の条件ある．全体の構成は，図 -4 のようになっている．最初に，を記述し，フィルタリングできる．

ユーザは更新個所をマウスでハイライトして PUM に与え，後は PUM からの更新通知をユーザが評価するだけ

以上で，Web サイト単位の更新モニタリングが実現さ

716

44 巻 7 号

情報処理2003 年 7 月

−4−

5

Web更新モニタリング������� 任意の更新を検出

失敗

����
監視領域の同定

不必要

成功������
更新の判定

監視領域

領域同定ルール

必要

更新判定ルール

��� 領域同定ルールの学習��� 更新判定ルールの学習

関係学習

関係学習

領域同定
訓練例

更新判定
訓練例

差分

ユーザ

��������
更新結果の提示

更新結果
表示
監視部分
は正解
更新結果の評価

更新結果の評価

監視部分の相違�回前の監視情報

監視部分を指定

��� 訓練例の生成

��� 指定領域の取得��� ���の登録

図 -4 PUM のシステム構成

マルチエージェントシステムとしてのWeb更新モニタリング

で，PUM が分類学習により，更新の位置を同定する領域同定ルール，更新の内容を判定する更新判定ルールの双方を学習する．そして，学習された判別ルールに基づ

4）き，更新の通知を行う．

WebBeholder は，Web ページの更新通知を行う先駆

たとえば，図 -5 に週間天気予報の Web ページを表示的な研究である．全体の構成は，図 -6 のようにマルチしている PUM のインタフェースを示す．この例では，エージェントシステムとなっている．更新モニタリング

ユーザが通知して欲しい更新は，「栃木の次の日曜日のを行うサービス提供エージェント，個々のユーザに対応降水確率が 30% 以下になる」更新である．ユーザは，するパーソナルエージェント，エージェント間の調整を

図 -5 の網掛け部分をマウスにより領域指定する．この行うメディエータから構成される．ユーザは，自分の更教示だけでは，PUM はユーザが通知して欲しい部分更新モニタリングの要求を持ったパーソナルエージェント

新を正確に特定できないため，別の曜日での更新や降水をメディエータに渡すことで，更新モニタリングが可能確率が上昇した更新もユーザに通知してしまう．
しかし，になる．

ユーザがそれらの更新通知を評価していくことにより，メディエータは，要求ブローカ，ナビゲータ，ファシ徐々に正しい更新を判別するルールを PUM が学習してリティの各モジュールを持つ．要求ブローカは，パーソいき，最終的には正しい部分更新のみを通知するに至る．

ナルエージェントのためにクエリをサービス提供エージ

このように，PUM は，ユーザが欲しい更新の条件を直ェントに渡したり，パーソナルエージェント間の調整を接記述することなく，通知された更新を評価するだけで，行う．ナビゲータは，パーソナルエージェントに，他の正しい更新を学習する点が優れている．

WebBeholder コミュニティの情報を提供する．また，フIPSJ Magazine Vol.44 No.7 July 2003

−5−717

特集

Webダイナミクス

図 -5 PUM のインタフェース

図 -6 WebBeholder のシステム構成 4）ァシリティは，新たに追加されたパーソナルエージェンの近くに追加された部分が表示されている．

トに実行可能な諸機能を提供する．

WebBeholder の特徴として，サービス提供エージェン

サービス提供エージェントが行う更新モニタリング

ト，メディエータ，そして複数のパーソナルエージェンは，HTML を構文解析した結果に対して，LCS を基に差トが 1 つのコミュニティを構成して，コミュニティ間で分を抽出して，更新部分を特定する．さらに，HTML タの協調が実現されていることがある．新しいパーソナルグを基に重み付けを行う．この重み付けは，たとえば，エージェントがコミュニティ A に追加された場合，そのアンカータグ中の URL は重要であり，プレーンテキス更新モニタリング対象の Web ページが他のコミュニテトは重要でない，というように設定される．抽出された

ィ B ですでにモニタリングされていれば，そのパーソナ差分に対し，この重みを用いて更新を重み付けして，重ルエージェントをコミュニティ B へ割り当てることがで要度を評価している．図 -7 が，WebBeholder の更新通きる．このように，WebBeholder では，マルチエージェ知画面である．削除された部分が線で消されており，そントコミュニティを使って，既存のクライアントとの連718

44 巻 7 号

情報処理2003 年 7 月

−6−

5

Web更新モニタリング

図 -7 WebBeholder の更新提示 4）携を実現している．

結果をいかに分かりやすくユーザに提示するかのユーザインタフェースなどの問題を，人工知能，ヒューマンインタフェースなどの関連分野の技術を使いながら解決し今後の方向ていくことが課題であろう．

本稿では，現在普及している Web 更新モニタリング

参考文献1）Boyapati, V., Chevrier, K., Finkel, A., Glance, N., Pierce, T., Stokton, R.
and Whitmer, C.: ChangeDetector: A Site-Level Monitoring Tool for thewww, In WWW 2002, pp.570-579 (2002).
2）ChangeDetect, http://www.changedetect.com/
3）Chen, Y., Douglis, F., Huang, H. and Vo, K.-P.: TopBlend: An Efficient
Implementation of HtmlDiff in Java, In WebNet 2000 (2000).
4）Saeyor, S. and Ishizuka, M.: WebBeholder: A Revolution in Tracking andViewing Changes on the Web by Agent Community, In WebNet 1998
(1998).
5）WebSpector: http://www.illumix.com/
6）山田誠二，中井有紀 : 対話的分類学習による Web ページの部分更新モ
ニタリング，人工知能学会論文誌，Vol.17, No.5 (2002).
（平成 15 年 4 月 1 日受付）

システムを紹介し，その機能，問題点について，議論した．また，それらの問題点を克服する先進的な Web 更新モニタリングのメカニズムを，具体的なシステムを例として説明した．
先進的なシステムでは，いくつかの問題点が解決されているものの，基本的には，更新があった場合，ブラウザで更新部分をリスト形式で表示するものがほとんどである．
今後は，ユーザの知りたいさまざまな更新の意図をどのようにユーザに負荷をかけることなく獲得するかというユーザモデリング，そして，検出された更新をいかに効果的に統合するかという情報統合，さらに統合された

IPSJ Magazine Vol.44 No.7 July 2003

−7−719−8−