題目 Web 検索結果の概観提示による 情報収集支援システム

平成

16

筑波大学第三学群情報学類

卒業研究論文

題目 Web 検索結果の概観提示による 情報収集支援システム

主専攻 情報科学主専攻

著者 小林 拓海

指導教員 田中二郎、志築文太郎

要  旨

 現在インターネット上に存在する

Web

Web

本研究では、現在の

Web

Web

Web

1

Web

Web

目 次

第

1

1

第

2

Web

3

2.1 Web

. . . . 3

2.2

Web

. . . . 5

第

3

6 3.1

. . . . 6

3.2

. . . . 6

3.3

. . . . 8

3.3.1

. . . . 8

クラスタリングとは

. . . . 8

形態素解析

. . . . 9

tf/idf

. . . . 10

ベクトル空間法

. . . . 10

3.3.2

. . . . 10

第

4

13 4.1

. . . . 13

4.1.1

. . . . 13

4.1.2 HTML

. . . . 13

4.1.3 HTML

. . . . 13

4.1.4

. . . . 14

4.1.5 Web

. . . . 15

4.2

. . . . 15

4.2.1

. . . . 15

4.2.2

. . . . 18

4.3

. . . . 20

第

5

22

第

6

26

第

7

27

謝辞

28

参考文献

29

図 目 次

1.1

(Internet Systems Consortium)[1] 1

2.1 Google

. . . . 4

3.1

(Yahoo!Japan) . . . . 7

3.2 Hyperbolic Tree(John Lamping)[8] . . . . 11

3.3 Hyperbolic Tree

. . . . 12

4.1

50

Web

. 16 4.2

. . . . 17

4.3 Web

A

Web

B

. . . . 18

4.4

. . . . 19

4.5

. . . . 19

4.6

. . . . 20

5.1

. . . . 23

5.2

. . . . 24

5.3

. . . . 24

5.4

. . . . 25

6.1 Web

. . . . . 26

表 目 次

3.1

. . . . 8

3.2

. . . . 9

4.1 HTML

. . . . 13

第 1 _{章 序論}

 現在、インターネットはより一般的なものとなり、情報を収集する場面などにおいて欠か せない存在となっている。インターネットを用いる事で、我々は世界中のあらゆる情報に容易 に触れることができるようになった。インターネットの情報量及び

Web

Google[2]

2005

80

Web

Internet Systems Consortium

2

[1]

2004

7

2

8

1.1

10

300,000,000 250,000,000 200,000,000 150,000,000 100,000,000 50,000,000

0

1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004

Internet Domain Survey Host Count

図

1.1:

(Internet Systems Consortium)[1]

このように膨大な数の

Web

必然的に検索結果として提示される

Web

Web

本研究の目的

本研究の目的は

Web

Web

Web

Web

1

本論文の構成

本論文の構成を述べる。第

2

Web

3

4

5

6

7

第 2 _章 Web _{検索の現状と問題点}

 本章ではまず日常の

Web

2.1 Web

IBM

Andrei Broder

Web

ズを次の

3

[3]

1.

(informational)

2.

(navigational) 3.

(transactional)

1

1

Web

2

Web

(

)

3

Web

(

Web

)

我々は以上のような種類の

Web

Web

サイト

Google

Web

ジを上位に表示するための様々な工夫がなされている。また

Google

“I’m Feeling Lucky”

Web

現在日本で最も多くのユーザに利用されていると考えられる検索サイトはディレクトリ型検 索を行う

Yahoo!

Google

infoseek

goo

Excite

Biglobe

@nifty

So-net

AOL

DION

Google

Web

Web

Google

2.1

125

Google

1000

図

2.1: Google

一般に

Web

Web

Excite

2.21

1

10

2.35

[4]

Web

Web

ODIN ¹

1

1.40

7

1

[5]

1

http://odin.ingrid.org/

以上のような

Web

Web

2.2

Web

情報指向型の検索を行う場合、ユーザは検索結果を様々な観点から眺め、必要な情報を取 捨選択する必要がある。前節で例を挙げた「つくばに関する様々な情報を収集する」という 目的の検索を行う場合を考えてみる。

「つくばに関する情報」は抽象的であり、市政に関する情報、交通に関する情報、ショッ ピングに関する情報、宿泊施設に関する情報など様々である。そのためユーザは特定の

Web

Web

