Kolmogorov記述量

に基づく類似度を用いた

WWWリンク構造解析手法

真板 育海

2/10

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

考察

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

考察

目的

コンピュータネットワークの発達とともに 情報が溢れている

そのような状況の中で自分の探したいトピックに関係しているwebページを探したい

目的

入力：探したいトピック
WWWリンク構造を解析(HITSアルゴリズム)
出力：関連性の高いWebページ

HITSアルゴリズム

特徴：ページの内容に立ち入らずに
ページ間のリンク構造のみに着目して トピックに関連した
AuthorityやHubの
ページ集合を抽出

Jon M.Kleinberg

AuthorityとHub

Hub

Authority

HITSアルゴリズムの紹介

AuthorityとHub

Hub

Authority

HITSアルゴリズムの紹介

AuthorityとHub

Hub

Authority

HITSアルゴリズムの紹介

目的

さらにページ内容に立ち入り
ページ間の類似性という観点から
Kolmogorov記述量を使い
HITSアルゴリズムの改善手法を提案
既存手法(西村)との比較実験を行う

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

今後の課題

HITSアルゴリズムの手順

１. root setの作成

２. base setの作成

３. AuthorityとHubの重み付け

HITSアルゴリズムの紹介

１、root setの作成

探したいトピックを検索エンジンにかけ r件のWebページを収集し
root setとする

root set

HITSアルゴリズムの紹介

2、base setの作成

root setに含まれるページからリンクされているページを収集

root set

2、base setの作成

root setに含まれるページにリンクしているページ(最大d件)を収集

root set

2、base setの作成

root setに含まれるページからリンクされているページ
root setに含まれるページにリンクしているページ(最大d件)収集し
root setに追加してbase setを作成

root set

base set

3、AuthorityとHubの重み付け

base setのページについて
AuthorityとHubに重みを付けていく

root set

base set

AuthorityとHubの重み

Hub

Weight

Authority

Weight

HITSアルゴリズムの紹介

AuthorityとHubの重み付け方

ページpがあるとき

: Authority weight

: Hub weight

HITSアルゴリズムの紹介

AuthorityとHubの重み付け方

Authority weight :

このようなとき

x(p)はpにリンクをはっている

全てのqの持つy(q)の総和である

→

.

.

.

.

p

HITSアルゴリズムの紹介

AuthorityとHubの重み付け方

Hub weight :

このようなとき

y(p)はpからリンクをはられている全てのqの持つx(q)の総和である

→

.

.

.

.

p

HITSアルゴリズムの紹介

AuthorityとHubの重み付け方

下記の式を反復することで
それぞれの値を更新していく

最終的にAuthority weightの高いページを抽出する

HITSアルゴリズムの紹介

反復計算

リンク構造を隣接行列と考える

隣接行列 A:

A=

a(1,1)

a(n,1)

a(1,n)

a(n,n)

....

....

.

.

.

.

a(i,j)=

1:i→jが存在するとき

0:しないとき

HITSアルゴリズムの紹介

反復計算

リンク構造を隣接行列と考える

隣接行列 A:

A=

a(1,1)

a(n,1)

a(1,n)

a(n,n)

....

....

.

.

.

.

a(i,j)=

1:i→jが存在するとき

0:しないとき

1

2

3

4

HITSアルゴリズムの紹介

反復計算

リンク構造を隣接行列と考える

隣接行列 A:

A=

a(1,1)

a(n,1)

a(1,n)

a(n,n)

....

....

.

.

.

.

a(i,j)=

1:i→jが存在するとき

0:しないとき

1

2

3

4

A=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

HITSアルゴリズムの紹介

計算方法

A:隣接行列

:Authority用ベクトル

:Hub用ベクトル

∈

初期値:

更新のルール:

i:反復回数

(i=1,2,...,k)

HITSアルゴリズムの紹介

反復計算

1

2

3

4

=

0 0 0 0

1 0 0 0

1 1 0 0

0 1 1 0

0

1

2

2

1

1

1

1

A=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

Authority

Weight

Hub

Weight

HITSアルゴリズムの紹介

反復計算

1

2

3

4

=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

3

4

2

0

0

1

2

2

A=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

Hub

Weight

Authority

Weight

HITSアルゴリズムの紹介

反復計算

1

2

3

4

A=

0 1 1 0

0 0 1 1

0 0 0 1

0 0 0 0

1

1

1

1

1

1

1

1

0

1

2

2

3

4

2

0

0

3

7

6

10

13

6

0

0

10

23

19

33

42

19

0

HITSアルゴリズムの紹介

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

考察

改善案(西村)

HITSはWebページの内容に立ち入らない

→トピックとは関係ないページを関係あるページ と同じように扱ってしまう

トピックと関係あるページのWeightを重くし たい

ページの内容に立ち入り
Webページのタグの部分について着目している

改善案の紹介

改善案(西村)

(1)tag weight

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

