九州大学学術情報リポジトリ Kyushu University Institutional Repository 自己学習型トピッククローラーの構築と評価 冨山, 北斗九州大学大学院システム情報科学研究府 伊東, 栄典九州大学情報基盤研究開発センター 廣川, 佐千男九州大学情報基盤研究開発センター

九州大学学術情報リポジトリ

Kyushu University Institutional Repository

自己学習型トピッククローラーの構築と評価

冨山, 北斗

九州大学大学院システム情報科学研究府

伊東, 栄典

九州大学情報基盤研究開発センター

廣川, 佐千男

九州大学情報基盤研究開発センター

Tomiyama, Hokuto

他

http://hdl.handle.net/2324/17784

出版情報：電子情報通信学会 第17回データ工学ワークショップ(DEWS 2006), 2006-01-06. 電子情報通信

学会

バージョン：

権利関係：

DEWS2006 1A-XX

自己学習型トピッククローラーの開発と評価

冨山 北斗

†

伊東 栄典

‡

廣川 佐千男

‡

†九州大学システム情報科学府 〒812-8581 福岡市東区箱崎 6-10-1

‡九州大学情報基盤センター 〒812-8581 福岡市東区箱崎 6-10-1

E-mail: †hokuto.tomiyama@i.kyushu-u.ac.jp, ‡{itou, hirokawa}@cc.kyushu-u.ac.jp

あらまし Web 上の情報量は、個人が必要とする情報量をはるかに上回っている。利用者の情報収集を支援する、

Google や Yahoo 等の汎用的な検索エンジンが開発されている。しかし汎用的な検索エンジンでは、特定の分野につ

いて網羅的に収集し、情報をまとめるといった要求には応えられない。著者らは、特定分野の Web ページ収集を

効率的に行なうトピッククローラーの研究開発を行なっている。トピッククローラーでは、トピックに関するペー

ジの判定精度も必要であるが、トピックページへ早く辿りつく速度も重要である。著者らは、One man & his dog シ

ステムと呼ぶトピック判定とリンク選出戦略機能を連携させるシステムを試作した。また、２つのトピックについ

ての収集実験を行い本論文の手法の効率性を調査した。

キーワード Web とインターネット，情報検索，知識発見，トピッククローラー

1. は じ め に

Web（ WorldWideWeb）の 情 報 量 は 個 人 が 必 要 と す る 情 報 量 を は る か に 上 回 っ て お り 、 情 報 爆 発 と 呼 ば れ る 状 況 を 作 り 出 し て い る 。 そ こ で 、 利 用 者 が 求 め る 情 報 を Web か ら 探 し 出 す た め に 、Google[1]や Yahoo[2]と い っ た 汎 用 的 な 検 索 エ ン ジ ン が 構 築 、 提 供 さ れ て い る 。 ま た 、 こ の よ う な 汎 用 目 的 の 検 索 エ ン ジ ン で は 対 応 で き な い 詳 細 な 検 索 要 求 に 対 応 す る た め 、 特 定 分 野 の 情 報 の み を 対 象 に し た 検 索 サ ー ビ ス を 提 供 す る 専 門 検 索 エ ン ジ ン も 多 数 存 在 し て い る 。 更 に 、 要 求 に 見 合 う Web ペ ー ジ を 見 つ け 出 す こ と に 留 ま ら ず 、Web 上 に 存 在 す る 情 報 に 対 し て 、自 動 的 に 知 識 を 発 見 す る Web マ イ ニ ン グ の 研 究 も 盛 ん に 行 わ れ て い る [5]。こ う い っ た 専 門 検 索 エ ン ジ ン の 構 築 や 、 Web マ イ ニ ン グ の 研 究 の 際 に は 、対 象 と す る 特 定 分 野（ ト ピ ッ ク ）の デ ー タ を 、 高 品 質 か つ 多 数 収 集 し な け れ ば な ら な い 。 そ の た め 、 特 定 ト ピ ッ ク の ペ ー ジ を 効 率 良 く 収 集 す る シ ス テ ム が 必 要 で あ る 。 我 々 は 、 ト ピ ッ ク 判 定 と リ ン ク 選 出 戦 略 機 能 を 連 携 さ せ る ”One man & His dog”と 呼 ぶ シ ス テ ム を 搭 載 し た 自 己 学 習 型 ト ピ ッ ク ク ロ ー ラ ー （ G-CRAWLER） を 試 作 し た 。 本 論 文 で は G-CRAWLER に つ い て 説 明 し 、 こ れ を 用 い た 収 集 実 験 及 び 性 能 評 価 に つ い て 述 べ る 。 本 論 文 の 構 成 は 以 下 の 通 り で あ る 。 第 ２ 章 で は 一 般 的 な Web ク ロ ー ラ ー に つ い て 述 べ る 。ま た 、一 般 的 な 収 集 方 法 と 特 定 分 野 （ ト ピ ッ ク ） の 収 集 の 違 い に つ い て も 述 べ る 。 第 ３ 章 で は 関 連 研 究 に つ い て 簡 単 に 紹 介 す る 。 第 ４ 章 で は 開 発 し た 自 己 学 習 型 ト ピ ッ ク ク ロ ー ラ ー （ G-CRAWLER） を 紹 介 し 、 そ の 特 徴 的 な シ ス テ ム で あ る One man & His dog シ ス テ ム に つ い て 述 べ る 。

