半構造データを用いた
www リンク構造解析アルゴリズムの新提案

A New Algorithm for

Analyzing the Link Structure

of WWW Using

Semi-structured Data

日本大学 文理学部 情報システム解析学科

谷 研究室 西村 有美子

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

本研究の目的

1. 研究の目的

WWW で情報を入手することは簡単

[ 検索エンジンの利用 ]

目的のページが上位にくるとは限らない

本研究の目的

WWW リンク構造の解析を行い,トピックに

関係している web ページを正確に探し出したい

1. 研究の目的

WWW で情報を入手することは簡単

[ 検索エンジンの利用 ]

目的のページが上位にくるとは限らない

HITS アルゴリズムの改善手法を提案し

比較実験を行った

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

HITS アルゴリズムの特徴

＊ Jon M.Kleinberg 1997

＊各 Web コンテンツの内容には立ち入らず

サイト間のリンク構造の解析のみで適切な情報

を抽出する

＊適切な情報： Authority や Hub のページ集合

2. HITS アルゴリズムの紹介

Authority と Hub

Hubs

Authorities

2. HITS アルゴリズムの紹介

Authority と Hub

Hubs

Authorities

2. HITS アルゴリズムの紹介

Authority と Hub

Hubs

Authorities

2. HITS アルゴリズムの紹介

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

1 : root set の作成

2 : base set の作成

3 : Authority と Hub の重み付け

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

1 : root set の作成

探したいトピックを検索エンジンにかけ

一定数 r 件の Web ページを収集し root set 作成

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

1 : root set の作成

探したいトピックを検索エンジンにかけ

一定数 r 件の Web ページを収集し root set 作成

root set

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

2 : base set の作成

root set のページからリンクされている全てのページ

root set のページにリンクしているページ最大 d 件収集

root set に追加し大きさ n の base set 作成

root set

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

2 : base set の作成

root set のページからリンクされている全てのページ

root set のページにリンクしているページ最大 d 件収集

root set に追加し大きさ n の base set 作成

root set

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

2 : base set の作成

root set のページからリンクされている全てのページ

root set のページにリンクしているページ最大 d 件収集

root set に追加し大きさ n の base set 作成

root set

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

base set

root set

root set のページからリンクされている全てのページ

root set のページにリンクしているページ最大 d 件収集

root set に追加し大きさ n の base set 作成

2 : base set の作成

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

3 : Authority と Hub の重み付け

base set のページについて Authority と Hub

に重みを付けていく

base set

root set

2. HITS アルゴリズムの紹介

HITS アルゴリズムの手順

3 : Authority と Hub の重み付け

base set

root set

base set のページについて Authority と Hub

に重みを付けていく

Authority と Hub の重み

Authority

weight

高い

高い

低い

低い

Hub

weight

2. HITS アルゴリズムの紹介

Hub

weight

Authority

weight

高い

高い

低い

低い

2. HITS アルゴリズムの紹介

Authority と Hub の重み

Hub

weight

Authority

weight

高い

高い

低い

低い

2. HITS アルゴリズムの紹介

Authority と Hub の重み

Authority weight:xp

Hub weight:yp

(p ∈ base set)

q1

qn

p

Authority と Hub の重みのつけ方

2. HITS アルゴリズムの紹介

・

・

・

Authority weight:xp

Hub weight:yp

(p ∈ base set)

q1

qn

p

・

・

・

xp := sum of yq , for all q pointing to p

2. HITS アルゴリズムの紹介

Authority と Hub の重みのつけ方

Authority weight:xp

Hub weight:yp

(p ∈ base set)

q1

qn

p

・

・

・

yp := sum of xq , for all q pointed to p

2. HITS アルゴリズムの紹介

Authority と Hub の重みのつけ方

Authority weight：

上記の２式を反復計算し

Authority weight と Hub weight を抽出

Hub weight：

2. HITS アルゴリズムの紹介

Authority と Hub の重みのつけ方

隣接行列：A

反復計算

2. HITS アルゴリズムの紹介

隣接行列：A

1

2

3

4

反復計算

2. HITS アルゴリズムの紹介

隣接行列：A

1

2

3

4

A =

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

反復計算

2. HITS アルゴリズムの紹介

A：隣接行列

k：反復回数

初期値：

更新ルール：

2. HITS アルゴリズムの紹介

反復計算

1

2

3

4

反復計算

A =

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

2. HITS アルゴリズムの紹介

1

2

3

4

0 0 0 0

1 0 0 0

1 1 0 0

0 1 1 0

2. HITS アルゴリズムの紹介

反復計算

A =

T

Authority weight

反復計算

1

2

