連想構造を用いた WWW からの情報抽出と整理
前田 晴美・糀谷 和人・西田 豊明
奈良先端科学技術大学院大学 情報科学研究科
Extraction and Reorganization of Information from WWW Pages
Using Associative Structures

Harumi MAEDA, Kazuto KOUJITANI and Toyoaki NISHIDA

E-mail: harumi-m@is.aist-nara.ac.jp
雑多で構造の不均質なHTML 文書の情報を抽出・整理する手法を提案する。基本となるアイディアとして雑多な情報をゆるやかに関連づけるための連想構造というデータ構造を用いる。我々は、連想構造

WWW から情報を収集し、整理する過程を支援するシステム CM-2(Contextual Media version 2) を試作した。 CM-2 では、 URL で示される HTML 文書を入力して、利用者の整理項目に従って情報を切り出し、構造化して出力できる。人工知能研究者のホームページを題材として CM-2 を実験的に評価したところ、適合率において研究者毎で 90%、プロジェクト毎で 68%、また再現率において研究者毎で 83%、プロジェクト毎で 73% の確度で情報整理が正しく行われることが確認できた。
を用いて

1

はじめにインターネットには情報が溢れている。特に上では急速に情報が増加している。

Wide Web)

WWW(WorldWWW 上の膨大な情報の中から、個人が必要な情報だけを得られると便利である。これまでに、インターネットからの異質な情が報告されている報源からの情報獲得の研究が、これらは主に情報収集の手法に焦点があてられている。などの検索エンジンのようにから利また、用者の要求に応じてや文書を提示するシステ
文書から必要な情報をムは数多くあるが、収集した[1][2][3][4][5]Yahoo

URL HTMLHTMLWWW抽出して利用者の視点から整理できるシステムはこれまでにほとんどなかった。
文書では、情報の構造や表現方法が作者によっHTMLて違うため、必要な情報を抽出することが難しい。インター
ネット上の雑多で構造が不均質な情報源から情報を抽出する研究として、浅い自然言語処理を用いて電子ニュースかがこれまでに報告されてらダイジェストを作成する研究いる。この研究では、抽出したい情報に固有のドメイン知識や構造情報を組み込んだプログラムを作成するため、目標となる情報やドメインが変わるとプログラムを新たに作成しなくてはならず、人間の負荷が高い。また、利用者の入力から情報を整理するところまでは研究が進められてい

[6]

ない。
上の文書のような雑多で本論文では、構造の不均質な情報源から情報を抽出・整理する手法を提WWW

HTML案する。基本となるアイディアとして雑多な情報をゆるやかに関連づけるための連想構造というデータ構造を用いる。
連想構造を用いることにより、生データから必要な情報を抽出し、利用者の視点から簡単に整理できる。
我々は、連想構造を用いて情報を収集し、整理する過程
1 を試作した。
を支援するシステム
では、で示された文書を入力して、利用者の整理項目に従って情報を切り出し、構造化して出力できる。
本論文は以下のように構成される。 節では連想構造とHTML

CM-2

CM-2

URL

2
CM-2 の概要について述べる。 3、 4 節では情報抽出・整理手法について説明する。 5 節では実験結果を示し、有効性について議論する。

2

連想構造と CM-2

2.1

連想構造

連想構造はkey と呼ぶいくつかのユニットと value と呼keykeyが与えられるぶいくつかのユニットの間に定義され、「が想起される」というゆるやかな関連を表す。とvalue
valueとの間の連想関係は厳密に定義されたのではなく、多分に主観的であることを許している。これは既存の情報の雑多性、多様性に対応することを狙っている。
における情報の基本構成要素であユニットとは、CM-2る。ユニットは CM-2 の外部のテキストファイルやイメージファイルを表す外部参照データユニットと、 CM-2 において情報を関連付けるための内部的な対象である概念ユニッ
1 \CM" とは我々の長期的研究目標である Contextual Media の略語である。超並列計算機 CM-2 とは無関係である。

(a)

(b)

奈良奈良& 寺

奈良公園

東大寺

AAAAAA
利用者入力

大仏

興福寺

図HTML文書

法隆寺

鹿URL

1: 連想構造情報抽出

CM-2連想構造

(a)

(b)

東大寺

奈良先端大寺

NAIST(IS-A)

(辞書)

図

整理項目

CM-2
1(a) keykey( 2(b))
IS-A

1

IS-A
IS-A

value
1(b)

( 2(a))

2(a) IS-A

2(b)

NAIST

CM-2

CM-2 は、連想構造を用いて WWW から情報を収集し、整理する過程を支援する。の処理の流れを示す。情報抽出過程は、利
図 に

3 CM-2
用者からの URL 入力で示される HTML 文書を取り込み、CM-2 の連想構造を生成する。情報整理過程は、 CM-2 の連想構造を統合し、利用者からの整理項目に従って情報を整理し、表や箇条書形式で出力する。

図例題

e-mail

CM-2HTML

4
HTMLsoningに関連する情報を知りたいが適当な書籍やデータベースが存在しないとする。このような時に、のページを収集して、必要な情報だけを得ることができると便利である。
文書では、情報の構造や表現方法が作
しかし、者によって違うため、必要な情報を抽出することが難しい。

WWW

HTML

例えば、ある人は、ページの最初に写真や名前を載せ、次にURL

4(a)

WWW

rea-e-mail4(b)ブラウザに出力した結果を示す。同様に図は、」「大学」を整理項目「プロジェクト」「研究者」「e-mailとして入力してプロジェクト毎に箇条書形式で出力した結果を示す。

3

情報抽出

URL で指定される HTML 文書から情報を取り込み、 CM2 の連想構造を生成する情報抽出過程について述べる。アル
ゴリズムの概要は以下のとおり。

 step 2

例えば、自分の興味のある分野の研究者やプロジェクト

3: CM-2 の処理の流れ

履歴や研究に関する情報を通常の文章として書いている。
アドレス、肩書などを箇条書
またある人は、名前、で書いている。さらに、作者によって同じ概念に違う名前をつけたり、違う概念に同じ名前をつけることもある。
では、連想構造を用いてこれらの構造の異なる文書からゆるやかに情報を取り込み、利用者の入力に従って必要な情報を切り出し、構造化して出力する。
を入力
図 に、人工知能研究者のホームページの文書を収集し、利用者の入力に応じて情報をとしては、利用者がキーワード「整理した結果を示す。図
」と、整理項目「研究者」「」「プロジェクト」「大学」を入力して、研究者毎に表形式に情報を整理して step 1
2.3

箇条書

表

value

2.2

情報整理

2: 連想構造の特別な形態

トに大別される。
における連想構造を図 のように記述
本論文ではする。図は「奈良」が与えられると「奈良公園」「大仏」「鹿」が想起されることを示す。図は「奈良」と「寺」から「東大寺」「法隆寺」「興福寺」が想起されることを示す。
構造 図
連想構造には、特別な形態として、と辞書構造 図を定義できる。
構造は推論に使用される。
構造においては、クラス、サブクラスなどを区別することなく、上位概念をクラス、下位概念をインの構造では、「東大スタンスと呼ぶ。例えば、図寺」がインスタンスで「寺」がクラスである。辞書構造は、の辞概念ユニット間の変換に使用される。例えば、図書構造がある場合、利用者が「奈良先端大」と入力すると」というユニットに変換が可能である。
「CM-2

URL 解析による HTML 文書の取得
形態素解析と HTML 構造解析を用いたユニットと連想構造の生成{ step 2.1 形態素解析を用いたユニットの生成{ step 2.2

HTML 構造解析を用いた連想構造の生成 step 3 クラス判定ヒューリスティックを用いた構造の生成と連想構造の修正

IS-A

(a) 研究者毎に表形式で出力

図3.1

4: 人工知能研究者のホームページの HTML 文書を入力とした CM-2 の出力例

形態素解析と HTML 構造解析を用いたユニットと連想構造の生成

3.1.1

HTMLのタグ表現などの自然言語以外のまず文書から情報を除去する。ただし、形態素解析では処理できないが、などは事前有用だと想定される、電話番号、に抽出し、概念ユニットとして登録する。
、英語
次に形態素解析 日本語

e-mail URL:juman: Brill's Rule Based

Tagger[7]) を用いて品詞情報を獲得し、名詞と、名詞が連続して出現する品詞群 (間に前置詞や接続詞、冠詞を含んでもよい) を概念ユニットとして取り込む。
なお、ストップワード辞書を用いて、不要語や非重要語を除去できる。
3.1.2

{

それらの概念がどのタイトル スコープに含まれているかを元に連想関係を生成する。同一スコープに属する概念はとす
そのスコープのタイトルに含まれる概念の集合をを構成する。概念が複数のスコープに属る連想関係のしている時は、それぞれのスコープのタイトルに含まれるトとする連想関係のを構成する。
概念の和集合を

key

value

形態素解析を用いたユニットの生成((b) プロジェクト毎に箇条書形式で出力HTML 構造解析を用いた連想構造の生成

key

3.2

value

クラス判定ヒューリスティックを用いた ISA 構造の生成と連想構造の修正

最初にクラス判定ヒューリスティックに基づき、people

project

まず <h1> や <h2> などの見出しがある場合、また <dl><ul>、 <ol> などのリスト表現を見出しとして用いている 含まれる文字列からクラスを推論する。

{

場合にタイトル スコープを設定する。また、（ ）の直前の概念と中に含まれる概念の関係、：の直前と直後の概念で分割されているもの）に含まの関係、異なる段落（で表す。
れる概念の集合は、それぞれ異なる連想構造のさらに見出し 本文の構造が入れ子になっている時はそれ<p>{ぞれのる。

value

value の含まれるブロックの各 key の集合を key とす

前段で設定した概念とタイトル{ スコープをもちいて、IS-A 構造を生成する。
判定ヒューリ
クラス判定ヒューリスティックは、判定ヒューリスティックなどの、個別スティックやクラス判定ヒューリスティックから構成される。ユニットに対して、個別クラス判定ヒューリスティックを順番に適用し、最初の判定結果をそのユニットのクラスとする。個別クラ、ス判定ヒューリスティックは、与えられたユニットの名前にpeople

クラス判定ヒューリスティックと以下に判定ヒューリスティックの概要を述べる。

project

people クラス判定ヒューリスティックは、あるユニットの名前に、知識として与えた人間の名前が含まれる場合にであると判定する。
そのユニットをクラス判定ヒューリスティックは、あるユニッ
トが、ユニットの名前に、知識として与えたプロジェク
ユニットの名前に文字列「トの名前が含まれる場合

project(1)people(2)

project」

URL http://www.cs.rochester.edu/u/james/
step1

表HTML file

1: 情報整理 (step 1) の主要ヒューリスティック

同名概念統合辞書参照概念統合<h1>James F.Allen, URCS Faculty Member </h1><p>b. 1950. Ph.D. (1979) University of Toronto.
...................; University of Rochester.

包含的連想生成<p>James Allen's research interests.........................
These areas of research are combined in TRAINS Project,
step2

文脈参照連想統合
James F.Allen &URCS Faculty Member
Ph.D.
University of Toronto
University of Rochester

James F.Allen &URCS Faculty Member
research interests
areas of research
TRAINS

構造を修正する。

4step3James F.Allen

University of Toronto

people(IS-A)
University of Rochester(IS-A)
James F.Allen(IS-A)
James F.Allenの連想構造を統合し、利用者の整理項目入力に従って情報を整理して提示する情報整理過程について述べる。
以下に基本的なアルゴリズムを示す。

university

University of Toronto
University of Rochester step 1 ヒューリスティックを用いたユニットと連想

TRAINS

構造の統合

5: 情報抽出のアルゴリズム動作例が含まれる場合 (3) ユニットの名前がすべて大文字で、 3 文
図字以上で知識として与えた不要語を含まない場合のいずれであると判定する。
かに、そのユニットは構造が生成された後、で生成され最後に、構造で連結されていないユニッた連想構造の中から、トを削除し、連想構造を修正する。

IS-A

3.3

project
IS-A

step 2James AllenURL step 2 利用者の項目入力による、経路探索を用いた連想構造の生成と結果の出力
4.1

ヒューリスティックを用いたユニットと連想構造の統合ヒューリスティックを用いて、情報抽出過程で別個に生成されたユニットと連想構造を統合する。利用者が選択可能なヒューリスティックの中で、主要なものを表 に示す。

1

例

URL

2 が与
例えば、氏のホームページのえられた場合どのような処理が行われるのか説明する 図 参
照 。
解析によりファイル取得後、形態素解析を用いて、名詞句とそれに準じるものを概念ユニットとしてに囲まれる範囲から抽出する。見出し表現」、「生成されたユニット「」をとし、段落表現で囲まれる範)

情報整理

CM-2

university(IS-A)
TRAINS
project

同名の概念ユニットを統合する
辞書構造を参照して概念ユニットを統合するある概念ユニットの名前が他の概念ユニットの名前に含まれている時、その概念ユニットを key として他の概念ユニットを value とする連想構造を生成する
ある連想構造と他の連想構造の key が同じ時、連想構造を統合する

HTML( 54.2

利用者の項目入力による、経路探索を用いた連想構造の生成と結果の出力利用者の項目入力に従って、経路探索を用いて連想構造を生成し、結果を表や箇条書形式で出力する。概略は図 の6とおりである。
<h1>...</h1>
基本的には、項目 1 で入力された概念を、利用者の視点
James F.Allen
URCS Faculty
2 以降の入力は、視点に関する属性として設定する。項目
Member key<p>...<p>囲から生成されたユニット「Ph.D.」 「University of Toronto」 を設定する。視点として設定されたユニットから IS-A 構造で連結されるユニット (インスタンス) に関して、属性情報「University of Rochester」を value とする連想構造を生を整理する。
成する.
キーワードが入力されている場合には、上記のインスタ「James F.Allen」は「James」という英語名の単語をンスの中から、キーワードの文字列が含まれているユニット含むため「people」であると推論し、 IS-A 構造を生成する。
のみを抽出し、それらに関する属性情報を整理する。
「University of Rochester」「University of Toronto」は「university」という単語を含むため「university」であると推論し、 IS-A 構造を生成する。
4.3
例「James F.Allen」と「URCS Faculty Member」を key
例えば、利用者が「reasoning」に関連のある研究者とプとする連想構造から、 IS-A 構造によって連結されていないロジェクトについて知りたいとする。「reasoning」という「URCS Faculty Member」と「Ph.D.」を削除して、連想キーワードと、整理項目 1 「研究者」、整理項目 2 「プロジェ2 http://www.cs.rochester.edu/u/james/
クト」を入力した場合の動作例を示す (図 7参照)。

表2: 実験結果

begin

入力項目 1 と同名の概念ユニット item1 から IS-A 構造で連結されたユニット (インスタンス) を最初の key の候補集合
key1-candidates とする;
if item1 が辞書構造で連結されている辞書構造で連結されたユニットから IS-A 構造で連結されたユニット (インスタンス) を key1-candidatesに加える;
if キーワードが入力されている

thenelse key1s := key1-candidates;for すべての key1 := key1s dofor すべての item := 2 番目以降の入力項目
do begin

辞書構造で連結されたユニットから IS-A 構造で連結されたユニット (インスタンス) を value-candidatesに加える;
key1 から連想をたどって value-candidates の中から valueの集合 values を確定する;
key1, key2 を key とし, values を value とする連想構造を生成する

end;

結果を表または箇条書形式にして HTML ファイルを作成してブラウザに表示する

people93%85%

people以外のクラス

89%

83%

総合

90%

83%

project

78%

82%

project以外のクラス

65%

69%

総合

68%

73%

テスト2

キーワードの文字列を含む概念ユニットを探し連想をたどって
key1-candidates の中から最初の key の集合 key1s を確定
する

then

再現率

テスト1

then

key2 := item と同名の概念ユニット;
key2 から IS-A 構造で連結されたユニット (インスタンス) をvalue の集合 value-candidates とする;
if key2 が辞書構造で連結されている

適合率

正しく生成された連想構造のユニット数
適合率：× 100(%)
生成された連想構造のユニット数
正しく生成された連想構造のユニット数
再現率：× 100(%)
生成されるべき連想構造のユニット数

reasoning」というキーワードを名前に含むユニット「planreasoning」を検索する。「研究者」または「people」クラスのインスタンスであるユニットの中から、「plan reasoning」と連想構造でつながりがあるユニット「James F.Allen」を最初の key とする。項目 2 「プロジェクト」を 2 番目の keyとする。「プロジェクト」または「project」クラスのインスタンスであるユニットの中から、「James F.Allen」と連想構造でつながりがあるユニット「TRAINS」を value とし「て、連想構造を生成する。

end.

図

6: 情報整理 (step 2) のアルゴリズム

利用者入力
キーワード: reasoning
項目1: 研究者
項目2: プロジェクト

reasoning

プロジェクト

研究者

James F.Allen & topic
plan reasoning
discourse

研究者
peopleJames F.Allen(辞書)
プロジェクトpeopleproject(IS-A)(辞書)

James F.Allen

TRAINS

TRAINS

project(IS-A)

James F.Allen&プロジェクト
TRAINS

図7: 情報整理 (step2) のアルゴリズム動作例

5

実験と考察

100

URL
e-mail

人工知能研究者のホームページを示す
個のを入力して情報を抽出した後に、整理項目「研究者」「」「大学」「プロジェクト」「トピック」を入力して情報を整理するテスト と、整理項目「プロジェクト」「研究者」「大学」「トピック」を入力するテスト を行った。
生成されたユニットは個、連想構造は個、構造は個である。クラス判定ヒューリスティックの個でために与えた個別知識は、 つのクラスに関して

1

A7647552625

IS-7288ある。 people 毎に残りのクラスを整理するテスト 1、 project毎に残りのクラスを整理するテスト 2 の結果を表 2に示す。
この結果、適合率において研究者毎で 90%、プロジェク
ト毎で 68%、また再現率において研究者毎で 83%、プロジェクト毎で 73% の確度で情報整理が正しく行われることが確認できた。 project 毎は、 people 毎に比べると若干率が悪いが、これはもともとのページが人間に関するページであクラスのインスタンスと他のクラスのインスタり、ンスの間に直接的な連想関係がないためである。
我々のアプローチでは、連想構造を用いることにより、文書からの特別な自然言語処理を行なわなくても、重要なキーワード抽出と視点の変換がほぼ満足できる確度

projectHTMLで行えると評価する。の研究と比較する。これらの研究で本研究を佐藤らは、あらかじめ抽出したい情報ターゲットを設定し、ドメイ[6]ン知識や構造情報を与えて浅い自然言語処理に基づくプログラムを作成するアプローチがとられている。本研究では、利用者にドメイン知識がない場合や最初からほしい情報が文書ならどのようなドわからない場合も考慮して、と、メインでも汎用的に取り込み可能な過程 抽出知識を与えてより有用な情報を取り込む過程 抽出から構成されるアプローチをとった。連想構造を用いた我々のアプローチの長所は以下のとおりである。

HTML 抽出

step 2(step 2)( step 3)

step 3は汎用性があり、抽出はプログラム作成が容易であるため、プログラミング負荷が軽減される。

 利用者の項目入力による視点の変換と情報の整理、及び整理結果の出力が容易である。
短所は、現在は連想構造を生成する過程では知識をほとんど与えていないので、従来の方法と比べるときめ細かい情報抽出が難しく、情報の精度が低いことである。
この実験の主要な誤りは以下のように分類される。
抽出における名詞句生成失敗によるユニットの生成抽出における構造解析失敗にの誤り。
よる連想構造生成の誤り。
抽出における知識不足による構造生成の誤り。
抽出において、名詞句生今後の課題として、成のためのヒューリスティックを導入する、
構抽出中に得た知識を造解析の精度を向上させる、構造として再利用できるしくみをつくる、実験量をふ、他ドメイン、日本語などやして検証する クラス、などがあげられる。

(1)

step 2(2)

step 2

IS-A

(3)

(1)

step 2(3)(6HTML
step 3

URL(2) HTML
IS-A
(4))

おわりに雑多で構造の不均質なHTML 文書の情報を抽出・整理する手法を提案した。基本となるアイディアとして雑多な情報をゆるやかに関連づけるための連想構造というデータから情報構造を用いた。我々は、連想構造を用いてを収集し、整理する過程を支援するシステムを試作した。
では、
文書

Media version 2)

WWW
CM-2(Contextual
CM-2
HTMLを入力して、利用者の整理項目に従って情報を切り出し、構造化して出力できる。人工知能研究者のホームページをを実験的に評価したところ、適合率にお題材として、プロジェクト毎で、また再現率いて研究者毎でCM-2
90%68%において研究者毎で 83%、プロジェクト毎で 73% の確度で情報整理が正しく行われることが確認できた。
我々のアプローチでは、連想構造を用いることにより、文書からの特別な自然言語処理を行なわなくても、重要なキーワード抽出と、利用者入力による視点の変換がHTML可能な情報整理がほぼ満足できる確度で行えると評価する。

参考文献[1] Levy, A. Y., Sagiv, Y. and Srivasava, D.: Towards ecient information gathering agents, Working Notes of the AAAI Spring Symposium on Software Agents , pp.64{70 (1994).

[2] Armstrong, R., Freitag, D., Joachims, T. andMitchell, T.: A learning apprentice for the World
Wide Web, Working Notes of the AAAI Spring

Symposium on Information Gathering from Heterogeneous, Distributed Environments , pp.6{12 (1995).

[3] Balabanovi'c, M. and Shoham, Y.: Learning information retrieval agents: Experiments with automated web browsing, Working Notes of the AAAISpring Symposium on Information Gathering from
Heterogeneous, Distributed Environments , pp.13{18(1995).
[4] Li, W.: Knowledge Gathering and Matching in Heterogeneous Databases, Working Notes of the AAAI

Spring Symposium on Information Gathering from
Heterogeneous, Distributed Environments , pp.116{

121 (1995).
[5] Iwazume, M., Takeda, H., Nishida,T.: Ontologybased approach to information gathering and text
categorization, Proceedings of International Symposium on Didital Libraries, pp.186{193 (1995).
[6] 佐藤円, 佐藤理史, 篠田陽一.: 電子ニュースのダイジェ
スト自動生成, 情報処理学会論文誌, Vol. 36, No. 10,
pp.2371{2379 (1995).
[7] Brill, E.: Some Advance in TransformationBased Part of Speech Tagging, Proceedings of theTwelefth National Conference on Arti cial Intelligence (AAAI-94) , (1994).