第 ５ 章 で は ２ つ の ト ピ ッ ク に つ い て の 収 集 実 験 を 述 べ る 。 第 6 章 で は 実 験 の 結 果 に つ い て の 議 論 と 考 察 を 述 べ る 。 最 後 に 第 ７ 章 で ま と め と 今 後 の 課 題 を 述 べ る 。

2. Web ク ロ ー ラ ー と Web ペ ー ジ の 収 集

一 般 的 な ク ロ ー ラ ー に つ い て 簡 単 に 説 明 す る 。 ま た 、 一 般 的 な 収 集 方 法 と 、 特 定 分 野 （ ト ピ ッ ク ） の 収 集 の 違 い に つ い て も 述 べ る 。

2.1. ク ロ ー ラ ー と は

Web ペ ー ジ の 収 集 を 人 手 で 行 う に は 莫 大 な 時 間 と 人 件 費 が か か る 。そ こ で 、人 に 代 わ っ て Web ペ ー ジ の 自 動 収 集 を 行 う プ ロ グ ラ ム が 必 要 に な る 。 こ の た め の プ ロ グ ラ ム が Web ク ロ ー ラ ー と 呼 ば れ る も の で あ る 。 Web ク ロ ー ラ ー は 、『 Web ロ ボ ッ ト 』、『 Web ス パ イ ダ ー 』と 呼 ば れ る こ と も あ る [9]。Google な ど の 検 索 エ ン ジ ン で も こ の Web ク ロ ー ラ ー を 用 い て い る 。

2.2. ク ロ ー ラ ー の Web ペ ー ジ 収 集 の し く み

Web ク ロ ー ラ ー が Web ペ ー ジ を 取 得 し て い く 仕 組 み を 示 す 。 ま ず 与 え ら れ た URL 集 合 か ら 次 に 取 得 す る URL を 選 ぶ 。そ し て Web サ ー バ に ア ク セ ス し 、収 集 可 能 な ら Web ペ ー ジ を ダ ウ ン ロ ー ド し 、 保 存 す る 。 取 得 し た ペ ー ジ か ら 、リ ン ク の 抽 出 を 行 い 、URL 集 合 に 追 加 す る 。 以 下 、 こ の 処 理 を 繰 り 返 す こ と で 、 ク ロ ー ラ ー は Web ペ ー ジ を 収 集 し て い く 。 処 理 の 流 れ 図 を 図 １ に 示 す 。

図 1 Web ク ロ ー ラ ー の 処 理 の 流 れ 図

2.3. 一 般 的 な 収 集 と 特 定 分 野 の 収 集

る こ と が 多 が 欲 し い 』、『 求 人 情 報 の デ ー タ が の 収 集 の イ メ ー ジ の 違 い を 一 般 的 な 収 集 方 法 で は 、 幅 優 先 探 索 を 用 い い 。 こ の 収 集 方 法 で は 、 Web ペ ー ジ を 広 く 、 浅 く 収 集 し て い く こ と に な る 。 指 定 し た 範 囲 の ペ ー ジ を も れ な く 収 集 で き る 、 プ ロ グ ラ ム へ の 実 装 が 容 易 で あ る な ど の 利 点 が あ る 。 『 レ シ ピ の デ ー タ 欲 し い 』 な ど の あ る 特 定 分 野 （ ト ピ ッ ク ） に つ い て 収 集 す る 場 合 に は 、 幅 優 先 探 索 で は 効 率 の 良 い 収 集 が で き な い 。こ こ で 、効 率 の 良 い 収 集 と は 、『 で き る だ け 必 要 な Web ペ ー ジ だ け を 集 め 、 必 要 の 無 い ペ ー ジ は で き る だ け 集 め な い 収 集 法 』 と す る 。 特 定 の ト ピ ッ ク に 関 す る ペ ー ジ を 効 率 よ く 集 め る た め に は 、 何 か う ま い 手 法 を 考 え る 必 要 が あ る 。 一 般 的 な 収 集 と 、 特 定 分 野 図 2 に 示 し た 。 図 2 一 般 的 な 収 集 と 特 定 分 野 の 収 集

