発表資料 - 九州大学

半構造化文書に対する木構造と文字列
を組合せたラッパーの自動生成法
山田泰寛* 池田大輔** 廣川佐千男**
*九州大学大学院システム情報科学府
**九州大学情報基盤センター
発表手順
 コンテンツ抽出プログラム：ラッパー
 PLRラッパー
 PLRラッパーの自動生成法
 実験
 まとめと今後の課題
背景
異なるサイト間の情報を比較
たくさんのリンクを巡る
情報を記録・記憶
手間と時間がかかる
背景
自動的に統合
容易に比較が可能
（１）発見・収集（２）抽出・整列（３）統合
サイトごとにテンプレートが異なる
ラッパー
 1サイト上のWebページで同種の内容を含み、
大量に存在するものから、同種の内容を抽出
するプログラム

同一のテンプレートを持つ
ラッパー生成問題
 与えられた１サイト上のWebページの集合
から、同種の内容を抽出するためのルール
を作成する問題
 入力：同種の内容を含むWebページの集合
 出力：ルールの集合
ラッパー生成のポイント
 コンテンツ部分の特定


ページ中に広告や無関係な情報が含まれる
GUIや訓練例による半自動的な手法
 ルールの表現方法

文字列ベース


LRラッパー（Kushmerickら, 1997）
木構造ベース

Treeラッパー (村上ら, 2001)
LRラッパー
.....
廣川佐千男
.....
<a href=“mailto:[email protected]”>
Address: hirokawa.xxx.jp</a>
.....
山田泰寛
.....
<a href=“mailto:[email protected]”>
Address: [email protected]</a>
.....
項目を囲んでいる
左・右区切文字列で特定
同じ項目を囲む区切文字
列は同一
名前
左区切文字列: 5“>
右区切文字列: </f
LRラッパーの問題点
.....
廣川佐千男
.....
<a href=“mailto:[email protected]”>
Address: [email protected]</a>
.....
山田泰寛
.....
<a href=“mailto:[email protected]”>
Address: [email protected]</a>
.....
メールアドレス
左区切文字列: “>
右区切文字列: </a
左区切文字列が
特定できない
Treeラッパー
body
木構造のパスを用いて表現
font
a
font
a
名前
<body>--TEXT
メールアドレス
< body>-<a>-TEXT
廣川佐千男
山田泰寛
Address: [email protected]
Address: [email protected]
Treeラッパー問題点
body
font
a
font
a
Address: [email protected] Address: [email protected]
不必要な文字列まで抽出する
統合の際にノイズとなる
PLRラッパー
 PLR(Path-Left-Right)ラッパー


木構造によるパスの特定
左・右区切文字列
メールアドレス
パス < body>-<a>-TEXT
左区切文字列 Address:
右区切文字列 NULL
body
a
Address: [email protected]
a
Address: [email protected]
発表手順
 コンテンツ抽出プログラム：ラッパー
 PLRラッパー
 PLRラッパーの自動生成法
 実験
 まとめと今後の課題
高頻度部分（赤）と低頻度部分（黒）に分ける
ラッパー生成アルゴリズム
境界を決め、
ルールを抽出
(1) コンテンツ部分特定
入力：1サイト上の
複数の半構造化文書
出現頻度の低い
ルールを捨てる
(2)ルール抽出
出力：ルール
ルール
(3)不要なルールの削除
コンテンツ部分特定
高頻度部分（赤）
文字列
低頻度部分（黒）
対応
対応
構造記述部分
コンテンツ部分
 高頻度部分：頻度の高い部分文字列の現れる部分
 部分文字列の長さ n と頻度の上位 a (%)の決定

頻度の高い部分文字列が構造部分に現れるように
コンテンツ部分特定
 長さ n が小さいとき

文書１
文書２
文書３
頻度の高い部分文字列は構造記述・コンテンツ
部分の両方に現れる
コンテンツ部分特定
 長さ n が大きいとき


文書１
文書２
文書３
コンテンツ部分の頻度が下がる
頻度の高い部分文字列は構造記述部分のみに現れる
位置による頻度
(a) 長さ 2
(b) 長さ 5
コンテンツ部分特定
 長さ n が大きすぎるとき