Google

Web

また、検索結果が数十ページにわたって分割されて提示される表示法も、検索結果全体の 概観の理解ができず、有益な情報を見落としてしまう場合がある。また、このような表示法 ではランキングの後方にあるページはほとんど閲覧されないため、有益な情報がある可能性 があるにもかかわらず情報が発見される前に検索そのものを打ち切ってしまうなどといった 問題点が考えられる。検索結果が

1

膨大な数の

Web

1

第 3 _{章 概観提示システム}

 本章ではまず情報指向型検索を行う際の既存インタフェースの問題点を改善する手法とし て概観提示システムを提案し、概観提示システムを実現するために

2

3.1

本研究では、前章に述べた情報指向型検索における既存インタフェースの問題点を改善す る方法として、概観提示システムを提案する。提案したシステムを実現するために、以下の

2

目標

1 : Web

(

)

目標

2 :

Web

1

1

Web

Web

(

Web

)

目標

2

1

Web

1

“Hyperbolic Tree”

“Hyperbolic Tree”

“Hyperbolic Tree”

このような機能を実装したシステムを利用することで、検索結果全体としてどのような特 徴があるかというような概観の直感的理解を支援することが可能となり、クラスタリングの 結果、内容の近い

Web

3.2

ここでは提案システムと他の類似インタフェースとの相違点について述べることで本手法 の特徴をさらに明らかにする。他の類似インタフェースとしては、本システムと同様に検索 結果をジャンルごとに分けてユーザに提示するディレクトリ型検索エンジンを取り上げる。

ディレクトリ型検索エンジンには様々あるが、登録されている

Web

3.1

図

3.1:

(Yahoo!Japan)

「つくば」で検索した場合、

784

24

Google

これは

Google

Web

Web

して、ディレクトリ型検索エンジンは人手で

Web

表示インタフェースについて見てみると、カテゴリも登録

Web

ここで本研究とディレクトリ型検索との相違点を表

3.1

Web

Web

Web

表

3.1:

PPP PPP

PPPP

分類のタイミング 静的 動的

分類の方法 人の手で分類、多くの人手が必 要

アルゴリズムによって分類、ほ ぼ自動的に計算機が分類してく れる

分類の正確さ 正確だが、分類を行う人間の主 観が伴う

アルゴリズムによる、ある程度 正確

対象の規模 対象文書は少ない 対象文書は多い

検索時の必要時間 時間がかからない 時間がかかる

(

)

カテゴリ カテゴリはあらかじめ人手で設 定されている

キーワードによって同一の

Web

検索結果 複数ページにまたがる

1

め収集し、分析しておくことで処理時間を短縮できると考えている。各

Web

Web

1

3.3

本節では

Web

3.3.1

ここではクラスタリングについて説明し、クラスタリングに用いるベクトル空間法と

tf/idf

クラスタリングとは

クラスタリングとは、異なる性質のもの同士が混在している集合の中から互いに類似したも のを集めてクラスタを作り、集合を分類するための方法である

[6]

な種類が存在しているが、本研究では「階層的クラスタリング」を用いてクラスタリングを 行った。この手法は対象間の類似度

¹

1. 1

n

2.

2

1

3.

4.

1

2

3

本研究において

n

Web

Web

n

Web

A

Web

B

A

B

類似度を求めることになる。

形態素解析

文書の特徴を分析するにはその文書にどのような単語が出現するかを調べる必要がある。そ のために用いるのが形態素解析という技術である

[7]

3.2

表

3.2:

-

-

は ハ は 助詞

-

筑波大学 ツクバダ イガク

筑波大学 名詞

-

-

-

-

通っ トオッ 通る 動詞

-

-

い イ いる 動詞

-

。 。 。 記号

-

このように形態素解析を行って得られた単語から、不要語を除いた単語の出現頻度を計測 したものを、文書の特徴語とし、類似度判定に用いた。不要語とは助詞や助動詞、記号など

1ここでいう類似度とは値が大きいほど類似性が高いということを示す数値である

単語のみでは意味を成さない語である。なお、本研究においては検索クエリも不要語に含ん でいる。検索クエリは検索結果の

Web

tf/idf

形態素解析を用いる事で、

1

Web

Web

tf/idf

tf/idf

相対的な重要度」を算出することができる。文書

D _i

t _j

(

)w _ij