3. 関 連 研 究

Chakrabarti[7,8]ら は 、 収 集 し た い ト ピ ッ ク X に 関 連 す る ペ ー ジ か ら 収 集 を 始 め 、X に 関 連 す る Web ペ ー ジ を 選 択 的 に 収 集 し て い く Focused Crawler に つ い て 研 究 し て い る 。 例 え ば 『 レ シ ピ 』 を 集 め た い と い う 要 求 が あ っ た と し よ う 。レ シ ピ が Web 上 に ど の よ う に 存 在 し て い る か と 考 え る と 、 料 理 に 関 す る ペ ー ジ の 近 く に 多 く 存 在 し て い る と 経 験 的 に 分 か る は ず で あ る 。 つ ま り 、『 似 て い る ペ ー ジ は Web 上 に お い て 近 い 場 所 に 存 在 し て い る 』 ⇒ 『 タ ー ゲ ッ ト に 似 て い る ペ ー ジ （ 関 連 度 の 高 い ペ ー ジ ） を 集 め て い け ば 、 タ ー ゲ ッ ト も 集 ま り や す い は ず だ 』 と い う の が 、 こ の ク ロ ー ラ ー の 発 想 で あ る 。ち な み に 、ト ピ ッ ク X へ の 関 連 度 は 、事 前 に よ く 学 習 さ れ た 文 書 分 類 器 で 計 算 す る 。 Diligenti[6]ら は 、 タ ー ゲ ッ ト ペ ー ジ 周 辺 の 典 型 的 な 文 脈（ リ ン ク 情 報 ）を 学 習 し た context graphs を 用 い た ク ロ ー ラ ー に つ い て 研 究 し て い る 。図 3 に context graph の 概 念 図 を 示 す 。 図 3 context graphs の 例 タ ー ゲ ッ ト に １ 回 の リ ン ク で 辿 り 着 く ペ ー ジ 群 を レ イ ヤ ー 1、2 回 の リ ン ク で た ど り 着 く ペ ー ジ 群 を レ イ ヤ ー 2 と し 、以 下 、レ イ ヤ ー 3、レ イ ヤ ー 4 と 定 義 す る 。 こ う し て 、 あ る 一 定 の 大 き さ を も っ た グ ラ フ （ context graphs） を 事 前 に 作 成 す る 。 こ の グ ラ フ は タ ー ゲ ッ ト 周 辺 の 特 徴 を 示 し た 地 図 の よ う な も の で あ る 。 地 図 を 用 い な が ら 探 索 す る こ と で 、 タ ー ゲ ッ ト ペ ー ジ を 発 見 し や す く な る と い う 発 想 で あ る 。 Martin ら は 、 Web サ イ ト を 発 見 す る 外 部 ク ロ ー ラ ー と 、 サ イ ト 内 を ク ロ ー リ ン グ す る 内 部 ク ロ ー ラ ー を 統 合 し た Web ク ロ ー ラ ー の 研 究 を 行 っ て い る [11]。 こ の 手 法 は 、 サ イ ト 内 の ペ ー ジ を 探 す の で は な く 、 ト ピ ッ ク に 関 す る サ イ ト を 探 す こ と を 目 的 と し て い る 。

4. 自 己 学 習 型 ト ピ ッ ク ク ロ ー ラ ー

我 々 は G-CRAWLER と 呼 ぶ 自 己 学 習 型 ト ピ ッ ク ク ロ

ー ラ ー を 開 発 し て い る [10]。 G-CRAWLER の 概 要 と 、 内 部 に 搭 載 し て い る One man & His dog シ ス テ ム に つ い て 述 べ る 。

4.1. G-CRAWLER の 概 要

