概要
グラフィカルデザインの原則に「近接」,「整列」,「反復」,「コントラスト」がある. これらは意味的に類似したものは見た目を似せ,物理的に近接した領域に配置することをあらわすキーワードである. 本研究の目標は,これらに基づいて作成されたデザインされたを利用することで, 特定のHTML文書に依存しないWebページからの自動情報抽出を行うことである. 本年度は抽出対象を二次元にレイアウトされたリスト(以下,二次元リストと呼ぶ)からの要素抽出に限定したアルゴリズムを提案する. これはDocument Object Model(DOM)ツリー中の各ノードを,ブラウザ中の位置と大きさをもとにクラスタリングを行う. 作成されたクラスターをリスト候補,その要素をリスト要素の候補とする. 本報告書では研究の背景と,提案するアルゴリズムについて説明する.
1. はじめに
Webは日常生活の隅々にまで浸透し,われわれの生活にはなくてはならないものになっている. 検索エンジンを利用してWeb上の情報を検索し,得られたWebサイトを通じて情報を収集し, 比較することは日常的に行われる行為となっている.
従来のWebは人間が利用することを前提としたシステムである. Web上の情報を扱うプログラムの多くは,WebサーバからWebページを取得して利用者にそれを表示することのみ行う. Webページから情報を取得し,他のWebページの情報と比較を行うのはあくまでプログラムの利用者である.
Tim Barners-Leeによって提唱されたSemantic Web[2]では, この情報の抽出と比較もプログラムの役割となる. W3Cはプログラムが処理可能な形で情報を記述するためのフレームワークであるResource Description Framework(RDF)[3]を提案している.RDFではWeb上のリソースや,様々な情報の性質を二項関係で記述する.このとき利用される語彙はWeb Ontology Language(OWL)[4]によって定義される.OWLによって定義された語彙を用いて記述されたRDFデータがプログラム間で交換され,現在人間が行っている比較や推論がプログラムによって行われるのがSemantic Webである.
Semantic Webは,データがRDFの形で交換されいることが前提である.しかし未だRDFで記述されたデータは少なく,また利用されている語彙もRDF Site Summary(RSS)[5]やFriend Of A Friend(FOAF)[6]といった限られたものとなっており,多くの情報はHTMLの形で流通している.よって現在プログラムが情報の比較を行う場合,まずWebページを処理し,そこから情報を抽出することが必要となる.
2. Visual Cueを利用した情報抽出
従来のWebページを対象とした情報抽出法[1]は,HTML文書の構造を解析するものが大半であった. しかしこれらの多くは特定のHTML文書やWebサイトのみ適用可能な手法であり, 他のドメインには利用不可能であった.
またWebページには表やリストといった,視覚に依存した情報表現も少なくなく利用される. これらはtableやulといったタグで表現されるものもあれば,他のタグを組み合わせて表現されたものや, tableタグを用いているが実際はリストを作成している,といったような場合も存在する. このような場合,従来のタグやHTML文書の構造を解析する手法では効率的に情報を抽出することはできない.
以上の背景から登場したのが,Visual Cueを利用した情報抽出である[9] [13][14]. 元来Webページは,作者が視覚的な効果までを考慮して作成されたものである. よってHTML文書の構造ではなく,実際の表示を解析することで情報抽出を行うアプローチである. 従来のアプローチとの差を図1に示す.
図1:Visual Cueを使った情報抽出と従来型の情報抽出([9]より引用)
3. 提案するアルゴリズム
[7]ではグラフィカルデザインの原則として次の4つを挙げている.
- 近接
- 整列
- 反復
- コントラスト
この中で今回利用するのは「近接」,「反復」,「整列」の原則である. 「近接」とは近接したいくつかの項目はバラバラのものではなく一つの項目として認識されるため, 関連した項目は近接した領域に配置するという原則である. 「反復」とは統一感のために視覚的な要素を反復的に利用するというものである. また要素を整列させて配置すると,明快さや簡潔さが生じる. 二次元に配置されたリストはこの三つの原則を踏まえてデザインされることが多い. 以降,上記三つの原則を利用した二次元リストの要素抽出について解説する.
3.1. 対象とする要素
[9]によると,HTML文書のうち視覚的な理解が必要な要素は図2のように分類される. 今回はこのうち"Simple 2-D lists"と"Substructured 2-D lists"を対象とする.
図2: 視覚的な理解が必要となる要素の分類([9]より引用)
二次元リストとは各要素をマトリックス状に配置したリストである. これは2種類に分類できる. "Simple 2-D list"は各要素の大きさが均等になるようレイアウトされたリストである. そしてもう一方の"Substructured 2-D list"は個々の要素の大きさが均等ではない. どちらも静止画や動画像,ECサイトの商品の検索結果などを一覧で出力するために良く用いられる. そのためリストの要素を自動的に抽出できれば, 検索結果を自動的に手元のデータベースに保存するといったようなことが容易になると考えられる.
3.2. リスト候補の列挙
HTML文書はリストのみで構成されているわけではない. ヘッダやフッタ,メニューや他のページへ遷移するためのパンくずリストといったサイトを構造化するために必要な要素や, リストの説明文といったものも含まれる. 要素抽出のためには,これらをリスト以外のものとリストの要素とを区別しなくてはならない. そのために3で紹介したデザイン上の原則を利用する.基本的な考え方を次に二つあげる.
- リストの各要素は近接した領域に存在する(近接の原則)
- 各要素はマトリックス状に整列して配置されている(整列の原則)
- 各要素は類似した大きさを持つ(反復の原則)
この3つの考え方を元にHTML文書中の各ブロック要素を分類を行う. HTML[10]にはブロック要素とインライン要素の二つが定義されているが, 今回はこの定義を利用せず,ブラウザがブロック要素として処理をする要素をブロック要素とした. これはCascading Style Sheets[11]を利用することで, インライン要素でもブロック要素として処理され,ブロック要素のように表示されることがあるからである.
分類のため各ブロック要素を次のように4次元のベクトルで表現した. 各要素は順に,バウンディングボックスの左上のx座標,バウンディングボックスの左上のy座標,バウンディングボックスの幅, そしてバウンディングボックスの高さを表す.
ベクトル表現されたブロック要素をSelf-Organizing Map[12]を使って二次元上にマップする. Self-Organizing Mapとは次元削減法の一種で,近傍学習を用いて距離的に近いベクトルを二次元マップ上に配置する. これを利用することで,近接した要素,大きさの類似した要素を近くに集める.
ただ二次元リストはWebページに検索結果を「詰め込む」ために利用されることが多く,リスト自体が巨大になりがちである. 隣接した個々の要素は近接していても,リストの左上に配置された要素とリストの右下に配置された要素とでは 距離が遠くなってしまうこともありうる. そのため今回は位置よりも面積のほうが結果に大きく影響を与えるよう,ベクトルに重みをつけた近傍学習を行う.
要素を二次元マップ上に配置した後は,マップ上の密度分布を元にクラスタ分類を行う. これで作成されたクラスタのうち要素数が2以上のものをリストの候補とした.
3.3. リストの認識
二次元リストは主に検索結果をページに詰め込むために利用される. そのため,リストは通常ページに一つのみ存在する. 前節で述べた分類ではリストに,たまたま同じような面積をもつ要素の集合もリストの候補とされてしまう可能性がある. よって次の関数を用いて各クラスタのポイントを計算する.この関数はクラスタ中の各要素の面積をすべて掛け合わせたものをスコアとして返す.
このスコアが最大となったクラスタをリスト,その要素をリストの要素とする. これでリスト要素の抽出は終了である. あとは各要素に含まれるインライン要素を取得することで,リストの要素の持つ情報を取得することができる.
実装
実装は次の二つモジュールに分けられる.
- 視覚的特徴の抽出部
- 分類器
視覚的特長の抽出はWebブラウザを利用する. WebブラウザはWebページを表示する際,DOMツリーと呼ばれる内部的データを作成する. これはWebページの持つHTMLの解析結果に表示のためのスタイル情報がまとめられたものである.
DOMツリーへのアクセス方法はいくつかあるが,今回は簡便なJavaScriptを利用することにした. JavaScriptはWebブラウザ内で実行されるプログラム言語で, 動的に変化するWebページやインタラクティブなWebインタフェースを実現するために利用される.
分類器もJavaScriptで記述し,ブラウザ上に実装することも考えた. しかし分類器は大きな行列を対象とした行列演算を多く行うため, ブラウザ上ではなく独立して実装することとした. 結果,各モジュールの関係は下図のようになった.
図3: アーキテクチャ
JavaScriptでDOMツリー上に含まれるスタイル情報を取得し, それを分類器に送るというアーキテクチャの実装には次の二つの困難があった.
- 視覚的特徴の抽出スクリプトをどのようにして起動するか
- 視覚的特徴の抽出スクリプトと分類器との通信はどのようにして行うか
JavaScriptは本来Webページ内に記述されているものであるが, 今回は与えられるページすべてに対して特定のスクリプトを実行させる必要があった. これを実現する方法はプロキシサーバを利用したHTMLの書き換えを行うのが一般的であるが, 今回はGreasemoneky[8]というFireFox用のアドオンを利用することで実現した. GreasemonekyはWebページをカスタマイズするためのもので, Webページに対してユーザの指定する任意のJavaScriptを実行させることができる.
後者の問題もGreasemonkeyを使うことで解決した. セキュリティ上の理由より,JavaScriptはそのWebページが保存されているWebサーバとしか通信できない. しかしGreasemonkeyは任意のサーバとHTTPを用いた通信を行うための機能が用意されている. これを利用してDOMツリーの各ノードが持つ視覚的特徴を分類器に送信する.
5. まとめと課題
DOMツリー中の各要素をその位置と大きさをもとに分類し, 画面に占める面積の比率を元に二次元リストの同定を行うアルゴリズムを提案した. またそのアルゴリズムをWebブラウザを利用した分類器という形で実装を行った. 以上が本年度の研究成果である.
来年度以降は次の3つを行う.
- 提案したアルゴリズムの評価
- 一次元に配置されたリストへの適用
- 表への適用
まずは提案したアルゴリズムの評価を行う. 今回の成果はアルゴリズムの提案にとどまっている. さまざまなWebサイトに対してアルゴリズムを適用し,実際に情報を抽出を行う. 抽出結果を人間の行った抽出結果と比較し,再現率と適合率を計算することで本研究の有用性を検証する. また従来のHTML文書構造を利用した手法と比較し,速度やメモリ使用量の面での比較も行う.
次に提案したアルゴリズムの一次元に配置されたリストへの適用を行う. 今回提案したアルゴリズムは,一つのWebページに含まれるリストが一つである場合に最も正確に動作することが予想される. これは二次元に配置されたリストの利用傾向上,十分であろうと考えられる. なぜなら,二次元に配置されたリストは多くの要素を一つのWebページに詰め込むために利用されるため, Webページ内に含まれる二次元リストが一つであることが多いからである.しかし一次元のリストはそうは行かない. 複数のリストが一つのページ内に共存することは常態であるからだ. 提案したアルゴリズムを一次元リストに適用し,複数のリストがどのように分類されるか, 一つのリストとして誤認識される場合はその分割方法について検討する.
最後に表への適用も行う. 表も一次元に配置されたリストと同様,1つのWeb複数個の表が含まれることが常である. また,表からの情報抽出を行う際には,行と列の認識も行わなくては行けない. よって更なる拡張が必要であることが予想される. また表からの情報抽出はさまざまな手法が提案されているため,それらとの比較も行う必要がある.
参考文献
- Mei Kobayashi and Koichi Takeda, "Information retrieval on the web", ACM Comput. Surv., ACM Press, 2000, Vol.32(2), 144-173
- Berners-Lee, Tim. and Hendler, James "Publishing on the Semantic Web", Nature, April 2001 p. 1023-1025
- Frank Manola, Eric Miller, "RDF Primer", http://www.w3.org/TR/REC-rdf-syntax/, February 2004
- Peter F. Patel-Schneider, Lucent Technologies, Patrick Hayes, IHMC, Ian Horrocks, "OWL Web Ontology Language Semantics and Abstract Syntax", http://www.w3.org/TR/owl-semantics/, February 2004
- Aaron Swartz, et.al, "RDF Site Summary(RSS) 1.0", http://web.resource.org/rss/1.0/, December 2004
- Dan Brickley, et al, "The 'friend of a friend' project: FOAF", http://rdfweb.org/foaf/
- Robin Williams著, 吉川典秀 訳 "ノンデザイナーズ・デザインブック", 毎日コミュニケーションズ, 2004
- Aaron Boodman, "Greasemoneky", https://addons.mozilla.org/en-US/firefox/addon/748
- Wolfgang Gatterbauer,Paul Bohunsky,Marcus Herzog, Bernhard Krüpl Bernhard Pollak, "Towards domain-independent information extraction from web tables", Proceedings of the 16th international conference on World Wide Web, May 2007
- Dave Raggett, Arnaud Le Hors, Ian Jacobs, "HTML 4.01 Specification", http://www.w3.org/TR/REC-html40/, Dcember 1999
- Bert Bos,Hakon Wium Lie,Chris Lilley,Ian Jacobs, "Cascading Style Sheets, level 2 CSS2 Specification", http://www.w3.org/TR/REC-CSS2/, May 1998
- T.Kohonen, Self-Organizing Maps, Springer, 1996
- Hsin-Hsi Chen , Shih-Chung Tsai , Jin-He Tsai, "Mining tables from large scale HTML texts" Proceedings of the 18th conference on Computational linguistics, 2000
- Yonatan Aumann , Ronen Feldman , Yair Liberzon , Benjamin Rosenfeld, Jonathan Schler, "Visual information extraction", Knowl. Inf. Syst.p1-15 Springer-Verlag New York, Inc., 2006