w _ij = tf _ij × idf _j (3.1)

tf _ij

D _i

t _j

D _i

t _j

tf _ij

idf _j

t _j

idf _j

まとめると、ある文書

D _i

t _j

(

)

D _i

t _j

tf/idf

ベクトル空間法

ベクトル空間法とは、文書やクエリの内容を多次元空間上のベクトルとして表現する手法 である。これには

tf/idf

m

w _ij

Di

t _j

D _i

d _i

d _i = ^h w _i1 w _i2 w _i3 · · · w _im ⁱ (3.2)

Web

3.3.2

クラスタリング結果の可視化は

Hyperbolic Tree

Hyperbolic Tree

John Lamping[8]

Hyperbolic Tree

1

Hyperbolic Tree

図

3.2: Hyperbolic Tree(John Lamping)[8]

⇒ ⇒

図

3.3: Hyperbolic Tree

小さく表示される。

Hyperbolic Tree

3.2

1

3.3

第 4 章 システムの流れと詳細

4.1

4.1.1

ユーザはまずシステムに対して検索クエリを与える。検索クエリは

1

するとシステムは

GoogleAPI[9]

Web

URL

4.1.2 HTML

次に検索結果として得られた

URL

Web

URL

HTML

Perl

HTTP::Lite

4.1.3 HTML

HTML

tf/idf

HTML

Web

4.1

HTML

表

4.1: HTML

META

TITLE Web

CENTER

STRONG

A HREF

H

FRAME

IFRAME

まず付加的な情報を表現するタグについて述べる。

META

Web

Web

URL

Web

場合が多いことが分かった。このような場合には、フレームやインフレームを参照している

URL

次に直接

Web

HTML

において

TITLE

Web

の特徴を表している部分といえる。また、

H

STRONG

Web

このようにタグを利用して

Web

Web

4.1.4

HTML

Web

[10]

Web

tf/idf

Web

D _i

t _j

f _ij

tf _ij = log(1 + f _ij ) (4.1)

となる。対数を用いたのは、

tf _ij = f _ij

1

f _ij = 0

tf _ij = 0

また

d _j

t _j

Web

n

Web

idf _j

idf _j = log( n

d _j ) (4.2)

となる。

d _j

t _j

Web

idf _j

単に

tf/idf

Web

問題点がある。そのため

Web

tf _ij

idf _j

コサイン正規化は、

Web

m

m

(tf _i1 idf ₁ , tf _i2 idf ₂ , · · · , tf _im idf _m )

1

n _i = v u u t

X m j=1

(tf _ij × idf _j ) ² (4.3)

まとめると、文書

D _i

t _j

w _ij

w _ij = tf _ij × idf _j

n _i (4.4)

こうした計算を行って、

Web

m

Web

2

Web

(Web

)

Web

4.1.5 Web

ここでは

Web

50

Web

4.1

Web

GoogleAPI

これを観察すると以下のような問題があることが分かる。

1.

Web

2.

Web

本研究のクラスタリング手法は、すべての

Web

そのために、あまり類似していない

Web

このクラスタリングにおける問題を概観提示部において表示インタフェース的に解決する ために、うまくまとまっていない階段状になっている部分をまとめて新たなクラスタとする ことを考えた。このようにすることで深い階層を浅くすることが可能となり、概観提示部に おいてユーザに対して検索結果の概観をより分かりやすく提示することができる。

4.2

本システムでは、ユーザの入力した検索クエリに対しての検索結果をクラスタリングし、概 観提示部でクラスタリング結果を

Hyperbolic Tree

4.2.1

図

4.2

ちょうど半球の表面に樹形図を貼り付け、上から眺めたようなイメージである。ユーザは必 要と思われる部分木をドラッグして中央に移動させることにより部分木を拡大して見ること ができる。子ノードを持たないノードは

Web

図

4.1:

50

Web

図

4.2:

次に各ノードの関係について述べる。親ノード単語

1

2

3

Web

A

Web

B

4.3

図

4.3: Web

A

Web

B

クラスタリング部において類似度を求める際に、

Web

A

Web

B

3

Web

A

Web

B

Web

A

Web

B

Web

図

4.4

「小林」というクエリによって得られた検索結果をクラスタリングし、議員のホームページ がそれぞれの近傍に配置されていることが分かる。

4.2.2

本研究のクラスタリング手法には、あまり類似していない