図 4 に G-CRAWLER の 処 理 の 流 れ を 示 す 。 図 4 G-CRAWLER の 処 理 の 流 れ G-CRAWLER の 特 徴 は 、 リ ン ク 先 ペ ー ジ が タ ー ゲ ッ ト で あ る か ど う か を 判 定 す る 関 数 と 、 リ ン ク 元 ペ ー ジ の 評 価 す る 判 定 関 数 と の 、 二 つ の 判 定 関 数 を 持 っ て い る こ と で あ る 。 さ ら に 、 リ ン ク 元 ペ ー ジ 判 定 関 数 は 、 学 習 機 能 を 持 っ て い る 。 こ の シ ス テ ム を 、 One man & His dog シ ス テ ム と 名 づ け て い る 。 次 節 で One man & His dog シ ス テ ム に つ い て 説 明 す る 。

4.2. One man & His dog シ ス テ ム

G-CRAWLER が 搭 載 す る One man & His dog シ ス テ ム は リ ン ク 先 ペ ー ジ が タ ー ゲ ッ ト か ど う か を 判 定 す る 関 数 を 犬（ dog）に 見 立 て 、リ ン ク 元 ペ ー ジ の ス コ ア を 判 定 す る 関 数 を 人 間 （ man） に 見 立 て る シ ス テ ム で あ る (図 5 参 照 )。リ ン ク 元 ペ ー ジ を 判 定 す る「 人 間 」は 、 学 習 を 行 う 。

図 5 One man & His dog シ ス テ ム の イ メ ー ジ 「 人 間 」 の 学 習 機 能 に つ い て 述 べ る 。 犬 が リ ン ク 先 ペ ー ジ を タ ー ゲ ッ ト で あ る と 判 定 し た 場 合 、 人 間 は リ ン ク 元 ペ ー ジ を 形 態 素 解 析 し て 、 単 語 情 報 を 抽 出 し 、 正 例 と し て デ ー タ ベ ー ス に 登 録 す る 。つ ま り 、『 タ ー ゲ ッ ト に 結 び つ く ペ ー ジ 出 現 す る 単 語 』 を 学 習 す る （ 図 6 参 照 ）。 犬 が リ ン ク 先 ペ ー ジ を タ ー ゲ ッ ト で は な い と 判 定 し た 場 合 も 同 様 の 処 理 を 行 う 。 こ の 場 合 は 、 負 例 と し て デ ー タ ベ ー ス に 登 録 す る 。つ ま り 、『 タ ー ゲ ッ ト に 結 び つ か な い ペ ー ジ に 出 現 す る 単 語 』 を 学 習 す る 。 図 6 犬 が タ ー ゲ ッ ト を 発 見 し た 場 合 正 例 、 負 例 の 単 語 情 報 は そ れ ぞ れ 以 下 の よ う な 形 で 足 し 合 わ せ て い く 。

( )

=

( )

+

_∑

( )

+ i t i i t

w

P

w

P

w

P

₁

( )

=

( )

+

_∑

( )

+ i t i i t

w

N

w

N

w

N

₁ こ こ で 、 wi (i=0,1, ...) は ペ ー ジ に 出 現 す る 単 語 、 P は 正 例 の 単 語 情 報（ Positive Word）を 格 納 し た 配 列 、N は 負 例 の 単 語 情 報（ Negative Word）を 格 納 し た 配 列 で あ る 。ま た 、tは ク ロ ー ラ ー が 辿 る ペ ー ジ の 訪 問 順 番 で あ る 。 例 え ば 、3000 番 目 の ペ ー ジ (t=3000)ま で で 、P(wi)の 値 が 45 だ と す る 。 3001 ペ ー ジ 目 に 単 語 wiが 5 回 出 現 し 、 か つ そ の ペ ー ジ が タ ー ゲ ッ ト と な る ト ピ ッ ク の ペ ー ジ で あ る と す る 。こ の 場 合 、P(wi)の 値 を +5、つ ま り 50 に す る 。 タ ー ゲ ッ ト で は な い 場 合 、 N(wi)の 値 を ＋ ５ す る 。 人 間 は 次 に 辿 る ペ ー ジ を 決 め る た め に 、 収 集 ペ ー ジ か ら URL を 抜 き 出 す 。 そ の 際 、 前 述 の P と N を も と に URL へ 次 の 式 で ス コ ア 付 け を す る 。 Score(URL) =

∑

+

t t t

N

P

P

正 例 の 単 語 を 多 く 含 む ペ ー ジ か ら の リ ン ク は ス コ ア を 高 く 、 負 例 の 単 語 を 多 く 含 む ペ ー ジ か ら の リ ン ク は ス コ ア が 低 く な る 。そ し て 、ス コ ア 付 け さ れ た URL を URL キ ュ ー に 追 加 す る 。図 7 に ス コ ア 付 け の 様 子 を 示 す 。