3

4

0 0 0 0

1 0 0 0

1 1 0 0

0 1 1 0

1

1

1

1

0

1

0

1

2

2

=

2

2

2. HITS アルゴリズムの紹介

Authority weight

反復計算

1

2

3

4

0

1

2

2

A =

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

2. HITS アルゴリズムの紹介

Hub weight

反復計算

1

2

3

4

0

1

2

2

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

0

1

2

2

3

4

2

0

=

3

4

2

0

2. HITS アルゴリズムの紹介

Hub weight

反復計算

1

2

3

4

0 0 0 0

1 0 0 0

1 1 0 0

0 1 1 0

3

4

2

0

0

3

0

3

7

6

=

7

6

3

4

2

0

2. HITS アルゴリズムの紹介

Authority weight

反復計算

1

2

3

4

0

3

10

13

6

0

=

7

6

10

13

6

0

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

0

3

7

6

2. HITS アルゴリズムの紹介

Hub weight

反復計算

0 0 0 0

1 0 0 0

1 1 0 0

0 1 1 0

10

13

6

0

0

10

23

19

=

1

2

3

4

0

10

23

19

10

13

6

0

2. HITS アルゴリズムの紹介

Authority weight

反復計算

32

42

19

0

=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

0

10

23

19

1

2

3

4

0

10

23

19

32

42

19

0

2. HITS アルゴリズムの紹介

Hub weight

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

HITS アルゴリズムの改善点の概要

3. HITS アルゴリズムの改善

HITS アルゴリズムは各ページのコンテンツに

立ち入らない事が前提

HITS アルゴリズムの改善点の概要

HITS アルゴリズムは各ページのコンテンツに

立ち入らない事が前提 topic drift 問題

3. HITS アルゴリズムの改善

HITS アルゴリズムの改善点の概要

3. HITS アルゴリズムの改善

HITS アルゴリズムは各ページのコンテンツに

立ち入らない事が前提 topic drift 問題

探したいトピックがページ内に含まれているならば

ページの weight を重くしてもよいのではないか？

HITS アルゴリズムの改善点の概要

探したいトピックがページ内に含まれているならば

ページの weight を重くしてもよいのではないか？

Web ページが半構造データであることを利用

3. HITS アルゴリズムの改善

HITS アルゴリズムは各ページのコンテンツに

立ち入らない事が前提 topic drift 問題

HITS アルゴリズムの改善点の概要

半構造データとは

“無構造データ”と“構造データ”の間のデータ

構造のこと

3. HITS アルゴリズムの改善

HITS アルゴリズムの改善点の概要

“無構造データ”と“構造データ”の間のデータ

構造のこと

無構造データ：スキーマ(データベースで論理構造や物理構造を定めた仕様)が全く存在しないデータ[ ex. 普通の文章]

半構造データとは

3. HITS アルゴリズムの改善

HITS アルゴリズムの改善点の概要

半構造データとは

“無構造データ”と“構造データ”の間のデータ

構造のこと

無構造データ：スキーマ(データベースで論理構造や物理構造を定めた仕様)が全く存在しないデータ[ ex. 普通の文章]

構造データ：スキーマが決まっているデータ

[ ex. RDB]

3. HITS アルゴリズムの改善

HITS アルゴリズムの改善点の概要

無構造データ：スキーマ(データベースで論理構造や物理構造を定めた仕様)が全く存在しないデータ[ ex. 普通の文章]

構造データ：スキーマが決まっているデータ

[ ex. RDB]

“タグ”によって部分的に構造を記述できるデータ

[ ex. XML や HTML]

半構造データとは

3. HITS アルゴリズムの改善

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

tag weight の 導入

探したいトピックが特定の HTML タグで

強調されているならばその頻度を隣接行列に

反映させる

・<TITLE>～</TITLE>

・<STRONG>～</STRONG>

・<H1>～</H1>,...,<H6>～</H6> ...等

3. HITS アルゴリズムの改善

特定の HTML タグ

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

anchor weight の 導入

探したいトピックが

「アンカーテキスト」「アンカータグ」

「アンカータグ前後のテキスト」

に含まれているならばその頻度を隣接行列に反映させる

....<A HREF =”http:// ...”>～</A>....

3. HITS アルゴリズムの改善

anchor weight の 導入

探したいトピックが

「アンカーテキスト」「アンカータグ」

「アンカータグ前後のテキスト」

に含まれているならばその頻度を隣接行列に反映させる

....<A HREF =”http:// ...”>～</A>....

3. HITS アルゴリズムの改善

トピック値を用いて隣接行列の改善を行う

トピック値の決定・隣接行列の改善