されているならば
その出現回数をリンクの重みに反映させる

＊特定のタグ

<TITLE>topic</TITLE>

<STRONG>topic</STRONG>

<H6>topic</H6>

.

.

.

など

改善案の紹介

改善案(西村)

(2)anchor weight

ページ内のアンカーテキスト

アンカータグ

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

探したいトピックがあれば

その出現回数をリンクの重みに反映させる

*例

<a href =”...../topic”>....</a>

<a href =”.../〜 /!!!”>topic</a>

topicの<a href =”.../~~/!!>概要</a>

など

改善案の紹介

改善案(西村)

a(i,j)=

1:i→jが存在するとき

0:しないとき

a(i,j)=

1＋出現回数:i→jが存在

するとき

0 :しないとき

改善案の紹介

改善案(Kolmogorov)

ページの内容に立ち入り
各ページ間の類似性に着目した
改善案を提案したい

改善案の紹介

Bとの類似性

＞Cとの類似性

＞Aとの類似性

Bへの振り分け

＞ Cへの振り分け

＞ Aへの振り分け

X

A

B

C

類似性と振り分けの関係

改善案の紹介

改善案(Kolmogorov)

元のページに対して
類似しているページは
元のページとの関連性が強い
(同じ対象を扱っている可能性が高い)
のではと考えられる
元のページと類似性の高いページに対して
多く重みを付けたい

改善案の紹介

改善案(Kolmogorov)

Kolmogorov記述量に基づき
二つのデータの類似性を類似度として求めることができる
リンクのある２つのページの類似度を求め
それに応じた振り分けをリンクの重みに反映させる
＊対象としてタグ等を除いた本文のみとする

改善案の紹介

ページi. jの類似度をKolmogorov記述量に基づいて求める式は

*k(i):iのKolmogorov記述量
*ij:iとjを連結させたもの

類似度

のとき

改善案の紹介

しかしKolmogorov記述量は計算不可能であることが知られている

近似値として圧縮した後のサイズを用いることができる

*zip(i):iを圧縮した後のサイズ

類似度の近似

改善案の紹介

改善案(Kolmogorov)

a(i,j)=

1:i→jが存在するとき

0:しないとき

a(i,j)=

1 - d(i, j) :i→jが存在 するとき

0 :しないとき

改善案の紹介

振り分け方

他に

また既存手法と組み合わせることで

改善案の紹介

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

考察

比較対象

1, Google サーチエンジン
2, HITS アルゴリズム
3, 既存手法(tag weight)
4, 既存手法(anchor weight)
5, HITSにKolmogorov記述量(1-d(x,y)) を導入したもの

比較実験

比較対象

6, HITSにKolmogorov記述量(1/d(x,y)) を導入したもの
7, 既存手法(tag weight)にKolmogorov 記述量(1-d(x,y))を導入したもの
8, 既存手法(anchor weight)にKolmogorov 記述量(1-d(x,y))を導入したもの
9, Yahoo サーチエンジン
10, HITS アルゴリズム ２

改善案の紹介

比較方法

root set の収集方法
2〜8 : Google web API
10 : Yahoo! API

改善案の紹介

base set

root set収集(100件)
root setのページからリンクされているページ収集
root setのページにリンクしているページ収集(最大50件)
隣接行列の作成 反復計算
Authority Weightの高いページの抽出

HITSアルゴリズムの紹介

評価方法

評価方法
アンケート方式

対象者
谷研究室 3.4年 21名

アンケートの方法
比較対象それぞれにトピックごとに
結果の上位３位のページを閲覧し
内容を３段階で評価してもらった
どの比較対象がどのページを返したかは
伏せて行った

改善案の紹介

実験結果

目次

目的

HITSアルゴリズムの紹介

改善案の紹介

比較実験

考察

考察

Webページの内容に
立ち入って
ページ間の類似度を
用いて
ページを評価する
有効である

考察

考察

Kolmogorov記述量
を用いた改善手法は
他の手法と組み合わ
せた方が
さらに有効である

考察

考察

root set
収集方法の違い
有効性において
影響は少ない

考察

考察

Kolmogorovを用いた
改善手法において
類似度による
リンクの重み付け
評価に影響がある

考察

今後の課題

root set の収集方法
今回用いなかった
MSN, AltaVista などの
サーチエンジンやAPIを用いる

考察

今後の課題

Kolmogorov 記述量を用いた改善手法
1. リンクの重み付けにおいて
類似度を使った重み付けの式

考察

今後の課題

Kolmogorov 記述量を用いた改善手法
2. 距離を求める式において
圧縮方式の選択
zip
bzip2など他の方式

考察

今後の課題

Kolmogorov 記述量を用いたの改善手法
3. タグを利用した既存手法と
Kolmogorov 記述量を用いた改善手法を
組み合わせる
対象：全てのページ
一定以上のトピック出現回数
のあるページ

考察

終

Ikumi Maita

2005-10-11T15:05:15