One man & His dog シ ス テ ム は 、 タ ー ゲ ッ ト へ の リ ン ク が 張 ら れ て い そ う な ペ ー ジ か ら の リ ン ク を 優 先 す る と い う 、 単 純 な 考 え に 基 づ い て い る 。 人 間 が 学 習 し

た 知 識 に 基 づ い て 次 に 訪 れ る 場 所 を 決 定 し 、 犬 を そ の 場 所 に 行 か せ る 。そ し て 、犬 が 訪 れ た ペ ー ジ を 判 定 し 、 そ の 結 果 に よ り ま た 人 間 が 学 習 す る ・ ・ ・ と い っ た イ メ ー ジ で あ る 。 図 7 URL の ス コ ア 付 け

4.3. リ ン ク 集 と タ ー ゲ ッ ト

One man & His dog シ ス テ ム で 効 率 よ く 集 ま る ペ ー ジ 郡 の 構 造 に つ い て 述 べ る 。 Web に お い て 、 あ る 特 定 ト ピ ッ ク に 関 す る ペ ー ジ を 集 め た リ ン ク 集 ペ ー ジ を 作 る こ と は 、 よ く 行 わ れ て い る 。 リンク集ページ ターゲットページ リンク集ページ ターゲットページ 図 8 リ ン ク 集 と タ ー ゲ ッ ト の 構 造 す な わ ち 、 図 8 の よ う な リ ン ク 集 ペ ー ジ が 見 つ か れ ば 、 大 量 の タ ー ゲ ッ ト が 得 ら れ る 。 リ ン ク 集 ペ ー ジ の 特 徴 を 学 習 し 、 そ こ か ら の リ ン ク 先 を 優 先 し て 収 集 す る こ と で 、 タ ー ゲ ッ ト ペ ー ジ の 収 集 効 率 を 上 げ る の が One man & His dog シ ス テ ム の 発 想 で あ る 。

5. 収 集 実 験

こ の 章 で は 、 G-CRAWLER の 実 験 と 性 能 評 価 に つ い て 述 べ る 。 ま ず 、 実 験 の 評 価 指 標 お よ び ３ つ の 実 験 方 法 に つ い て 述 べ る 。 次 に レ シ ピ の 収 集 実 験 お よ び ニ ュ ー ス 記 事 の 収 集 実 験 に つ い て 述 べ る 。

5.1. 評 価 指 標

G-CRAWLER を 評 価 す る に 当 た っ て 、 次 の ２ つ の 指 標 を 考 え る 。 ① タ ー ゲ ッ ト 判 定 関 数 の 評 価 ② 収 集 速 度 ③ 学 習 機 能 の 評 価 ① は 収 集 し た ペ ー ジ が 、 集 め た い ト ピ ッ ク の ペ ー ジ で あ る か ど う か の 正 確 さ で あ る 。 つ ま り 、 One man & His dog シ ス テ ム に お い て は 、 ど の く ら い 正 確 に 判 断 で き る 犬 な の か と い う こ と に な る 。 こ の 評 価 に は 、 適 合 率 （ precision） を 使 う 。

ーゲット数

システムが見つけたタ

真のターゲット数

=

precision

② の 収 集 速 度 は 、 ト ピ ッ ク の ペ ー ジ へ の 辿 り や す さ を 表 す 。 訪 問 ペ ー ジ 数 に 対 し 、 取 得 タ ー ゲ ッ ト 数 が 多 け れ ば 、 早 い （ 効 率 の よ い ） ク ロ ー ラ ー で あ る と い え る 。 こ の 評 価 に は 、 縦 軸 を 収 集 し た タ ー ゲ ッ ト ペ ー ジ 数 、 横 軸 を ク ロ ー ラ ー の 訪 問 ペ ー ジ 数 に し た グ ラ フ を 描 く 。 One man & His dog シ ス テ ム で は 、 人 間 の リ ン ク 先 選 択 戦 略 機 能 の 効 率 を あ ら わ す 。

③ に つ い て は 、 One man & His dog シ ス テ ム に お け る 人 間 の 学 習 機 能 の 効 率 を あ ら わ す 。 そ の た め に 、 単 な る 幅 優 先 探 索 と 、 学 習 機 能 を 有 効 に し た 場 合 と を 比 べ て 、 収 集 効 率 の 変 化 を 調 査 す る 。 さ ら に 、 一 回 目 に 学 習 し た 単 語 情 報 を 使 っ て 再 度 収 集 し 、 学 習 結 果 を 活 用 し た 場 合 に つ い て も 収 集 効 率 を 調 べ た 。