Web

Web

1

図

4.5

図

4.4:

⇒

図

4.5:

とユーザの混乱を招く恐れがある。右図は階段状になり適切にまとまっていない

Web

Web

Web

4.3

ここでシステムの流れと相互関係を図

4.6

図

4.6:

本システムではまず

GoogleAPI

URL

URL

HTML

クラスタリング処理については検索ごとに変化するが、

HTML

Web

HTML

処理を行うタイミングは、一度得た

URL

HTML

URL

Web

URL

HTML

Web

第 5 _{章 システムの実用例}

 ここでは具体的な検索場面の例を挙げて本研究のシステムを適用する。あるユーザが日本 の歴史について様々な観点から調べたいと思い、本システムに検索クエリ「日本 歴史」を 与えた。システムはアルゴリズムにしたがってクラスタリングし、結果をユーザに提示する。

提示された情報の中からユーザは必要な情報を取捨選択する。

図

5.1

図

5.1

Web

Web

Web

Web

図

5.1

5.2

Web

5.3

Web

5.4

Web

図

5.1:

図

5.2:

図

5.3:

図

5.4:

第 6 _{章 関連研究}

Poznan University of Economics, Department of Information Technology

Periscope[11]

は本研究と同様に

Web

3D

Web

3D

Web

2D

Web

Web

University of Kent at Canterbury

Jonathan Roberts

Web

[12]

Web

x

y

Web

Web

図

6.1: Web

Palo Alto Research Center,Information Sciences and Technologies Laboratory

J.D.Mackinlay

Perspective Wall[13]

を提案した。

Perspective Wall

第 7 _{章 結論}

 本稿ではまず現在の

Web

Web

Web

今後は提示インタフェースの改良や検索時間の短縮などを行い、ユーザにとってさらに使 いやすいシステムに改良すること、さらにシステムのユーザ評価を行って開発に役立てたい と考えている。

謝辞

 本研究を進めるにあたり、指導教官である田中二郎教授に様々な助言やご指導をいただき ました。深く感謝いたします。また、三末和男助教授にはチームミーティングなどにおきま して適切なご指導をいただきました。深く感謝いたします。有益な助言、ご指導を下さった 志築文太郎講師ならびに高橋伸講師に心から感謝いたします。また、田中研究室の皆様およ びチームリーダー佐藤大介さんをはじめとする

SWAT

参考文献

[1] Inc. Internet Systems Consortium. http://www.isc.org/index.pl?/ops/ds/.

[2] Google. http://www.google.co.jp/.

[3] Andrei Broder. A taxonomy of web search. SIGIR Forum, Vol. 36, No. 2, pp. 3–10, 2002.

[4] Barnard J.Jansen, Amanda Spink, and Tefko.Saracevic. Real users, and real needs:A study and analysis of usr queries on the web. Information Processing and Management, Vol. 36, No. 2, pp. 207–227, 2000.

[5]

,

,

.

. DEWS, 2003.

[6] Brain S.Everitt. Cluster analysis. London:E.Arnold, 3rd edition, 1993.

[7]

. http://www.unixuser.org/ euske/doc/nlpintro/.

[8] John Lamping, Ramana Rao, and Peter Pirolli. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. In CHI ’95: Proceedings of the SIGCHI conference on Human factors in computing systems, pp. 401–408. ACM Press/Addison-Wesley Publish- ing Co., 1995.

[9] Google Web APIs. http://www.google.com/apis/.

[10]

,

,

,

,

,

,

.

「茶筅」

version 2.2.1

. Technical report,

, 2000.

[11] Wojciech Wiza, Krzysztof Walczak, and Wojciech Cellary. Periscope: a system for adaptive 3D visualization of search results. In Web3D ’04: Proceedings of the ninth international conference on 3D Web technology, pp. 29–40. ACM Press, 2004.

[12] Jonathan Roberts, Nadia Boukhelifa, and Peter Rodgers. Multiform Glyph Based Web Search

Result Visualization. the Sixth International Conference on Information Visualisation (IV

02), pp. 549–554. IEEE, 2002.

[13] Jock D. Mackinlay, George G. Robertson, and Stuart K. Card. The perspective wall: detail and

context smoothly integrated. In CHI ’91: Proceedings of the SIGCHI conference on Human

factors in computing systems, pp. 173–176. ACM Press, 1991.