文書１
文書２
文書３
構造記述部分の頻度が下がる
再び、頻度の高い部分文字列は構造記述・コンテンツ
部分の両方に現れる
コンテンツ部分特定
n: 小
a: 小
n: 小
a: 大
n: 大
a: 小
n: 大
a: 大
n: 大きすぎる
分割がうまく行なわれないときは、境界の数が大きい
交代数（山田他、Discovery Science 2001)
長さ n と割合 a の決定
初期状態(n,a)は(2,1)
2
3
4
1
2
n
n+1
長さ
(n, a)の交代数と
(n+1, a)、(n, a+1)の交代数を比較
a
a+1
極小の交代数をとる時、長さnと頻度の上位aは十分大きいと判断
%
出力例
 例１
 例２
高頻度部分（赤）と低頻度部分（黒）に分ける
ラッパー生成アルゴリズム
境界を決め、
ルールを抽出
(1) コンテンツ部分特定
入力：1サイト上の
複数の半構造化文書
出現頻度の低い
ルールを捨てる
(2)ルール抽出
出力：ルール
ルール
(3)不要なルールの削除
ルールの生成
 パスの特定


入力文書を木構造に展開
低頻度部分（黒）を含むノー
ドのパスを特定
ルールの生成
 区切文字列の抽出




前ステップで特定されたパスで特定されるノード
左区切文字列は、高頻度部分と低頻度部分の境界から前
に出現する文字列で共通する最長の文字列
右区切文字列は、低頻度部分と高頻度部分の境界から後
に出現する文字列で共通する最長の文字列
共通する文字列が無い場合は“NULL”
アドレスは[email protected]です。
アドレスは[email protected]です。
アドレスは[email protected]です。
左区切文字列“アドレスは”
右区切文字列“です。”
高頻度部分（赤）と低頻度部分（黒）に分ける
ラッパー生成アルゴリズム
境界を決め、
ルールを抽出
(1) コンテンツ部分特定
入力：1サイト上の
複数の半構造化文書
出現頻度の低い
ルールを捨てる
(2)ルール抽出
出力：ルール
ルール
(3)不要なルールの削除
不要なルールの削除
 有用な項目の判断


項目の出現に注目
ある文書には現れ、ある文書には現れない項目
 半数以上の文書から抽出できるルールを採用
高頻度部分（赤）と低頻度部分（黒）に分ける
ラッパー生成アルゴリズム
境界を決め、
ルールを抽出
(1) コンテンツ部分特定
入力：1サイト上の
複数の半構造化文書
出現頻度の低い
ルールを捨てる
(2)ルール抽出
出力：ルール
ルール
(3)不要なルールの削除
発表手順
 コンテンツ抽出プログラム：ラッパー
 PLRラッパー
 PLRラッパーの自動生成法
 実験
 まとめと今後の課題
実験
 産経新聞(日本語, 50ファイル)

本文, 日付, 見出し, ジャンル
ジャンル <html><head><title>TEXT
SankeiNULL
 Altavista（英語, 50ファイル） Sankei-international



検索結果の件数
左区切文字列“We_found_”
右区切文字列“_results”
We_found_187,302_results
失敗例(1)
 左・右区切文字列特定の問題点

産経新聞の日付
日付


<html><body bgcolor>TEXT
2002.01.1
NULL
項目部分が区切文字列の一部に含まれる
項目部分の一部が高頻度部分に含まれること
が原因
2002.01.12
日にちの１の位のみ低頻度部分
失敗例(2)
 同一ノードに複数の項目


例日付とセキュリティホールの種類
左・右区切文字列特定の問題点
[_2003,09,18_]_openssh_にセキュリティホール
いづれの項目も、左区切文字列“[_”
右区切文字列“_にセキュリティホール”
２つの項目が同時の項目として抽出される
Treeラッパーの問題点
<blockquote>
段落1
段落2
段落3
</blockquote>
産経新聞の本文部分
段落ごとにタグがはさまれている
本文全体ではなく、段落ごとに抽出
Treeラッパーの問題点
同じ項目にタグが挟まれている場合に、細かく分かれてしまう
ただし、全体として抜き出すほうがいいのか、
細かく抜き出すほうがいいのか判断が難しい
まとめ
 PLRラッパーの自動生成法



Treeラッパー + LRラッパー
項目部分を含むノードのパス
前後に共通する左・右区切文字列
 実験

不要な文字列の削除に成功
今後の課題
 境界特定の精度の向上


不要部分と項目部分
問題点：項目部分が区切文字列に含まれる
 複数の項目の分離

共通部分特定に改善の必要あり
 項目の抽出に成功した後

異なるサイト間の同種の項目の統合