5.2. 実 験 方 法

収 集 し た ト ピ ッ ク に つ い て 述 べ る 。 実 験 で は 、「 料 理 の レ シ ピ 」（ 以 下 レ シ ピ ）と「 ワ ー ル ド カ ッ プ サ ッ カ ー の ニ ュ ー ス 記 事 」（ 以 下 、ニ ュ ー ス 記 事 ）２ つ の ト ピ ッ ク を 選 ん だ 。 レ シ ピ は 、 ト ピ ッ ク か ど う か の 判 定 が し や す く 、 か つ 図 ８ に あ る 構 造 を 持 つ 例 と し て 選 ん で い る 。「 レ シ ピ 」 と い う 単 語 を 含 む 文 書 は 、 料 理 レ シ ピ 以 外 に は ほ と ん ど 存 在 し な い た め 、 判 定 が 容 易 で あ る 。 一 方 、 ワ ー ル ド カ ッ プ に つ い て は 、関 連 す る ペ ー ジ が 多 い た め 、 簡 単 に ト ピ ッ ク 判 定 が で き な い 。 次 に 、 収 集 方 法 に つ い て 述 べ る 。 実 験 で 用 い た 表 1 に 実 験 方 法 を 述 べ る 。方 法 と し て 、ABC の 3 通 り の 方 法 を 比 較 し た 。 方 法 内 容 A 幅 優 先 探 索 B 学 習 機 能 ON C 学 習 機 能 ON２ 回 目 表 1 収 集 方 法

な お 、Precision の 値 は 、実 験 に よ り ク ロ ー ラ ー が 見 つ け た タ ー ゲ ッ ト ペ ー ジ が 、 本 当 に ト ピ ッ ク ペ ー ジ で あ る か を 人 手 で 一 つ 一 つ 判 断 し 、 算 出 し て い る 。

5.3. レシピ収 集 実 験

ま ず 、 レ シ ピ の 収 集 実 験 に つ い て 述 べ る 。『 味 の 素 レ シ ピ 大 百 科 』[3]の サ イ ト か ら 、レ シ ピ の 収 集 実 験 を 行 っ た 。ス タ ー ト URL を サ イ ト の ト ッ プ ペ ー ジ に 設 定 し た 。 た ど る リ ン ク を サ イ ト 内 に 限 定 し 、 他 の サ イ ト に 飛 ば な い よ う に し た 。 そ し て 、 １ 万 ペ ー ジ を 収 集 し た 。 結 果 を 表 2 に 示 す 。 方 法 収 集 数 正 解 数 Precision A 3,860 3,860 1 B 6,435 6,435 1 C 6,807 6,807 1 表 2 レ シ ピ 集 実 験 結 果 図 9 レ シ ピ 集 実 験 precision が １ と 、最 高 の 値 を 出 し て い る が 、こ れ は 、 サ イ ト 内 の レ シ ピ は 全 て 、 あ る テ ン プ レ ー ト に 沿 っ て 書 か れ て お り 、 そ の お か げ で 正 確 な 判 定 関 数 を 作 成 す る こ と が で き た か ら で あ る 。 レ シ ピ ペ ー ジ の 例 は 、 図 10 に 示 し た 。 こ の よ う に 、 タ ー ゲ ッ ト ペ ー ジ が あ る 基 準 に そ っ て 書 か れ て い れ ば 、 正 確 な タ ー ゲ ッ ト 判 定 関 数 を 作 成 す る こ と が で き る 。 し か し 、 こ の サ イ ト 以 外 の 、 つ ま り Web 上 に 存 在 す る 他 の 多 く の レ シ ピ に つ い て は 、 こ の サ イ ト の テ ン プ レ ー ト に 沿 っ て 書 か れ て い る わ け で は な い の で 、 こ こ で 用 い た 判 定 関 数 が 、 ど ん な レ シ ピ で も 正 確 に 判 定 で き る わ け で は な い 。 図 10 レ シ ピ ペ ー ジ の 例

5.4. ニ ュ ー ス 記 事 収 集 実 験

