WWWからの情報抽出

１．はじめに
１・１　WWWと情報抽出
HTMLやXMLなどの半構造化文書から有用な知識を発見、抽出するためのWebマイニングの研究が注目を集めている。そしてWebマイニングの研究のひとつとして、Webページのコンテンツと構造を再構成し、新たな情報としてユーザに提供するための研究が行われている。これらの情報の再構成の鍵となる技術が、Webページから特定の箇所を自動的に抽出するための情報抽出である。
１・２　Webラッパー
Webページからある特定の部分を抽出するためのぷろぐらむや、抽出するための場所を指示する文法はWebラッパーと呼ばれる。ラッパーで抽出した情報は関係データベースのレコードやXMLデータなど必要な形式に変換され、新たなサービスを提供するために用いられる。
１・３　Webラッパーの自動生成
Webラッパーが抽出の対象とするものはフィールド（例えば新聞記事といった限られたジャンル）やレコード（テーブルタグに囲まれた部分など）を対象としているものが多い。本稿ではラッパーの自動生成法を中心に、Webラッパー構築に関する様々な話題を紹介する。
１・４　Webラッパーの応用
Webラッパーの最も重要な応用の一つが、情報の統合である。分散した複数の情報サービスを統合して、それを見やすくまとめて情報を提供するのである。情報の統合を可能にするには、情報抽出と同時にそれらの持つ意味的構造、スキーマ（データベースの構造）を抽出する必要がある。その意味で情報の統合は情報抽出の間接的な応用と言える。一方Webラッパーの直接的な応用として半構造化文書から必要な部分のみを抽出することによるデータの圧縮がある。これにより、モバイル端末や携帯電話などの小さなディスプレイへの表示や、HTMLページの要約に役に立つ。

２．　ラッパーの自動生成
ラッパーの対象となる半構造化文書群は様々なサイト上に存在し、様々な形式で記述されているため、サイトごと、同種の項目を持つページ群ごとにラッパーを生成しなければならない。WWW上に存在する膨大な量の半構造化文書を考えると手動でラッパーを生成することはコストの大きい仕事であり、また間違う可能性も高いため自動的な生成法が求められる。機械学習を用い、訓練例を入力例を入力として与えることによりラッパー生成を行うもの、タグによる階層構造に着目したもの、機械学習を用いる代わりに、訓練例を与えずに自動的にラッパーを生成するものなどがある。また人間によるWebラッパーの生成支援環境についても研究が盛んに行われている。

３．教師つき学習による情報抽出
本章では、ラベルやデータ間の区切り目などの付加的な情報を含んだ訓練例からの学習によってラッパーを構築する、教師つき学習による情報抽出を紹介する。
３．１　Kushmerickのラッパー帰納
ラッパーとは与えられたHTMLから所望の部分を切り出すためのルールまたはプログラムであるが、Kushmerickが提案したラッパーのうち最も単純なLRラッパーを説明しよう、LRラッパーの一般系は、W: = ((a1,b1),(a2,b2).........(ak,bk))　と表現される。例えばテーブルで
<tr><td>CPU</td><td>2.8GHz</td></tr>
<tr><td>メモリ</td><td>512MB</td></tr>
とあったとするとa1=(<tr><td>,</td>) b1=(<td>,</td></tr>)としてやることで間にあるCPUと２．８GHｚを抽出することができる。同様の規則でメモリも抽出することができる。このように、いったんラッパーを構築することができれば、与えられたHTMLページから自動的に必要な情報を抽出できる。しかし、求める情報を正しく切り出すラッパーを構築することは難しい問題である。Kushmerickはこの問題をラッパー帰納問題とよび、定式化した。これは与えられたHTMLファイルPと、切り出しに関する訓練例Lから、正確に訓練例と同じ切り出しをする、すなわちW(P) = LとなるラッパーWを見つける問題である。

３．２　STALKER:DFAの学習
　２番目の事例はMusleaらによるラッパー帰納問題である。彼らはHTMLページが木構造で表現できることに注目し、その構造からラッパーを構築する方法を提案した。彼らのSTALKERアルゴリズムは、一言で言うと与えられたHTMLページから非常に限定された正規表現のパターンをオートマトン形式で抽出するアルゴリズムである。
３・３　カーネル法
Kashimaらは、木構造からの情報抽出問題を定式化し、その問題にSVM(Support Vector Machine)による分類問題で威力を発揮するカーネル法を適用した。これを元に機械学習を行ったところ、非常に高い精度で正しい切り出し場所を学習していることが報告されている。特に、あいまいなマッチングによる木の埋め込みを許したベクトル表現のほうが通常のベクトル表現よりも高い精度で学習が行われていることが実験データで示されていることが興味深い。
４．教師なし学習による情報抽出
本章では、データを加工せずに学習者に与える教師なし学習の枠組みで提案されている情報抽出の研究事例を紹介する。
４．１IEPAD:文字列の繰り返しの発見
これまでに紹介した学習における切り出しでは、アルゴリズムに与える訓練例は、どこを切り出すかを指定したり、必要な部分だけをあらかじめ取り出したりしたHTMLページの加工品であった。このような方法では、精密な切り出しを期待できる半面、そのような訓練例を準備することはユーザにとってしばしば非常に手間のかかることである。これにたいしてIEPADでは、訓練例に特別な加工は必要なく、手に入れたHTMLをそのままアルゴリズムの入力として利用できる。IEPADは繰り返し登場するHTMLの文字列のパターンで、文字列数が最長のものを探し出してそこを切り出すことにより情報を抽出しようという考え方である。PAT木と呼ばれる特別なデータ構造を使うことでO(n)時間で計算可能である。
４．２　PLRラッパー:木構造と文字列の組み合わせ
Treeラッパーによって情報抽出を行うときにパスに対応する文字列には不必要な文字列がついている場合がある。例えば、毎日新聞の記事では、あるパスに対応する文字列が”[毎日新聞３月１日]（２００２－０３－０１－１１：６）のように、日付・時間の回りに不要な文字列がついている。これは、情報統合を考える際に不要である。そこで、パスに対応する文字列の中から、さらに細かく文字列を抽出するために、山田らはTreeラッパーとLRラッパーを組み合わせたPLRラッパー(Path-Left-Rightラッパー）を提案している。PLRラッパーは、入力として与えられた半構造化文書から各項目を抜き出すためのルールの集合によって表現される。ルールとは各項目の出現する木構造のパスと、そのパスで特定されるノードに対応する文字列中の項目を囲んでいる左区切り文字列と右区切り文字列と呼ばれる文字列の組から成り立つ。そしてノードの文字列のうち不要な部分は削除される。