隣接行列：A

ページ p におけるトピック w の頻度を wp とし

トピックベクトル W を作成

3. HITS アルゴリズムの改善

トピック値の決定・隣接行列の改善

隣接行列：A

ページ p におけるトピック w の頻度を wp とし

トピックベクトル W を作成

3. HITS アルゴリズムの改善

以降は HITS アルゴリズムと同様の手順で行う

トピック値を使用した反復計算

1

2

3

4

1

1

0

1

0

1

3. HITS アルゴリズムの改善

トピック値を使用した反復計算

1

2

3

4

1

1

0

1

0

1

3. HITS アルゴリズムの改善

A =

0 2 1 0

0 0 1 2

0 0 0 2

0 0 0 0

トピック値を使用した反復計算

1

2

3

4

1

1

1

1

0

2

0

2

4

4

=

4

4

0 0 0 0

2 0 0 0

1 1 0 0

0 2 2 0

1

1

3. HITS アルゴリズムの改善

Authority weight

トピック値を使用した反復計算

1

2

3

4

0

2

4

4

6

10

8

0

0

2

4

4

6

10

8

0

=

0 2 1 0

0 0 1 2

0 0 0 2

0 0 0 0

1

1

3. HITS アルゴリズムの改善

Hub weight

1

1

1

1

1

1

1

1

0

2

4

4

6

10

8

0

0

12

16

26

40

68

52

0

0

80

108

240

268

582

480

0

1

2

3

4

A =

0 2 1 0

0 0 1 2

0 0 0 2

0 0 0 0

1

1

0

1

0

1

3. HITS アルゴリズムの改善

トピック値を使用した反復計算

・・・

目次

1. 研究の目的

2. HITS アルゴリズムの紹介

3. HITS アルゴリズムの改善

・ tag weight の 導入

・ anchor weight の 導入

4. 実験・考察

実験方法

(a) Google サーチエンジン

(b) HITS アルゴリズム

(c) HITS + tag weight

(d) HITS + anchor weight

Google Web API を利用

root set : 100

base set : 1000～5000

4. 実験・考察

base set

root set

パラメータ

root set の収集方法

比較対象

評価方法

対象者

谷研究室 20名

アンケート方法

各々の上位３つのWeb ページを閲覧し

「good」「fair」「bad」の３段階で評価

4. 実験・考察

注：どの方法がどの Web ページを返したかは

伏せて行った

HITS アルゴリズムの評価を行った

研究グループを参考 ： アンケート形式

4. 実験・考察

実験結果

HITS + tag weight

Google サーチエンジン

HITS + anchor weight

HITS アルゴリズム

: 30.83%

: 29.91%

: 26.62%

: 12.64%

4. 実験・考察

HITS + tag weight

Google サーチエンジン

HITS + anchor weight

HITS アルゴリズム

: 30.83%

: 29.91%

: 26.62%

: 12.64%

考察 １

各 Web ページのコンテンツに立ち入りページを評価することは有効

考察 ２

HITS + tag weight

Google サーチエンジン

HITS + anchor weight

HITS アルゴリズム

: 30.83%

: 29.91%

: 26.62%

: 12.64%

トピックが固有名詞のとき

Google は正式なページが上位にくる

4. 実験・考察

HITS + tag weight

Google サーチエンジン

HITS + anchor weight

HITS アルゴリズム

: 30.83%

: 29.91%

: 26.62%

: 12.64%

どんなトピックを検索しても

Google は企業のページが上位にくる

考察 ３

4. 実験・考察

今後の課題

＊ ドメイン名に注目したページの重み付け

＊ HTML タグの種類による重みの調節

＊ 複数のトピックによる検索

4. 実験・考察

今後の課題

＊ ドメイン名に注目したページの重み付け

＊ HTML タグの種類による重みの調節

＊ 複数のトピックによる検索

URL にトピックが含まれ

ドメイン名が “co.jp” や “ac.jp” 等の場合

ページの weight を重くする

4. 実験・考察

今後の課題

＊ ドメイン名に注目したページの重み付け

＊ HTML タグの種類による重みの調節

＊ 複数のトピックによる検索

tag weight 導入の際

<TITLE>～</TITLE> 等で

トピックが挟まれていた場合

ページの weight を重くする

4. 実験・考察

今後の課題

＊ ドメイン名に注目したページの重み付け

＊ HTML タグの種類による重みの調節

＊ 複数のトピックによる検索

今回の実験ではトピックを１つに限定したが

複数のトピックで検索することにより

また別の結果が得られるかも知れない

4. 実験・考察

おわり

yumiko

2004-10-29T16:41:23

yumiko