こ こ で は ニ ュ ー ス 記 事 の 収 集 実 験 に つ い て 述 べ る 。 集 め る タ ー ゲ ッ ト は 、サ ッ カ ー W 杯 に 関 す る ニ ュ ー ス 記 事 と し た 。ニ ュ ー ス サ イ ト『 asahi.com』[4]の ス ポ ー ツ ニ ュ ー ス の ト ッ プ ペ ー ジ を ス タ ー ト URL に 指 定 し て 、最 大 訪 問 ペ ー ジ 数 を 1000 ペ ー ジ と し た 。タ ー ゲ ッ ト の 判 定 は 、 出 現 単 語 に つ い て 、 （ ワ ー ル ド カ ッ プ ∨ W 杯 ） ∧ サ ッ カ ー を 満 た す も の と し た 。 収 集 し た タ ー ゲ ッ ト に 対 し て 、 人 目 で 確 認 を 行 っ た 結 果 、 次 の よ う に な っ た 。 方 法 収 集 数 正 解 数 Precision A 11 10 0.909 B 89 87 0.978 C 106 103 0.972 表 3 ニ ュ ー ス 収 集 実 験 結 果 図 11 ニ ュ ー ス 収 集 実 験

収 集 し た ニ ュ ー ス 記 事 の 例 は 図 12 に 示 す 。 図 12 収 集 し た 記 事 の 例

6. 考 察

6.1. 学 習 効 果

学 習 機 能 の 効 果 に つ い て 考 察 す る 。 図 9、 図 １ １ か ら も わ か る よ う に 、A の 幅 優 先 探 索 よ り も B の 学 習 機 能 を 使 っ た 場 合 の 方 が 、 明 ら か に 効 率 が 良 い こ と が わ か る 。 レ シ ピ の 場 合 、 訪 問 ペ ー ジ が 1 万 ペ ー ジ の 時 点 で 、 B の 学 習 機 能 を ON に し た 場 合 で は 、 A の 幅 優 先 探 索 の 場 合 に 比 べ て 、約 1.67 倍 の レ シ ピ を 収 集 で き て い る 。 ニ ュ ー ス 記 事 の 場 合 、1000 ペ ー ジ の 時 点 で B の 学 習 機 能 を ON に し た 方 が A の 幅 優 先 探 索 の 8.7 倍 の ペ ー ジ を 収 集 で き て い る 。 ま た 、 C の 蓄 積 さ れ た 単 語 情 報 を 最 初 か ら 生 か し た 場 合 は 、両 方 の 実 験 に お い て B よ り も 効 率 が 上 が っ て い る 。 つ ま り 、 学 習 機 能 を 使 っ た 場 合 （ B と C） は 、 幅 優 先 探 索 の 場 合 と 比 べ て 、 収 集 の ス ピ ー ド が 早 い と い う こ と が 言 え る 。 た だ し 、図 ９ 、図 １ １ を み る と 、B の 学 習 機 能 を ON に し た 場 合 で は 、開 始 直 後 は A の 幅 優 先 探 索 よ り も 効 率 よ く 収 集 で き て い な い 。 し か し 、 単 語 情 報 が 集 ま っ て く る 中 盤 以 降 は 、 蓄 積 し た 知 識 を 生 か し て 、 収 集 効 率 が 大 幅 に 上 が っ て い る 。つ ま り 、One man & His dog シ ス テ ム に お い て は 、 学 習 を 重 ね る こ と で 、 人 間 の 頭 が 良 く な っ て い く と い う イ メ ー ジ で あ る 。 実 験 数 が 少 な い の で 、 た ま た ま こ の よ う な 結 果 が 出 た の か も し れ な い が 、 未 学 習 の 場 合 が 幅 優 先 探 索 よ り も 効 率 が 悪 い 理 由 に つ い て は 、 今 後 調 査 し て い く 。 C の 蓄 積 さ れ た 単 語 情 報 を 最 初 か ら 用 い た 場 合 で は 、 ス タ ー ト 直 後 か ら で も 効 率 よ く 収 集 で き て い る こ と が 分 か る 。 蓄 積 さ れ た 知 識 （ 単 語 情 報 ） を 次 回 の 収 集 に 生 か せ る と い う 利 点 が 、 One man & His dog シ ス テ ム に は あ る と 言 え る 。

6.2. リ ン ク 集 と タ ー ゲ ッ ト

レ シ ピ や 、 ニ ュ ー ス 記 事 が 4.3 節 で 述 べ た よ う な 、 リ ン ク 集 と タ ー ゲ ッ ト の 構 造 を し て い る か ど う か を 調 べ た 。 そ の 結 果 、 図 １ ３ や 図 １ ４ の よ う な リ ン ク 集 ペ ー ジ が 見 つ か っ た 。 こ れ に よ り 、 リ ン ク 集 と タ ー ゲ ッ ト の 構 造 を も つ ペ ー ジ 群 に 対 し て 、One man & His dog シ ス テ ム は 効 率 良 く ト ピ ッ ク ペ ー ジ の 収 集 を 行 え こ と が 分 か っ た 。

図 13 レ シ ピ へ の リ ン ク 集 ペ ー ジ

7. ま と め と 今 後 の 課 題

Web 上 の 情 報 量 の 爆 発 的 増 加 に 伴 い 、 専 門 検 索 エ ン ジ ン の 構 築 や 、 Web マ イ ニ ン グ な ど と い っ た 研 究 が 盛 ん に 行 わ れ て い る 。 ま た 、 日 常 の 様 々 な 場 面 で 情 報 技 術 の 利 用 が 進 め ら れ て い る 。 本 論 分 で は 特 定 の ト ピ ッ ク に 関 す る Web ペ ー ジ を 効 率 よ く 収 集 す る 自 己 学 習 型 ト ピ ッ ク ク ロ ー ラ ー （ G-CRAWLER） に つ い て 述 べ た 。G-CRAWLER の 特 徴 と し て 、リ ン ク 先 と リ ン ク 元 、 二 つ の 判 定 関 数 を も ち い た 学 習 シ ス テ ム で あ る One man & His dog シ ス テ ム が あ げ ら れ る 。 こ の 学 習 シ ス テ ム の 効 率 を 評 価 す る た め に 、 レ シ ピ と ニ ュ ー ス に つ い て 収 集 実 験 を 行 い 、 ペ ー ジ が リ ン ク 集 と タ ー ゲ ッ ト の 構 造 を 持 っ て い れ ば 、 一 般 的 な 幅 優 先 探 索 の 手 法 よ り も ト ピ ッ ク ペ ー ジ を 効 率 よ く 集 め る こ と が で き る こ と を 示 し た 。 今 後 の 課 題 と し て は 、 ま ず 他 の 論 文 で 提 案 さ れ て い る 手 法 と の 比 較 を 行 う 。 関 連 研 究 の 章 で と り あ げ た 手 法 と 、 我 々 の One man & His dog シ ス テ ム と の 比 較 実 験 を 行 う 予 定 で あ る 。 た だ し 、 比 較 の た め に は 他 者 の 収 集 手 法 の 実 装 が 必 要 に な る 。 リ ン ク 集 と タ ー ゲ ッ ト 群 と の 構 造 に な っ て い な い ト ピ ッ ク で の 、 One man & His dog シ ス テ ム の 効 果 も 確 か め る 予 定 で あ る 。 最 終 的 に は 扱 い や す い イ ン タ ー フ ェ ー ス の 開 発 、 新 た な 機 能 な ど の 追 加 を 行 い 、 Web 上 か ら の デ ー タ 収 集 の た め の 強 力 な ツ ー ル の 開 発 を 目 指 し た い 。

文 献

[1] Google : http://www.google.co.jp/ [2] Yahoo! : http://www.yahoo.co.jp/ [3] 味 の 素 レ シ ピ 大 百 科 : http://www.ajinomoto.co.jp/recipe/ [4] asahi.com : http://www.asahi.com/ [5] 鈴 木 英 之 進 、 他 , “特 集 最 新 ！ デ ー タ マ イ ニ ン グ 手 法 ”,情 報 処 理 , vol.46 No.1, pp.4-51, 2005.

[6] M. Diligenti et al., “Focused Crawling Using Context Graphs”, Proc. of the 26th International Conference on Very Large Data Bases(VLDB2000), pp.527 – 534,2000.

[7] Soumen Chakrabarti et al., “Focused crawling: a new approach to topic specific Web resource discovery”, Computer Networks, Vol31, No.11-16, pp.1623-1640, 1999.

[8] Soumen Chakrabarti et al., “Accelerated focused crawling through online relevance feedback”, Proceedings of the 11th inrnational conference on World Wide Web, pp.148 – 159, 2002.

[9] Kevin Hemenway, Tara Calishain, 村 上 雅 章 （ 訳 ） , “Spidering Hacks”, オ ラ イ リ ー ・ ジ ャ パ ン , 2004. [10] Yoshihiro Matsunaga, Shintaro Yamada, Eisuke Ito,

Sachio Hirokawa, “A Web Syllabus Crawler and its E

ciency Evaluation”, Proc. of International Symposium on Information Science and Electrical Engineering 2003, pp.565-568, 2003.

[11] Martin Ester, Hans-Peter Kriegel, Matthias Schubert, “Accurate and Efficient Crawling for Relevant Websites”, Proc. of the 30th VLDB Conference (VLDB2004), pp.396-407, 2004.